Celery's Blog

0%

聚类

发表于 Valine：

数据挖掘算法——聚类

概念

按照数据之间的相似性，对数据集进行分组或分类（簇，cluster）的过程，试图使类内差距最小化，类间差距最大化

利用聚类结果，可以提取数据集中隐藏的信息，对未来数据进行预测和分类

聚类在数据挖掘中的典型应用

  • 聚类分析可以作为其他算法的预处理部分：利用聚类进行数据预处理，可以获得数据的基本概况，在此基础上进行特征抽取或分类就可以提高精确度和挖掘效率。也可将聚类结果用于进一步关联分析，以获得进一步的有用信息
  • 可以作为一个独立的工具来获得数据的分布情况：聚类分析是获得数据分布情况的有效方法。通过观察聚类得到的每个簇的特点，可以集中对特定的某些簇进一步分析。这在诸如市场细分、目标顾客定位、业绩评估、生物种群划分等方面具有广阔的应用前景
  • 聚类分析可以完成独立点挖掘：许多数据挖掘算法试图使孤立点影响最小化，或者排除他们。然而孤立点本身可能是非常有用的。如在欺诈探测中，孤立点可能预示着欺诈行为的存在。

聚类分析的目标

  • 聚类分析的目标就是形成的数据簇，并且满足下面两个条件：

    • 一个簇内的数据尽量相似（high intra-class similarity）
    • 不同数据簇的数据尽量不相似(low inter-class similarity)

  • 衡量一个聚类分析算法质量，依靠：

    • 相似度测量机制是否合适
    • 是否能发现数据背后潜在的、
    • 手工难以发现的类知识

  • 相似性度量:

    • 距离相似性度量
    • 角度相似性度量

相似性计算方法

Dissimilarity / Similarity 度量

对于不同的数据类型，距离函数的定义是非常不同的：

  • 区间标度度量（Interval-scaled variables）

  • 二元变量（Binary variables）

  • 标称型、序数型和比例标度型

  • 混合型

区间标度度量

距离通常是用来作为对象之间相似度和不相似度量的最主要方法

区间标度是一个粗略线性标度的连续度量。典型的例子包括重量和高度，经度和纬度坐标（聚类房屋），以及大气温度。

明考斯基距离（Minkowski distance）

d(i,j)=(∣xi1−xj1∣q+∣xi2−xj2∣q+...+∣xip−xjp∣q)pd(i, j) = \sqrt[p]{(|x_{i_1} - x_{j_1}|^q+|x_{i_2} - x_{j_2}|^q + ... + |x_{i_p} - x_{j_p}|^q)}

where i =(xi1,xi2,...,xip) and j = (xj1,xj2,...,xjp) are two p-dimensional data object, and q is a positive integer\text{where i =} (x_{i_1}, x_{i_2}, ...,x_{i_p}) \text{ and j = }(x_{j_1}, x_{j_2}, ...,x_{j_p}) \text{ are two p-dimensional data object, and q is a positive integer}

曼哈顿距离

if q = 1, d is Manhattan distance 曼哈顿距离

d(i,j,)=∣xi1−xj1∣+∣xi2−xj2∣+...+∣xip−xjp∣d(i, j,) = |x_{i_1} - x_{j_1}| + |x_{i_2} - x_{j_2}|+... + |x_{i_p} - x_{j_p}|

欧几里得距离

if q = 2, d is Euclidean distance 欧几里得距离

d(i,j)=(∣xi1−xj1∣2+∣xi2−xj2∣2+...+∣xip−xjp∣2)2d(i, j) = \sqrt[2]{(|x_{i_1} - x_{j_1}|^2+|x_{i_2} - x_{j_2}|^2 + ... + |x_{i_p} - x_{j_p}|^2)}

性质：

  • d(i,j)>0d(i, j) > 0
  • d(i,i)=0d(i, i) = 0
  • d(i,j)=d(j,i)d(i, j) = d(j, i)
  • d(i,j)<d(i,k)+d(k,j)d(i , j) < d(i, k) + d(k, j)

二元变量

一个二元变量只有两个状态：0 或 1，0 表示改变量为空，1表示改变量存在

例如，给出一个描述病人的变量smoker，1表示病人抽烟，0表示病人不抽烟

