本次笔记目标：
第一章节：相似度的度量方法及联系
第二章节：K-means算法
第三章节：层次聚类
第四章节：密度聚类（DBSCAN、密度最大值聚类）
第五章节：谱聚类
第一章节：相似度的度量方法及联系
1.1 聚类的定义：
聚类就是对大量位置标注的数据集，按数据的内在相似性将数据集划分为多个类别，使类别内的数据相似度较大而类别间的数据相似度较小。
1.2 相似度/距离
1.3 相似度方法间的联系
聚类相似度间的方法和联系（需要打上连接）
第二章节 K-means算法
2.1 聚类的基本思想
对于给定的类别数目k，首先给出初始划分，通过迭代改变样本和簇的隶属关系，使得每一次改进之后的划分方案都较前一次好。
2.2 K-mean算法
K-means算法，也被称为k-平均或k-均值，是一种广泛使用的聚类算法，或者成为其他聚类算法的基础。
算法步骤：
a. 初始化聚类中心个数和聚类中心点。
b. 对于每个样本将其标记为距离类别中心最近的类。
c. 将每个类别中心更新为隶属该类别的所有样本的均值。（目标函数的极值）
d. 重复最后两步，直到类别中心的变化小于某阈值。
中止条件：迭代次数/簇中心变化率/最小平方误差MSE(MinimumSquaredError)
K-Means算法的缺陷
1.k值需要预先给定(改进：可以通过在一开始给定一个适合的数值给k，通过一次K-means算法得到一次聚类中心。对于得到的聚类中心，根据得到的k个聚类的距离情况，合并距离最近的类，因此聚类中心数减小，当将其用于下次聚类时，相应的聚类数目也减小了，最终得到合适数目的聚类数。可以通过一个评判值E来确定聚类数得到一个合适的位置停下来，而不继续合并聚类中心。重复上述循环，直至评判函数收敛为止，最终得到较优聚类数的聚类结果)。
2.k-means算法对初始选取的聚类中心是敏感的(改进1：k-means++;改进2：二分K-means，，相关知识详见这里和这里）
3.对于不是凸的数据集比较难收敛
4.采用迭代方法，得到的结果只是局部最优。
5.对噪音和异常点比较的敏感。(改进1：离群点检测的LOF算法，通过去除离群点后再聚类，可以减少离群点和孤立点对于聚类效果的影响；改进2：改成求点的中位数，这种聚类方式即K-Mediods聚类（K中值）)。
6.如果各隐含类别的数据不平衡，比如各隐含类别的数据严重失衡，或者各隐含类别的方差不同，则聚类效果不佳。
可作为其他聚类方法的基础算法，如谱聚类
2.3 Mini Batch k-Means
在原始的K-means算法中，每一次的划分所有的样本都要参与运算，如果数据量非常大的话，这个时间是非常高的，因此有了一种分批处理的改进算法。
使用Mini Batch（分批处理）的方法对数据点之间的距离进行计算。
Mini Batch的好处：不必使用所有的数据样本，而是从不同类别的样本中抽取一部分样本来代表各自类型进行计算。n 由于计算样本量少，所以会相应的减少运行时间n 但另一方面抽样也必然会带来准确度的下降。
2.4 Camopy算法
参考：https://my.oschina.net/liangtee/blog/125407
2.5 聚类的衡量指标
第三章节：层次聚类
1、概述：
层次聚类方法对给定的数据集进行层次的分解，直到某种条件满足为止。具体又可分为
凝聚的层次聚类：AGNES算法：一种自底向上的策略，首先将每个对象作为一个簇，然后合并这些原子簇为越来越大的簇，直到某个终结条件被满足。
分裂的层次聚类：DIANA算法：采用自顶向下的策略，它首先将所有对象置于一个簇中，然后逐渐细分为越来越小的簇，直到达到了某个终结条件。
2、凝聚的层次聚类（AGENS）算法
AGNES(AGglomerativeNESting)算法最初将每个对象作为一个簇，然后这些簇根据某些准则被一步步地合并。两个簇间的距离由这两个不同簇中距离最近的数据点对的相似度来确定；聚类的合并过程反复进行直到所有的对象最终满足簇数目。
DIANA(DIvisiveANAlysis)算法是上述过程的反过程，属于分裂的层次聚类，首先将所有的对象初始化到一个簇中，然后根据一些原则(比如最大的欧式距离)，将该簇分类。直到到达用户指定的簇数目或者两个簇之间的距离超过了某个阈值。
1、概述：
密度聚类方法的指导思想是，只要样本点的密度大于某阈值，则将该样本添加到最近的簇中。
（优点）这类算法能克服基于距离的算法只能发现“类圆 形”(凸)的聚类的缺点，可发现任意形状的聚类，且对噪声数据不敏感。（缺点）但计算密度单元的计算复杂度大，需要建立空间索引来降低计算量。
2、DBSCAN算法
DBSCAN(Density-Based Spatial Clustering of Applications with Noise)
一个比较有代表性的基于密度的聚类算法。 与划分和层次聚类方法不同，它将簇定义为 密度相连的点的最大集合，能够把具有足够高密度的区域划分为簇，并可在有“噪声”的数据中发现任意形状的聚类
算法流程：
a. 如果一个点p的ε-邻域包含多于m个对象，则创建一个p作为核心对象的新簇；
b. 寻找并合并核心对象直接密度可达的对象；
c. 没有新点可以更新簇时，算法结束。
由于包含过少对象的簇被认为是噪声，这种算法的抗噪性比较好。
3、密度最大值聚类（2014年science）
算法核心：
那些有着比较大的局部密度
和很大的高密距离
的点被认为是簇的中心；
高密距离
较大但局部密度
较小的点是异常点；
确定簇中心之后，其他点按照距离已知簇的中心最近进行分类。
这种方法可以自动选择聚类中心，并且结合了DBSCAN算法的抗噪声的优点。
第五章节：谱聚类
1、谱：
方阵作为线性算子，它的所有特征值的全体统称方阵的谱。
2、谱半径：
方阵的最大值称为谱半径。
矩阵的谱半径：
的最大特征值
3、谱聚类概述：
b. 用相似度图来解决样本数据的聚类问题：找到图的一个划分，形成若干个组，使得不同组之间有较低的权值，组内有较高的权值。
5、未正则拉普拉斯矩阵的谱聚类算法：
输出N个点{Pi}，簇数目K。
a. 计算n×n的相似度矩阵W和度矩阵D
b. 计算拉普拉斯矩阵L=D-W
，将k个列向量
组成矩阵
d. 令
是U的第i行的向量
e. 用k-means算法将点
聚类成簇 
f. 输出簇
6、谱聚类算法：随机游走拉普拉斯矩阵（效果最好）
a. 计算n×n的相似度矩阵W和度矩阵D
b. 计算拉普拉斯矩阵
c. 计算L的前k个特征向量
，将k个列向量
组成矩阵
d. 令
是U的第i行的向量
e. 用k-means算法将点
聚类成簇 
f. 输出簇
7、谱聚类算法：对称拉普拉斯矩
输出N个点{Pi}，簇数目K。
a. 计算n×n的相似度矩阵W和度矩阵D
b. 计算拉普拉斯矩阵
c. 计算L的前k个特征向量
，将k个列向量
组成矩阵
是U的第ie. 将
依次单位化，使得
f. 用k-means算法将点
聚类成簇 
g. 输出簇
附录：拉普拉斯矩阵及其性质
L是对称半正定矩阵，最小特征值是0，相应的特征 向量是全1向量。
五、标签传递算法
对于部分样本的标记给定，而大多数样本的标记未知的情形，是半监督学习问题。
标签传递算法(Label Propagation Algorithm,LPA)，将标记样本的标记通过一定的概率传递给未标记样本，直到最终收敛。
