页面树结构

2017-11-09 ApacheCN 开源组织,第二期邀请成员活动,一起走的更远 : http://www.apachecn.org/member/209.html


MachineLearning 优酷地址 : http://i.youku.com/apachecn

转至元数据结尾
转至元数据起始

可以使用模块进行未标记数据的聚类sklearn.cluster

每个聚类算法有两个变体:一个类,实现了fit学习列车数据上的集群的方法,以及给定列车数据的函数返回与不同集群对应的整数标签数组。对于该类,训练数据中的标签可以在labels_属性中找到。

 

输入数据


需要注意的一点是,本模块中实现的算法可以采用不同种类的矩阵作为输入。 所有的方法接受形状[n_samples,n_features]的标准数据矩阵。 这些可以从 sklearn.feature_extraction模块中的类获得。 对于AffinityPropagationSpectralClustering 和 DBSCAN 也可以输入形状[n_samples,n_samples]的相似矩阵。 这些可以从 sklearn.metrics.pairwise 模块中的函数获得。

聚类方法概述

在scikit学习中的聚类算法的比较

方法名称参数可扩展性用例几何(使用度量)
K-Means群集数非常大n_samples,中型n_clusters有 MiniBatch代码通用,甚至集群大小,平面几何,集群不太多点之间的距离
Affinity propagation阻尼,样品偏好不可扩展的n_samples许多簇,群集大小不均匀,非平面几何图距离(例如最近邻图)
Mean-shift带宽不可扩展 n_samples许多簇,群集大小不均匀,非平面几何点之间的距离
Spectral clustering群集数中等n_samples,小n_clusters几个簇,甚至簇大小,非平面几何图距离(例如最近邻图)
Ward hierarchical clustering群集数n_samplesn_clusters许多集群,可能连接限制点之间的距离
Agglomerative clustering簇数,链接类型,距离n_samplesn_clusters许多集群,可能是连接约束,非欧几里德距离任何成对距离
DBSCAN社区大小非常大n_samples,中等n_clusters非平面几何,不均匀的簇大小最近点之间的距离
Gaussian mixtures许多不可扩展平面几何,适合密度估算马哈拉诺比斯距离中心
Birch分支因子,阈值,可选全局集群。n_clustersn_samples大数据集,异常值去除,数据简化。欧几里得距离之间的距离

当群集具有特定形状即非平坦歧管时,非平面几何聚类非常有用,标准欧几里德距离不是正确的度量。这种情况出现在上图的两个顶行。

用于聚类的高斯混合模型在专门针对混合模型的文档的另一章中进行了描述 。可以将KMeans视为具有每个分量相等协方差的高斯混合模型的特殊情况。

 

K-means

KMeans算法通过试图分离n个相等方差组的样本来聚集数据,从而最小化称为 惯性或簇内和平方的标准。该算法需要指定簇的数量。它可以很好地扩展到大量样品,并已被广泛应用于许多不同领域的应用领域。

k-means算法将一组ñ样本X 分成ķ不相交的聚类C,每个聚类由集群中样本的平均值描述。手段通常称为集群“质心”; 注意,一般来说,他们并不一样,X虽然他们住在同一个空间。K-means算法旨在选择最小化惯性的质心,或者在群内的平方和之和:

惯性或集群内的平方和标准可以被认为是内部相干聚类的度量。它有各种缺点:

  • 惯性假定簇是凸的和各向同性的,这并不总是这样。它对细长的团簇或具有不规则形状的歧管反应不佳。
  • 惯性不是归一化度量:我们只知道较低的值是更好的,零是最优的。但是在非常高维的空间中,欧几里德的距离往往变得膨胀(这是所谓的“维度诅咒”的一个例子)。 在k-means聚类之前运行诸如PCA的维度降低算法可以缓解这个问题并加快计算速度。

K-means通常被称为劳埃德算法。在基本术语中,算法有三个步骤。第一步选择初始质心,最基本的方法是ķ从数据集中选择样本 X。初始化后,K-means由两个其他步骤之间的循环组成。第一步将每个样本分配到其最近的质心。第二步通过取分配给每个先前质心的所有样本的平均值来创建新的质心。计算旧和新质心之间的差异,并且算法重复这些最后两个步骤,直到该值小于阈值。换句话说,它重复,直到质心不显着移动。

K-means等价于具有小的全对称协方差矩阵的期望最大化算法。

该算法也可以通过Voronoi图的概念来理解。首先,使用当前质心计算点的Voronoi图。Voronoi图中的每个段都成为单独的集群。其次,质心被更新为每个细分的平均值。然后,该算法重复此操作,直到满足停止标准。通常,当迭代之间的目标函数的相对减小小于给定的公差值时,该算法停止。在此实现中不是这样:当质心移动小于公差时,迭代停止。

