机器学习(ML)

机器学习(ML) since 2012-20-20

聚类，分类和推荐

聚类

聚类，即将相似的东西放到一个类别中，聚类之前唯一需要做的就是定义相似度计算方法，因此，聚类是一种无监督的学习过程

华盖聚类(Canopy)

不需指定聚类个数，设置两个相似度阈值(T1 < T2)
开始将所有点放到list中，循环该list，计算每个点和当前聚类的距离
- 小于T1则放到该聚类中，并从list中删除该点
- 小于T2大于T1,则该点暂时加入该类，但不从list中删除
- 如果距离大于T2,则开辟一个新的类。

KMeans聚类

需要指明分类个数k，适用于类别以‘点群’分布的数据
随机k个点作为初始分类中心
- 计算所有点到每个聚类中心的距离，选择最小的作为该点的类别
- 重新计算聚类中心（点群中心的点）
- 不断重复上面过程直到聚类中心不再变动，或达到迭代次数上限
最常用的距离是欧式距离，也可以使用扩展形式：明可夫斯基距离，聚类的图形可以为星形，圆形，方形
缺陷及解决方法
- 聚类个数k的选取。可以通过Canopy聚类估计
- 初始化点的选取直接影响最终聚类结果，简单实用随机方式，容易达到局部最优
  - 一方面，可以多次随机取点，选Cost最小的
  - 使用KMeans++算法选初始点
    - 先随机选第一个初始种子点
    - 计算剩余点到种子点的距离(选最小的)，以这些距离为权重(正相关)，在剩余点中选下一个种子点
    - 重复上面过程，直到选取K个种子点，之后再进行KMeans聚类

Kmeans聚类的Cost函数为：

$J = \sum_{n=1}^N \sum_{k=1}^K r_{nk}\|x_n-\mu_k\|^2$

其中，$$ r_{nk}= \begin{cases} 1 & \text{ if } x_n \in cluster_k \ 0 & \text{ else } \end{cases} $，$ u_k$$是第k个类的中心

我们发现代价函数J中有两个变量 $r_{nk}, \mu_k$ ，而且连个变量之间还有依赖关系，可以将 $\mu_k$ 理解成隐含的中间变量，这样就和EM的思想不谋而合

KCentroid聚类

普聚类 Spectral Clustering

普聚类其实就是通过 Laplacian Eigenmap 的降维方式降维之后再做 K-means 的一个过程

具体过程如下：

根据数据构造一个Graph，Graph的没一个节点对应一个数据点，将相似的点连接起来，并且边的权重用于表示数据之间的相似度。把这个Graph用邻接矩阵的形式表示出来，记为W，一个最偷懒的办法就是：直接用 K-medoids 中用的相似度矩阵作为 W 。
把 W 的每一列元素加起来得到 N 个数，把它们放在对角线上（其他地方都是零），组成一个 $N \times N$ 的矩阵，记为 D 。并令 L = D-W 。
求出 L 的前 k 个特征值（在本文中，除非特殊说明，否则“前 k 个”指按照特征值的大小从小到大的顺序） $\{\lambda\}_{i=1}^k$ 以及对应的特征向量 $\{\mathbf{v}\}_{i=1}^k$ 。
把这 k 个特征（列）向量排列在一起组成一个 $N\times k$ 的矩阵，将其中每一行看作 k 维空间中的一个向量，并使用 K-means 算法进行聚类。聚类的结果中每一行所属的类别就是原来 Graph 中的节点亦即最初的 N 个数据点分别所属的类别。

参考

http://blog.pluskid.org/?p=17&cpage=1
http://coolshell.cn/articles/7779.html

分类问题

决策树(DecisionTree)

决策树是一个树形结构，每个非叶子节点表示一个特征属性上的测试，每个分支代表这个属性在不同值域上的输出，最终每个叶子存放一个类别
天生适合多分类问题，具有可表示性，分类速度快
非叶节点决策属性的选择：
- 指标：不纯度
  - 熵(信息)不纯度 i(N)=-sigma_j P(w_i)*logP(w_i)
  - ‘Gini’不纯度 i(N)=1-sigma_j P^2(w_i)
  - 误分类不纯度 i(N)=1-max_jP(w_j)
- 衡量方法：
  - 不纯度降低量(对熵不纯度而言，比较决策的信息增益量)
  - 不纯度降低比率(对熵不纯度而言，比较决策的信息增益率)
  - 用信息增益率来选择属性，克服了用信息增益选择属性时偏向选择取值多的属性的不足
叶节点标记
- 如果叶节点只包括单一类别样本，直接标记
- 如果不纯，使用占优势的类别标记
解决Overfitting的问题：剪枝
- ‘预剪枝’技术–分支停止原则
  - 在分支的时候考虑是否需要停止，降低计算量，但可能提前停止：’视界局限效应‘
  - 验证和交叉验证技术，划分交叉验证集合，持续分支，直到验证集的分类误差最小化
  - 设置不纯度下降的最小阈值
  - 最小化如下cost函数：
    
    alpha*size + sigma_叶节点 i(N) alpha: 正常量 size: 树大小，节点或分支个数 i(N): 叶节点不纯度
- ‘后剪枝’技术
  - 首先让树充分生长，之后考虑所有相邻叶节点，是否进行合并
  - 克服了视界局限效应，但计算量很大
解决属性丢失问题：使用最普遍值的替代
常见树算法
- 分类和回归树(CART)
  - 通用的树生长框架
  - 采用一种__二分__递归分割的技术，使得生成的决策树的每个非叶子节点都有两个分支
- ID3
  - 只能处理‘语义（无序）数据’，因此如果数据是连续实数，可以装填到整数格子中，当作无序语义数据处理
  - 实际中，很少只用二分树，所以常用‘增益比不纯度’
  - 生长算法持续进行，直到所有叶子点都为纯，或者没有其他待分支的变量
- C4.5

贝叶斯分类

Boosting

整合多弱分类器形成一个强大的分类器

线性回归

因变量和自变量之前存在线性关系

逻辑回归

被logistic方程__归一化__后的线性回归
能够打压过大和过小的结果（往往是噪音），以保证主流的结果不至于被忽视。
more

支持向量机SVM

通过寻求结构化风险最小来提高学习机泛化能力，实现经验风险和置信范围的最小化，从而达到在统计样本量较少的情况下，亦能获得良好统计规律的目的
SVM 通过使用最大分类间隙Maximum Margin Classifier 来设计决策最优分类超平面
最大间隔能获得最大稳定性与区分的确信度，提高泛化力