简介
聚类分析又称群分析,是对多个样本(或指标)进行定量分类的一种多元统计分析方法。
系统聚类法:每一步都要计算类的距离,计算量大、占内存
动态快速聚类法
本节只记录系统聚类法
一个能产生高质量聚类的算法必须满足下面两个条件:
聚类质量的高低通常取决于聚类算法所使用的相似性测量的方法和实现方式,同时也取决于该算法能否发现部分或全部隐藏的模式。
簇的凝聚度可以定义为连接簇内心的邻近度图中边的加权和。
两个簇的分离度可以用从一个簇的点到另一个簇的点的边的加权和来度量。
根据凝聚度和分离度可以求出聚类的轮廓系数,使用轮廓系数来评估聚类结果。
划分方法首先根据给定要构建划分的数目k创建一个初始划分,然后采用一种迭代的重定位技术,尝试通过对象在划分间移动来改进划分。一个好的划分的一般准则是:在同一类中的对象之间尽可能“接近”或相关,而不同类中的对象之间尽可能“远离”或不同。为了达到全局最优,基于划分的聚类会要求穷举所有可能的划分。实际上,绝大多数应用采用了以下两个比较流行的启发式方法:(a)K-平均(K-MEANS)算法,在该算法中,每个簇用该簇中对象的平均值来表示。(b)K-中心点(K-MEDOIDS)算法,在该算法中,每个簇用接近聚类中心的一个对象来表示。
xK-means算法首先随机选择k个对象,每个对象代表一个聚类的质心。对于其余的每一个对象,根据该对象与各聚类质心之间的距离,把它分配到与之最相似的聚类中。然后,计算每个聚类的新质心。重复上述过程,直到准则函数会聚。通常采用的准则函数是平方误差准则函数。
该算法具有很好的可伸缩性,其计算复杂度为O(nkt),其中,t是循环的次数。K-means聚类算法的不足之处在于它要多次扫描数据库,此外,它只能找出球形的类,而不能发现任意形状的类。还有,初始质心的选择对聚类结果有较大的影响,该算法对噪声很敏感。
xxxxxxxxxx
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确定结果簇的个数,并且不适合于发现非凸面形状的簇,或者大小差别很大的簇,所以这些启发式聚类方法对在中小规模的数据库中发现球状簇很适用。为了对大规模的数据集进行聚类,以及处理复杂形状的聚类,基于划分的方法需要进一步的扩展。
xxxxxxxxxx
层次方法对给定数据对象集合进行层次的分解。根据层次的分解如何形成,层次的方法可以分为凝聚的和分裂的[30]。凝聚的方法,也称为自底向上的方法,一开始将每个对象作为单独的一个组,然后相继地合并相近的对象或组,直到所有的组合并为一个(层次的最上层),或者达到一个终止条件。分裂的方法,也称为自顶向下的方法,一开始将所有的对象置于一个簇中,在迭代的每一步中,一个簇被分裂为更小的簇,直到最终每个对象在单独的一个簇中,或者达到一个终止条件。
BIRCH算法
xxxxxxxxxx
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(Clustering Using Representative)算法选择基于质心和基于代表对象方法之间的中间策略。它不用单个质心或对象来代表一个簇,而是选择数据空间中固定数目的具有代表性的点。针对大型数据库,CURE采用随机取样和划分两种方法的组合:一个随机样本首先被划分,每个划分再被部分聚类。
CURE算法不能处理枚举型数据,而ROCK算法是在CURE基础之上适用于枚举数据的聚结分层聚类算法。通过把两个聚类的聚集相互连接度(aggregate interconnectivity)与用户定义的静态相互连接模型相比较,从而度量两个聚类之间的相似度。其中,两个聚类的相互连接度是指两个聚类之间的交叉连接数目,而连接link(pi,pj)是指这两点之间的共同邻居数。换句话说,聚类相似度是用不同聚类中又共同邻居的点的数目来确定的。
ROCK算法首先用相似度阀值和共同邻居的概念,从给定的数据相似度矩阵中构建一个稀疏图,然后对该稀疏图使用分层聚类算法进行聚类。
Chameleon(变色龙)是一个利用动态模型的层次聚类算法。算法思想是:首先通过一个图划分算法将数据对象聚类为大量相对较小的子聚类,然后用一个凝聚的层次聚类算法通过反复地合并子类来找到真正的结果簇。它既考虑了互连性,又考虑了簇间的近似度,特别是簇内部的特征,来确定最相似的子簇。
Chameleon跟CURE和DBSCAN相比,在发现高质量的任意形状的聚类方面有更强的能力。但是,在最坏的情况下,高维数据的处理代价可能对n个对象需要O(n^2) 的时间。
总的来说,层次的方法的缺陷在于,一旦一个步骤(合并或分裂)完成,它就不能被撤消,该技术的一个主要问题是它不能更正错误的决定。有两种方法可以改进层次聚类的结果:
算法名称 | 可伸缩性 | 适合的数据类型 | 高维性 | 异常数据的抗干扰性 | 聚类形状 | 算法效率 |
---|---|---|---|---|---|---|
WaveCluster | 很高 | 数值型 | 很高 | 较高 | 任意形状 | 很高 |
ROCK | 很高 | 混合型 | 很高 | 很高 | 任意形状 | 一般 |
BIRCH | 较高 | 数值型 | 较低 | 较低 | 球形 | 很高 |
CURE | 较高 | 数值型 | 一般 | 很高 | 任意形状 | 较高 |
K-Prototypes | 一般 | 混合型 | 较低 | 较低 | 任意形状 | 一般 |
DENCLUE | 较低 | 数值型 | 较高 | 一般 | 任意形状 | 较高 |
OptiGrid | 一般 | 数值型 | 较高 | 一般 | 任意形状 | 一般 |
CLIQUE | 较高 | 数值型 | 较高 | 较高 | 任意形状 | 较低 |
DBSCAN | 一般 | 数值型 | 较低 | 较高 | 任意形状 | 一般 |
CLARANS | 较低 | 数值型 | 较低 | 较高 | 球形 | 较低 |
在闵式(Minkowski)距离中,最常用的是欧几里得距离,其主要优点:
在对变量进行聚类分析时,首先要确定变量的相似性度量,常用的变量相似性度量有两种。
使用方法: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)包含了相应的在类中的两两对象间的连接距离。
使用方法:T = cluster(Z, ‘cutoff’, c)
表示将由linkage产生的信息矩阵Z分成c类,其中:
调用格式:T=clusterdata(X,…)
说明:根据数据创建分类。
T=clusterdata(X,cutoff)与下面的一组命令等价:
xxxxxxxxxx
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提供了5个聚类过程,即cluster,fastclus,modeclus、varclus和tree过程。
xxxxxxxxxx
proc cluster data = 数据集 <可选项>;
var 变量列表;
id 变量;
freq 变量;
copy 变量列表;
rmsstd 变量;
by 变量列表;
说明
可选项
xxxxxxxxxx
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;
参考