聚类就是对大量未知标注的数据集，按数据的内在相似性将数据集划分为多个类别，使类别内的数据相似度较大而类别间的数据相似度较小。属于一种无监督算法。
关于kmenas聚类算法，转至：
小小：机器学习理论（十三）Kmeans聚类
一、相似度/距离计算方法总结
1、闵可夫斯基距离（Minkowski）：
2、杰卡德相似系数（Jaccard）：
3、余弦相似度（cosine similarity）：
4、Pearson相似系数：
5、相对熵（K-L距离）：
6、Hellinger距离：
二、聚类的衡量指标
评价指标分为外部指标和内部指标两种，外部指标指评价过程中需要借助数据真实情况进行对比分析的指标，内部指标指不需要其他数据就可进行评估的指标。
1、均一性：Homogeneity，一个簇只包含一个类别的样本，则满足均一性。
2、完整性：Completeness，同类别样本被归类到相同簇中，则满足完整性。
3、V-measure，均一性和完整性的加权平均。
4、ARI（Adjusted Rand Index），这个指标不考虑使用的聚类方法，把方法当做一个黑箱，只注重结果。
首先介绍感性地理解一下RI：
这里，我们解释一下a,b,c,d分别代表什么。
a就是应该在一类，最后聚类到一类的数量，b就是不应该在一类 ，最后聚类结果也没把他们聚类在一起的数量。c和d那么就是应该在一起而被分开的和不应该在一起而被迫住在一起的。
对于随机结果，RI并不能保证分数接近零。为了实现“在聚类结果随机产生的情况下，指标应该接近零”，调整兰德系数（Adjusted rand index）被提出，它具有更高的区分度：
ARI取值范围为[-1,1]，值越大意味着聚类结果与真实情况越吻合。从广义的角度来讲，ARI衡量的是两个数据分布的吻合程度。可用于聚类算法之间的比较。
5、AMI（Adjusted Mutual Information）调整互信息
互信息/正则化胡信息：
本质上与K-L散度有点像。
借鉴ARI，有：
6、轮廓系数（Silhouette）
定义：
对于第
个对象，计算它到所属簇中所有其他对象的平均距离，记为 （体现凝聚度）
对于第
个对象和不包含该对象的任意簇，记为 （体现分离度）接近1，则说明样本聚类更加合理， 接近-1，则说明样本更应该分类到另外的簇，若 接近0，则说明样本在两个簇的边界上。所有样本的 的均值称为聚类结果的轮廓系数，是该聚类是否合理、有效的度量。
三、层次聚类
层次聚类方法对给定的数据集进行层次分解，直到某种条件满足为止，具体又可分为：凝聚的层次聚类（AGNES）和分裂的层次聚类（DIANA）。
（1）凝聚的层次聚类（AGNES）:一种自底向上的策略，首先将每个对象作为一个簇，然后合并这些原子簇为越来越大的簇，直到某个终结条件被满足。
AGNES中簇间距离的不同定义：
最小距离：两个集合中最近的两个样本的距离，容易形成链状结构。最大距离：两个集合中最远的两个样本的距离，若存在异常值则不稳定。平均距离：两个集合中样本间两两距离的平均值方差：使得簇内距离平方和最小，簇间平方和最大
（2）分裂的层次聚类（DIANA）：采用自顶向下的策略，它首先将所有对象置于一个簇中，然后逐渐细分为越来越小的簇，直到达到了某个终结条件。
四、密度聚类法
密度聚类方法的指导思想：只要样本点的密度大于阈值，则将该样本添加到最近的簇中。这类算法能克服基于距离的算法只能发现“类圆形”聚类的缺点，可发现任意形状的聚类，且对噪声数据不敏感，但计算密度单元的计算复杂度大，需要建立空间索引来降低计算量。
（1）DBSCAN（Density-Based Spatial Clustering of Applications with Noise）一个比较有代表性的基于密度的聚类算法，它将簇定义为密度相连的点的最大集合，能够把具有足够高密度的区域划分为簇，并可在有"噪声"的数据中发现任意形状的聚类。
DBSCAN的一些基本概念：
对象的 邻域：给定对象在半径 内的区域。核心对象：对于给定的数目m，如果一个对象的邻域至少包含m个对象，则称该对象为核心对象。直接密度可达：给定一个对象集合 ，如果 在 的-邻域内，而q是一个核心对象，就称对象p到对象q出发时密度可达的。密度可达：如果存在一个对象链 ，他们相邻两者之间是直接密度可达的， ,则称对象 关于 是密度可达的。密度相连：如果对象集合中 中存在一个对象 ，使得对象对象 和 是从 关于 密度可达，那么称对象 和 是关于 密度相连。簇：一个基于密度的簇是最大的密度相连对象的集合。噪声： 不包含在任何簇中的对象称为噪声。
举例理解这些概念，如下图，
，由于 的-邻域内只有 个对象，所以 就不是核心对象，而q的-邻域内有 的对象大于 ，所以q 是核心对象。由此从对象 出发到对象p是直接密度可达的。
DBSCAN的算法流程：
如果一个点 的 邻域包含多于 个对象，则创建一个 作为核心对象的新簇；寻找并合并核心对象直接密度可达的对象；没有新点可以更新新簇时，算法结束。
由上述算法可知:
每个簇至少包含一个核心对象非核心对象可以是簇的一部分，构成了簇的边缘包含了过少对象的簇被认为是噪声。
还可以尝试将层次聚类和密度聚类结合起来使用，HDBSCAN
（2）密度最大值聚类
密度最大值聚类是一种简洁优美的聚类算法，可以识别各种形状的类簇，并且参数很容易确定。
定义：局部密度
其中
是一个截断密度， 即到对象 的距离小于的对象的个数。由于该算法只对的相对值敏感，所以对 的选择是稳健的，一种推荐的做法是选择，使得平均每个点的邻居数位所有点的
定义：高局部密度点距离
即在大于6的样本中选择最小的那个样本点。在密度高于对象
的所有对象中，到对象 最近的距离，即高局部密度点距离。只有那些密度是局部或者全局最大的点才会有远大于正常值的高局部密度点距离。
那些有比较大的局部密度
和很大的高密度距离 的点被认为是簇的中心，高密度距离较大但局部密度较小的点是异常点。确定簇中心之后，其他点按照距离已知簇的中心最近进行分类。
不同数据下密度最大值聚类的效果：
五、AP聚类Affinity Propagation
谱聚类和AP聚类是基于图的两种聚类。AP算法又称为仿射传播聚类算法、近邻传播聚类算法、亲和传播聚类算法，是根据数据点之间的相似度来进行聚类，可以是对称的，也可以是不对称的。 该算法不需要先确定聚类的数目，而是把所有的数据点都看成潜在意义上的聚类中心。然后通过网络中各条边的消息传递计算出各样本的聚类中心。聚类过程中，共有两种消息在各节点间传递，分别是吸引度( responsibility)和归属度(availability)。AP算法通过迭代过程不断更新每一个点的吸引度和归属度值，直到产生m个高质量的聚类中心（类似于质心），同时将其余的数据点分配到相应的聚类中。
AP算法流程：
步骤1：算法初始，将吸引度矩阵R和归属度矩阵初始化为0矩阵；
步骤2：更新吸引度矩阵:
步骤3：更新归属度矩阵:
步骤4：根据衰减系数
对两个公式进行衰减:
重复步骤2，3,4直至矩阵稳定或者达到最大迭代次数，算法结束。
最终取a+r
最大的 作为聚类中心。
AP聚类算法的特点：
无需指定聚类“数量”参数算法复杂度较高，为 ， 为样本数， 为迭代次数，而K-Means只是 的复杂度。因此当N比较大时( )，AP聚类算法往往需要算很久。
六、谱聚类
方阵作为线性算子，它的所有特征值的全体统称为方阵的谱。
方阵的谱半径为最大的特征值。矩阵A的谱半径： 的最大特征值。
谱聚类是一种基于图论的聚类方法，通过对样本数据的拉普拉斯矩阵的特征向量进行聚类，从而达到对样本数据聚类的目的。
拉普拉斯矩阵的定义：
计算点之间邻接相似度矩阵
，若两个点的相似度越大，表示这两个点越相似，同时，定义 表示 两个点没有任何相似性(无穷远)。 的第 行元素的和为 的度，形成顶点度对角阵 , 表示第 个点的度，除对角线元素， 的其他位置为0。未正则的拉普拉斯矩阵为： 正则的拉普拉斯矩阵为：对称拉普拉斯矩阵和随机游走的拉普拉斯矩阵。
对称拉普拉斯矩阵：
随机游走的拉普拉斯矩阵：
进一步思考：
谱聚类中的k如何确定？
未正则/对称/随机游走的拉普拉斯矩阵，首选哪个？随机游走的拉普拉斯矩阵。
谱聚类可以用切割图、随机游走、扰动论等解释。
七、边界和噪声的重认识
在聚类分析中，通常需要确定每个点划分给某个簇的可靠性。首先为每个簇定义一个边界区域，即划分给每个簇但是距离其他簇的点的距离小于
的点的集合，然后为每个簇找到其边界区域的局部密度最大的点，令其局部密度为 。该簇中所有局部密度大于的点被认为是簇核心的一部分（即将该点划分给该类簇的可靠性很大），其余的点被认为是该类簇的光晕，即可认为是噪声。
我是尾巴~
每日一句毒鸡汤：也许曾经失望过，但是应该去坚信“生命满希望，前路由我创”。也许曾经很受挫，但是应该去坚持“包羞忍耻是男儿……卷土重来未可知”。也许曾经觉得生活亏欠我们，但是应该去坚守“对明天的无限美好的憧憬”。
本次推荐：网易云音乐下载：
网易云全音乐下载.zip - 蓝奏云
继续加油~
如果觉得《层次聚类算法_机器学习理论（十四）聚类》对你有帮助，请点赞、收藏，并留下你的观点哦！
