论文 - 扩展 K-Means 算法：混合数据类型的聚类

原文：Extensions to the k-means algorithm for clustering large datasets with categorical values
作者：ZHEXUE HUANG.
来源：Data mining and knowledge discovery, 1998, 2(3): 283-304.
转载：简书不支持公式渲染，便于阅读可参考 原博文。

• 更新进度：
  • 2018.06.04: 整理原文，完成初稿；
  • 2018.06.05: 更新第 5 / 6 章；

摘要

在早期，大多数聚类工作主要集中在数值数据上，且它们主要是利用数值数据的固有几何特性，即数据点之间的 距离函数 (见附录1)。但是，数据挖掘应用程序通常涉及许多数据集，这些数据集是由混合数值属性和标称属性组成的，仅拥有数值数据的测量方法已无法满足混合数据类型的聚类工作。

本论文基于经典的 K-Means 算法上，提出了两种聚类算法，分别应对 标称域 和 混合数值与标称域 属性值的聚类操作。首先介绍的是K-Modes (K-众数) 聚类算法，他运作的方式与 K-Means 相仿，只是它利用的是相异性度量处理标称对象，聚类中心以众数替代均值，且众数以基于频率的方法去迭代更新，直至 聚类代价函数 的结果最小化停止迭代。其次，是 K-Prototype 聚类算法，它定义了一组合的相异性度量值，进一步整合 K-Means 和 K-Modes 算法，以实现对混合数值与标称属性的对象进行聚类操作。

正文

引入

将数据库中的一组对象划分为同构组或集群是数据挖掘中最基本的操作。而讨论划分操作，自然离不开聚类。聚类是把每一组对象划分为一个簇，且同一簇中对象之间相似，而不同簇之间的对象相异。

数据挖掘最显著的特征是处理复杂的大型数据集。特别地，数据集包含数以百万计由不同类型属性或变量描述的对象，由此数据挖掘操作和算法应充分考虑可扩展性，以应付处理不同类型的属性。

在本论文中，提出的两个新聚类算法，即利用 K-Means 范式 对拥有标称属性的数据进行聚类。K-Modes (K-众数) 聚类算法，他运作的方式与 K-Means 相仿，只是它利用的是相异性度量处理标称对象，聚类中心以众数替代均值，且众数以基于频率的方法去迭代更新，直至 聚类代价函数 的结果最小化停止迭代。其次，是 K-Prototype 聚类算法，它定义了一组合的相异性度量值 s^r + \gamma s^c，以实现对混合数值与标称属性的对象进行聚类操作。其中，s^r 是由 平方欧式距离 定义的 数值属性 的相异性度量值，s^c 是由 两个对象间类别不匹配的数量 定义的 标称属性 的相异性度量值，\gamma 是平衡数值属性和标称属性两部分的的权值，以避免偏向于某一属性。若聚类的效果更青睐于数值属性，则可以设定一个较小的 \gamma 值；反之，设定一较大的 \gamma 值。

符号

• 假设需要聚类的对象数据集储存在数据集 D 中。

  • 集合的属性 A_1, A_2, ... , A_m 分别是值域 D_1, D_2, ... , D_m 的描述。
  • 在 D 中的每个对象由元组 t 表示，t \in D_1 \times D_2 \times ... \times D_m。

• 针对本文讨论的聚类问题，仅考虑两种常见数据类型：数值类型和标称类型。

  • 数值域的取值范围是实数域。
  • 在多维的密度空间中，每一个数值型的数据点都采用诸如欧式或马氏的距离度量方法。
  • 若值域 D_i 被定义为有限、无序的标称域，则对象的比较操作只允许在 D_i 中执行，即有 a, b \in D_i，either a = b or a \neq b。

• 对于数据集中的每一数据对象 X，也可由 属性-属性值 的键值对表示，

  [A_1=x_1] \bigwedge [A_2=x_2] \bigwedge ... \bigwedge [A_m=x_m]

• 即当 x_i \in D_i，for i = 1, 2, ..., m。为简单起见，这里以 X 表示元组：

  [x_1^r, x_2^r, ...,x_p^r, x_{p+1}^c, ..., x_m^c] \in D_1 \times D_2 \times ... \times D_m

  最后一个数值对象为元素 p ，其余的都是标称对象。当然，若元组中仅有一种数据类型，可表示为 [x_1, x_2, ..., x_m]。

K-Means (均值) 算法

