简介
- 聚类分析又称群分析，是对多个样本（或指标）进行定量分类的一种多元统计分析方法。
- 系统聚类法：每一步都要计算类的距离，计算量大、占内存
- ==Q型聚类==分析：对样本进行分类
- ==R型聚类==分析： 对指标进行分类
- 动态快速聚类法
本节只记录系统聚类法
聚类的评估
- 一个能产生高质量聚类的算法必须满足下面两个条件:
- 类内(intra-class)数据或对象的相似性最强；
- 类间(inter-class)数据或对象的相似性最弱。
- 聚类质量的高低通常取决于聚类算法所使用的相似性测量的方法和实现方式，同时也取决于该算法能否发现部分或全部隐藏的模式。
- 簇的凝聚度可以定义为连接簇内心的邻近度图中边的加权和。
- 两个簇的分离度可以用从一个簇的点到另一个簇的点的边的加权和来度量。
- 根据凝聚度和分离度可以求出聚类的轮廓系数，使用轮廓系数来评估聚类结果。
常见的聚类算法
- 聚类方法主要分为划分聚类、层次聚类、基于密度的聚类、基于网格的聚类和基于模型的聚类。
划分方法（partitioning method）
划分方法首先根据给定要构建划分的数目k创建一个初始划分，然后采用一种迭代的重定位技术，尝试通过对象在划分间移动来改进划分。一个好的划分的一般准则是：在同一类中的对象之间尽可能“接近”或相关，而不同类中的对象之间尽可能“远离”或不同。为了达到全局最优，基于划分的聚类会要求穷举所有可能的划分。实际上，绝大多数应用采用了以下两个比较流行的启发式方法：（a）K-平均（K-MEANS）算法，在该算法中，每个簇用该簇中对象的平均值来表示。（b）K-中心点（K-MEDOIDS）算法，在该算法中，每个簇用接近聚类中心的一个对象来表示。
K-means算法
K-means算法首先随机选择k个对象，每个对象代表一个聚类的质心。对于其余的每一个对象，根据该对象与各聚类质心之间的距离，把它分配到与之最相似的聚类中。然后，计算每个聚类的新质心。重复上述过程，直到准则函数会聚。通常采用的准则函数是平方误差准则函数。
该算法具有很好的可伸缩性，其计算复杂度为O(nkt)，其中，t是循环的次数。K-means聚类算法的不足之处在于它要多次扫描数据库，此外，它只能找出球形的类，而不能发现任意形状的类。还有，初始质心的选择对聚类结果有较大的影响，该算法对噪声很敏感。
K-medoids算法
K-medoids算法的过程和上述k-means的算法过程相似，唯一不同之处是：k-medoids算法用类中最靠近中心的一个对象来代表该聚类，而k-means算法用质心来代表聚类。在k-means算法中，对噪声非常敏感，因为一个极大的值会对质心的计算带来很大的影响。而k-medoid算法中，通过用中心来代替质心，可以有效地消除该影响。
K-medoids算法首先随机选择k个对象，每个对象代表一个聚类，把其余的对象分别分配给最相似的聚类。然后，尝试把每个中心分别用其他非中心来代替，检查聚类的质量是否有所提高。若是，则保留该替换。重复上述过程，直到不再发生变化。
常见的k-medoids算法有
PAM(Partitioning Around Medoids)算法、
CLARA(Clustering LARge Application)算法、
CLARANS(Clustering LARge Application based upon Randomized Search)算法。
当存在“噪声”和孤立点数据时，k-medoids算法比可k-means更健壮，这是因为中心点不像平均值那么容易被极端数据影响。但是，k-medoids算法的执行代价比k-means高。
总之，划分方法具有线性复杂度，聚类的效率高的优点。然而，由于它要求输入数字k确定结果簇的个数，并且不适合于发现非凸面形状的簇，或者大小差别很大的簇，所以这些启发式聚类方法对在中小规模的数据库中发现球状簇很适用。为了对大规模的数据集进行聚类，以及处理复杂形状的聚类，基于划分的方法需要进一步的扩展。
层次方法（hierarchical method）
层次方法对给定数据对象集合进行层次的分解。根据层次的分解如何形成，层次的方法可以分为凝聚的和分裂的[30]。凝聚的方法，也称为自底向上的方法，一开始将每个对象作为单独的一个组，然后相继地合并相近的对象或组，直到所有的组合并为一个（层次的最上层），或者达到一个终止条件。分裂的方法，也称为自顶向下的方法，一开始将所有的对象置于一个簇中，在迭代的每一步中，一个簇被分裂为更小的簇，直到最终每个对象在单独的一个簇中，或者达到一个终止条件。
- 主要的凝聚聚类算法有CURE,CHAMELEON,BIRCH,ROCK等。
BIRCH算法
BIRCH(Balanced Iterative Reducing and Clustering using Hierarchies)算法使用了一种叫做CF-树(聚类特征树，即Clustering Feature Tree)的分层数据结构，来对数据点进行动态、增量式聚类。
CF-树是存储了层次聚类过程中的聚类特征信息的一个加权平衡树，树中每个节点代表一个子聚类，并保持有一个聚类特征向量CF。
每个聚类特征向量是一个三元组，存储了一个聚类的统计信息。聚类特征向量中包含了一个聚类的三个统计信息：数据点的数目N，这N个数据点的线性和，以及这N个数据点的平方和SS。
一个聚类特征树是用于存储聚类特征CF的平衡树，它有两个参数：每个节点的最大子节点数和每个子聚类的最大直径。
当新数据插入时，就动态地构建该树。与空间索引相似，它也用于把新数据加入到正确的聚类当中。
BIRCH算法的主要目标是使I/0时间尽可能小，原因在于大型数据集通常不能完全装入内存中。
BIRCH算法通过把聚类分为两个阶段来达到此目的。首先通过构建CF-树对原数据集进行预聚类，然后在前面预聚类的基础上进行聚类。
CURE算法
CURE(Clustering Using Representative)算法选择基于质心和基于代表对象方法之间的中间策略。它不用单个质心或对象来代表一个簇，而是选择数据空间中固定数目的具有代表性的点。针对大型数据库，CURE采用随机取样和划分两种方法的组合：一个随机样本首先被划分，每个划分再被部分聚类。
ROCK算法
CURE算法不能处理枚举型数据，而ROCK算法是在CURE基础之上适用于枚举数据的聚结分层聚类算法。通过把两个聚类的聚集相互连接度(aggregate interconnectivity)与用户定义的静态相互连接模型相比较，从而度量两个聚类之间的相似度。其中，两个聚类的相互连接度是指两个聚类之间的交叉连接数目，而连接link(pi,pj)是指这两点之间的共同邻居数。换句话说，聚类相似度是用不同聚类中又共同邻居的点的数目来确定的。
ROCK算法首先用相似度阀值和共同邻居的概念，从给定的数据相似度矩阵中构建一个稀疏图，然后对该稀疏图使用分层聚类算法进行聚类。
Chameleon算法
Chameleon（变色龙）是一个利用动态模型的层次聚类算法。算法思想是：首先通过一个图划分算法将数据对象聚类为大量相对较小的子聚类，然后用一个凝聚的层次聚类算法通过反复地合并子类来找到真正的结果簇。它既考虑了互连性，又考虑了簇间的近似度，特别是簇内部的特征，来确定最相似的子簇。
Chameleon跟CURE和DBSCAN相比，在发现高质量的任意形状的聚类方面有更强的能力。但是，在最坏的情况下，高维数据的处理代价可能对n个对象需要O(n^2)
的时间。
总的来说，==层次的方法的缺陷==在于，一旦一个步骤（合并或分裂）完成，它就不能被撤消，该技术的一个主要问题是它不能更正错误的决定。有两种方法可以改进层次聚类的结果：
- （a）在每层划分中，仔细分析对象间的“联接”，例如CURE中的做法。
- （b）综合层次凝聚和迭代的重定位方法。首先用自底向上的层次算法，然后用迭代的重定位来改进结果。
算法总结
| 算法名称 | 可伸缩性 | 适合的数据类型 | 高维性 | 异常数据的抗干扰性 | 聚类形状 | 算法效率 |
|---|---|---|---|---|---|---|
| WaveCluster | 很高 | 数值型 | 很高 | 较高 | 任意形状 | 很高 |
| ROCK | 很高 | 混合型 | 很高 | 很高 | 任意形状 | 一般 |
| BIRCH | 较高 | 数值型 | 较低 | 较低 | 球形 | 很高 |
| CURE | 较高 | 数值型 | 一般 | 很高 | 任意形状 | 较高 |
| K-Prototypes | 一般 | 混合型 | 较低 | 较低 | 任意形状 | 一般 |
| DENCLUE | 较低 | 数值型 | 较高 | 一般 | 任意形状 | 较高 |
| OptiGrid | 一般 | 数值型 | 较高 | 一般 | 任意形状 | 一般 |
| CLIQUE | 较高 | 数值型 | 较高 | 较高 | 任意形状 | 较低 |
| DBSCAN | 一般 | 数值型 | 较低 | 较高 | 任意形状 | 一般 |
| CLARANS | 较低 | 数值型 | 较低 | 较高 | 球形 | 较低 |
Q型聚类分析
样本的相似性度量
- 要用数量化的方法对事物进行分类，就必须用数量化的方法描述事物间的相识程度。
- 一个事物常常需要多个变量来刻画。
- 如果对于一群有待分类的样本点需要用p个变量描述，则每个样本点可以看出是 R^p^ 空间中的一个点。
- 因此，很自然地想到可以用==距离==来度量样本间的相识程度。
距离
- 1、闵式（Minkowski）距离
- 2、马氏距离
- 3、样本相关系数
- 4、夹角余弦
- 5、兰氏距离
闵式（Minkowski）距离（也称明考夫斯距离）
- 在聚类分析中，对于定量变量，最常用的是==闵式（Minkowski）距离==
- q=1时，称为绝对距离，常被称为==”城市街区“距离==，对路程的度量使用绝对值距离更好。
- q=2时，为欧式距离。
- q=无穷时，为切比雪夫距离。
优点
在==闵式（Minkowski）距离==中，最常用的是==欧几里得距离==，其主要优点：
- 当坐标轴进行正交旋转时，欧式距离保持不变
缺点
1、一定要采用相同量纲的变量。量纲不同时，首先进行数据的标准化处理，在进行计算距离
2、尽可能避免变量的多重相关性。多重相关性所造成的信息重叠，会片面强调某些变量的重要性
马氏距离
- 马氏距离对一切线性变换是不变的，故不受量纲的影响。
- 考虑了各个变量之间的相关性。
缺点
- 聚类过程中，类一直变化，使得类内的样本协方差矩阵（或联合协方差矩阵）难以确定。
- 在实际聚类分析中，马氏聚类不是理想的距离。
兰氏距离
- 当所有数据皆为正时，可以使用兰氏距离。
- 该距离与各变量的单位无关，适用于高度偏差或含异常值的数据。
类与类间的相似性度量
- 最短距离法：直观意义为两个类中最近两点间的距离。
- 最长距离法：直观意义为两个类中最远两点间的距离。
- 重心法
- 类平均法
- 中间距离法
- 离差平方和法（Ward方法）：对异常值敏感，在许多场合优于重心法。
R型聚类分析
- 在实际工作中，变量的聚类法的应用是很重要的。
- 人们常常希望能研究变量间的相似系数，按照变量的相似关系把它们聚成若干类，进而找出影响系统的主要因素。
变量相识性度量
- 在对变量进行聚类分析时，首先要确定变量的相似性度量，常用的变量相似性度量有两种。
- 相关系数，用的最多
- 夹角余弦
变量聚类法
- 采用与系统聚类法相同的思路和过程。最常用：最长聚类法、最短聚类法。
实现
matlab
函数介绍
pdist
- 成对观测值之间的两两距离 - MATLAB pdist - MathWorks 中国
- 可以传入自定义距离函数
linkage
使用方法：Z = linkage(Y, ‘method’)
表示使用由’method’指定的算法计算生成聚类树，其中：
输入矩阵Y为dist函数输出的（m - 1）* m / 2维距离行向量
下面是’method’常用的字符串：
字符串 含义 ‘single’ 最短距离（默认） ‘average’ 无权平均距离 ‘centroid’ 重心距离 ‘complete’ 最大距离 ‘median’ 赋权重心距离 ‘ward’ 离差平方和方法 ‘weighted’ 赋权平均距离
输出Z为包含聚类数信息的（m - 1）* 3矩阵。聚类树上的叶子节点为原始数据集中的对象，由 1 ~ m.对应于Z中第j行生成的新类索引为 m + j，其中m为初始叶节点的数量。
第一列和第二列，即Z(:, 1:2)包含了被两两连接生成一个新类的所有对象的索引。生成的新类索引为 m + j。共有m - 1个级别更高的类，它们对应于聚类树中的内部节点。
第三列Z(:, 3)包含了相应的在类中的两两对象间的连接距离。
cluster
- 使用方法：T = cluster(Z, ‘cutoff’, c)
- 表示将由linkage产生的信息矩阵Z分成c类，其中：
- Z为linkage函数生成的*( m − 1 ) × 3*矩阵
- c 表示分成类的数量
- T为长度为m 的列向量，其中每行对应着X中的行(样本)，T中数字相同的为同一类
zsore
- 对数据进行标准化
clusterdata
调用格式：T=clusterdata(X,…)
说明：根据数据创建分类。
T=clusterdata(X,cutoff)与下面的一组命令等价：
- Y=pdist(X,’euclid’);
- Z=linkage(Y,’single’);
- T=cluster(Z,cutoff);
squareform
- 将pdist的输出转化为方阵
dendrogarm
- 给聚类图打标签
cophenet
调用格式：c=cophenetic(Z,Y)
说明：利用pdist函数生成的Y和linkage函数生成的Z计算cophenet相关系数。
clear; clc; close all;
%%
S=['福冈';'合肥';'武汉';'长沙';'桂林';'温州';'成都'];
X=[
16.2 1492 2000 -8.2 6.2;
15.7 970 2209 -20.6 1.9;
16.3 1260 2085 -17.3 2.8;
17.2 1422 1726 -9.5 4.6;
18.8 1874 1709 -4.9 8.0;
17.9 1698 1848 -4.5 7.5;
16.3 976 1239 -4.6 5.6
];
D=pdist(X,'seuclid');
M=squareform(D);
Z=linkage(D,'centroid');
H=dendrogram(Z,'labels',S);
xlabel('City');
ylabel('Scale');
C=cophenet(Z,D);
T=cluster(Z,3);
效果
参考
SAS
- SAS提供了5个聚类过程，即cluster，fastclus，modeclus、varclus和tree过程。
- cluster为系统聚类过程，可使用十一种聚类方法进行谱系聚类，包括重心法、Ward离差平方和法和欧氏平均距离法等。
- fastclus为动态聚类过程，使用 K-均值算法寻找不相交的聚类，适宜于大样本分析，观察值可多达10万个。
- modeclus为动态聚类过程，使用非参数密度估计法寻找不相交的聚类。
- varclus过程可用于系统或动态聚类，通过斜交多组分量分析对变量作“谱系的”和“不相交的”两种聚类。
- cluster过程、fastclus过程和modeclus过程用于对样品聚类，varclus过程用于对变量聚类。tree过程将cluster或varclus过程的聚类结果画出树形结构图或谱系图。
CLUSTER过程步
基本语法
proc cluster data = 数据集 <可选项>;
var 变量列表;
id 变量;
freq 变量;
copy 变量列表;
rmsstd 变量;
by 变量列表;
- 说明
- 可选项
- outtree=输出数据集 供tree过程调用，用来输出聚类结果的树状图；
- ==method===算法 【ward（离差平方和法），average（类平均法），centroid（重心法），complete（最长距离法），single（最短距离法），median（中间距离法），density（密度法），flexible（可变类平均法），twostage（两阶段密度法），eml（最大似然法），mcquitty（相似分析法）】；
- ==standard/ std==——对变量实施标准化；
- ==nonorm==——阻止距离被正态化成均数为1或均方根为1；
- ==nosquare==——阻止过程在method=average/centroid/median/ward方法中距离数据被平方；
- mode=n——当合并两个类时，规定对被指定的众数类中的每个类至少有n个成员，该选项只能在method=density/twostage时使用；
- penalty=p——指定用于method=eml中的惩罚系数（p>0, 默认p=2）；
- trim=p——要求从分析中删去那些概率密度估计较小的点（0≤p<100, 被当作百分比），在method=ward/complete时，因为类可能被异常值严重地歪曲，最好使用这个选项（也可用于method= single）；
- dim=n——用于method=density/twostage时指定使用的维数（n≥1），若是坐标数据，缺省值为变量个数；若是距离数据，缺省值为1；
- hybrid——要求用Wong混合聚类方法，其中密度用k均值法的初始聚类分析中的均值计算得到。这个选项只能在method=density/ twostage时使用；
- k=n——指定k最近邻估计法中近邻的个数（2≤n<观察数）；
- r=n——指定均匀核密度估计法的支撑球半径（n>0）；
- notie——阻止cluster过程在聚类历史过程中检查每次产生的类间最小距离连结（ties）的情况，此选项可以减少过程执行的时间和空间；
- rsquare——输出R2和半偏R2；
- rmsstd——输出每一类的均方根标准差；
- ==ccc==——输出在均匀的原假设下判断聚类分成几类合适的立方聚类准则统计量ccc和近似期望值R2；同时输出选项rsquare有关的R2和半偏R2；此选项不适合于method=single（容易删掉分布的结尾部分）；
- ==pseudo==——输出伪F统计量(PSF)和伪t2统计量(PST2)，当分类数目不同时，它们有不同的取值；
- simple——输出简单统计数；
- 在输出报表中，可以根据输出的ccc、psf和pst2统计量确定多少分类数较合适，当ccc和psf值出现峰值所对应的分类数较合适，而pst2值是在出现峰值所对应的分类数减1较合适。
- copy语句——指定输入数据集中的一些变量拷贝到outtree=的输出数据集中；
- rmsstd语句——当输入数据集中的坐标数据代表类的均值时，定义表示均方根标准差变量，通常与freq语句中的变量配合使用。
libname kc "C:\Users\Axieyun\Desktop\多元统计分析SAS数据 - (学生)";
proc print data = kc.p214_6_6;
run;
proc cluster data = kc.p214_6_6 method = ward std out=tree ccc pseudo;
var x1-x8;
id nation;
run;
/*
proc tree data=tree horizontal; *绘制水平谱系图;
id nation;
run;
*/
proc tree data=tree noprint out=out ncl = 8;
copy x1-x8;
run;
quit;
data kc.di_wu_zuo_ye_1;
input x y;
cards;
1 1
2 2
6 3
8 4
11 5
;
run;
proc cluster data = kc.di_wu_zuo_ye_1 method = complete;
var x;
id y;
run;
参考