我们可以对给定的数据计算相异度矩阵。如果假设所有的二元变量具有相同的权重，我们得到一个两行两列的可能性。

  • a contingency table for binary data

1577350893738

  • a 是对于对象i和j的值都为1的变量的数目

  • b 是对于对象i值为1而对象j值为0的变量数目

  • c和d同理

变量的总数是p：p = a + b + c + d

对称的二元变量

如果他的两个状态是同等价值的，并由相同的权重，那么该二元变量是对称的，也就是两个取值0或1没有优先权。例如性别

简单系数匹配：Simple matching coefficient (invariant, if the binary variable variable is symmetric)

1577351128272

不对称二元变量

如果两个状态的输出不是同样重要，那么该二元变量是不对称的

例如：一个疾病检查的肯定和否定结果。根据惯例，我们将比较重要的输出结果，通常也是出现几率较小的结果编码为1，而将另一种结果编码为0.给定两个不对称的二元变量，两个都取1的情况被认为比两个都取0的情况更有意义。因此，这样的二元变量被认为好像只有一个状态。

JACCARD系数

在计算中，负匹配数目d认为是不重要的，因此被忽略

1577351388626

例题：

1577351515180

1577351533566

类间距离

距离函数笃实关于两个样本的距离刻画，然而在聚类应用中，最基本的方法是计算类间的距离

设有两个类CaC_a和CbC_b，他们分别有m和n个元素，他们的中心分别为γa\gamma_a和γb\gamma_{b}。设元素x∈Ca,y∈Cbx \in C_a, y \in C_b，这两个元素间的距离通常通过类间距离来刻画，记为D(Ca,Cb)D(C_a, C_b)

两个聚类p和q

  • 最短距离法 Dpq=min{d(xi,xj)}D_{pq} = min \{d(x_i, x_j)\}

  • 最长距离法 Dpq=max{d(xi,xj)}D_{pq} = max\{d(x_i, x_j)\}

  • 中心法 Dpq=min{d(xp,xqˉˉ)}D_{pq} = min\{d(\bar{x_p, \bar{x_q}})\}

  • 类平均法 D_{pq} = \frac{1}{n_1 n_2} \underset{x_i \in G_p} \sum \underset{x_j \in G_q} \sum d(x_i, x_j)

距离阈值对聚类的影响

1577352186669

  • 特征选取不当使聚类无效

    1577352294743

  • 特征选取不足引起误分类

    1577352284070

  • 模式特征坐标单位的选取也会强烈地影响聚类结果

    1577352272327

解决尺度问题

yi=(xi−m)/sy_i = (x_i - m) / s

为了进行聚类，我们需要一种合适的距离度量尺度。这种距离度量尺度依赖于特征标准化方法，为了选择标准化方法我们必须知道聚类的类型。

试错法是唯一的避免这种恶性循环的方法。选择不同的条件进行试验，通过观察、数据解释和效用分析评价相应的解。平衡各特征值的贡献，并保持原有的语义信息

角度相似性变量

样本之间的角度相似性度量定义为他们之间夹角的余弦：

S(x,y)=cosθ=xTy∣∣x∣∣⋅∣∣y∣∣S(x, y) = cos\theta = \frac{x^Ty}{||x|| \cdot ||y||}

S(x,y)S(x, y)越大，x、y越相似

S(x,y)S(x, y)满足：

  • S(x,y)=S(y,x)S(x, y) = S(y, x)
  • 当x=yx=y时，S(x,y)S(x, y)达到最大
  • ∣S(x,y)≤1∣|S(x, y) \leq 1|

聚类分析方法的分类

按照聚类的标准，聚类方法可分为如下两种：

  • 统计聚类方法：这种聚类方法只要基于对象之间的几何距离的
  • 概念聚类方法：概念聚类方法基于对象具有的概念进行聚类

按照聚类算法所处理的数据类型，聚类方法可分为三种：

  • 数值型数据聚类方法：所分析的数据的属性只限于数值数据
  • 离散型数据聚类方法：所分析的数据的属性只限于离散型数据
  • 混合型数据聚类方法：能同时处理数值和离散数据

