聚类算法(1)


本文内容包含:
一、基本概念
二、K-means
三、凝聚层次聚类
四、DBSCAN密度聚类
五、簇评估


一、基本概念

聚类分析仅根据数据内部发现的描述对象及其关系信息将数据对象分组。组件的相似性(如凝聚度)越大,组件差别越大(如分离度),聚类就越好。

1. 不同的聚类类型

1.1 层次的和划分的

其区别是簇的集合是嵌套的还是非嵌套的。

  • 层次的: 适用于小数据。可以形成相似度层次图谱,便于直观地确定类之间的划分。
  • 划分的: 适用于大数据。将观测分为预先指定不重叠的类。但不能提供类相似度信息,需要实现决定聚类个数初始位置。(如K-means)

1.2 互斥的、重叠的与模糊的

互斥: 互斥表示一个对象最多只属于一个类。
重叠: 重叠表示一个对象可以被指定为多个类。没个对象以 1(绝对属于)和 0(绝对不属于)的概率属于任何一个集合,且隶属概率之和为1。

1.3 完全的与部分的

完全的: 将每个对象指派到一个簇
部分的: 忽略掉不感兴趣的背景(噪音或者离群点)

2. 部分聚类的方法

K-means: 是基于原型的、划分的聚类技术。适用于大数据。将观测分为预先指定不重叠的类。但不能提供类相似度信息,需要实现决定聚类个数初始位置
凝聚的层次聚类: 开始每个点作为单个簇;然后重复地合并两个最靠近的簇直到产生单个的、包含所有点的簇。
两步聚类: 适用于大样本数据。以 BIRCH 方法为代表,是层次聚类和 k-means 的结合。具有运算速度快、不需要大量递归运算,节省存储空间的优点。
基于密度的聚类: 适用于大样本数据,对噪音不敏感。基于划分的方法适用于样本形态为球状簇时的情况,当分布不规则时,需要使用该类方法。最常见的是 BDSCAN聚类。

二、K-means

1. 算法步骤

<1> 选择$K$个点作为初始质心

<2> Repeat:

<3> 将每个点指派到最近的质心,形成$K$个簇

<4> 重新计算每个簇的质心

<5> Until: 质心不发生变化终止

2. 距离的度量

闵可夫斯基距离

闵可夫斯基距离不是一种距离,而是一类距离的定义。对于 n 维空间中的两个点 $x(x_1,x_2,x_3,…,x_n)$和$y(y_1,y_2,y_3,…,y_n)$,那么$x$和$y$亮点之间的闵可夫斯基距离为:$$d_{xy}=\sqrt{\sum_{i=1}^{n}{\left( x_{i}-y_{i} \right)^{p}}}$$
其中p是一个可变参数:

  • 当p=1时,被称为曼哈顿距离
  • 当p=2时,被称为欧式距离
  • 当p=$\infty $时,被称为切比雪夫距离。

余弦相似度

$$cos(\Theta )=\frac {a^Tb}{|a|*|b|}$$

  • $a,b$表示两个向量,$|a|$和$|b|$表示向量的模。 余弦相似度一般衡量两个向量的相似情况,常用与文本处理。余弦角越小越相似。

杰卡德(Jaccard)相似系数

$$J(A,B)=\frac {|A \bigcap B|}{|A \bigcup B|}$$

  • 这里,$A、B$表示集合,$A \bigcap B$表示两个集合公共元素的个数,$A \bigcup B$表示两个集合并集元素的个数。 Jaccard 相似系数适用于度量两个集合的相似程度,取值在 0~1 之间,越大越相似。在推荐系统中常用衡量客户或商品的相似度。

3. 变量标准化

在聚类前,通常需要对个连续变量进行标准化,因为方差大的变量比方差晓得变量对距离或相似度的影响更大,从而对聚类结果的影响更大。

常用的方法有:

