本文主要是介绍聚类有效性检验(Hubert'Γ ),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
问题的提出
假设现在有N个样本需要聚类,根据某个聚类算法我们把这N个样本聚为K个簇,现在问题是怎么确定现在的聚类结果是有意义的,而不是仅仅通过随机得到的。下面我们将构造Hubert’Γ 统计量,通过假设检验的方法来解决这一问题。以下内容大部分出至Jain和Dubes的聚类教程《Algorithms for Clustering Data》。部分理解可能有误,欢迎指出错误。
所需用到的定义
在具体论述之前,我先直接给定义,具体说明放在后面。
先定义两个N*N大小的矩阵X和Y。
X(i,j) 表示样本i和样本j的距离,是对称阵。
Y(i,j) 的定义如下:
接下来根据上面2个矩阵构造Γ统计量
未标准化前:
标准化的Γ统计量:
其中
所有的累加是在 {(i,j):1≤i≤n−1,i≤j≤n} 上进行的,M是矩阵右上角元素的个数(不包括对角线上的元素), mx,s2x 分别是矩阵X右上角元素的均值和标准差,同样的 my,s2y 分别是矩阵Y右上角元素的均值和标准差。
基于一个实例的解释
我们从一个具体的例子出发,假设我们要对4个样本 (x1.x2,x3,x4) 进行聚类,
现在根据某个聚类算法(比如k-means)得到如下的结果: x1 和 x3 被划分成一个簇,而 x2 和 x4 被划分被另一个簇。
我们的目的是想要知道这样的一个划分到达好不好,但聚类不同于有监督的学习,并没有一个标签来评判好坏。我们想要知道这个划分有多不寻常(unusualness),换句话说它与完全无意义的随机划分有多大的差别,因此我们需要构造前面定义过的Hubert’Γ 统计量来进行假设检验。
要搞清楚Γ统计量的意义,首先得清楚矩阵X和Y的意义。
原书中提到X和Y可以有多种定义,为方便理解,我只讲最常见的一种。
矩阵X
首先X是这4个样本两两之间的距离,比如说最常用的欧式距离,很明显X是一个对称阵,对角线上的元素为0(这个很好理解,自己和自己距离为0)。
假设在本例中
矩阵Y
从上面描述的Y的定义可以看出,Y的元素和聚类的结果有关
Y(i,j)=0 表示样本 i 和
Y(i,j)=1 表示样本 i 和
Y反应的聚类的情况。根据上面的例子Y矩阵如下:
Γ统计量
在计算出矩阵X和Y后可由(2)式或(3)式得到统计量Γ的值,其实你会发现Γ的值就是矩阵X和Y右上角对应元素乘积的和,Γ越大意味着这两个矩阵相互之间更吻合。如果采用式(3)得到的Γ的区间为(-1,1)。
本例中根据式(2)得到: Γ=1.2+0.2+0.3+0.1=1.8
现在的问题是,我们想知道1.8是一个很不同寻常的值吗,如果这个聚类算法仅仅是随机进行聚类(瞎猜的),那么得到Γ=1.8的概率有多大。
现在要做的就是改变式(10)的横轴(和纵轴)的顺序,从而得到不同的Γ值
要知道式(10)是按排列 (x1.x2,x3,x4) 得到的,4个样本的排列数为4!=24
例如当排列为 (x2,x4,x1,x3) 时:
Γ(2,4,1,3) = 0.6+0.2+0.3+0.4=1.5
24种排列的Γ的值的分布如下表:
Γ的值 | 1.5 | 1.8 | 2.3 |
---|---|---|---|
频数 | 8 | 8 | 8 |
在知道了Γ的具体分布之后,就可以进行假设检验了
原假设H0:算法得到的Γ值只是Y随机排列的结果
我们发现Γ=1.8的概率为1/3, 也就是说瞎猜也有1/3的概率得到1.8的值,拒绝原假设的把握只有2/3,因此我们有理由任认为这个聚类算法其实没有任何意义。
当样本个数N取很大的值时该怎么办?
当N=4的时候,排列数为24,我们还可以算出每个Γ的值。但随着N的增长,其排列数呈指数增长, 8!=40320 ,N取12是时,其排列数超过了4亿。显然不可能计算出每种可能的Γ值,因此我们需要近似和估计统计量Γ的分布。
一种方法是对Γ的值进行随机抽样,比如抽取100个不同排列下的Γ值,先设置好不同的区间,统计落入不同区间的Γ的个数,然后画出直方图,这样就可以近似Γ的真实分布。当我们使用某种算法得到一个Γ值时,将其比较与其他100个点进行比较。
如果这个算法真的有效,那么统计量Γ的值应该足够大,比大多数随机得到的Γ[i]都要大,这样才能有足够把我拒绝原假设。
一种情况是如果随机模拟了100个Y,得到100个Γ[i],真正聚类得到的Γ只比42个Γ[i]大,那么拒绝原假设的把握只有0.42,因此有理由怀疑这个聚类没有任何意义。
另一种情况是真正聚类得到的Γ比所有的Γ[i]都要大很多,那么我们就有充分的理由拒绝原假设,认为聚类的结果是有意义的,至于有什么意义,还需要进一步研究。
http://blog.csdn.net/tyh70537/article/details/75451836
http://blog.csdn.net/tyh70537/article/details/75309042
这篇关于聚类有效性检验(Hubert'Γ )的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!