给定足够的时间,K-means将总是收敛,但这可能是局部最小的。这很大程度上取决于重心的初始化。因此,通常会进行几次计算,重心的初始化不同。帮助解决这个问题的一种方法是k-means ++初始化方案,它已经在scikit-learn(使用init='kmeans++'参数)中实现了。这将初始化质心(通常)彼此远离,导致比随机初始化更好的结果,如参考文献所示。

可以给出一个参数,以允许K-means并行运行 n_jobs。给这个参数一个正值使用许多处理器(默认值:1)。值-1使用所有可用的处理器,-2使用少一个等等。并行化通常以记忆的代价加速计算(在这种情况下,需要存储多个质心副本,每个作业一个)。

 

警告:当numpy使用 Accelerate Framework 时,K-Means的并行版本在OS X上损坏。这是预期的行为:可以在fork之后调用Accelerate,但是您需要使用Python二进制文件执行子进程(哪些多进程在posix下不执行)。

K-means可用于矢量量化。这是通过训练模型的变换方法实现的KMeans

例子:

参考文献:

小批处理的 K-Means

MiniBatchKMeansKMeans使用小批量来减少计算时间的算法的变体,同时仍然尝试优化相同的目标函数。小批量是输入数据的子集,在每次训练迭代中随机抽样。这些迷你批次大大减少了融合到本地解决方案所需的计算量。与其他减少k-means收敛时间的算法相反,小批量k-means产生的结果通常只比标准算法略差。

该算法在两个主要步骤之间进行迭代,类似于vanilla k-means。在第一步中,b样本从数据集中随机绘制,形成一个小批量。然后将它们分配到最近的质心。在第二步中,质心被更新。与k-means相反,这是在每个样本的基础上完成的。对于小批量中的每个样品,通过取样品的流平均值和分配给该质心的所有先前样品来更新分配的质心。这具有随时间降低质心的变化率的效果。执行这些步骤直到达到收敛或达到预定次数的迭代。

MiniBatchKMeans收敛速度快于结果KMeans,但结果的质量降低。在实践中,质量差异可能相当小,如示例和引用的参考。

例子:

参考文献:

 

Affinity Propagation(近邻传播)

AffinityPropagation通过在采样对之间发送消息来创建集群,直到收敛。然后使用少量示例来描述数据集,其被标识为最具代表性的其他样本。在对之间发送的消息表示一个样本作为另一个样本的样本的适用性,其被更新为响应于来自其他对的值。这种更新迭代直到收敛,此时选择最终样本,因此给出了最终聚类。

亲和传播可以是有趣的,因为它根据提供的数据选择簇数。为此,两个重要的参数是偏好,它控制使用多少个样本和阻尼因子

亲和传播的主要缺点是其复杂性。该算法具有顺序的时间复杂度, 样本数在哪里,ñŤ直到收敛的迭代次数。此外,如果使用密集的相似性矩阵,则存储器复杂度是顺序的 ,但是如果使用稀疏相似矩阵,则可以缩减。这使得Affinity传播最适合于中小型数据集。

例子:

算法描述: 点之间发送的消息属于两个类别之一。第一是责任,这是样本ķ 应该是样本样本的积累证据一世。第二个是可用性 ,这是样本一世 应该选择样本ķ作为其样本的累积证据,并考虑所有其他应用样本的样本的值ķ。以这种方式,样本由样本选择,如果它们(1)与许多样本相似,并且(2)由许多样本选择以代表它们自身。

更正式地说,样品的责任ķ 是样品的典范一世为:

哪里是样本之间的相似一世ķ。样品的可用性ķ 是样本的示范性一世由下式给出:

首先,对于所有的值,并一个设置为零,每个迭代的直到收敛计算。

 

 Mean Shift(平均偏移)

MeanShift聚类旨在发现样品平滑密度的斑点。它是一种基于质心的算法,通过将质心的候选更新为给定区域内的点的平均值。然后,这些候选者在后处理阶段被过滤以消除近似重复以形成最终质心集。

给定候选重心X_I的迭代Ť,候选者根据以下等式更新:

其中是围绕一给定距离内的样本的邻域X_I米均值偏移被计算为朝向在点的密度的最大增加的区域指向每个质心向量。这是使用以下等式计算的,有效地将质心更新为其邻域内样本的均值:

