kmeans 算法

基本步骤：

1、选择初始的k个类别中心u1u2……uk
2、对于每个样本，将其标记为距离类别中心最近的类别，即：

3、将每个类别中心更新为隶属该类别的所有样本的均值

4、重复最后两步，直到类别中心的变化小于某阈值

matlab代码

clc
clear
x=[0 0;1 0; 0 1; 1 1;2 1;1 2; 2 2;3 2; 6 6; 7 6; 8 6; 6 7; 7 7; 8 7; 9 7 ; 7 8; 8 8; 9 8; 8 9 ; 9 9];
z=zeros(2,2);
z1=zeros(2,2);
z=x(1:2, 1:2);
%% 寻找聚类中心
while 1
    count=zeros(2,1);
    allsum=zeros(2,2);
    for i=1:20 % 对每一个样本i，计算到2个聚类中心的距离
        temp1=sqrt((z(1,1)-x(i,1)).^2+(z(1,2)-x(i,2)).^2);
        temp2=sqrt((z(2,1)-x(i,1)).^2+(z(2,2)-x(i,2)).^2);
        if(temp1<temp2)
            count(1)=count(1)+1;
            allsum(1,1)=allsum(1,1)+x(i,1);
            allsum(1,2)=allsum(1,2)+x(i,2);
        else
            count(2)=count(2)+1;
            allsum(2,1)=allsum(2,1)+x(i,1);
            allsum(2,2)=allsum(2,2)+x(i,2); 
        end
    end
    z1(1,1)=allsum(1,1)/count(1);
    z1(1,2)=allsum(1,2)/count(1);
    z1(2,1)=allsum(2,1)/count(2)
    z1(2,2)=allsum(2,2)/count(2);
    if(z==z1)
        break;
    else
        z=z1;
    end
end
%% 结果显示
disp(z1);% 输出聚类中心
plot( x(:,1), x(:,2),'k*',...
    'LineWidth',2,...
    'MarkerSize',10,...
    'MarkerEdgeColor','k',...
    'MarkerFaceColor',[0.5,0.5,0.5])
hold on
plot(z1(:,1),z1(:,2),'ko',...
    'LineWidth',2,...
    'MarkerSize',10,...
    'MarkerEdgeColor','k',...
    'MarkerFaceColor',[0.5,0.5,0.5])
set(gca,'linewidth',2) ;
xlabel('特征x1','fontsize',12);
ylabel('特征x2', 'fontsize',12);
title('K-means分类图','fontsize',12);

评价指标1

记k个簇中心分别为u1,u2,u3……uk,每个簇的样本数目为N1、N2……Nk。
使用平方误差做为误差函数，得：

将该函数做为目标函数，求解该函数的最小值。可以使用梯度下降法求，该函数为凸函数，驻点为：

这解释了为什么每次在选择聚类中心的时候取的是该类所有坐标的平均值。

评价指标2 （轮廓系数）

disMean(out) 是该点到非本类点的平均距离，disMean(in) 是该点到本类点的平均距离。 -1<=s<=1 越接近于1说明分类越优秀。（说明了类间距离大 类内距离小）
要计算出每一个点对应的s，之后求取平均值。

详情参见：

https://blog.csdn.net/weixin_44344462/article/details/89337770

评价指标3（兰德指数）

评价指标4（互信息)

评价指标5（Compactness and Seperation)

Compactness:

Seperation:

评价指标6 Davies-Bouldin Index(戴维森堡丁指数)(分类适确性指标)(DB)

DB计算任意两类别的类内距离平均距离(CP)之和除以两聚类中心距离求最大值。DB越小意味着类内距离越小同时类间距离越大。该指标的计算公式：

评价指标7 （调和平均V-measure）

说V-measure之前要先介绍两个指标：
同质性(homogeneity)：每个群集只包含单个类的成员。完整性(completeness)：给定类的所有成员都分配给同一个群集。
同质性和完整性分数基于以下公式得出：

总结：不同的评价指标有不同的优缺点，主要根据的还是类内距离小，类间距离大的原则而设定。每一种指标的计算量也不尽相同，要视不同的情况选择不同的评价指标。

更多详情参见：

https://blog.csdn.net/weixin_36486455/article/details/112379886

概述

有ground-truth时
黄金标准（Gold Standard）作为Benchmark，是基于人工的判断制作而成。在有了这个Benchmark后，我们就可以定义出外部标准，通过簇和黄金标准之间类别的匹配的程度来评估聚类结果的好坏。
聚类质量四个外部标准：
1 纯度（Purity） 是一种简单而透明的评估手段；
2 标准化互信息（NMI, Normalized Mutual Information） 是从信息理论方面来评估；
3 兰德指数（RI, Rand Index） 能度量聚类过程中的假阳性和假阴性结果的惩罚；
4 F值（F measure） 支持调整这两种错误惩罚的权重。

没有ground-truth时
聚类前（聚类趋势）；聚类质量；交叉验证

纯度

每个簇中最大数量的类作为这个簇的类，数分对的和分错的。分的越好纯度越高
分对的点数 除以 总点数
簇数量很多时容易达到较高的纯度。因而不能简单用纯度衡量

兰德指数

