梳理 | 聚类分析

in 机器学习 Views: 7,775 s with 0 comment

说明

这篇文章主要是梳理聚类分析的基本算法以及步骤,每个步骤除了给出数学公式之外,还会附上R语言实现代码。
如果要跑以下的代码,你需要确保自己的电脑里安装有R环境以及这些包:cluster, NbClust, flexclust, fMultivar, ggplot2, rattle
所有引用的资料都在最底处References处。
【注意:此文目前还在更新中,所以你可以等这行字消失的时候再来阅读此文。】
(如果目前有疑问可以先在评论区里询问,我看到了会回复你哒~)

聚类分析是什么?

我们都知道,机器学习的算法通常被分为有监督、无监督、半监督等类型。

那么聚类就是在无监督任务里占据有很重要地位的一种算法,它这个算法的思路和它的名字一样,“物以类聚,人以群分”。
聚类分析通过将一组数据依照内在相似性划分为多个类别,这个类别称之为“簇”(cluster),将相似度高的样本聚在一起,相似度低的样本拆分开来,从而使得簇内数据相似度较大而簇间数据相似度较小,达到分类的目的。

因为实际工业环境中,大多数数据都是没有标签的,同时数据量巨大的话,也不可能采用人力的方法去打标签,因此虽然聚类的准确率比不上有监督的方法,但聚类在工业环境里还是占据了非常重要的地位。

聚类分析的典型步骤

聚类分析的典型步骤一般有以下几步:

  1. 选择合适的变量
  2. 数据归一化
  3. 寻找异常点
  4. 计算距离
  5. 选择聚类算法
  6. 获得一种或多种聚类方法
  7. 确定类的数目
  8. 获得最终的聚类解决方案
  9. 结果可视化
  10. 解读类
  11. 验证结果

我们通常说的聚类算法都聚集在了 第5步 选择聚类算法 上,因此如果你主要想看那部分的内容,可以直接用右边的导航栏快速跳过去。
那么下面从最初的步骤一点一点开始说起。

选择合适的变量

这一步主要就是特征选择了,虽然也是非常重要的步骤,但因为话题太大,以后有机会再单独提出来说吧。

缩放数据——即数据归一化

数据标准化(归一化)处理是数据挖掘的一项基础工作,不同评价指标往往具有不同的量纲和量纲单位,这样的情况会影响到数据分析的结果,为了消除指标之间的量纲影响,需要进行数据标准化处理,以解决数据指标之间的可比性。原始数据经过数据标准化处理后,各指标处于同一数量级,适合进行综合对比评价。主要有以下两种常用的方法

  1. min-max标准化(Min-Max Normalization)
    也称为离差标准化,是对原始数据的线性变换,使结果值映射到[0-1]之间。转换函数如下:

$$x^{*}=\frac{x-min}{max-min}$$
其中max为样本数据的最大值,min为样本数据的最小值。这种方法有个缺陷就是当有新数据加入时,可能导致max和min的变化,需要重新定义。
R代码:

df1 <- apply(mydata, 2, function(x){(x-min(x))/(max(x)-min(x))})
  1. Z-score标准化方法
    这种方法给予原始数据的均值(mean)和标准差(standard deviation)进行数据的标准化。经过处理的数据符合标准正态分布,即均值为0,标准差为1,转化函数为:

$$x^{*}=\frac{x-μ}{σ}$$
其中μ为所有样本数据的均值,σ为所有样本数据的标准差。
R代码:

df1 <- apply(mydata, 2, function(x){(x-mean(x))/sd(x)})
or
scale()
  1. 每个变量被其最大值相除
    $$x^{*}=\frac{x}{max}$$

R代码:

df1 <- apply(mydata, 2, function(x){x/max(x)})
  1. 该变量减去它的平均值并除以变量的平均绝对偏差(Mean Absolute Deviation)
    $$x^{*}=\frac{x-mean}{mad(x)}$$

R代码:

df1 <- apply(mydata, 2, function(x){(x-mean(x))/mad(x)})

寻找异常点

许多聚类方法对异常值是十分敏感的,它能扭曲我们得到的聚类方案,因此我们应该把异常点找出来并剔除掉。
方法:

  1. outliers包中函数来筛选和删除异常单变量离群点
  2. mvoutlier包中有能识别多元变量的离群点的函数
  3. 使用对异常值稳健的聚类方法,如 围绕中心点的划分。