该算法自动设置簇的数量,而不是依赖于一个参数bandwidth,这决定了要搜索的区域的大小。该参数可以手动设置,但可以使用提供的estimate_bandwidth功能进行估计 ,如果带宽未设置,则调用该参数。

该算法不是高度可扩展的,因为它在执行算法期间需要多个最近邻搜索。该算法保证收敛,但是当质心的变化较小时,算法将停止迭代。

通过找到给定样品的最近质心来执行新样本的标记。

例子:

参考文献:

 

Spectral clustering(光谱聚类)

SpectralClustering在样本之间进行亲和力矩阵的低维嵌入,其次是低维空间中的KMeans。如果亲和力矩阵稀疏并且安装了pyamg模块,这是非常有效的。SpectralClustering需要指定簇数。它适用于少量集群,但在使用许多集群时不建议。

对于两个集群,它解决了相似图上的归一化切割问题的凸起松弛:将图形切割成两个,使得切割的边的权重与每个聚类内的边缘的权重相比较小。在图像处理时,这个标准特别有意义:图形顶点是像素,相似图的边缘是图像的渐变的函数。

 

警告:将距离转化为良好的相似之处

请注意,如果您的相似度矩阵的值不是很好地分布,例如使用负值或距离矩阵而不是相似度,则光谱问题将是单数,并且问题不可解。在这种情况下,建议对矩阵的条目应用转换。例如,在有符号距离矩阵的情况下,应用热核是常见的:

 similarity = np.exp(-beta * distance / distance.std())

看到这样一个应用程序的例子。

例子:

不同的标签分配策略

可以使用不同的标签分配策略,对应于 assign_labels参数SpectralClustering。该"kmeans"策略可以匹配更精细的数据细节,但可能更不稳定。特别是,除非你控制random_state,否则可能无法从运行到运行,因为它取决于随机的初始化。另一方面,该"discretize"策略是100%的可重复性,但它往往会创建相当均匀和几何形状的包裹。

assign_labels="kmeans"assign_labels="discretize"

参考文献:

 

Hierarchical clustering(层次聚类)

层次聚类是一个通用的聚类算法族,它们通过依次合并或分割来构建嵌套簇。簇的这种层次被表示为树(或树形图)。树的根是收集所有样本的唯一簇,叶是仅具有一个样本的簇。有关详细信息,请参阅维基百科页面

AgglomerativeClustering对象使用自下而上的方法进行分级聚类:每个观测在其自己的集群开始,并且簇依次合并在一起。链接标准确定用于合并策略的度量:

  • 病区最小化所有簇内平方差的总和。这是一种方差最小化的方法,在这个意义上与k均值目标函数相似,但是采用了一种聚集分层的方法。
  • 最大完全连接使集群对之间的最大观察距离最小化。
  • 平均联动使得聚类对的所有观察结果之间的距离的平均值最小化。

AgglomerativeClustering 当与连接矩阵联合使用时,也可以缩放到大量样本,但是当样本之间没有添加连接约束时,计算费用很高:它在每个步骤考虑所有可能的合并。

FeatureAgglomeration

FeatureAgglomeration用途合并聚类组合在一起,看起来非常类似的功能,从而减少了一些功能。它是一个维度降低工具,参见 无监督维度降低

不同的联动类型:病房,完整和平均联动

AgglomerativeClustering 支持病房,平均和完整的联动策略。

  

聚集群集具有“丰富更丰富”的行为,导致群集规模不均匀。在这方面,完整的联动是最糟糕的策略,沃德给出了最规则的大小。然而,与Ward相比,亲和度(或聚类中使用的距离)不能改变,因此对于非欧几里德度量,平均链接是一个很好的选择。

例子:

 

添加连接约束

一个有趣的方面AgglomerativeClustering是连接约束可以被添加到这个算法中(只有相邻的集群可以合并在一起),通过连接矩阵为每个样本定义一个给定的数据结构后的相邻样本。例如,在下面的swiss-roll示例中,连接约束禁止在瑞士卷上不相邻的点的合并,并且因此避免形成在卷的重叠折叠上延伸的簇。

 

这些约束对于施加一定的局部结构是有用的,但是它们也使算法更快,特别是当样本数量较高时。

连通性限制是通过连接矩阵来实现的:一个scipy稀疏矩阵,它只在一行和一列的交集处具有应连接的数据集的索引。该矩阵可以从先验信息构建:例如,您可能希望通过仅将页面与从一个链接指向另一个的链接来集合网页。也可以从数据中学习,例如sklearn.neighbors.kneighbors_graph本示例中使用来限制与最近邻居的合并,或者使用sklearn.feature_extraction.image.grid_to_graph仅使图像上的相邻像素合并,如在 浣熊脸部示例中。

