机器学习基本概念(未完待补)

Nearest Neighbors

  • 无监督最近邻:
    • 返回每个数据样本点的$k$近邻节点或者距离,无训练集
    • 应用:流行学习(manifold learning)、谱聚类(spectral clustering)
  • 有监督最近邻
    • 返回训练集中的$k$近邻
    • 应用:数据分类/回归

VC-Dimension

VC-Dimension用来量化分类器能够分类的训练样本的最大数目,是模型容量量化的一种方法。

参数模型&非参数模型

参数模型在观测到新数据前,参数向量的分量个数是有限且固定的,如线性回归/分类[1]
非参数模型仅是一些不能实际实现的理论抽象(比如搜索所有可能概率分布的算法)。非参数模型有最近邻回归、K近邻、SVM等。

频率学派&贝叶斯学派

对于参数估计,存在两个学派的不同解决方案。一是频率学派解决方案:通过某些优化准则(比如似然函数)来选择特定参数值;二是贝叶斯学派解决方案:假定参数服从一个先验分布,通过观测到的数据,使用贝叶斯理论计算对应的后验分布。先验和后验的选择满足共轭,这些分布都是指数簇分布的例子。

频率派最常关心的是似然函数,而贝叶斯派最常关心的是后验分布。我们会发现,后验分布其实就是似然函数乘以先验分布再 normalize一下使其积分到1。因此两者的很多方法都是相通的。
贝叶斯派因为所有的参数都是随机变量,都有分布,因此可以使用一些基于采样的方法 (如MCMC)使得我们更容易构建复杂模型。频率派的优点则是没有假设一个先验分布,因此更加客观,也更加无偏,在一些保守的领域(比如制药业、法律)比 贝叶斯方法更受到信任。[2][3]

降维方法

  • 线性降维
    • PCA
    • SVD, NMF
  • 非线性降维
    • KPCA(Kernel Method+PCA)
    • 流行学习
      • 全局嵌入: 多维缩放MDS, ISOMAP
      • 局部嵌入: Laplacian Eigenmap

Laplace 矩阵与谱聚类沈, 网络数据挖掘-图聚类

“>[4]

定义矩阵$A$为$n$个顶点的无向图的邻接矩阵/边权非负矩阵,矩阵$D$是对角矩阵,且$D_{ii}=\sum_{j}A_{ij}$表示节点$i$的度数/边权和。
定义$L=D-A$,矩阵$L$就是矩阵$A$的对应的Laplace 矩阵
Laplace 矩阵的性质:

  • 对于任意向量$x$,都有$x^TLx=\frac{1}{2}\sum_{i,j}A_{ij}(x_{i}-x_{j})^2$
  • 半正定,即$0=\lambda_1\le\lambda_{2}\le\dots\le\lambda_{n}$

证明:

显然,当$x_{1}=x_{2}=\dots=x_{n}=\frac{1}{\sqrt{n}}$时,$x$是$L$的一个特征向量,且对应的特征值为$0$。

谱聚类算法的一般步骤:

  1. 通过$n$个数据点构造无向图。无向图中的节点对应数据点,按照数据点的近邻+相似度规则构造出邻接矩阵$A$;
  2. 计算无向图的度矩阵$D$,$D$是对角矩阵,对角元素的值为邻接矩阵$A$对应行的行和;
  3. 计算Laplace矩阵$L=D-A$;
  4. 对Laplace矩阵$L$进行特征值分解,取前$k$小的特征值及其对应的特征向量$(k
  5. 将数据点映射到$k$维空间中,在$k$维空间中,对所有变换之后的样本点采用K-Means聚类,聚类结果就是谱聚类之后的结果。

谱聚类的基本思想便是利用样本数据之间的相似矩阵(拉普拉斯矩阵)进行特征分解( 通过Laplacian Eigenmap 的降维方式降维),然后将得到的特征向量进行 K-means聚类。
此外,谱聚类和传统的聚类方法(例如 K-means)相比,谱聚类只需要数据之间的相似度矩阵就可以了,而不必像K-means那样要求数据必须是 N 维欧氏空间中的向量。

spectral-clusteringspectral-clustering
spectral-clusteringspectral-clustering

Reference

坚持原创技术分享,您的支持将鼓励我继续创作!