聚类算法距离矩阵_聚类算法的评估指标

1、聚类算法距离矩阵_聚类算法的评估指标在学习聚类算法得时候并没有涉及到评估指标，主要原因是聚类算法属于非监督学习，并不像分类算法那样可以使用训练集或测试集中得数据计算准确率、召回率等。那么如何评估聚类算法得好坏呢？好的聚类算法，一般要求类簇具有：-高的类内(intra-cluster)相似度-低的类间(inter-cluster)相似度0%014tHe%得分来评估算法好曙该类型的方法*对于聚类算法大致可分为2类度量标准：I一JW1Heir-ShIt1:Wiarc辰CAi出気哼DKOM-外部评估的方法：通过将聚类结果与已经有“groundtruth”分类进行对比。要么通过人类进行手动评估，要么通过

2、一些指标在特定的应用场景中进行聚类用法的评估。不过该方法是有问题的，如果真的有了label，那么还需要聚类干嘛，而且实际应用中，往往都没label;另一方面，这些label只反映了数据集的一个可能的划分方法，它并不能告诉你存在一个不同的更好的聚类算法。内部评价指标当一个聚类结果是基于数据聚类自身进行评估的，这一类叫做内部评估方法。如果某个聚类算法聚类的结果是类间相似性低，类内相似性高，那么内部评估方法会给予较高的分数评价。不过内部评价方法的缺点是：那些高分的算法不一定可以适用于高效的信息检索应用场景；这些评估方法对某些算法有倾向性，如k-means聚类都是基于点之间的距离进行优化的，而那些基于

3、距离的内部评估方法就会过度的赞誉这些生成的聚类结果。这些内部评估方法可以基于特定场景判定一个算法要优于另一个，不过这并不表示前一个算法得到的结果比后一个结果更有意义。这里的意义是假设这种结构事实上存在于数据集中的，如果一个数据集包含了完全不同的数据结构，或者采用的评价方法完全和算法不搭，比如k-means只能用于凸集数据集上，许多评估指标也是预先假设凸集数据集。在一个非凸数据集上不论是使用k-means还是使用假设凸集的评价方法，都是徒劳的。SSE和方差该统计参数计算的是拟合数据和原始数据对应点的误差的平方和，计算公式如下：SSE越接近于0,说明模型选择和拟合更好，数据预测也越成功。#断崖碎石

4、图选取最优K值importpandasaspdfromsklearn.clusterimportKMeansimportmatplotlib.pyplotaspit利用SSE选择kSSE=#存放每次结果的误差轮廓系数SilhouetteCoefficient轮廓系数适用于实际类别信息未知的情况。对于单个样本，设a是与它同类别中其他样本的平均距离，b是与它距离最近不同类别中均距离，其轮廓系数为：对于一个样本集合，它的轮廓系数是所有样本轮廓系数的平均值。轮廓系数的取值范围是-1,1，同类别样本距离越相近不同类别样本距离越远，分数越高。缺点：不适合基高密度的聚类算法DBSCAN。fromsklear

5、nimportmetricsfromsklearn.metricsimportpairwise_distancesfromsklearnimportdatasetsdataset=datasets.1oad_iris（）X=dataset.datay=daCalinski-HarabazIndex在真实的分群label不知道的情况下，Calinski-Harabasz可以作为评估模型的一个指标Calinski-Harabasz指标通过计算类中各点与类中心的距离平方和来度量类内的紧密度，通过计算各类中心点与数据集中心点距离平方和来度量数据集的分离度，CH指标由分离度与紧密度的比值得到。从而，CH

6、越大代表着类自身越紧密，类与类之间越分散，即更优的聚类结果。从m-k其中m为训练样本数，k是类别个数，是类别之间协方差矩阵，是类别内部数据协方差矩阵，为矩阵的迹。也就是说，类别内部数据的协方差越小越好，类别之间的协方差越大越好，这样的Calinski-Harabasz分数会高。同时，数值越小可以理解为：组间协方差很小，组与组之间界限不明显。优点当cluster（簇）密集且分离较好时，分数更高，这与一个标准的cluster（簇）有关。得分计算很快与轮廓系数的对比，最大的优势：快！相差几百倍！毫秒级。缺点凸的簇的Calinski-Harabazindex（Calinski-Harabaz指数）通常

7、高于其他类型的cluster（簇），例如通过DBSCAN获得的基于密度的cluster（簇）。所以不适合基于密度的聚类算法，DBSCAN。importnumpyasnpfromsklearn.clusterimportKMeanskmeans_model=KMeans(n_clusters=3,random_state=1).fit(X)labels=kmeans_modelabels_prinompactness（紧密性）（）CP计算每一个类各点到聚类中心的平均距离CP越低意味着类内聚类距离越近。著名的K-Means聚类算法就是基于此思想提出的。缺点:没有考虑类间效果。EH任山IITlp=1