例子:

 

警告:连接约束与平均和完整的连接

连通性约束和完整或平均联动可以增强聚集聚集的“丰富越来越多”的方面,特别是如果它们是建立的sklearn.neighbors.kneighbors_graph。在少量集群的极限中,它们倾向于给出一些宏观占用的集群,并且几乎是空的。(参见有和无结构的聚集聚类中的讨论 )。

 

 

 

  

改变度量

可以使用各种距离(或亲和度),特别是欧几里得距离(l2),曼哈顿距离(或城市街区,或11),余弦距离或任何预计算亲和度矩阵的平均和完整的连接。

  • l1距离通常对于稀疏特征或稀疏噪声是有利的:即许多特征都是零,如在使用罕见词的发生的文本挖掘中。
  • 余弦距离很有趣,因为它对信号的全局缩放是不变的。

选择度量标准的准则是使用最大化不同类别中样本之间距离的指南,并最小化每个类中的样本。

  

DBSCAN

DBSCAN算法将群集视为由低密度区域分隔的高密度区域。由于这种相当普遍的观点,DBSCAN发现的簇可以是任何形状,而不是假设簇是凸形的k-均值。DBSCAN的中心组件是核心样本的概念,这些样本是高密度区域的样本。因此,集群是一组核心样本,每个核心样本彼此靠近(通过一定距离度量测量)和一组接近核心样本的非核心样本(但本身不是核心样本)。有两个参数的算法, min_samples并且eps,它正式定义了我们的意思,当我们说密集。高min_samples或低eps表示形成簇所需的较高密度。

更正式地,我们将核心样本定义为数据集中的样本,使得存在min_samples距离内的其他样本 eps,其定义为核心样本的邻居。这告诉我们,核心样本在向量空间的密集区域。群集是一组核心样本,可以通过递归取岩芯样品,发现其所有的邻居都岩芯样品,发现所有的构建 自己的邻居是岩心样品,等等。集群还具有一组非核心样本,它们是集群中核心样本的邻居的样本,但本身不是核心样本。直观地,这些样本位于群集的边缘。

根据定义,任何核心示例都是集群的一部分。任何不是核心样本的样本,并且eps距离任何核心样本至少距离都被认为是该算法的异常值。

在下图中,颜色表示集群成员资格,大圆圈表示算法发现的核心样本。较小的圈子是仍然是群集的一部分的非核心样本。此外,异常值由下面的黑点表示。

履行

该算法是非确定性的,但核心样本将始终属于相同的簇(尽管标签可能不同)。非决定论来自于决定非核心样本属于哪个集群。非核心样本的距离可以低于eps不同群集中的两个核心样本。通过三角不等式,这两个核心样本必须比eps彼此更远 ,或者它们在同一个簇中。非核心样本被分配给首先生成的簇,其中顺序是随机确定的。除了数据集的排序之外,算法是确定性的,使得相同数据的运行之间的结果相对稳定。

当前的实现使用球树和kd-tree来确定点的邻域,避免计算全距离矩阵(如在0.14之前的scikit学习版本中所做的那样)。保留使用自定义指标的可能性; 详情见NearestNeighbors

大样本大小的内存消耗

这种实现默认情况下不是内存有效的,因为在不能使用kd-tree或ball-tree的情况下(例如使用稀疏矩阵),因为它构建了一个完整的成对相似性矩阵。该矩阵将消耗n ^ 2个浮点数。解决这个问题的几个机制是:

  • 稀疏半径邻域图(其中缺少条目被假定为超出eps)可以以高效的方式预先计算,并且可以使用dbscan来运行dbscan metric='precomputed'
  • 数据集可以通过删除精确重复的数据进行压缩,如果这些数据发生在数据中,或者使用BIRCH。那么你只有一个数量相对较少的代表数量很多。然后,您可以sample_weight在装配DBSCAN时提供。

参考文献:

  • “A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise”Ester,M.,HP Kriegel,J. Sander,and X. Xu,In Proceedings of the 2nd International Conference on Knowledge Discovery and Data Mining,Portland,OR ,AAAI Press,pp.226-231。1996年

 

