189 8069 5689
大数据分析之聚类算法
成都创新互联专注于郏县企业网站建设,自适应网站建设,商城网站制作。郏县网站建设公司,为郏县等地区提供建站服务。全流程定制网站建设，专业设计，全程项目跟踪，成都创新互联专业和态度为您提供的服务
1. 什么是聚类算法
所谓聚类，就是比如给定一些元素或者对象，分散存储在数据库中，然后根据我们感兴趣的对象属性，对其进行聚集，同类的对象之间相似度高，不同类之间差异较大。最大特点就是事先不确定类别。
这其中最经典的算法就是KMeans算法，这是最常用的聚类算法，主要思想是:在给定K值和K个初始类簇中心点的情况下，把每个点(亦即数据记录)分到离其最近的类簇中心点所代表的类簇中，所有点分配完毕之后，根据一个类簇内的所有点重新计算该类簇的中心点(取平均值)，然后再迭代的进行分配点和更新类簇中心点的步骤，直至类簇中心点的变化很小，或者达到指定的迭代次数。
KMeans算法本身思想比较简单，但是合理的确定K值和K个初始类簇中心点对于聚类效果的好坏有很大的影响。
聚类算法实现
假设对象集合为D，准备划分为k个簇。
基本算法步骤如下：
1、从D中随机取k个元素，作为k个簇的各自的中心。
2、分别计算剩下的元素到k个簇中心的相异度，将这些元素分别划归到相异度最低的簇。
3、根据聚类结果，重新计算k个簇各自的中心，计算方法是取簇中所有元素各自维度的算术平均数。
4、将D中全部元素按照新的中心重新聚类。
5、重复第4步，直到聚类结果不再变化。
6、将结果输出。
核心Java代码如下：
/**
* 迭代计算每个点到各个中心点的距离，选择最小距离将该点划入到合适的分组聚类中，反复进行，直到
* 分组不再变化或者各个中心点不再变化为止。
* @return
*/
public List[] comput() {
List[] results = new ArrayList[k];//为k个分组，分别定义一个聚簇集合，未来放入元素。
boolean centerchange = true;//该变量存储中心点是否发生变化
while (centerchange) {
iterCount++;//存储迭代次数
centerchange = false;
for (int i = 0; i k; i++) {
results[i] = new ArrayListT();
}
for (int i = 0; i players.size(); i++) {
T p = players.get(i);
double[] dists = new double[k];
for (int j = 0; j initPlayers.size(); j++) {
T initP = initPlayers.get(j);
/* 计算距离 这里采用的公式是两个对象相关属性的平方和，最后求开方*/
double dist = distance(initP, p);
dists[j] = dist;
}
int dist_index = computOrder(dists);//计算该点到各个质心的距离的最小值，获得下标
results[dist_index].add(p);//划分到对应的分组。
}
/*
* 将点聚类之后，重新寻找每个簇的新的中心点，根据每个点的关注属性的平均值确立新的质心。
*/
for (int i = 0; i k; i++) {
T player_new = findNewCenter(results[i]);
System.out.println("第"+iterCount+"次迭代，中心点是："+player_new.toString());
T player_old = initPlayers.get(i);
if (!IsPlayerEqual(player_new, player_old)) {
centerchange = true;
initPlayers.set(i, player_new);
}
}
}
return results;
}
上面代码是其中核心代码，我们根据对象集合List和提前设定的k个聚集,最终完成聚类。我们测试一下，假设要测试根据NBA球员的场均得分情况，进行得分高中低的聚集，很简单，高得分在一组，中等一组，低得分一组。
我们定义一个Player类，里面有属性goal，并录入数据。并设定分组数目为k=3。
测试代码如下:
List listPlayers = new ArrayList();
Player p1 = new Player();
p1.setName(“mrchi1”);
p1.setGoal(1);
p1.setAssists(8);
listPlayers.add(p1);
Player p2 = new Player();
p2.setName("mrchi2");
p2.setGoal(2);
listPlayers.add(p2);
Player p3 = new Player();
p3.setName("mrchi3");
p3.setGoal(3);
listPlayers.add(p3);
//其他对象定义此处略。制造几个球员的对象即可。
KmeansPlayer kmeans = new KmeansPlayer(listPlayers, 3);
ListPlayer[] results = kmeans.comput();
for (int i = 0; i results.length; i++) {
System.out.println("类别" + (i + 1) + "聚集了以下球员：");
ListPlayer list = results[i];
for (Player p : list) {
System.out.println(p.getName() + "---" + p.getGoal()
}
}
算法运行结果：
可以看出中心点经历了四次迭代变化，最终分类结果也确实是相近得分的分到了一组。当然这种算法有缺点，首先就是初始的k个中心点的确定非常重要，结果也有差异。可以选择彼此距离尽可能远的K个点，也可以先对数据用层次聚类算法进行聚类，得到K个簇之后，从每个类簇中选择一个点，该点可以是该类簇的中心点，或者是距离类簇中心点最近的那个点。
一、层次聚类
1）距离和相似系数
r语言中使用dist(x, method = "euclidean",diag = FALSE, upper = FALSE, p = 2) 来计算距离。其中x是样本矩阵或者数据框。method表示计算哪种距离。method的取值有：
euclidean 欧几里德距离，就是平方再开方。
maximum 切比雪夫距离
manhattan 绝对值距离
canberra Lance 距离
minkowski 明科夫斯基距离，使用时要指定p值
binary 定性变量距离.
定性变量距离： 记m个项目里面的 0:0配对数为m0 ,1:1配对数为m1，不能配对数为m2，距离=m1/(m1+m2);
diag 为TRUE的时候给出对角线上的距离。upper为TURE的时候给出上三角矩阵上的值。
r语言中使用scale(x, center = TRUE, scale = TRUE) 对数据矩阵做中心化和标准化变换。
如只中心化 scale(x,scale=F) ,
r语言中使用sweep(x, MARGIN, STATS, FUN="-", ...) 对矩阵进行运算。MARGIN为1，表示行的方向上进行运算，为2表示列的方向上运算。STATS是运算的参数。FUN为运算函数，默认是减法。下面利用sweep对矩阵x进行极差标准化变换
?
1
2
3
center -sweep(x, 2, apply(x, 2, mean)) #在列的方向上减去均值。
R -apply(x, 2, max) -apply(x,2,min) #算出极差，即列上的最大值-最小值
x_star -sweep(center, 2, R, "/") #把减去均值后的矩阵在列的方向上除以极差向量
?
1
2
3
center -sweep(x, 2, apply(x, 2, min)) #极差正规化变换
R -apply(x, 2, max) -apply(x,2,min)
x_star -sweep(center, 2, R, "/")
有时候我们不是对样本进行分类，而是对变量进行分类。这时候，我们不计算距离，而是计算变量间的相似系数。常用的有夹角和相关系数。
r语言计算两向量的夹角余弦：
?
1
2
y -scale(x, center =F, scale =T)/sqrt(nrow(x)-1)
C -t(y) %*%y
相关系数用cor函数
2）层次聚类法
层次聚类法。先计算样本之间的距离。每次将距离最近的点合并到同一个类。然后，再计算类与类之间的距离，将距离最近的类合并为一个大类。不停的合并，直到合成了一个类。其中类与类的距离的计算方法有：最短距离法，最长距离法，中间距离法，类平均法等。比如最短距离法，将类与类的距离定义为类与类之间样本的最段距离。。。
r语言中使用hclust(d, method = "complete", members=NULL) 来进行层次聚类。
其中d为距离矩阵。
method表示类的合并方法，有：
single 最短距离法
complete 最长距离法
median 中间距离法
mcquitty 相似法
average 类平均法
centroid 重心法
ward 离差平方和法
?
1
2
3
4
5
6
7
8
x -c(1,2,6,8,11) #试用一下
dim(x) -c(5,1)
d -dist(x)
hc1 -hclust(d,"single")
plot(hc1)
plot(hc1,hang=-1,type="tirangle") #hang小于0时，树将从底部画起。
#type = c("rectangle", "triangle"),默认树形图是方形的。另一个是三角形。
#horiz TRUE 表示竖着放，FALSE表示横着放。
?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
z -scan()
1: 1.0000.8460.8050.8590.4730.3980.3010.382
9: 0.8461.0000.8810.8260.3760.3260.2770.277
17: 0.8050.8811.0000.8010.3800.3190.2370.345
25: 0.8590.8260.8011.0000.4360.3290.3270.365
33: 0.4730.3760.3800.4361.0000.7620.7300.629
41: 0.3980.3260.3190.3290.7621.0000.5830.577
49: 0.3010.2770.2370.3270.7300.5831.0000.539
57: 0.3820.4150.3450.3650.6290.5770.5391.000
65:
Read 64items
names
[1] "shengao""shoubi""shangzhi""xiazhi""tizhong"
[6] "jingwei""xiongwei""xiongkuang"
r -matrix(z,nrow=8,dimnames=list(names,names))
d -as.dist(1-r)
hc -hclust(d)
plot(hc)
然后可以用rect.hclust(tree, k = NULL, which = NULL, x = NULL, h = NULL,border = 2, cluster = NULL)来确定类的个数。 tree就是求出来的对象。k为分类的个数，h为类间距离的阈值。border是画出来的颜色，用来分类的。
?
1
2
3
plot(hc)
rect.hclust(hc,k=2)
rect.hclust(hc,h=0.5)
result=cutree(model,k=3) 该函数可以用来提取每个样本的所属类别
二、动态聚类k-means
层次聚类，在类形成之后就不再改变。而且数据比较大的时候更占内存。
动态聚类，先抽几个点，把周围的点聚集起来。然后算每个类的重心或平均值什么的，以算出来的结果为分类点，不断的重复。直到分类的结果收敛为止。r语言中主要使用kmeans(x, centers, iter.max = 10, nstart = 1, algorithm =c("Hartigan-Wong", "Lloyd","Forgy", "MacQueen"))来进行聚类。centers是初始类的个数或者初始类的中心。iter.max是最大迭代次数。nstart是当centers是数字的时候，随机集合的个数。algorithm是算法，默认是第一个。
?
使用knn包进行Kmean聚类分析
将数据集进行备份，将列newiris$Species置为空，将此数据集作为测试数据集
newiris - iris
newiris$Species - NULL
在数据集newiris上运行Kmean聚类分析， 将聚类结果保存在kc中。在kmean函数中，将需要生成聚类数设置为3
(kc - kmeans(newiris, 3))
K-means clustering with 3 clusters of sizes 38, 50, 62: K-means算法产生了3个聚类，大小分别为38,50,62.
Cluster means: 每个聚类中各个列值生成的最终平均值
Sepal.Length Sepal.Width Petal.Length Petal.Width
1 5.006000 3.428000 1.462000 0.246000
2 5.901613 2.748387 4.393548 1.433871
3 6.850000 3.073684 5.742105 2.071053
Clustering vector: 每行记录所属的聚类（2代表属于第二个聚类，1代表属于第一个聚类，3代表属于第三个聚类）
[1] 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
[37] 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 3 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
[73] 2 2 2 2 2 3 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 3 2 3 3 3 3 2 3
[109] 3 3 3 3 3 2 2 3 3 3 3 2 3 2 3 2 3 3 2 2 3 3 3 3 3 2 3 3 3 3 2 3 3 3 2 3
[145] 3 3 2 3 3 2
Within cluster sum of squares by cluster: 每个聚类内部的距离平方和
[1] 15.15100 39.82097 23.87947
(between_SS / total_SS = 88.4 %) 组间的距离平方和占了整体距离平方和的的88.4%，也就是说各个聚类间的距离做到了最大
Available components: 运行kmeans函数返回的对象所包含的各个组成部分
[1] "cluster" "centers" "totss" "withinss"
[5] "tot.withinss" "betweenss" "size"
("cluster"是一个整数向量，用于表示记录所属的聚类
"centers"是一个矩阵，表示每聚类中各个变量的中心点
"totss"表示所生成聚类的总体距离平方和
"withinss"表示各个聚类组内的距离平方和
"tot.withinss"表示聚类组内的距离平方和总量
"betweenss"表示聚类组间的聚类平方和总量
"size"表示每个聚类组中成员的数量)
创建一个连续表,在三个聚类中分别统计各种花出现的次数
table(iris$Species, kc$cluster)
1 2 3
setosa 0 50 0
versicolor 2 0 48
virginica 36 0 14
根据最后的聚类结果画出散点图，数据为结果集中的列"Sepal.Length"和"Sepal.Width"，颜色为用1，2，3表示的缺省颜色
plot(newiris[c("Sepal.Length", "Sepal.Width")], col = kc$cluster)
在图上标出每个聚类的中心点
〉points(kc$centers[,c("Sepal.Length", "Sepal.Width")], col = 1:3, pch = 8, cex=2)
三、DBSCAN
动态聚类往往聚出来的类有点圆形或者椭圆形。基于密度扫描的算法能够解决这个问题。思路就是定一个距离半径，定最少有多少个点，然后把可以到达的点都连起来，判定为同类。在r中的实现
dbscan(data, eps, MinPts, scale, method, seeds, showplot, countmode)
其中eps是距离的半径，minpts是最少多少个点。 scale是否标准化（我猜) ,method 有三个值raw,dist,hybird,分别表示，数据是原始数据避免计算距离矩阵，数据就是距离矩阵，数据是原始数据但计算部分距离矩阵。showplot画不画图，0不画，1和2都画。countmode，可以填个向量，用来显示计算进度。用鸢尾花试一试
?
1
2
3
4
5
6
7
8
9
10
11
install.packages("fpc", dependencies=T)
library(fpc)
newiris -iris[1:4]
model -dbscan(newiris,1.5,5,scale=T,showplot=T,method="raw")# 画出来明显不对 把距离调小了一点
model -dbscan(newiris,0.5,5,scale=T,showplot=T,method="raw")
model #还是不太理想……
dbscan Pts=150MinPts=5eps=0.5
012
border 34518
seed 04053
total 344571
第一次迭代下,除了a4点,其他点都归为一类c1:(a1 a2 a3 a5);c2:(a4) 聚类中心：c1:(2,2);c2(5,4)（聚类中心的计算方式是平均类中所有点）
第二次迭代下,c1(a1 a2 a5);c2(a3 a4) 聚类中心c1:(4/3,5/3);c2(9/2 7/2)
第三次迭代下,c1(a1 a2 a5);c2(a3 a4) 聚类中心c1:(4/3,5/3);c2(9/2 7/2)结果已经稳定跳出循环
层次聚类方法对给定的数据集进行层次的分解，直到满足某种条件为止，传统的层次聚类算法主要分为两大类算法：
1、凝聚的层次聚类： AGNES算法 (AGglomerative NESting)==采用自底向上的策略。最初将每个对象作为一个簇，然后这些簇根据某些准则被一步一步合并，两个簇间的距离可以由这两个不同簇中距离最近的数据点的相似度来确定；聚类的合并过程反复进行直到所有的对象满足簇数目。
2、分裂的层次聚类： DIANA算法 (DIvisive ANALysis)==采用自顶向下的策略。首先将所有对象置于一个簇中，然后按照某种既定的规则逐渐细分为越来越小的簇(比如最大的欧式距离)，直到达到某个终结条件(簇数目或者簇距离达到阈值)；
1、简单，理解容易。
2、合并点/分裂点选择不太容易。
3、合并/分类的操作不能进行撤销。
4、大数据集不太适合。
5、执行效率较低O(t*n2)，t为迭代次数，n为样本点数。
两个聚簇中最近的两个样本之间的距离(single/word-linkage聚类法)。
最终得到模型容易形成链式结构。
两个聚簇中最远的两个样本的距离(complete-linkage聚类法)。
如果存在异常值，那么构建可能不太稳定。
两个聚簇中样本间两两距离的平均值(average-linkage聚类法)。
两个聚簇中样本间两两距离的中值(median-linkage聚类法)。
CF-Tree (Cluster Feature Tree)：每个节点是由三个聚类特征组成。这三个聚类特征构成一个三元组，用(N, LS, SS)来表示。
其中：
N 表示这个CF中包含的样本数量；
LS 表示这个CF中包含的样本点的向量和；
SS 表示这个CF中包含的样本点各个特征的平方和。
CF-Tree中父节点的某个CF值等于其指向的所有子节点CF值的总和。
CF-Tree 的几个关键超参数：
B： 每个内部节点最大的CF个数。
L： 每个叶节点最大的CF个数。
T： 新样本若被分到某一CF中，其到该CF中心的距离最大值。
CF-Tree构建步骤：
1、初始状态，CF树是空的，无任何样本。读入第一个样本x(a,b)，生成一个CF三元组，此处N=1，LS=(a,b)，SS=a2+b2，我们令其为CF1。
2、读入第二个样本，若到CF1的距离小于T，那么这个样本也归入CF1，更新三元组数据；如果大于T，则新划分出一个CF，这个样本作为CF2当中的首个样本，生成一个CF三元组。
注意：此时都是在节点内进行CF的建立，而非产生新的节点。
3、分裂：如果新数据进入该节点后，距离所有CF中心的距离都大于T，且Cf个数在生成新CF后大于B，则该节点需要进行划分。
4、找到该分支内各个CF之间的距离最大的两个CF，分别作为两个新叶子结点的CF，再计算剩余CF到这两个CF之间的距离，距离近的分到一个节点当中。
5、如果节点分裂过后叶子节点个数超过L，则该节点要进行分裂，分裂方式和上一步相同。
6、生成CF和分裂过程直至所有样本均进入CF树后停止。
BIRCH算法 (平衡迭代削减聚类法)：聚类特征使用3元组进行一个簇的相关信息，通过构建满足分枝因子和簇直径限制的 聚类特征树(CF-Tree) 来求聚类，聚类特征树其实是一个具有两个参数 分枝因子(B、L) 和 类直径(T) 的高度平衡树；分枝因子规定了树的每个节点的子女的最多个数，而类直径体现了对这一类点的距离范围；非叶子节点为它子女的最大特征值；聚类特征树的构建可以是动态过程的，可以随时根据数据对模型进行更新操作。对应生成的结果就是一个 簇(聚类特征 - CF) ；BIRCH算法的过程就是建立CF-Tree的过程。
优缺点：
1、适合大规模数据集，线性效率；
层次聚类算法 的复杂度为 OT(n2) ；
优化后的 BIRCH算法 构建聚类特征树(CF-Tree)的时间复杂度为 O(n) ；
2、只适合分布呈凸形或者球形的数据集、需要给定聚类个数和簇之间的相关参数；
CURE算法 (使用代表点的聚类法)：是一种 凝聚算法(AGNES) 。该算法先把每个数据点看成一类，然后合并距离最近的类直至类个数为所要求的个数为止。但是和AGNES算法的区别是： 取消了使用所有点或用中心点+距离来表示一个类 ，而是 从每个类中抽取固定数量、分布较好的点作为此类的代表点 ，并将这些 代表点(一般10个) 乘以一个适当的 收缩因子(一般设置0.2~0.7之间) ，使它们更加靠近类中心点。代表点的收缩特性可以调整模型可以匹配那些非球形的场景，而且收缩因子的使用可以减少噪音对聚类的影响。
代表点 不是原来的点，而是那些需要重新计算的点。
关于聚类分析的介绍，可参见本人之前的笔记： 聚类分析
案例一：世界银行样本数据集
创建世界银行的一个主要目标是对抗和消除贫困。在这个不断发展的世界中，世界银行持续的发展并精细地调整它的政策，已经帮助这个机构逐渐实现了消除贫困的目标。消除贫困的成果以下指标的改进衡量，这些指标包括健康、教育、卫生、基础设施以及其他需要用于改进穷人生活的服务。与此同时，发展成果必须保证以一种环保的、全社会的、经济可持续的方式达成。
准备工作
为了进行层次聚类，我们需要使用从世界银行收集的数据集。
第1步：收集和描述数据
该任务使用名为WBClust2013的数据集。该数据以标准格式存储在名为WBClust2013.csv的CSV格式的文件中。其有80行数据和14个变量。 点我获取数据
第一列Country为非数值型变量，其他列均为数值型变量。
第2步：探索数据
让我们探索数据并理解变量间的关系。我们通过导入名为WBClust2013.csv的CSV文件开始。存储数据到wbclust数据框中：
下一步输出wbclust数据框，head（）函数返回wbclust数据框。wbclust数据框作为一个输入参数传入：
结果如下：
第3步：转换数据
中心化变量和创建z值是两个常见的用于归一化数据的数据分析手段。上面提到的数值型变量需要创建z值。scale（）函数是一个通用的函数，其默认方法中心化并比例缩放一个数值化矩阵的列。数据框wbclust被传给该比例函数。只有数据框中数值化的变量会被缩放。结果存储在wbnorm数据框中。
结果如下：
所有的数据框都有rownames属性。rownames（）函数用来获取或设置矩阵类变量的行名或列名。数据框wbclust以及第一列被传递给rownames（）函数。
调用rownames（wbnorm）方法显示第一列的数值。结果如下：
第4步：训练并评估模型效果
下一步是训练模型。首先使用dist（）函数计算距离矩阵。使用特定的距离度量方法计算数据矩阵行间的距离。使用的距离度量可以是欧式距离、最大距离、曼哈顿距离、堪培拉距离、二进制距离，或闵可夫斯基距离。这里的距离度量使用欧式距离。使用欧式距离计算两个向量间的距离为sqrt（sum（（x_i-y_i）^2））。结果被存储在一个新的数据框dist1中。
下一步是使用Ward方法进行聚类。hclust（）函数对一组不同的n个对象进行聚类分析。第一阶段，每个对象被指派给它自己的簇。之后每个阶段，算法迭代聚合两个最相似的簇。这个过程不断持续直到只剩一个簇。hclust（）函数要求我们以距离矩阵的形式提供数据。dist1数据框被作为输入传入。默认使用全链接算法。此外还可以使用不同的聚集方法，包括ward.D、ward.D2、single、complete和average。
输入clust1命令可显示所使用的聚集方法，计算距离的方法，以及数据对象的数量。结果如下：
第5步：绘制模型
plot（）函数是一个通用的绘制R语言对象的函数。这里plot（）函数用来绘制系统树图：
结果如下：
rect.hclust（）函数强调不同的簇，并在系统树图的枝干处绘制长方形。系统树图首先在某个等级上被剪切，之后在选定的枝干上绘制长方形。
clust1对象以及需要形成的簇的数量作为输入变量传入函数。
结果如下：
cuts（）函数基于期望的簇数量或者切割高度将树中的元素切割到不同的簇中。这里，clust1对象以及需要形成的簇的数量作为输入变量传入函数。
结果如下：
得到每个簇的国家列表：
结果如下：