8、eparation（间隔性）（）SP计算各聚类中心两两之间平均距离，SP越高意味类间聚类距离越远。缺点：没有考虑类内效果。kk丽=-VVIIn；-心IIaviesouldin戴维森堡亍指数）分类适确性指标）（）（）其中n是类别个数，是第i个类别的中心，DB计算任意两类别的类内距离平均距离（CP）之和除以两聚类中心距离求最大值DB越小意味着类内距离越小同时类间距离越大。该指标的计算公式：是类别i中所有的点到中心的平均距离;中心点和之间的距离。算法生成的聚类结果越是朝着类内距离最小（类内相似性最大）和类间距离最大（类间相似性最小）变化，那么Davies-Bouldin指数就会越小。缺点：因使用欧式

9、距离所以对于环状分布聚类评测很差。fromsklearnimportdatasetsfromsklearn.clusterimportKMeansfromsklearn.metricsimportdavies_bouldin_scorefromsklearn.datasets.samples_generunnalidityndeX邓恩指数)(DVI计算任意两个簇元素的最短距离(类间)除以任意簇中的最大距离(类内)DVI越大意味着类间距离越大同时类内距离越小。“m血闵厂1*mayb,”Cl厂其中：是聚类的集合，表示第k个聚类的集合。是文档集合，表示第J个文档。表示文档总数。上述过程即给每个聚类簇

10、分配一个类别,且这个类别的样本在该簇中出现的次数最多，然后计算所有K个聚类簇的这个次数之和再归一化即为最终值Purity值在01之间，越接近1表示聚类结果越好。cluster1cluster2duster3当簇的数量很多的时候，容易达到较高的纯度一一特别是，如果每个文档都被分到独立的一个簇中，那么计算得到的纯度就会是1。因此，不能简单用纯度来衡量聚类质量与聚类数量之间的关系。另外Purity无法用于权衡聚类质量与簇个数之间的关系。defpurity(result,label):#计算纯度total_num=len(label)cluster_counter=collections.Counte

11、r(result)original_counter=collections.Counter(label)t=标准化互信息(互信息(NormalizedMutualInformation)是用来衡量两个数据分布的吻合程度。也是一有用的信息度量，它是指两个事件集合之间的相关性。互信息越大，词条和类别的相关程度也越大oNMI(NormalizedMutualInformation)即归一化互信息：其中，表示互信息(MutualInformation),为熵，当log取2为底时，单位为bit，取e为底时单位为nat。dpz戶(叫叨厂匸画匕|_纲呦n其中，可以分别看作样本(document)属于聚类簇,

12、属于类别，同时属于的概率。第二个等价式子则是由概率的极大似然估计推导而来。Hf门、_P口爲”互信息表示给定类簇信息的前提条件下,类别信息的增加量，或者说其不确定度的减少量。直观地，互信息还可以写出如下形式：互信息的最小值为0,当类簇相对于类别只是随机的，也就是说两者独立的情况下，对于未带来任何有用的信息如果得到的与关系越密切，那么值越大。如果完整重现了,此时互信息最大：G)=H(0)=忆当K=N时,即类簇数和样本个数相等，Ml也能达到最大值。所以MI也存在和纯度类似的问题，即它并不对簇数目较大的聚类结果进行惩罚，因此也不能在其他条件一样的情况下，对簇数目越小越好的这种期望进行形式化NMI则可以

13、解决上述问题，因为熵会随着簇的数目的增长而增大。当K=N时，会达到其最大值，此时就能保证NMI的值较低。之所以采用宙阿+R(Cj./2作为分母是因为它是的紧上界，因此可以保证示例：111111,222222.33333665gHd是-grou勺groups.问题：计算序列gnd和grps的NMI.先计算联合概率分布pfqrap,qnagrps,gnd1231pM=jf卫(1=i2P(2,1)二寺-备p(2j3)-ft-Jm_o咐_i计算边际分布计算熵和互信息H伽册.隔H(qws=1.522口皿疔词二1.014I(gnd;grps)=H(gnd)-丹加|卯卫勾殊盘趣计算NMI门2xKgsrps代

14、码实现：defNMI(result,label):#标准化互信息total_num=len(label)cluster_counter=collections.Counter(result)original_counter=collections.Counter(label)sklearn中自带的方法：fromsklearn.metrics.clusterimportnormalized_mutual_info_scoreprint(normalized_mutual_info_score(0,0,1,1,0,0,1,1)调整互信息AMI(Adjustedmutualinformation)已

15、知聚类标签与真实标签，互信息(mutualinformation)能够测度两种标签排列之间的相关性，同时忽略标签中的排列。有两种不同版本的互信息以供选择，一种是NormalizedMutualInformation(NMI),种是AdjustedMutualInformation(AMI)。假设U与V是对N个样本标签的分配情况，则两种分布的熵(熵表示的是不确定程度)分别为：其中：是从U中随机选取的对象到类的概率从V中随机选取的对象到类的概率U与V之间的互信息(Ml)定义为：MUf；V1=WPi4山討“匕亦其中是随机选择的对象落入两个类的概率和。调整互信息(Adjustedmutualinfor

16、mation)定义为:Ml的期望可以用以下公式来计算。在这个方程式中，为元素的数量，为元素的数量：利用基于互信息的方法来衡量聚类效果需要实际类别信息，Ml与NMI取值范围为0,1,AMI取值范围为-1,1，它们都是值越大意味着聚类结果与真实情况越吻合。优点随机（统一）标签分配的AMI评分接近0）有界范围0,1:接近0的值表示两个主要独立的标签分配，而接近1的值表示重要的一致性。此外，正好0的值表示purely（纯粹）独立标签分配，正好为1的AMI表示两个标签分配相等（有或者没有permutation）。对簇的结构没有作出任何假设：可以用于比较聚类算法缺点：与inertia相反，Ml-based

17、measures需要了解groundtruthclasses,而在实践中几乎不可用，或者需要人工标注或手动分配（如在监督学习环境中）。然而，基于Ml七asedmeasures（基于Ml的测量方式）也可用于纯无人监控的设置，作为可用于聚类模型选择的ConsensusIndex（共识索引）的构建块。NMI和Ml没有调整机会。fromsklearnimportmetricslabels_true=0,0,0,1,1,1labels_pred=0,0,1,1,2,2print（metrics.adjusted_mutual_info_score（labels_true,labels_pred）andi

18、nde兰德指数兰德指数（Randindex,Rl）,将聚类看成是一系列的决策过程，即对文档集上所有N（N-1）/2个文档（documents）对进行决策。篇文档相似时，我们将它们归入同一簇中。Positive:TP将两篇相似文档归入一个簇（同-同）TN将两篇不相似的文档归入不同的簇（不同-不同）Negative:FP将两篇不相似的文档归入同一簇（不同-同）FN将两篇相似的文档归入不同簇（同-不同）（worse）Rl则是计算正确决策的比率（精确率,accuracy）：”TP+TNTP+TNRl取值范围为0,1,值越大意味着聚类结果与真实情况越吻合。defcontingency_table（res

19、ult,label）:total_num=len（label）TP=TN=FP=FN=0foriinrange（total_num）:调整兰德系数（AdjustedRandindex）对于随机结果，Rl并不能保证分数接近零。为了实现“在聚类结果随机产生的情况下，指标应该接近零”，调整兰德系数（Adjustindex）被提出，它具有更高的区分度：ARl取值范围为-1,1,值越大意味着聚类结果与真实情况越吻合。从广义的角度来讲，ARl衡量的是两个数据分布的吻合程度。优点：对任意数量的聚类中心和样本数，随机聚类的ARl都非常接近于0取值在1,1之间，负数代表结果不好，越接近于1越好对簇的结构不需作出

20、任何假设：可以用于比较聚类算法。缺点：*与inertia相反，ARl需要groundtruthclasses的相关知识，ARl需要真实标签，而在实践中几乎不可用，或者需要人工标注者手动分配（如在监督学习环境中）。然而，ARl还可以在purelyunsupervisedsetting（纯粹无监督的设置中）作为可用于聚类模型选择（TODO）的共识索引的构建块。fromsklearnimportmetricslabels_true=0,0,0,1,1,1labels_pred=0,0,1,1,2,2print(metrics.adjusted_rand_score(labels_true,label

21、s_pred)F值方法这是基于上述Rl方法衍生出的一个方法，我们可以FN罚更多，通过取巧中的大于1,此时实际上也相当于赋予召回率更大的权重：RI方法有个特点就是把准确率和召回率看得同等重要，事实上有时候我们可能需要某一特性更多一点，这时候就适合F值方法。defprecision(result,label):TP,TN,FP,FN=contingency_table(result,label)return1.0*TP/(TP+FP)defrecall(result,label):TP,TN,FP,FN=contiFowlkes-MallowsscoresFowlkes-MallowsScores

22、(FMI)FMI是成对的precision(精度)和recall(召回)的几何平均数。取值范围为0,1,越接近1越好。定义为:TP代码实现:fromsklearnimportmetricslabels_true=0,0,0,1,1,1labels_pred=0,0,1,1,2,2print(metrics.fowlkes_mallows_score(labels_true,labels_pred)调和平均measure说V-measure之前要先介绍两个指标：同质性(homogeneity):每个群集只包含单个类的成员。完整性(completeness):给定类的所有成员都分配给同一个群集。同质性和完整性分数基于以下公式得出：.HiCK)“H(K0其中是给定给定簇赋值的类的条件熵，由以下公式求得：是类熵，公式为：其