Birch(利用层次方法的平衡迭代规约和聚类

Birch建立一个称为特征树(CFT),用于给定数据树。数据本质上是有损的压缩到一组特征特征节点(CF节点)。CF节点具有称为特征特征子集群(CF Subclusters)的多个子集群,并且位于非终端CF节点中的这些CF子集群可以具有CF节点作为子节点。

CF子群集保存用于聚类的必要信息,防止将整个输入数据保存在存储器中。此信息包括:

  • 子集群中的样本数。
  • 线性和 - 保存所有样本之和的n维向量
  • 平方和 - 所有样本的L2范数的平方和。
  • 质心 - 避免重新计算线性和/ n_samples。
  • 质心的平方范数。

Birch算法有两个参数,即阈值和分支因子。分支因子限制了节点中子集群的数量,阈值限制了进入样本和现有子集群之间的距离。

该算法可以被视为实例或数据简化方法,因为它将输入数据减少到直接从CFT的叶子获得的一组子集群。这种减少的数据可以通过将其送入全局集群来进一步处理。这个全局集群可以设置n_clusters。如果n_clusters设置为None,则直接读取叶子中的子集群,否则全局集群步骤将这些子集群标记为全局集群(标签),并将样本映射到最近子集群的全局标签。

算法描述:

  • 将新样本插入到作为CF节点的CF树的根中。然后将其与根的子集群合并,其在合并后具有最小半径,受阈值和分支因子条件约束。如果子集群有任何子节点,则重复执行,直到它到达一个叶子。在找到叶中最近的子集群之后,该子集群和父子集群的属性被递归地更新。
  • 如果通过合并新样本和最近的子集群获得的子集群的半径大于阈值的平方,并且如果子集群的数量大于分支因子,则临时分配给该新样本的空间。两个最远的亚群落被取走,并且亚群体基于这些亚群体之间的距离被分成两组。
  • 如果这个拆分节点有一个父子集群,并且有一个新的子集群的空间,那么父分割为两个。如果没有空间,则该节点再次分为两个,并且该过程被递归地继续,直到它到达根。

桦木还是MiniBatchK?

  • Birch不能很好地扩展到高维数据。根据经验,如果 n_features大于二十,通常最好使用MiniBatchKMeans。
  • 如果需要减少数据实例的数量,或者如果需要大量的子集群作为预处理步骤或其他方式,Birch比MiniBatchKMeans更有用。

如何使用partial_fit?

为避免计算全局聚类,对于每次调用partial_fit,建议用户使用

  1. n_clusters=None最初设定
  2. 通过多次调用partial_fit来训练所有数据。
  3. 设置n_clusters为必需值 brc.set_params(n_clusters=n_clusters)
  4. partial_fit最后调用没有参数,即brc.partial_fit() 执行全局集群。

 

参考文献:

 

聚类性能评估

评估聚类算法的性能并不像计数错误数量或监督分类算法的精度和调用那样微不足道。特别地,任何评估度量不应该考虑到集群标签的绝对值,而是如果这个聚类定义类似于某些基本真值集合的数据的分离或满足一些假设,使得属于同一类的成员更相似根据一些相似性度量,不同类的成员。

调整后的Rand指数

考虑到labels_true 相同样本的基本真实类分配和聚类算法分配 的知识labels_pred调整后的Rand指数是衡量两个赋值相似度的函数,忽略排列和机会规范化

>>> from sklearn import metrics
>>> labels_true = [0, 0, 0, 1, 1, 1]
>>> labels_pred = [0, 0, 1, 1, 2, 2]

>>> metrics.adjusted_rand_score(labels_true, labels_pred)  
0.24... 

 

可以在预测的标签中排列0和1,重新命名为2到3,并得到相同的分数:

>>> labels_pred = [1, 1, 0, 0, 3, 3]
>>> metrics.adjusted_rand_score(labels_true, labels_pred)  
0.24... 

 

此外,adjusted_rand_score对称的:交换参数不会改变得分。因此,它可以作为一个共识的措施

>>> metrics.adjusted_rand_score(labels_pred, labels_true)  
0.24...

 

完美标签得分为1.0:

>>> labels_pred = labels_true[:]
>>> metrics.adjusted_rand_score(labels_true, labels_pred)
1.0

 

坏(如独立标签)有负数或接近0.0分:

>>> labels_true = [0, 1, 2, 0, 3, 4, 5, 1]
>>> labels_pred = [1, 1, 0, 0, 2, 2, 2, 2]
>>> metrics.adjusted_rand_score(labels_true, labels_pred)  
-0.12... 

 

优点

  • 随机(统一)标签分配 对于任何值的ARI分数接近0.0n_clustersn_samples(对于原始的兰德指数或V度量,情况不是这样)。
  • 有界范围[-1,1]:负值是坏的(独立标注),相似的聚类具有正的ARI,1.0是完美的匹配得分。
  • 对集群结构没有作出任何假设:可以用于比较聚类算法,例如k-means,其假设各向同性斑点形状与可以找到具有“折叠”形状的聚类的频谱聚类算法的结果。

缺点

  • 与惯性相反,ARI需要对地面真相类的知识,而在实践中几乎不可用,或者需要人工注释者的人工分配(如在受监督的学习环境中)。

    然而,ARI也可以在纯无人监控的设置中用作可用于聚类模型选择(TODO)的共识索引的构建块。

例子:

数学公式

如果C是一个地面真实类赋值和K个聚类,我们定义一个b如下:

  • 一个,在C中与K中相同集合中的相同集合中的元素对数
  • b,C中不同集合中的元素对数,K中的不同集合中的元素对数

原始(未调整)兰德指数则由下式给出:

数据集中可能的对的总数(不排序)在哪里。

然而,RI分数不能保证随机标签分配将获得接近零的值(特别是如果聚类的数量与样本数量相同数量级)。

为了抵消这种影响,我们可以通过定义经调整的兰德指数来折现随机标签的期望RI ,如下所示:

参考

 

基于相互信息的分数

鉴于labels_true相同样本的基本真实类分配和我们的聚类算法分配的知识labels_pred, 互信息是衡量两个分配的一致性的函数,忽略排列。这种措施的两个不同的标准化版本是可用的,归一化互信息(NMI)调整的相互信息(AMI)。文献中经常使用NMI,而最近提出了AMI,并针对机会进行归一化

>>> from sklearn import metrics
>>> labels_true = [0, 0, 0, 1, 1, 1]
>>> labels_pred = [0, 0, 1, 1, 2, 2]

>>> metrics.adjusted_mutual_info_score(labels_true, labels_pred)  
0.22504... 

 

可以在预测的标签中排列0和1,重命名为2到3并得到相同的分数:

>>> labels_pred = [1, 1, 0, 0, 3, 3]
>>> metrics.adjusted_mutual_info_score(labels_true, labels_pred)  
0.22504... 

 

所有,mutual_info_scoreadjusted_mutual_info_score和 normalized_mutual_info_score是对称的:交换的说法不改变比分。因此,他们可以作为一个共识的措施

>>> metrics.adjusted_mutual_info_score(labels_pred, labels_true)  
0.22504... 

 

完美标签得分为1.0:

>>> labels_pred = labels_true[:]
>>> metrics.adjusted_mutual_info_score(labels_true, labels_pred)
1.0

>>> metrics.normalized_mutual_info_score(labels_true, labels_pred)
1.0 

 

这不是真的mutual_info_score,因此更难判断:

>>> metrics.mutual_info_score(labels_true, labels_pred)  
0.69...

 

坏(如独立标签)有非积分:

>>> labels_true = [0, 1, 2, 0, 3, 4, 5, 1]
>>> labels_pred = [1, 1, 0, 0, 2, 2, 2, 2]
>>> metrics.adjusted_mutual_info_score(labels_true, labels_pred)  
-0.10526...

 

优点

  • 随机的(均匀的)标签指定具有AMI得分接近0.0 为任何值n_clustersn_samples(其不是生互信息或V-措施例如的情况下)。
  • 有界范围[0,1]:接近零的值表示两个主要独立的标签分配,而接近1的值表示重要的一致性。此外,恰好为0的值表示独立的标签分配,并且恰好为1的AMI表示两个标签分配是相等的(有或没有排列)。
  • 对集群结构没有作出任何假设:可以用于比较聚类算法,例如k-means,其假设各向同性斑点形状与可以找到具有“折叠”形状的聚类的频谱聚类算法的结果。

缺点

  • 与惯性相反,基于MI的措施需要了解地面真相类,而在实践中几乎不可用,或需要人为注释者的人工分配(如在受监督的学习环境中)。

    然而,基于MI的措施也可用于纯粹无监督的设置,作为可用于聚类模型选择的共识索引的构建块。

  • NMI和MI没有调整机会。

例子:

数学公式

假设两个标签分配(相同的N个对象)üV。他们的熵是一个分区集的不确定性量,由

随机抽取的物体ü落入课堂的概率在哪里U_i。同样适用于V

。相互信息(MI)之间ü 和之间V的计算公式如下:

其中是一个对象拾取随机落入两个类的概率U_iV_j

归一化互信息定义为

这个互信息值和归一化变量的值不会因机会而被调整,随着标签分配之间的“互信息”的实际数量的增加,随着不同标签(簇)的数量的增加而增加。

互信息的期望值可以使用以下方程式计算,从Vinh,Epps和Bailey(2009)。在这个方程式中, (元素的数量U_i)和 (元素的数量V_j)。

使用预期值,然后可以使用与调整后的兰德指数相似的形式来计算调整后的相互信息:

参考

 

均匀性,完整性和V度量

考虑到样本的基本真实类分配的知识,可以使用条件熵分析来定义一些直观度量。

特别是Rosenberg和Hirschberg(2007)为任何集群分配定义了以下两个理想的目标:

  • 同质性:每个集群只包含一个类的成员。
  • 完整性:给定类的所有成员都分配到同一个集群。

我们可以把这些概念分数homogeneity_score和 completeness_score。两者都在0.0以下被界定为1.0以下(越高越好):

>>> from sklearn import metrics
>>> labels_true = [0, 0, 0, 1, 1, 1]
>>> labels_pred = [0, 0, 1, 1, 2, 2]

>>> metrics.homogeneity_score(labels_true, labels_pred)  
0.66...

>>> metrics.completeness_score(labels_true, labels_pred) 
0.42... 

 

称为V度量的谐波平均值是通过v_measure_score以下公式计算的 :

>>> metrics.v_measure_score(labels_true, labels_pred)    
0.51...
 

V度量实际上等于上面讨论的互相信息(NMI),由标准熵[B2011]的总和归一化。

同质性,完整性和V度量可立即计算 homogeneity_completeness_v_measure如下:

>>> metrics.homogeneity_completeness_v_measure(labels_true, labels_pred)
...                                                      
(0.66..., 0.42..., 0.51...) 

以下聚类分配稍微好一些,因为它是同构但不完整的:

>>> labels_pred = [0, 0, 0, 1, 2, 2]
>>> metrics.homogeneity_completeness_v_measure(labels_true, labels_pred)
...                                                      
(1.0, 0.68..., 0.81...) 

注意:v_measure_score对称的:它可以用于评估同一数据集上两个独立分配的协议

这是不是这样的completeness_score和 homogeneity_score:两者都是由关系的约束:

 homogeneity_score(a, b) == completeness_score(b, a)
 

优点

  • 有界分数:0.0是不错的,1.0是一个完美的分数。
  • 直观的解释:可以在均匀性和完整性方面进行 质量分析, 以便更好地感受到作业中出现什么样的错误。
  • 对集群结构没有作出任何假设:可以用于比较聚类算法,例如k-means,其假设各向同性斑点形状与可以找到具有“折叠”形状的聚类的频谱聚类算法的结果。

缺点

  • 先前引入的度量标准并不是随机标记的标准化的:这意味着根据样本数量,簇和地面真值类别,完全随机的标签并不总是产生同质性,完整性和因此的v-度量的相同值。特别是当簇数量大时,随机标记不会产生零分

    当样本数量超过一千,群集数小于10时,可以安全地忽略此问题。对于较小的样本数量或较大数量的群集,使用调整后的索引(如“调整后的” ARI)

  • 这些指标需要知识的地面真相类,而在实践中几乎不可用,或者需要人类注释者的人工分配(如在受监督的学习环境中)。

例子:

数学公式

均匀性和完整性得分正式由以下方式给出:

给定集群分配的类条件熵在哪里,由下式给出:

并且熵,由下式给出:

ñ样品的总数,n_cn_k 分别属于类的样本的数目C和簇ķ,以及最后从类的样本的数目C分配给簇ķ

给定类的簇 的条件熵和簇的  以对称方式定义。

Rosenberg和Hirschberg进一步将V-measure定义为均匀性和完整性谐波均值

参考

[RH2007]V-Measure:基于条件熵的外部集群评估措施 Andrew Rosenberg和Julia Hirschberg,2007
[B2011]社会媒体事件的识别与表征,Hila Becker,博士论文。

 

 

Fowlkes-Mallows得分

sklearn.metrics.fowlkes_mallows_score当知道样本的地面实例类分配时,可以使用Fowlkes-Mallows index()。Fowlkes-Mallows得分FMI被定义为成对精度和召回的几何平均值:

哪里TP是多少真阳性(即属于两个真正的标签和预测的标签相同集群对点的数量),FP是多少假阳性(即属于一对点的即数真正标签中的相同聚类,而不是预测标签中),并且FN假阴性数(即,预测标签中属于同一簇的点对数,而不在真实标签中)。

分数范围为0到1.高值表示两个群集之间的良好相似性。

>>> from sklearn import metrics
>>> labels_true = [0, 0, 0, 1, 1, 1]
>>> labels_pred = [0, 0, 1, 1, 2, 2]
>>>
>>> metrics.fowlkes_mallows_score(labels_true, labels_pred)  
0.47140...

 

可以在预测的标签中排列0和1,重命名为2到3并得到相同的分数:

>>> labels_pred = [1, 1, 0, 0, 3, 3]

>>> metrics.fowlkes_mallows_score(labels_true, labels_pred)  
0.47140... 

 

完美标签得分为1.0:

>>> labels_pred = labels_true[:]
>>> metrics.fowlkes_mallows_score(labels_true, labels_pred)  
1.0 

 

坏(如独立标签)的分数为零:

>>> labels_true = [0, 1, 2, 0, 3, 4, 5, 1]
>>> labels_pred = [1, 1, 0, 0, 2, 2, 2, 2]
>>> metrics.fowlkes_mallows_score(labels_true, labels_pred)  
0.0 

 

优点

  • 随机的(均匀的)标签指定具有FMI得分接近0.0 为任何值n_clustersn_samples(其不是生互信息或V-措施例如的情况下)。
  • 有界范围[0,1]:接近零的值表示两个主要独立的标签分配,而接近1的值表示重要的一致性。此外,恰好为0的值表示独立的标签分配,并且恰好为1的AMI表示两个标签分配是相等的(有或没有排列)。
  • 对集群结构没有作出任何假设:可以用于比较聚类算法,例如k-means,其假设各向同性斑点形状与可以找到具有“折叠”形状的聚类的频谱聚类算法的结果。

缺点

  • 与惯性相反,基于FMI的措施需要了解地面真相课程,而在实践中几乎不可用,或需要人工注释器进行人工分配(如在受监督的学习环境中)。

参考

 

剪影系数

如果地面真相标签不知道,则必须使用模型本身进行评估。剪影系数(sklearn.metrics.silhouette_score)是一个这样的评估的例子,其中较高的剪影系数分数与具有更好定义的聚类的模型相关。剪影系数是为每个样本定义的,由两个分数组成:

  • a:样本与同一类别中所有其他点之间的平均距离。
  • b:样本与下一个最近聚类中所有其他点之间的平均距离。

轮廓系数小号然后对单个样品被给出为:

给定一组样本的轮廓系数作为每个样本的轮廓系数的平均值。

>>> from sklearn import metrics
>>> from sklearn.metrics import pairwise_distances
>>> from sklearn import datasets
>>> dataset = datasets.load_iris()
>>> X = dataset.data
>>> y = dataset.target 

 

在正常使用情况下,将轮廓系数应用于聚类分析的结果。

>>> import numpy as np
>>> from sklearn.cluster import KMeans
>>> kmeans_model = KMeans(n_clusters=3, random_state=1).fit(X)
>>> labels = kmeans_model.labels_
>>> metrics.silhouette_score(X, labels, metric='euclidean')
...                                                      
0.55... 

 

参考

优点

  • 对于不正确的聚类,分数为-1,高密度聚类为+1。零点附近的分数表示重叠的聚类。
  • 当集群密集且分离好时,分数更高,这与集群的标准概念有关。

缺点

  • 凸系数通常比群集的其他概念更高,例如通过DBSCAN获得的基于密度的集群。

例子:

 

Calinski-Harabaz指数

如果地面真相标签是未知的,sklearn.metrics.calinski_harabaz_score则可以使用Calinski-Harabaz指数()来评估模型,其中较高的Calinski-Harabaz分数与具有更好定义的聚类的模型相关。

对于ķ群集,Calinski-Harabaz得分小号是以簇间色散平均值与群内色散之间的比率给出的:

B_K组间色散矩阵在哪里,是W_K 由以下定义的群内色散矩阵:

ñ是点在我们的数据的数量,C_q在集群的点的集合qc_q是集群的中心 qC是中心Ën_q在集群的点数q

>>> from sklearn import metrics
>>> from sklearn.metrics import pairwise_distances
>>> from sklearn import datasets
>>> dataset = datasets.load_iris()
>>> X = dataset.data
>>> y = dataset.target

 

在正常使用情况下,将Calinski-Harabaz指数应用于聚类分析的结果。

>>> import numpy as np
>>> from sklearn.cluster import KMeans
>>> kmeans_model = KMeans(n_clusters=3, random_state=1).fit(X)
>>> labels = kmeans_model.labels_
>>> metrics.calinski_harabaz_score(X, labels)  
560.39... 

 

优点

  • 当集群密集且分离好时,分数更高,这与集群的标准概念有关。
  • 得分快速计算

缺点

  • 凸群的Calinski-Harabaz指数通常高于簇的其他概念,例如通过DBSCAN获得的基于密度的集群。

参考

 

  • 无标签