• K-Means，是一种划分或非分层的聚类算法，为进一步阐述细节，需给出如下设定：

  • 一组含 n 个数值数据的对象集 D = \{X_1, X_2, ..., X_n\}；
  • 距离度量 d；
  • 自然数 k (\leq n)，并把 D 划分 k 个非空且相分离的簇群 C_1, C_2, ..., C_k, \, with \, C_i \bigcap C_j = \emptyset \, and \, \bigcup_{i=1}^k C_i = D；
  • D 中随机选取 k 个对象，每个对象代表一个簇的初始均值或中心。

• 如此一来，使得数据对象与其簇的中心之间的平方误差总和被最小化。然后，根据非线性优化问题，将该问题描述为:

  Minimise \, P(W,Q) = \sum_{l=1}^k \sum_{i=1}^n w_{i,l} d(X_i, Q_l) \tag{1}

  且服从：

  \begin{cases} \sum_{l=1}^k w_{i,l} = 1, \, i = 1, 2, ..., n \\ w_{i,l} \in \{0,1\}, \, i = 1, 2, ..., n; l = 1, 2, ..., k \end{cases} \tag{2}

  • w_{i,l} 指标变量表示对象 X_i 仅属于哪一个簇。即取值为 1 时，表示对象 X_i 在 簇 C_l 中；反之，取值为 0。
  • W = \left[ w_{i,l} \right]_{n \times k} 是分块矩阵 (见公式 3)，Q = \{Q_1, Q_2, ..., Q_K\} 是簇的中心集合，d(·,·) 是两对象间的平方欧式距离 (见附录1)。

  W = \left[ w_{i,l} \right]_{n \times k} = \begin{bmatrix} w_{11} & \cdots & w_{1l} & \cdots & w_{1k} \\ \vdots & & \vdots & & \vdots \\ w_{i1} & \cdots & w_{il} & \cdots & w_{ik} \\ \vdots & & \vdots & & \vdots \\ w_{n1} & \cdots & w_{nl} & \cdots & w_{nk} \\ \end{bmatrix} \tag{3}

• 紧接着，在约束条件 (2) 下对 (1) 中的 P 进行优化，即对 Q 和 W 进行局部优化。首先，我们先固定 Q 并找出必要条件 W 使 P 最小化。然后，根据 Q 去修正 W 并最小化 P。基于上述几点，若为了达到 P 最小化，K-Means 算法通过 三步迭代，直到 P(W, Q) 收敛 到某个 局部最小值。

  • Step.01： 初始化 Q^{(0)} = \{Q_1^{(0)}, Q_2^{(0)}, ..., Q_k^{(0)}\}，且设立 t = 0。

  • Step.02：固定 Q^{(t)} 不变，求解 P(W, Q^{(t)}) 再去获得 W，即以 Q 作为簇群的中心，将每个对象分配到距离其最近的簇中心的簇群当中。

  • Step.03：固定 W^{(t)} 不变，生成 Q^{(t+1)}，求解 P(W^{(t)}, Q^{(t+1)})。比较 P(W, Q^{(t)}) \, and \, P(W^{(t)}, Q^{(t+1)})，若后者为最小化，则根据当前的对象部分构造新的簇群中心。

    • Q_t^{t+1} = \{q_{l,1}^{(t+1)}, ..., q_{l,m}^{(t+1)}\}, \, for \, l = 1, 2, ..., k，且：

    q_{l,j}^{(t+1)} = \frac { \sum_{i=1}^n w_{i,l}^{(t)} x_{i,j} }{ \sum_{i=1}^n w_{i,l}^{(t)} }, \, j = 1, 2, ..., m \tag{4}

  • Step.04：当满足收敛或给定的停止条件时 ( 局部最优化 )，输出结果并停止；反之，令 t = t + 1，并继续从 Step.02 开始执行。

• 为了解决 簇间边界不明确 的问题，模糊分区的概念成功地应用到聚类问题中，即模糊聚类 ^{[2,3]}。但是，我们在本论文中不考虑这个问题。

• 综上所述，K-Means 算法具有以下特征：

  • 局部最优化为算法结束的终止条件；
  • 仅适用于数值属性数据的聚类；
  • 簇群的特征为球形簇.

K-Modes (众数) 算法

原则上，K-Means 算法中问题 P 的公式对于分类和混合类型的对象也是有效的，之所以 K-Means 算法不能对标称属性对象进行聚类的原因是它的相异性度量方法和用于构造新的簇群中心的方法不适用，故通过对 K-Means 算法进行以下修改，可消除不适用问题：