计算距离

聚类算法的本质,其实就是不停计算样本之间的距离(相似度),然后把它们放到合群的位置上去。
因此距离计算是其中很基础但也很关键的一步。

这里给定样本$x_i=(x_{i1};x_{i2};...;x_{in};)$与$x_j=(x_{j1};x_{j2};...;x_{jn};)$

距离度量需满足的基本性质

常用的距离度量方法有:

  1. 闵可夫斯基距离(Minkowski distance)
    $$dist(x_i,x_j) = (\sum_{u=1}^n|x_{iu} - x_{ju}|^p)^{\frac{1}{p}}$$ (1)

对p≧1,式(1)显然满足四条基本性质准则。

  1. 欧几里得距离(Euclidean distance)(最常用)(即p=2的时候)
    通常作为连续型数据的距离度量。公式为:

$$dist(x_i,x_j) = \sqrt{\sum_{u=1}^n |x_{iu}-x_{ju}|^2}$$

  1. 曼哈顿距离(Manhattan distance)(即p=1的时候)
    $$dist(x_i,x_j) = \sum_{u=1}^n|x_{ip}-x_{jp}|$$
  2. 兰氏距离
  3. 非对称二元距离
  4. 最大距离

R代码

d <- dist(x, method=)   # 默认返回一个下三角矩阵
as.matrix(d)[1:4][1:4]  # 使用标准括号符号得到距离

(可在R console中使用?dist查看详细信息,method对应有几种常见的距离计算方法)

属性划分方式:

第一种划分方式——

第二种划分方式——

可采用闵可夫斯基距离来计算。

可采用VDM(Value Difference Metric)来计算
可以用的包:cluster包的daisy(),距离使用gower

VDM

令$m_{u,a}$表示在属性u上取值为a的样本数,$m_{u,a,i}$表示在第i个样本簇中在属性u上取值为a的样本数,k为样本簇数,则属性u上两个离散值a与b之间的VDM距离为
$$VDM_p(a,b) = \sum_1^k|\frac{m_{u,a,i}}{m_{u,a})}-\frac{m_{u,b,i}}{m_{u,b}}|^p$$

处理混合属性

将闵可夫斯基距离和VDM结合起来即可处理混合属性。
假定有$n_c$个有序属性,$n-n_c$个无序属性,不失一般性,令有序属性排列在无序属性之前,则公式为
$$MinkovDM_p(x_i,x_j)=(\sum_{u=1}^{n_c} |x_{iu}-x_{ju}|^p + \sum_{u=n_c+1}^n VDM_p(x_{iu},x_{ju}))^{\frac{1}{p}}$$

加权距离(weighted distance)

当样本空间中不同属性的重要性不同时,可使用“加权距离”
$$dist(x_i,x_j)=(\omega_1·|x_{i1}-x_{j1}|^p+...+\omega_n·|x_{in}-x_{jn}|^p)^{\frac{1}{p}}$$
其中权重$\omega_i≧0(i=1,2,...,n)$表征不同属性的重要性,通常$\sum_{i=1}^{n} \omega_i=1$

选择聚类算法

聚类算法分类

第一种分类方法——

第二种分类方法——

第三种分类方法——

簇类型

常见算法:K-means算法,学习向量量化,高斯混合聚类,密度聚类
clustMixType是k-prototype聚类的包

常见算法:DBSCAN(Density-Based Spatial Clustering of Applications with Noise)

层次聚类

每个观测值自成一类,这些类每次两两合并,直到所有类被聚成一类为止
算法如下:

  1. 定义每个观测值(行或单元)为1类
  2. 计算每类和其他各类的距离
  3. 把距离最短的两类合并为一类,这样类的个数就减少一个
  4. 重复步骤2,3,直到包含所有观测值的类合并成单个的类为止。

在层次聚类算法中,主要的区别是他们对类的定义不同

常用算法

