65.9K
CodeProject 正在变化。 阅读更多。
Home

数据聚类入门

Andy Allinger
starIconstarIconstarIconstarIcon
emptyStarIcon
starIcon

4.96/5 (21投票s)

2017 年 4 月 10 日

公共领域

10分钟阅读

viewsIcon

29611

downloadIcon

590

介绍数据聚类和 k-means++ 算法

本文介绍了数据聚类是什么以及它的用途。它提供了流行 k-means++ 算法在 FORTRAN 和 C 中最简单的实现，并讨论了几个示例问题。

它是什么

数据聚类，有时也称为聚类分析，是寻找数据中组的过程。相似的对象被归为一类；不同的对象被分开。

作为一个图形示例，如果你的数据是这样

那么聚类就是这样

机器学习的主要任务
回归
进行数值预测。示例：根据父亲的身高预测儿子的身高。
分类
将每个对象分配到几个给定类别中的一个。示例：将绵羊与山羊分开
模式识别
在数据集中搜索已知对象的出现。示例：大海捞针。
聚类
将对象分组到以前未定义的组中。示例：在植物标本集中命名花卉物种
数据融合
决定来自一个信息源的对象与来自另一个信息源的对象相对应。示例：将导弹设施的卫星图像与间谍报告匹配（是的，“融合”一词主要由军方使用。）

数据聚类是统计学中的一个主题，也是机器学习的主要任务之一。

它的用途

探索性分析
公司的营销部门可能希望将其客户分为几个细分市场。生物学家可能对将标本集合整理成几个物种感兴趣。统计学中很多注意力都集中在假设检验上：证明或反驳组之间是否存在差异。探索性分析是另一回事：还没有假设。分析师正在寻找可能存在的组。
总结数据集
为了处理大量数据，通常会抽取一个小的样本来代表整个集合。这个样本可能是随机选择的，但可能会忽略稀有对象。数据聚类可用于生成一个包含常见和稀有对象的样本。

数据聚类不应与分类混淆。在分类中，类别是预先知道的。通常，人类专家提供一个训练集，其中每个数据点都已标记其类别。在聚类中，事先不知道可能存在哪些类别。例如，假设数据是关于某些肿瘤细胞的信息。分类任务是识别每个标本是良性还是恶性。聚类任务是识别不同类型的肿瘤细胞。

聚类种类

原型聚类

每个簇由一个原型、一个示例或某种平均值表示。每个对象都与此原型进行比较，以确定它是否属于该簇。k-means 算法就属于这种类型。

层次聚类

生物学家将每个物种放入一个属，每个属放入一个科，每个科放入一个目，每个目放入一个纲，每个纲放入一个门。因此，所有生物都形成了一个群体的层次结构。数据聚类的早期工作大部分是由植物学家完成的，当然是层次结构的。本文将不再进一步讨论。

图聚类

数据点与其他点进行比较，没有簇原型。这里引入图论：数据对象称为顶点，相似性称为边。图聚类然后就是通过切割最少的边来分割图的问题。由于没有中心点，因此簇可以是任何形状。这使得图聚类适用于图像分割，本文将不再进一步讨论。

具体细节

x 的分量可以是各种量，温度、压力、距离、能量等等。使用欧几里德距离会将苹果和橙子相加。将平方压力与平方时间相加有任何物理意义吗？没有，但这种公式的使用背后有其合理性，初学者无需详细理解，但应该提及。大多数值接近平均值的一组测量可以用多元正态分布来描述

f(x, μ, V) = exp(-½(x - μ)V-1(x - μ)T) / ((2π)½p √|V|)

此方程给出的值 f 与从平均值 μ 和协方差矩阵 V 的总体中抽取具有值 x 的对象的概率成比例。例如，人群中成年男性的身高和体重。如果忽略变量之间的相互作用，则协方差矩阵简化为方差向量。然后取负对数并省略常数因子

f ∝ Σ((xj - μj)/σj)²

这是欧几里德距离的平方，在每个量的单位被它们的（簇内）标准差除以之后。因此，尽管有些统计学家将数字烹饪成浓稠的糊状，我们仍然可以而且应该为我们对数据进行的操作提供合理的理由！

有必要精确地说明“对象”是什么，以及“相似性”意味着什么。

设一个对象是 RP 中的一个向量，即一个长度为 P 的 float 类型数组。这是最容易处理的数据类型，许多感兴趣的实际问题都可以用这种方式描述。

x = [x1 x2…xP]

设每个簇的原型是其质心，即其向量的算术平均值

c = (1/N) Σxi

设对象与其原型之间的不相似度为欧几里德距离，即根据勾股定理

d² = Σ(xj - cj)²

k-means 方法

k-means 方法自 1956 年或更早以来就已存在，并且由于其简单、快速且通常能给出良好结果，因此仍然广泛使用。通常。请注意，形式上，k-means 是一种方法，而不是算法，因为它不能保证会产生正确答案。

将对象称为“点”，将原型称为“中心”。该方法在两个主要步骤之间交替进行

  • 将每个点分配到其最近的中心
  • 让每个中心是其点的平均值

当点的簇分配不再改变时退出。设 N 表示对象数量，P 表示每个对象的测量值，K 表示所需簇的数量。那么最大的计算成本是比较点和中心，这需要每次迭代 O(NPK) 次操作。1

k-means++ 变体