• 用于标称属性对象的相异性度量的方法；
• 簇群的中心以 众数 替代 均值；
• 使用基于频率的方法求的众数，以构造新的簇群中心。

相异性度量

相异性度量：设 X,Y 是由 m 个标称属性描述的两个标称属性对象， X,Y 的相异性度量可通过两个对象间相对应属性的不匹配总和来定义，即不匹配的次数越少，两个对象越相似。定义如下：

d(X,Y) = \sum_{j=1}^m \delta (x_j,y_j) \tag{5}

且满足条件：

\delta (x_j,y_j) = \begin{cases} 0 , \, (x_j = y_j) \\ 1 , \, (x_j \neq y_j) \end{cases} \tag{6}

众数集

设 X 是由标称属性 A_1, A_2, ..., A_m 描述的标称属性对象集。X= \{X_1, X_2, ..., X_n\} 的众数由向量 Q =\{q_1, q_2, ..., q_m\} 表示，并最小化函数：

Minimise \, D(X,Q) = \sum_{i=1}^n d(Xi,Q) \tag{7}

注意，这里 Q 并不一定是 X 中包含元素 (有别于 K-Medoids 算法 ^{[4]}，质心从它的样本点中选择 )。

挑选众数

设 n_{c_{k,j}} 为属性 A_j 中包含第 k 个标称属性 c_{k,j} 的对象数量，且定义 f(A_j = c_{k,j} | X) = \frac{ n_{c_{k,j}} }{n} 为标称属性 c_{k,j} 在 X 中的出现频率。

• 定理 1：若满足下述条件 (8)，即 D(X,Q) 已最小化 ( 证明见附录2 )。即定理定义了一种从给定的 X 中找到 Q 的方法，即它允许使用 K-Means 范式来聚类标称数据，且定理 1 暗示了数据集 X 的众数不是唯一的。

  f(A_j = q_j | X) \geq f(A_j = c_{k,j} | X) \, for \, q_j \neq c_{k,j},j=1, 2, ..., m \tag{8}

算法核心

• 当公式 (5) 用作标称属性对象的相异性度量时，公式 (1) 的代价函数将推导为：

P(W,Q) = \sum_{l=1}^k \sum_{i=1}^n \sum_{j=1}^m w_{i,l} \delta(x_{i,j},q_{l,j})\\\ where \, w_{i,l} \in W \, and \, Q_l = [q_{l,1}, q_{l,1}, ..., q_{l,m}] \in Q \tag{9}

• 为了最小化代价函数，则修改经典 K-Means 算法：

  • 以相异性度量方法求解 W，即上述 Step.02 所描述的，以当前 Q 为簇群中心，将每个对象分配到距离其最近的簇中心的簇当中去；
  • 用簇的众数代替均值，根据 定理 1 选择众数来求解 Q，即上述 Step.03 所描述的，求得新的簇群中心。

• 在经典算法中，我们需要在每次获得一个新的 Q 或 W 时，根据整个数据集计算总代价 P。为了提高计算效率，我们在实践中采用了下面的算法。

  • Step.01：初始化 k 个众数，且每个众数对应一个簇；

  • Step.02：根据公式 (5)，将距离众数最近的对象分配该簇当中。再根据 定理 1，在每次分配后更新簇群的众数。

  • Step.03：当所有对象分配到具体的簇群之后，重新测试对象与当前众数的相异性。如果找到一个对象，距离其最近的众数属于另一个簇群而不是当前的簇群，则将该对象重新分配给该簇群，并更新两个簇群的众数。

  • Step.04：重复执行 Step.03，直到对整个数据集进行完整的循环测试之后，没有对象更改簇群。

    目前，虽没有证明该算法的收敛性，但在实际使用过程中，它的表现总是收敛的。