算法名字 类的定义 聚类结果
单联动 一个类中的点和另一个类中的点的最小距离 倾向于发现细长的、雪茄型的类,通常展示一种链式的现象,即不相似的观测值分到一类中,因为它们和它们的中间值很相像
全联动 一个类中的点和另一个类中的点的最大距离 倾向于发现大致相等的直径紧凑类,对异常值很敏感
平均联动 一个类中的点和另一个类中的点的平均距离(也称作UPGMA, 即非加权对组平均) 提供了以上两种方式的折中办法,不像链式,而且对异常值没有那么敏感,倾向于把方差小的类聚合。
Ward方法 两个类之间所有变量的方差分析的平方和。 倾向于把有少量观测值的类聚合在一起,并且倾向于产生与观测值个数大致相等的类。对异常值敏感。
质心 两类中质心(变量均值向量)之间的距离。对单个的观测值来说,质心就是变量的值。 类距离的定义比较简单、易于理解,相比其他方法对异常值不是很敏感,但是可能不如平均联动法或Ward方法表现得好。

R代码

hclust(d, method=)

d是通过dist()产生的距离矩阵
method包括single, complete, average, centroid, ward

划分聚类

首先指定类的个数K,然后观测值被随机分成K类,再重新形成聚合的类。常用算法有——

K-means算法

  1. 选择K个中心点(随机选择K行)
  2. 把每个数据点分配到离它最近的中心点(计算距离一般采用欧几里得距离)
  3. 重新计算每类中的点到该类中心点距离的平均值
  4. 分配每个数据到它最近的中心点
  5. 重复步骤3和4,直到所有的观测值不再被分配或是达到最大的迭代次数(R把10次作为默认迭代次数)

评价:
可以处理比层次聚类更大的数据集,另外观测值不会永远被分到一类中。当我们提高整体解决方案时,聚类方案也会改动,但是均值的使用意味着所有的变量必须是连续的,并且这个方法很有可能被异常值影响。
它在非凸聚类(如U型)情况下会变得很差。

R代码

kmeans(x, centers)
# x表示数值数据集(矩阵或数据框),centers是要提取的聚类数目。函数返回类的成员、类中心、中心和(类内平方和、类间平方和、总平方和)和类大小。

由于聚类方法对初始中心值的选择很敏感,kmeans()有一个nstart选项可以供你尝试多种初始配置并输出最好的一个。

围绕中心点的划分

  1. 随机选择K个观测值(每个都称为中心点)
  2. 计算观测值到每个中心的距离/相异性
  3. 把每个观测值分配到最近的中心点
  4. 计算每个中心点到每个观测值的距离的总和(总成本)
  5. 选择一个该类中不是中心的点,并和中心点互换。
  6. 重新把每个点分配到距它最近的中心点
  7. 再次计算总成本
  8. 如果总成本比步骤4计算的总成本少,把新的点作为中心点
  9. 重复步骤5-8直到中心点不再改变

评价:
更稳健,可容纳混合数据类型,并且不仅限于连续变量。
K-means一般使用欧几里得距离,PAM可以使用任意的距离来计算。

R代码
Cluster包中的pam()

pam(x, k, metric="euclidean", stand=FALSE)

x表示数据矩阵或数据框,k表示聚类的个数,metric表示使用的相似性/相异性的度量,而stand是一个逻辑值,表示是否有变量应该在计算该指标之前被标准化。

获得一种或多种聚类方法

这一步可以使用步骤5选择的方法

确定类的数目

为了得到最终的聚类方案,你必须确定类的数目。
常用方法:

获得最终的聚类解决方案

一旦类的个数确定下来,就可以提取出子群,形成最终的聚类方案了。
对于层次聚类
cutree()函数用来把树状图分成k类
aggregate()函数用来获取每类的中位数
rect.hclust()函数用来叠加k类的解决方案

结果可视化

帮助判定聚类方案的意义和用处。

解读类

需要注意,因为聚类是根据样本之间的相似性将它们分到一堆的,其实它并不知道这一簇簇样本,在现实世界里有什么意义。所以这里我们需要解读这一簇簇样本。
这一步通常通过获得类中的每个变量的汇总统计来完成。

验证结果

相当于在问“这种划分并不是因为数据集或聚类方法的某种特性,而是确实给出了一个某种程度上有实际意义的结果吗?”
希望结果:簇内相似度高,簇间相似度低。

性能度量方式

常用度量指标:

    • Jaccard系数(JC)
    • FM指数
    • Rand指数
  • 常用度量指标:

    fpc, clv, clValid包里包含了评估聚类解的稳定性的函数。

    References

    「一键投喂 软糖/蛋糕/布丁/牛奶/冰阔乐!」

    薇拉航线

    (๑>ڡ<)☆谢谢老板~

    使用微信扫描二维码完成支付

    Comments are closed.