3.2 常用聚类算法
聚类算法是机器学习中非常重要的算法，聚类是将大量数据以相似度为基础形成若干类，使得类内之间的数据最为相似，各类之间的数据相似度差别尽可能大。聚类分析就是以相似性为基础，对数据集进行聚类划分，属于无监督学习。聚类分析可以直接比较各事物之间的性质，将性质相近的归为一类，将性质差别较大的归入不同的类。
聚类分析具有广泛的应用领域。对于网络流量的监控和数据挖掘，可以实现舆情分析，获知出现的前所未有的热点事件。在商业上，市场消费数据的聚类，可以使企业相关人员获知新的消费趋势和市场需求。而在城市规划领域，对于市政交通或者人口分布的聚类，可以帮助市政规划人员更好地进行城市分区和道路建设。
3.2.1 K均值法及代码展示
K均值算法应用非常广泛，可以将一个未标记的数据集聚类成不同的组。K-Means算法通过迭代不断移动聚簇中心和簇类成员，直到得到理想的结果。通过K均值算法得到的聚簇结果，簇内项相似度很高，簇间项相似度很低，具有较好的局部最优特性，但并非是全局最优解。具体算法步骤如下：
1）随机选择K个聚类中心。
2）寻找每个数据点{x}距离最近的中心点，将两者关联，最后所有与同一中心点关联的点都聚成一类。
3）确定每组关联的中心点，并计算其均值。
反复操作2～3步，当中心点不发生变化时停止操作。
但K均值算法同样存在若干缺陷，例如需要事先确定K值，而K值的选择比较困难。在实际项目中，无法事先预估数据集最合适的类别个数。并且因为事先确定初始聚类中心，那么初始值选择好坏与否将对后面产生很大影响。此外，K均值只能定义在数值类属性值上，无法处理其他类型的数据。
面试时涉及K均值算法时，往往会有一个问题：应该如何改进K均值算法，改进的方法非常多，下面简要介绍其中一种。
K调和均值这个算法并不需要掌握，但是应当平时多接触更多的论文来准备好面试官的问题：某某算法应当如何改进？
K-Harmonic Means（K调和均值）算法流程为根据簇均值将数据初始分为K个簇，通过目标函数和中心移动公式对簇成员和中心点进行移动，算法迭代执行至不再有点移动即停止。其评价函数为所有点到所有中心的均方距离的调和平均值函数，平均值定义为
。然后将过于集中的中心点移到数据附近没有中心点的区域上。这种算法降低了对初始点选取的依赖，提高了算法的鲁棒性。
K调和均值算法仍然可以改进。AKHM算法使用了新的度量函数d(x,y)=1-exp(-β||x-y||2)进行了改进。得到新的目标函数如下：
以及由此可得新的中心更新公式：
AKHM调和均值的特性可以根据数据点特征赋予其不同权重，抗噪声性明显优于K-means算法。
K均值的代码实现如下。
Kmeans也可直接通过调用python函数实现，即sklearn.cluster.KMeans()，调用该函数也需要理解其中的参数含义，例如n_clusters是簇的个数，init是初始簇中心的获取方法，max_iter:是最大迭代次数，参数需要根据实际需要来调用。
在面试中经常会问到KNN与kmeans算法的不同点。KNN是监督学习算法，而kmeans是非监督的。这两种算法的相同点是都需要计算样本之间的距离。KNN算法需要事先已有标注好的数据，当对未标注的数据进行分类时，只需统计它附近最近的k个样本并划分为样本数最多的类别中。kmeans聚类并不需要事先标注好的数据，算法会逐渐将样本点进行分成族类。
3.2.2 谱聚类及代码展示
谱聚类是基于谱图理论的聚类算法，其原理是根据数据集相似性矩阵以聚类。相比于传统的K均值聚类法，谱聚类具有更强的数据分布适应性，好比K均值聚类法仅用于区分线性可分的类别，而谱聚类则不仅限于此，即便是非凸的模型同样也可很好地实现聚类。
以下简要介绍聚类数目为K的算法步骤。
1）计算相似度矩阵P∈Rn∗n。
2）计算度矩阵D，D是对角矩阵，对角线上的元素就是相似矩阵P的每行元素之和：
3）计算拉普拉斯矩阵L=D-W。
4）计算矩阵L的特征值，从小到大排序，通过前K个特征值计算特征向量X1,X2,…,Xk，构造新的矩阵：
X=[X1,…,XN]∈Rn∗k
5）将X的行向量规范化，得到矩阵：
6）Y是K维空间中的点矩阵，后面通过用Kmeans等聚类算法聚成K类，即可得到K个聚类中心点。
以上只是谱聚类的简单介绍。谱聚类算法本质上是将聚类问题转化为图的最优划分问题，属于对点聚类算法。谱聚类最重要的问题就是由于数据量太大，所以谱聚类中的很多大规模矩阵运算都无法很快完成。
谱聚类的代码展示如下。
3.2.3 幂迭代算法
幂迭代聚类算法（PIC）是一种运算效率更高的算法。该算法的计算效率高，因为它只涉及矩阵的向量迭代乘法和原始数据嵌入后的低维聚类，尤其是对大型稀疏矩阵，向量迭代乘法的计算量更小。幂迭代聚类（PIC）在数据归一化的逐对相似矩阵上，使用截断的幂迭代寻找数据集的一个超低维嵌入，该算法在真实数据集上总是好于广泛使用的谱聚类方法。
幂迭代聚类算法基本思想是：求某个n阶方阵A的特征值和特征向量时，先任取一个非零初始向量v(0)，进行如下的迭代计算，直到收敛：
v(k+1)=Av(k) k=0,1, 2,…
当k增大时，序列的收敛情况与绝对值最大的特征值有密切关系，分析这一序列的极限，即可求出按模最大的特征值和特征向量。在这个算法中还用到了一个小技巧：使用了早期截断，即不像常规迭代过程一直要迭代至最终收敛，而是迭代到一定程度就停止迭代，具体算法步骤如下。
1）输入按行归一化的关联矩阵W和期望聚类数k。
2）随机选取一个非零初始向量V(0)。
3）计算
。
4）重复迭代上式，直到O(t+1)满足早起截断条件。
5）使用K均值对向量v(t)中的点进行聚类。
6）输出最终得到的K类。
PIC算法一般针对数据量非常大的任务，此时可通过分布式计算工具spark 2.0中的org.apache. spark.mllib. clustering. PowerIterationClustering实现。
3.2.4 相似度度量公式
K-means常用欧氏距离来计算最近的邻居之间的距离，但有时也用曼哈顿距离，请对比下差别。
欧氏距离是最常见的两点之间或多点之间的距离表示法，如点x=(x1,…,xn)和y=(y1,…,yn)之间的距离为：
曼哈顿距离的意义为L1-距离或城市区块距离，也就是在欧几里得空间的固定直角坐标系上两点所形成的线段对轴产生的投影的距离总和。例如在平面上，坐标(x1,y1)的点P1与坐标(x2,y2)的点P2的曼哈顿距离为：
。
此外常见的相似度度量公式还有Jaccard系数：
，常用于二值型数据的相似度计算。在数据挖掘中将属性值二值化，通过计算Jaccard相似度，可以简单快速地得到两个对象的相似程度。
余弦相似度：
，可以简单地描述为空间中两个对象的属性所构成的向量之间的夹角大小。
皮尔森系数：
，可以描述为不同对象偏离拟合的中心线程度。
相对熵（K-L距离）：
。