• 与 K-Means 算法一样，K-Modes 算法也是产生 局部最优解，且依赖于数据集中的 初始的众数 和 对象的顺序。考虑 初始的众数 和 对象的顺序 的因素影响，我们通过两种方法改进算法。

  • 第一个方法是第一次从数据集中选择 k 个不同的记录作为初始 k 个众数值。
  • 第二个方法通过以下步骤实现：

    • Step.01：计算所有属性的所有标称值的频率，并按照频率的降序将它们存储在一个标称类型的数组中，如图 2-1 所示，展示了标称类型数组中，分别包含 4、2、5、3 个标称值的 4 个属性。这里 c_{i,j} 表示属性 i 的标称值 j，f(c_{i,j}) 为标称值的频率，且 f(c_{i,j}) \geq f(c_{i+1,j})。

    • Step.02：将频率最高的标称值作为 k 个众数的初始值。

    • Step.03：从 Q_1 开始，选择相似性最接近其的记录并替换它的初始众数。以此类推，直至 Q_k 的初始众数被替换完成。其中，Q_l \neq Q_t \, for \, l \neq t。

      Step.03 的目的在于避免空簇群的情况，致使初始众数具有多样性，以获得更好的聚类结果。

  \begin{Bmatrix} c_{1,1} & c_{1,2} & c_{1,3} & c_{1,4} \\ c_{2,1} & c_{2,2} & c_{2,3} & c_{2,4} \\ c_{3,1} & \, & c_{3,3} & c_{3,4} \\ c_{4,1} & \, & c_{4,3} & \, \\ \, & \, & c_{5,3} & \, \\ \end{Bmatrix}

  <center>图 2-1 标称类型数组 ( 横向表示集合的属性 A，纵向表示簇中心点 Q )</center>

附录

1 距离函数

距离函数：关于数据点之间的距离函数，即数值属性刻画的对象相异性的距离度量。度量方法 ^{[1]} 包括闵可夫斯基距离 (闵氏距离)、欧几里得距离 (欧式距离) 和曼哈顿距离。

令 i=(x_{i1},x_{i2},...,x_{ih}) 和 j=(x_{j1},x_{j2},...,x_{jh}) 是两个被 h 个属性描述的对象。

闵氏距离是欧式距离和曼哈顿距离的推广，定义如下：

d(i, j) = \sqrt[h]( \sum_{f=1}^h |x_{if}-x_{jf}|^{h} ),h \geq 1 \tag{1}

• 当 h = 1 时，它表示 曼哈顿距离，也称 城市块 距离 (城市两点之间的街区距离，如向南 2 个街区，横过 3 个街区，共计五个街区)，其定义如下：

d(i, j) = \sum_{f=1}^h |x_{if}-x_{jf}|,h \geq 1 \tag{2}

• 当 h = 2 时，它表示 欧式距离，也称 直线或乌鸦飞行 距离，其定义如下：

d(i, j) = \sqrt(\sum_{f=1}^h (x_{if}-x_{jf})^2) ,h \geq 1 \tag{3}

• 当 h = \infty 时，它表示 上确界距离，又称 切比雪夫距离，其定义如下L：

d(i, j) = \lim_{h \to \infty} ( \sum_{f=1}^h |x_{if}-x_{jf}|^h )^\frac{1}{h} = max_{f}^h |x_{if}-x_{jf}| \tag{4}

2 定理证明

定理 1 的证明如下：

• 让 f_r (A_j = c_{k,j} | X) = \frac { n_{c_{k,j}} }{n} 为属性 A_j 的第 k 个标称属性 c_{k,j} 的相对频率，n 是 X 中对象的总数，n_{C_{k,j}} 是拥有标称属性 c_{k,j} 的对象的计数。
• 则有，相异性度量公式可推导为：

\sum_{i=1}^n d(X_i,Q) = \sum_{i=1}^n \sum_{j=1}^m \delta(x_{i,j},q_j) \\ = \sum_{i=1}^n ( \sum_{j=1}^m \delta(x_{i,j},q_j) ) = \sum_{i=1}^m n(1-\frac{n_{q_j}}{n}) = \sum n( 1-f_r(A_j = q_j | X) )

• 因为 n( 1-f_r(A_j = q_j | X) ) \geq 0 \, , \, 1 \leq j \leq m，若让 \sum_{i=1}^n d(X_i,Q) 最小化，则需让每一个 n( 1-f_r(A_j = q_j | X) ) 取最小值，即 f_r(A_j = q_j | X) 必须取最大值。

思考

参考

[1] Jiewei Han, Micheline Kamber and Jian Pei. 数据挖掘 (第三版) [M]. 机械工业出版社, 2018, 48-49.
[2] Bezdek J C. A convergence theorem for the fuzzy ISODATA clustering algorithms [J]. IEEE transactions on pattern analysis and machine intelligence, 1980 (1): 1-8.
[3] Ismail M A, Selim S Z. Fuzzy c-means: optimality of solutions and effective termination of the algorithm[J]. Pattern recognition, 1986, 19(6): 481-485.
[4] Park H S, Jun C H. A simple and fast algorithm for K-medoids clustering[J]. Expert systems with applications, 2009, 36(2): 3336-3341.