算TP，FN除以总数，就是准确率accuracy

假阳性和假阴性有着同等的重要性。但是在实际情况中，把相似的文档分开比把不同的文档放在一个簇里更糟糕。我们可以使用F值，通过让参数 [公式] 来让假阴性比假阳性获得更多的惩罚，也就是说，给召回（Recall）更大的权重。

F值

β = 1 或 5 或其他

2.1聚类趋势： （聚类前）

霍普金斯统计量（Hopkins Statistic）评估给定数据集是否存在有意义的可聚类的非随机结构。聚类的前提需要数据是非均匀分布的。[0.01, 0.3]表示数据结构regularly spaced，该值为0.5时数据是均匀分布的，[0.7, 0.99]表示聚类趋势很强。

2.2聚类质量

2.3交叉验证

这个验证主要是针对kmeans等划分聚类方法。把给定的数据集D划分成m个部分。然后，使用m-1各部分建立一个聚类模型，并使用剩下的一部分检验聚类的质量。

2.4 聚类稳定性

聚类结果的稳定性越高，引入新的（来自相同underlying model）后再次聚类结果越不容易被改变。
比如：
某两组同分布的数据，k=2时聚类结果差别很大，k=5时差别不大，则5更稳定（不能只看这一项，因为k=1最稳定）

不同聚类算法的目标函数相差很大。 聚类没有统一的评价指标

1.定义：

聚类有效性指标（Cluster Validity Index，CVI）：用于度量聚类的效果。
详细介绍wiki：http://www.turingfinance.com/clustering-countries-real-gdp-growth-part2/#quality

2.聚类评估方法介绍

聚类具有随机性，聚类效果的好坏我们并没有办法去判断，这里面给出的聚类有效性指标，可以帮助我们在聚类一组数据后对其聚类效果进行度量，然后根据数据的实际意义做出判断。

聚类评估目前常用的方式有两大类：内部评估（internal）和外部评估（external），内部评估是汇总得到一个单独质量分数，外部评估是通过与公知标准作比较。当然，还有人工评估方法（专家），通过评估其在应用中的聚类效果的间接评估。

（一）内部评估

内部评估就是基于聚类数据评估聚类结果。
下面介绍几种可以用来评估聚类（kmeans算法）质量的内部准则：

Davies-Bouldin index(戴维森堡丁指数，简称DB或DBI)

计算公式：
$$DB=\frac{1}{n}\sum _{i=1}^n\underset{j\ne i}{\max }\left(\frac{{\sigma }_i+{\sigma }_j}{d(c_i,c_j)}\right)$$

公式含义：DB为任意两个类别的类内距离平均距离之和与两聚类质心间距之比的最大值

具体解析：

• 分子：簇内所有点到该簇质心点的平均距离之和
• 分母 $d(ci,cj)$：两类别质心间的距离
• max()最大值部分：选取每组比例中的最大值（即选取最糟糕的一组）
• 1/n求和部分：将所选比例加和除以类别数

结果意义：DB值越小表示聚类结果同簇内部紧密，不同簇分离较远。即类内距离越小，类间距离越大。

具体过程：

• step1：计算每个聚类d(A)，d(B)，d©的平均内部距离。
• step2：计算任意质心间的距离d(A,B)，d(A,C)和d(B,C)。
• step3：返回最大比例（任意内部聚类之和与其质心间距之比）

Dunn’s index(邓恩指数，简称DVI)

计算公式：
$$D=\frac{{\min }_{1\le i<j\le n}d(i,j)}{{\max }_{1\le k\le n}{d}^{\prime }(k)},$$

公式含义：任意两簇类间最短距离与任意簇的类内最大距离之比

结果意义：DVI值越大表明聚类结果同簇内部紧密，不同簇分离较远。即类间距离越大，类内距离越小。

Silhouette index（轮廓指数，简称SI）

计算公式：
s ( i ) = b ( i ) − a ( i ) max ⁡ { a ( i ) , b ( i ) } s(i) = \frac{b(i) - a(i)}{\max\{a(i),b(i)\}} s(i)=max{a(i),b(i)}b(i)−a(i)​
或者是
$$s(i)=\{\begin{array}{ll}1-a(i)/b(i),& \text{if }a(i)<b(i)\\ 0,& \text{if }a(i)=b(i)\\ b(i)/a(i)-1,& \text{if }a(i)>b(i)\end{array}$$

公式含义：它测量每个模式中自身簇中的模式与其他最近簇中的模式相比的相似程度。

具体解析：

• a(i) 表示从模式 i 到所有同一聚类中的每个模式的平均距离;
• b(i) 表示从模式 i 到其他聚类中最接近的那个聚类的每个模式的平均距离。

结果意义：SI值越高表示 i 与自身聚类匹配较好，与其他类匹配较差。即类内密集，类间疏散。

缺点：复杂度较大

参考

DBI的代码思路大家可参考：
https://gist.github.com/StuartGordonReid/7841ab6837e7e84476f3#file-clusteringobjectivefunctions-py
强烈推荐详细介绍聚类及质量评估等的参考文章：http://www.turingfinance.com/clustering-countries-real-gdp-growth-part2/#quality
剩下的外部评估之后再补上。