按照聚类的尺度，聚类方法可被分为以下三种：

  • 基于距离的聚类算法：用各式各样的距离来衡量数据对象之间的相似度，如K-means，K-medoids， BIRCH， CURE等方法
  • 基于密度的聚类方法：相对于基于距离的聚类方法，基于密度的聚类方法只要是依据合适的密度函数
  • 基于互连性（Linkage-Based）的聚类算法：通常基于图或超图模型。高度连通的数据聚为一类

K-Means算法

k−meansk-means算法，也被称为k-平均或k-均值，是一种得到最广泛应用的聚类算法。相似度的计算是根据一个簇中对象的平均值来计算的。

算法步骤

  • 首先将所有对象随机分配到k个非空的簇中
  • 计算每个簇的平均值，并用该平均值代表相应的簇
  • 根据每个对象与各个簇中心的距离，分配给最近的簇
  • 然后转达第二步，重新计算每个簇的平均值。这个过程不断重复知道满足某个准则函数才停止

Example

1577353118224

1577353232300

实例

样本数据

序号 属性1 属性2
1 1 1
2 2 1
3 1 2
4 2 2
5 4 3
6 5 3
7 4 4
8 5 4

根据所给的数据通过对其实施k-means（设n = 8, k = 2），其主要执行步骤为：

第一次迭代：假定随机选择的两个对象，如序号1和序号3当做初始点，分别找到离两点最近的对象，并产生两个簇{1, 2}和 {3, 4, 5, 6, 7, 8, 9}

对于产生的簇分别计算平均值，得到平均值点

对于{1, 2}，平均值点为(1.5, 1)

对于{3, 4, 5, 6, 7, 8}, 其平均值点为(3.5, 3)

第二次迭代：通过平均值调整对象的所在的簇，重新聚类，即将所有点按离平均值点(1.5, 1)和(3.5, 5)最近的原则重新分配。得到两个新的簇：{1, 2, 3, 4} 和 {5, 6, 7, 8}。重新计算簇平均值点，得到新的平均值点为(1.5, 1.5) 和 (4.5, 3.5)

第三次迭代：将所有点按离平均值点(1.5, 1.5) 和 (4.5, 3.5)最近的原则重新分配，调整对象，簇仍然为{1, 2, 3, 4}和{5, 6, 7, 8}，发现没有出现重新分配，而且准则函数收敛，程序结束。

迭代次数 平均值(簇1) 平均值(簇2) 产生的新簇 新平均值(簇1) 新平均值(簇2)
1 (1, 1) (1, 2) {1, 2}, {3, 4, 5, 6, 7, 8} {1.5, 1} {3.5, 3}
2 {1.5 ,1} {3.5, 3} {1, 2, 3, 4}, {5, 6, 7 8} {1.5, 1.5} {4.5, 3.5}
3 {1.5, 1.5} {4.5, 3.5} {1, 2, 3, 4}, {5, 6, 7, 8} {1.5, 1.5} {4.5, 3.5}

性能分析

主要优点
  • 是解决聚类问题的一种经典算法，简单、快速
  • 对处理大数据集，该算法是相对可伸缩和高效率的
  • 当结果簇是密集的而簇间区别是明显的是，它的效果较好
主要缺点
  • 必须事先给出k（要生成的簇的数目），而且对初值敏感，对于不同的初始值，可能会导致不同结果
  • 不适合于发现非凸面形状的簇或者大小差别很大的簇
  • 对于“噪声”和孤立点数据是敏感的，因为簇的中心是通过计算数据的平均值得到的，这些数据的存在会使聚类的中心发生很大的偏移

K-means算法的集中改进方法

  • k-mode算法：实现对离散数据的快速聚类，保留了k-means算法的效率同时将k-means的应用范围扩大到离散数据

  • k-prototype算法：可以对离散与数值属性两种混合的数据进行聚类，在k-prototype中定义了一个队数值与离散属性都计算的相异性度量标准

  • k-中心点算法：k-means算法对于孤立点是敏感的。为了解决这个问题，不采用簇中的平均值作为参照点，可以选用簇中位置最中心的对象，即中心点作为参照点。这样划分方法仍然是基于最小化所有对象与其参照点之间的相异度之和的原则来执行的