上述方法没有说明如何选择起始位置。传统方法是随机选择 K 个点作为初始中心，或将每个点随机分配到一个簇。这可能会导致非常糟糕的结果，因此以前的建议是多次运行 k-means 并保留最佳结果。

自 2006 年以来，提出了选择初始中心的新方法，这些方法提供了逼近最优聚类的理论保证。2, 3 这个新变体称为 k-means++ 算法。随机均匀选择一个点作为第一个中心。其余的 K-1 个中心从其他点中选择，其概率与其到最近先前选择的中心的平方距离成比例。

以下是如何以任意概率选择一个元素。首先，我们需要一个长度为 N 的 WORK 数组来保存每个数据点的最短平方距离，并将 TOT 作为 WORK 中元素的总和。然后，4

! Choose center with probability proportional to its squared distance
!     from existing centers.
         CALL RANDOM_NUMBER (U)  ! draw random number from 0 ... 1
         U = U * TOT    ! uniform at random over cumulative distance
         TOT = 0.
         DO I = 1, N
           I1 = I
           TOT = TOT + WORK(I)
           IF (TOT > U) GO TO 20
         END DO                ! next I
  20     DO J = 1, P         ! assign center
           C(J,L) = X(J,I1)
         END DO

因为 WORK 中的每个元素都是正数，相加将任意概率分布转换为累积概率分布，因此在 I 循环的每个步骤中，TOT 必须增加。如图所示

累积分布是能将单纯的均匀随机数转换为任何其他概率分布的随机变量的魔杖。

使用代码

子程序 KMPP 以纯正的 FORTRAN 实现了 k-means++。提供了 C 语言的翻译版本。原型如下

     SUBROUTINE KMPP (X, P, N, K, C, Z, WORK, IFAULT)
       INTEGER P, N, K, Z, IFAULT
       REAL X, C, WORK
       DIMENSION X(P,N), C(P,K), Z(N), WORK(N)

其中，X 是 RP 中点的输入数据，P 是变量的数量，N 是对象的数量，K 是要形成的簇的数量，C 是 RP 中点的输出中心，Z 是一个 1…K 的整数数组，表示每个点的簇成员资格，WORK 由子程序内部使用，其内容用户可以忽略，IFAULT 是一个错误代码，成功时返回 0。

在 C 语言中，它看起来像

    int kmpp (float **x, int p, int n, int k, float **c, int *z, float *work)

请注意，矩阵采用指针数组的形式，避免使用 double 精度，并且错误代码现在是函数的返回值。

示例：鸢尾花数据

鸢尾花数据集是统计学中最古老、最著名的测试问题之一。5 它是 R. A. Fisher 在 1935 年介绍线性判别分析时使用的示例问题。它是 150 个鸢尾花标本（三个物种）的花瓣宽度、花瓣长度、萼片宽度和萼片长度的测量值。因此 N=150，P=4，K=3。数据的前两个维度绘制如下

t_iris 示例程序调用 KMPP 并将结果写入 CSV 文件，该文件易于导入任何电子表格。用颜色表示簇成员资格，用 X 标记中心

簇可能会出现重叠，因为此图只是 4 维数据集的 2D 投影。6 作为参考，这是按类别标签着色的鸢尾花数据

有一些分歧。请记住，聚类不是分类。k-means 很好，但它肯定不完美。

示例：单位圆中的随机点

t_round 示例程序在单位圆中随机生成点，N=30000，P=2，K=6。KMPP 的输入是

它被分成簇

请注意，k-means 会很听话地将数据分成 K 块，即使输入中不存在簇！

限制

这里给出的简单例程

  • 无法处理未表示为实数向量的数据
  • 无法处理缺少任何值的数据集
  • 无法告诉你应该创建多少个簇
  • 无法衡量其结果的质量

我希望在未来的文章中以中等难度级别展示如何解决这些限制。

注释

  1. 如果将中心放入树数据结构中，则可以在不与所有中心进行比较的情况下找到距离点最近的中心。
  2. Rafail Ostrovsky、Yuval Rabani、Leonard J. Schulman 和 Chaitanya Swamy，“k-means 问题的 Lloyd-Type 方法的有效性”，第 47 届 IEEE 计算机科学基础年度研讨会 (FOCS'06) 论文集
  3. David Arthur 和 Sergei Vassilvitskii，“k-means++：精心播种的优势”，第十八届 ACM-SIAM 离散算法年度研讨会论文集，2007 年。不用做任何数学运算，但凭一些常识，很明显，由于 k-means++ 依赖于抽取随机数，它只能在某种平均意义上，从长远来看“保证”结果的质量。因此，多次运行子程序仍然很重要。
  4. 这种线性前向搜索可以通过将累积分布存储在 WORK 中并进行二分搜索来替换，以提高速度。
  5. 鸢尾花数据未包含在分发中。您可以从以下网址下载：UC Irvine 机器学习存储库，其中有许多有价值的测试问题。
  6. 奇异值分解 (SVD) 或多维缩放 (MDS) 可用于查找数据集的低维投影，这些投影优于丢弃整个维度。

参考文献

  • Leonard Kaufman 和 Peter J. Rousseeuw，《在数据中寻找群组：聚类分析导论》，Wiley，1990 年，2005 年再版。
  • R 核心团队，kmeans.c，2004 年。
  • 维基百科，当然

历史

版本 1.0，2017 年 4 月 2 日

© . All rights reserved.