正态标准化:$x_i=\frac {x_i-mean(X)}{std(X}$
归一化:$x_i=\frac {x_i-min(X)}{max(X)-min(X)}$

4. 变量的维度分析

假设一组变量中,一个维度有5个变量,二另一个维度只有1个变量,则第一个维度的权重被明显提高了。一般情况下,每个维度上使用的变量个数应该是一样的,不过分析人员要结合具体场景不同维度提供不同数量的变量个数,这相当于加大了一些维度的权重。

除了机遇业务定义进行变量的选择,另一种常用的方法是在聚类之前进行主成分分析。

5. 质心的目标函数

5.1 SSE 误差平方和

聚类的目标通常用一个目标函数表示,该函数依赖于点之间,或点到簇的质心的临近性;
如,考虑临近性度量为欧几里得距离的数据,我们使用误差平方和(SSE)作为度量聚类质量的目标函数,即最小化簇中点到质心的距离平方和。 SSE也称散布(scatter),定义如下:
$$SSE=∑^K_{i=1}∑_{x\in C_i}dist(c_i,x)^2$$
其中,$dist$是欧几里得空间中两个对象之间的标准欧几里得距离。

给定这些假设,实际上可以证明:对 SSE 求导,另导数为 0 求解 $c_k$使簇的 SSE 最小的质心是均值

$$\frac {\partial }{\partial c_k}SSE =\frac {\partial }{\partial c_k}∑^K_{i=1}∑_{x\in C_i}(c_i,x)^2=0 $$

最终得到: $$∑_{x\in C_k}2(c_k-x_k)=0\Longrightarrow m_kc_k=∑_{x\in C_k}x_k \Longrightarrow c_k = \frac 1{m_k}∑_{x\in C_k}x_k$$

文档数据

考虑文档数据和余弦相似性度量。这里我们假定文档数据用文档——词矩阵表示,我们的目标是最大化簇中文档与簇的质心的相似性;该量乘坐簇的凝聚度(cohesion)。对于该目标,可以证明,与欧几里得数据一样,簇的质心是均值。总 SSE 的类似量是总凝聚度(total cohesion):
$$Total Cohesion=∑^K_{i=1}∑_{x\in C_i}cosine(c_i,x)$$

关于凝聚度的知识,会在下文模型评估里面详细介绍

5.2 SAE 绝对误差和

为了表明$K$均值可以用各种不同的目标函数,我们考虑如何将数据分成$K$个簇,使得点到其簇中心的曼哈顿距离之和最小。如下式绝对误差和(SAE)

$$SAE = ∑^K_{i=1}∑_{x \in C_i}|c_i-x|$$

$$\frac {\partial }{\partial c_k}SAE =\frac {\partial }{\partial c_k}∑^K_{i=1}∑_{x\in C_i}|c_i-x|=0 $$

最终得到: $$∑_{x\in C_k}\frac {\partial }{\partial c_k}|c_k-x|=0\Longrightarrow ∑_{x\in C_k}sign(x-c_k )=0 \Longrightarrow c_k=median{x\in C_k}$$
即簇中点的中位数。一组点的中位数的计是直截了当的,并且减少受离群值的影响。

5.3 常见的邻近度、质心和目标函数组合

邻近度函数 质心 目标函数
曼哈顿距离 中位数 最小化对象与质心的绝对误差和SAE
平方欧几里得距离 均值 最小化对象与质心的误差平方和SSE
余弦 均值 最大化对象与质心的余弦相似度和
Bregman散度 均值 最小化对象到质心的Bregman散度和

Bregman散度实际上是一类紧邻性度量,包括平方欧几里得距离。Bregman散度函数的重要性在于,任意这类函数都可以用作以均值为质心的 K-means 类型的聚类算法的基础。

6. 选择初始质心

当质心随机初始化时,K-means 将产生不同的总 SEE。选择适当的初始质心是基本 K-menas 过程的关键步骤。常见的是随机选取,但这种情况下簇的质量常常很差。考虑什么情况下选择的初始质心能找到最优解?答案是:每个簇刚好分到一个质心。事实证明发生这种情况的概率是非常非常低的。

常见一种技术是:多次运行,然后选取具有最小 SEE 的簇集。该策略虽然简单,但是效果可能不太好,依然是概率事件。

另一种有效的技术是:取一个样本,并使用层次聚类技术对他聚类。从层次聚类中提取 $K$ 个簇,并用这些簇的质心作为初始质心。该方法虽然有效,但仅对下列情况有效:(1)样本相对较小,例如数百到数千(层次聚类开销较大);(2)$K$ 相对与样本大小较小。

还有一种方法是:随机选择第一个点或者所有点到质心作为第一个点。然后对于每个候机初始质心,选择里已经选取的初始质心最远的点,并且把该方法应用与点样本。 这样可以大大缓解可能会选择离群点作为质心的可能,并且大大减小计算量。

另外,我们也可以采用对初始化问题不太敏感的 K-means 的变种,二分K-means、使用后处理来“修补”
所产生的簇集

7. 时间复杂性和空间复杂性

  • 所需空间:$O((m+K)n)$,m 是点数, n 是属性数

  • 所需时间:$O(IKm*n)$,$I$ 是收敛所需迭代次数,通常很小,可以是有界的。

8. K-means 其他问题

8.1 处理空簇

K-means 存在的问题之一是:如果所有的点在指派的步骤都为分配到某个簇,就会得到空簇。这种情况下需要选择一个替补质心,否则误差将会偏大。

  • 方法一: 选择一个距离当前任何质心最远的点
  • 方法二: 从具有最大 SSE 的簇中选择一个替补质心。浙江分裂簇并降低聚类的总 SSE。

8.2 离群点

当然我们想到的第一反应是删除离群点,但是有些聚类应用,不能删除离群点。在某些情况下(财经分析),明显的离群点可能是最令人感兴趣的点。

那么问题来了,如何识别离群点?

  • 方法一:聚类前删除离群点
  • 方法二:后处理离群点。如删除那些具有不寻常影响的点(尤其是多次运行算法时),另外也可以删除那些很小的簇,他们尝尝代表离群点的组。

8.3 后处理降低 SSE

  • 增加簇个数

    • 分裂一个簇:通常选择具有最大 SSE 的簇,页可以分裂在特定属性上具有最大标准差的簇。
    • 引进一个新的质心:通常选择离所有质心最远的点。
  • 减少簇个数

    • 拆散一个簇: 通常选择拆散使总 SSE 增加最少的簇, 删除对应的质心
    • 合并两个簇: 通常选择合并质心最接近的两个簇,或者合并两个导致总 SSE 增加最少的簇。这两种方法与层次聚类使用的方法相同,分别乘坐质心方法和 Ward 方法。

9. 二分 K-means

二分 K-means 算法时基于 K-means 算法的直接扩充,它基于一种简单想法:为了得到 K 个簇,将所有点的集合分裂成两个簇,从这些簇中选取一个继续分裂,如此下去,知道产生 K 个簇。

算法实现步骤:

<1> 初始化簇表,是指包含有所有的点组成的簇。

<2> Repeat

<3> 从簇表中取出一个簇

<4> 对选出的簇进行多次二分“实验”

<5> for i = 1 to 试验次数 do:

<6> 使用基本 K-means,二分选定的簇

<7> end for

<8> 从二分实验中选择具有最小 SSE 的两个簇

<9> 将这两个簇添加到簇表中

<10> Until 簇表包含 K 个簇。

待分裂的簇有许多不同的选择方法。可以选择最大的簇,选择具有最大 SSE 的簇,或者使用一个基于大小和 SSE 的标准进行选择。不同的选择导致不同的簇。

我们通常使用结果簇的质心作为基本 K-means 的初始质心,对结果逐步求精。 因为尽管 K-means 可以保证找到使 SSE 局部最小的聚类,但是自二分 K-means 算法中,我们“局部地”使用了 K-means ,即二分个体簇。因此,最终的簇集并不代表使 SSE 局部最小的聚类。

10. K-means优缺点

10.1 优点

  • 简单并且可以用于各种数据类型;
  • 具备适合的空间复杂度和计算负责度,适用于大样本数据;
  • K-means 某些变种甚至更有效 (二分K-means)且不受初始化问题影响。

    10.2 缺点

  • 不能处理非球形簇、不同尺寸和不同密度的簇;

  • 对离群点敏感;
  • K-means 仅限于具有中心(质心)概念的数据。有一种相关的 K-中心点聚类技术没有这种限制,但是开销更大。

三、凝聚层次聚类

有两种产生层次聚类的基本方法:

  • 凝聚的: 从点作为个体簇开始,每一步合并两个最接近的簇
  • 分裂的: 从包含所有的点某个簇开始,每一步分裂一个簇,知道今生下单点簇

到目前为之,凝聚层次聚类最常见,这里只讨论这类方法。

1. 基本聚类层次聚类算法

<1> 如果需要,计算邻近度矩阵

<2> Repeat:

<3> 合并最接近的两个簇

<4> 更新临近性矩阵,以反映新的簇与原来簇之间的临近性

<5> Until: 仅剩下一个簇

2. 定义簇之间的临近性

  • MIN:MIN定义簇的邻近度为不同簇的两个最近点之间的距离,也叫做单链(sigle link)
  • MAX:MAX定义簇的邻近度为不同簇的两个最远点之间的距离,也叫做全链(complete link)
  • 组平均:它定义簇邻近度为取自不同簇的所有点对邻近度的平均值。

如果我们取基于原型的观点,簇用质心代表,则不同簇邻近度定义就更加自然。

  • 簇质心间邻近度:两个簇质心之间的距离
  • Ward方法:同样嘉定簇用气质心代表,但他使用合并两个簇导致 SSE 的增量来度量两个簇之间的临近性。像 K-means 一样, Ward 方法也是图最小化点到其簇质心的距离平方和。

3. 时间和空间复杂性

  • 空间复杂度: $O(m^2)$
  • 时间复杂度: $O(m^2)$时间计算邻近度矩阵,基于以上算法所需总时间为$O(m^2log(m))$

基本层次聚类使用邻近度矩阵,这需要存储$m^2/2$个邻近度(假定邻近度矩阵是对称的),其中$m$是数据点的个数。记录簇所需要的空间正比于簇的个数$m-1$,不包括单点簇。因此空间复杂度是$O(m^2)$。

上面步骤中<3>和<4>涉及$m-1$次迭代,因为开始有$m$个簇,每次迭代合并两个簇。如果邻近度矩阵采用线性搜索,则对于第$i$次迭代,步骤3需要$O(m-i+1)^2$的时间,步骤<4>只需要$O(m-i+1)$时间,在合并两个簇后更新邻近度矩阵(对于我们考虑的技术,簇合并至影响$O(m-i+1)$个邻近度)不做修改,时间负责度将为$O(m^3)$。如果某个簇到其他所有簇的距离存放在一个有序表或堆中,则查找两个最近簇的开销可能降低到$O(m-i+1)$,然而,由于维护有序表或堆的附加开销,基于以上算法的层次聚类所需总时间是$O(m^2log(m))$。

由此可见,层次聚类算法需要消耗大量的存储和计算资源,严重限制了它所能处理的数据集的大小。

4. 层次聚类的主要问题

4.1 缺乏全局目标函数

也就是说凝聚层次聚类技术使用各种标准,在每一步局部地确定哪些簇应当合并(或分裂,对于分裂方法)。这种方法产生的聚类算法避开了解决困难的组合优化能力。此外这样的方法没有局部极小问题或很难选择初始化的问题。当然,在许多情况下$O(m^2)$的空间复杂度和$O(m^2log(m))$的事件负责度也阻碍了它的应用。

4.2 处理不同大小簇的能力

对于如何处理待合并的簇对的相对大小(鄙人理解为权值,该讨论仅适用于涉及求和的簇临近性方法,如质心、Ward方法和组平均)有两种方法:

  • 加权:平等的对待所有簇,赋予不同大小的簇中点不同的权值
  • 非加权: 赋予不同大小簇中点相同的权值

4.3 合并不可逆

对于合并两个簇,凝聚层次聚类算法去相遇作出有好的局部决策。然而,一旦做出合并决策,以后就不能撤销。这种方法阻碍了局部最优标准变成全局最优标准。

有一些技术是图克服“合并不可逆”这一限制,一种通过移动树的分支以改善全局目标函数;另一种使用划分聚类技术(如K-means)来创建许多小簇,然后从这些小簇出发进行层次聚类。
看似第二种更可取

5. 总结

该算法缺点上面描述的已经很详细了,通常使用这类算法是因为基本应用需要层次结构,此外有些研究表明这些算法能产生高质量的聚类。然而就计算量和存储量而言,凝聚层次聚类算法是昂贵的,合并时不可逆的,对于噪声、高维数据(如文档数据),这也可能造成问题。

首先使用其他技术(K-均值)进行部分聚类,这两个问题都可以在某种程度上加以解决。

四、DBSCAN 基于密度的聚类

基于密度的聚类寻找被低密度区域分离的高密度区域。DBSCAN 是一种简单、有效的基于密度的聚类算法。

1. 基本名词

  • 核心点: 如果该点满足给定的邻域内(半径为$Eps$的范围内)的点的个数超过给定的阈值$Minpts$,则该点为满足该条件下的核心点。
  • 边界点: 边界点落在某个核心点的邻域内,同时边界点可能落在多个核心点的邻域内。
  • 噪声点: 噪声点既非核心点,也不是边界点

2. SBSCAN算法步骤

<1> 将所有点标记为核心点、边界点或噪音点

<2> 删除噪音点

<3> 为距离在 $Eps$ 之内的所有核心点之间赋予一条边

<4> 每组联通的核心点形成一个簇

<5> 将每个边界点指派到一个与之关联的核心点的簇中

3. 时间和空间复杂度

  • 时间复杂度: $O(m 找出邻域中的点所需要的时间)$,在最坏的情况下时间复杂度为$O(m^2)$;当数据结构为 KD树,可以有效地检索特定点给顶距离内的所有点,时间复杂度降低到$O(mlog(m))$
  • 空间复杂度: $O(m)$,每个点只需维护少量数据,即簇标号和每个点是核心点、边界点还是噪音点的标示。

4. 选择 DBSCAN 参数

  • $k-$距离:如何选择 $Eps$ 和 $MinPts$ 参数,基本的方法是观察点到它的第 $k$ 个最近邻的距离。

    考虑下,如何 $k$ 不大于簇个数的话, $k-距离$ 相对较小,反之对于不咋簇中的点(噪音点或异常值)则$k距离$较大。因此对于参数的选取我们可以利用这点进行作图:先选取一个 $k$ (一般为4),计算所有点的$k-距离$,并递增排序,画出曲线图,则我们会看到$k-距离的变化$,并依照此图选择出合适的 $MinPts$ 参数,即对应拐点的位置。

5. 优点和缺点

  • 对噪声不敏感,而且能处理任意形状和大小的簇, DBSCAN 可以发现使用 K 均值不能发现的许多簇。
  • 当簇的密度变化太大时, DBSCAN 就会有麻烦。 对于高维数据也会有问题,因为对于这样的数据,密度定义更困难。最后,当邻近计算需要计算所有的点对邻近度时(对于高维数据,常常如此),DBSCAN 的开销可能是很大的。

五、簇评估

1. 簇评估的基本目标和度量

簇评估的一些重要问题包含:

  1. 确定数据集的聚类趋势,即识别数据中是否实际存在非随机结构
  2. 确定正确的簇个数
  3. 不引用附加的信息,评估聚类分析结果对数据的拟合情况
  4. 将聚类分析结果与已知客观结果相比较
  5. 比较两个簇集,确定哪个更好

用于评估簇的各方面的评估度量或指标一般分成如下三类:

  • 非监督的:非监督度量通常称为内部指标,仅使用出现在数据集中的信息。如 SSE
    • 凝聚性:度量簇中对象的密切关系,越大越好
    • 分离性:度量簇与簇之间的分离度,也是越大越好
  • 监督的:例如监督指标的 熵,它度量簇表好与外部提供标号的匹配程度。通常称为外部指标
  • 相对的:不是一种单独的簇评估度量类型,而是度量的一种具体使用。如使用 SSE 和 熵 对两个 K-means 聚类进行比较。

2.划分聚类的非监督簇评估

2.1 凝聚的和分离度

通常,将 K 个簇的集合的总体有效性表示为个体簇有效性的加权和:

$$overall_validity=∑^K_{i=1}w_i*validity(C_i)$$

其中,$validity$函数可以是凝聚度、分离度,或者这些量的组合。权值将因簇有效性的度量而异。在某些情况下,全职可以简单地取 1 或者簇的大小;而在其他情况下,他们反应更复杂的性质。如凝聚度的平方根。如果有效性函数是凝聚度,则值越高越好。如果是分离度,则簇与簇之间越大越好;簇中点越小越好。

凝聚度和分离度是分两种情况下考虑的,一个是基于图的观点。

基于图的观点:

该情况下度量的取值需要簇中所有的点加入运算求出平均距离或者总距离来对凝聚程度和分离程度作出度量。(一个簇的话是计算簇内两两之间距离,两个簇的话计算其中一个簇内每个点到另一个簇内所有点的距离,因此这种情况下计算量往往比较大)
$$基于图的凝聚度SSE=\frac 1{2m}∑_{x\in C_i}∑_{y\in C_i}dist(x,y)^2$$
$$基于原型的凝聚度SSE= ∑_{x\in C_i}dist(c_i,x)^2$$
基于原型的观点:

这个比较好理解,就是取每个簇的质心(或中心点)作为该簇的代表。簇内凝聚度计算的是簇内每个点到质心的距离;分离性度量的是每个簇质心到总体质心的距离或者每个簇两两之间质心的距离。

$$总分离度 SSB=∑_{i=1}^Km_idist(c_i,c)^2=\frac 1{2K}∑^K_{i=1}∑^K_{j=1}\frac mKdist(c_i,c_j)^2$$
其中 $c_i$ 是第 $i$ 个簇的均值,$c$ 是总均值。总 $SSB$ 越高,簇之间的分离性越好。

凝聚度和分离度之间的关系:

可以证明总 $SSE$ 和总 $SSB$ 之和是一个常数,它等于总平方和($TSS$,即每个点到总体数据均值距离的平方和):

$$TSS=SSE+SSB$$
因此,最小化SSW(凝聚度)等价于最大化SSB(分离度)

2.2 轮廓系数

流行的轮廓系数方法结合了凝聚度和分离度,该方法分三部分组成:

<1> 对于第 $i$ 个对象,计算它到簇中所有其他对象的平均距离,记作$a_i$。

<2> 对于第 $i$ 个对象和不包含该对象的任意簇,计算该对象到给定簇中所有对象的平均距离。关于所有的簇,找出最小值,记作 $b_i$。

<3> 对于第 $i$ 个对象,轮廓系数是 $s_i=\frac {(b_i-a_i)}{max(a_i,b_i)}$。

轮廓系数取值在 -1 到 1 之间变化,但我们不希望取负值因为负值代表着簇中平均距离大于到其他簇的最小平均距离是不合理的。我们希望的是 $b_i>a_i即上面的max(a_i,b_i)=b_i$,并且 $a_i$ 越接近 0 越好,因为当 $a_i=0$ 时轮廓系数取其最大值1。

我们可以简单地取簇中点的轮廓系数取平均值,计算簇的平均轮廓系数。通过计算所有点的平均轮廓系数,可以得到聚类优良性的总度量。

2.3 邻近度矩阵

数据挖掘导论参考

3. 层次聚类的非监督度量

共性分类距离:凝聚层次聚类技术首次将对象放在同一个簇时的邻近度。即,如果在凝聚层次聚类进行的某个时刻,两个合并的簇之间的最小距离时 0.1,则其中一个簇中的所有点关于另一个簇中各点的共性分类距离都是 0.1。

共性相关系数:是该矩阵与原来的相异度矩阵的项之间的相关度,是(特定类型的)层次聚类对数据拟合程度的标准度量。该度量最常见的应用是评估对于特定的数据类型,那种类型的层次聚类最好。

霍普金斯(Hopkins)统计量

对于该方法度量的是聚类趋势。我们随机产生 p 个随机分布在数据空间上的点,并且也抽取 p 个世纪数据点。 对于这两个点集没我们找出每个点到原数据集的最近邻距离。 设 $u_i$是人工产生的点的最近邻距离,$w_i$是样本点到源数据集的最近邻距离。则 Hopkins 统计量:
$$H=\frac {∑^p_{i=1}w_i}{∑^p_{i=1}u_i+∑^p_{i=1}w_i} $$

如果随机产生的点与样本点具有大致相同的最近邻距离,则 $H$ 将在 0.5 左右。$H$ 越接近 0 或者 1 分别表明数据是高度聚类的和数据在数据空间是有规律分布的。

簇有效性面向分类的度量

  • :每个簇由单个累的对象组成的程度。对于每个簇,首先计算数据的类分布,即对于簇 $i$,计算成员属于类 $j$ 的概率 $P_{ij}=m_{ij}/m_i$,其中$m_i$是簇 $i$ 中对象的个数,而 $m_{ij}$是簇 $i$ 中类 $j$ 的对象个数。使用类分布,用标准公式 $e_i=-∑^L_{j-1}P_{ij}log_2P_{ij}$ 计算每个簇的熵。 其中$L$是类的个数。 簇集合的总熵用每个簇的熵的加权和计算,即$e=∑^K_{i=1}\frac {m_i}{m}e_i$,其中$K$是簇的个数,而$m$是数据点的总数。
  • 纯度:簇包含单个累的对象的另一种度量程序。使用前面的属于,簇 $i$ 的纯度是 $P_i=\max_j P_{ij}$,而聚类的总纯度是$purity=∑^K_{i=1}=\frac {m_i}mPi$
  • 精度:簇中一个特定的对象所占的比例。簇$i$关于类$j$的精度是$precision(i,j)=P_{ij}$
  • 召回率:簇包含一个特地昂累的所有对象的程度。簇$i$关于类的召回率是$recall(i,j)=m_{ij}/m_j$,其中$m_j$是类$j$的对象个数。
  • F度量:精度和召回率的组合,度量在多大程度上,簇只包含一个特定类型累的对象和包含该累的所有对象。簇 $i$关于类$j$的$F$度量是$F(i,j)=2 \frac{精度*召回率}{精度+召回率}$

《未完待续…》

参考文献: