【机器学习】常用聚类算法

什么是聚类？

聚类的定性理解

聚类是机器学习的一类问题，它的目的是将一大堆样本进行分类。与更广为人知的分类算法的区别在于，分类算法在训练过程中提供了样本的类别（即属于监督学习），而聚类算法则不提供标签类别，仅仅提供数据样本（即属于无监督学习）。从另一个角度，分类算法的结果通常是一个训练好的分类器，可以在下次提供一个输入的时候判断出它属于什么类别；而聚类的结果则通常是样本的分类结果，并且在很多场合下作为后续处理的基准，例如电商平台对用户进行聚类，分出多个类别以后再进行针对性地推广。

聚类的数学定义

假设一个样本集：

$$D = \lbrace x_1, …, x_n \rbrace$$

聚类算法把这个样本集划分为 $m$ 个不相交的子集 $C_1, …, C_m$ 即簇。这些子集的并集是整个样本集：

$$C_1 \cup C_2 … \cup C_m = D$$

每个样本只能属于这些子集中的一个，即任何两个子集之间没有交集：

$$C_i \cap C_j = \emptyset, \forall i, j \in [1, n], i \neq j$$

同一个子集内部的各个样本之间尽可能相似，而不同子集的样本之间则尽可能不同。

常用的聚类算法

聚类算法按照聚类依据大致可以分为基于连通性的聚类、基于质心的聚类、基于概率分布的聚类、基于密度的聚类、基于图的聚类和基于网格的聚类等。

基于连通性的聚类

基于连通性的聚类算法的典型是层次聚类，它根据样本间的连通性构造簇，所有连通的样本属于同一个簇。下面介绍层次聚类的具体原理。

感性理解

首先来对层次聚类算法在干什么进行一个感性的理解。假设我们现在有一堆水果，其中有黄元帅、红富士、蛇果、白杏、红杏。对于聚类算法，首先这五种水果每一个都是一个簇，接下来对其中“距离最近”的水果进行聚类，例如，红富士和蛇果聚为一簇；接下来再找最近的进行聚类，举例来讲，可能是白杏和红杏聚为一簇；然后找最近的，例如黄元帅和“红富士与蛇果”聚为一类，最后把“白杏和红杏”及“黄元帅和红富士和蛇果”聚为一簇。这样就形成了自下而上的聚类层次，如下图（原谅我线画得不好）。

层次聚类示意

层次聚类基本步骤

有了以上对层次聚类的感性理解以后，我们可以很容易地提取出层次聚类的基本操作步骤：

计算每两个观测（即当前的簇）之间的距离。
将距离最近的两个观测聚为一类，将其看作一个整体来计算其与其他观测之间的距离。
重复上述步骤，直到所有的观测均被聚为一类。

聚类距离的计算

聚类距离的计算的难点主要在于簇间距离的计算，目前有许多方法来计算这一个距离。下面将介绍其中的一些，重点介绍应用最广泛的 Ward 算法。

Single Linkage

这个算法是以簇之间的最短距离来计算的，即

$$dist(C_1, C_2) = \underset{x_i \in C_1, x_j \in C_2} {min} \lbrace dist(x_i, x_j) \rbrace$$

由于以最短距离来计算簇间距离，因此两个很不相似的簇可能因为某两个极端数据点距离较近而被合并到一起。

Complete Linkage

这个算法与 Single Linkage 相反，是以簇之间的最长距离来计算的，即

$$dist(C_1, C_2) = \underset{x_i \in C_1, x_j \in C_2} {max} \lbrace dist(x_i, x_j) \rbrace$$

Complete Linkage 与 Single Linkage 的问题也相似，两个很相似的簇可能因为某两个极端数据点距离较远而不能合并到一起。

Average Linkage

这种算法以两个簇之间所有距离的平均值作为簇间距离，即

$$dist(C_1, C_2) = \frac{1}{|C_1| \cdot |C_2|} \underset {x_i \in C_1, x_j \in C_2}{\sum}dist \lbrace x_i, x_j \rbrace$$

相比前两种算法，这种算法从结果角度更合理，但是计算复杂度也大大提高，每次迭代需要把所有的距离都算一遍，耗时太久，而且得到的结果也不普适，所得到的簇倾向于拥有相同的直径。

Ward

Ward 法利用离差平方和（Sum of Squares of Deviations, SS）来进行距离的计算。离差平方和指的是各项与平均项之差的平方和，即

$$SS = \sum (x_i - \overline{x})^2$$

对于每一个簇，我们可以通过这个公式得到它的离差平方和，这个结果越小表示类内距离越小，越相似。那么如何利用这个公式来进行聚类呢？

将每一个点初始化为一个簇，此时，每一个簇的 SS 均为 0
计算所有簇的总 SS 和。
对每两个簇，计算将他们合并以后的新的 SS 值。
以总 SS 值最小的方式进行合并。
如果不是所有样本都合并为一个簇，则回到步骤 2 。

这里总 SS 值最小的方式也就是使得 $SS(C_i \cup C_j) - (SS(C_i) + SS(C_j))$ 最小的一种合并方式。

基于质心的聚类

基于质心的聚类，顾名思义，是根据每个簇的中心向量来将别的零散的样本归到簇中。典型的代表是 k-means 算法（k 均值算法）。

模型原理

k-means 算法假设如果一些数据被分为不同的类，那么同一类的数据之间按照某种算法应该距离很近，也就是说离得越近的数据越相似。有了这个假设，我们在利用 k-means 算法进行分类时，会尽可能将离得近的数据划分为一类。

假设我们要把数据 $\lbrace x_i \rbrace$ 分为 $k$ 类，经过聚类以后每一个数据所属的类别为 $\lbrace t_i \rbrace$ ，而这 $k$ 个聚类中心为 $\lbrace \mu_i \rbrace$，那么我们定义如下的损失函数：

$$L = \sum_{i = 1} ^ {n} (x_i - \mu_{t_i})^2$$

k-means 算法的目的就是寻找最佳的 $\lbrace t_i \rbrace$ 使得损失函数最小。这里有一个问题在于，我们的目的是寻找最佳的 $\lbrace t_i \rbrace$ ，但是在寻找的过程中，为了计算损失函数，我们需要用到 $\lbrace t_i \rbrace$ 和 $\lbrace \mu_i \rbrace$ 。同时这两个参数又是互相依赖的：要计算每一个聚类的中心我们需要知道每一个样本的分类结果，而要知道每一个样本的分类结果我们首先需要根据聚类中心来进行归类。

这个问题的解决用到了 EM 算法（最大期望算法）。EM 算法的大致思路是，当有两个未知的参数 $\alpha, \beta$ 互相依存时，不妨先假设其中的一个参数 $\alpha$ 的值，用 $\alpha$ 来计算 $\beta$ 的值，然后再用 $\beta$ 来重新计算 $\alpha$ 。进行多次迭代以后，这两个参数将逐渐趋于一个合理的值。更多关于 EM 算法的详细解释和证明这里不多展开，可以参考下面的链接。

【机器学习】EM——期望最大（非常详细）

基本步骤

利用 EM 算法，k-means 算法的基本步骤如下：

随机生成 k 个聚类中心点得到 $\lbrace \mu_i \rbrace$ 。
根据聚类中心点，将数据分为 k 类得到 $\lbrace t_i \rbrace$ 。分类的依据是，样本数据离哪个中心点近就归为哪一类。
根据第 2 步分号的类别，重新计算聚类中心点（如取均值）。
回到第 2 步，直到中心点不再变化或变化范围小于某一阈值。

下图是 k-means 算法的过程示意。

k-means

基于密度的聚类

基于密度的聚类算法的核心思想是根据样本某一邻域内的样本数量，即样本的空间密度，进行归类。这种算法可以找出形状不规则的簇，而且不需要指定簇的数量。典型的基于密度的聚类算法是 DBSCAN 算法和在此基础上改进的 OPTICS 算法。

DBSCAN 算法

算法相关概念

对于 DBSCAN 算法，我们需要提供两个参数，$(\epsilon, MinPts)$，其中 $\epsilon$ 表示某一样本的邻域的距离阈值，$MinPts$ 表示某一样本邻域内的样本数量的阈值。

假设有样本集 $D = \lbrace x_1, …, x_n \rbrace$ ，那么对 DBSCAN 算法，我们定义以下概念：

$\epsilon$-邻域：对于 $x_i \in D$ ，其 $\epsilon$-邻域为包含了样本集 $D$ 中到 $x_i$ 的距离不大于 $\epsilon$ 的样本的子样本集，即 $N_{\epsilon}(x_i) = \lbrace x_j \in D | dist(x_i, x_j) \leq \epsilon \rbrace$ ，这个子样本集的集合大小记为 $|N_\epsilon(x_i)|$ 。
核心对象：对于任意样本 $x_i \in D$ ，如果其 $\epsilon$-邻域对应的子样本集 $N_\epsilon(x_i)$ 包含至少 $MinPts$ 个样本，即如果 $|N_\epsilon(x_i)| \geq MinPts$ ，则称 $x_i$ 为一个核心对象。
密度直达：如果 $x_j$ 位于 $x_i$ 的 $\epsilon$-邻域中，且 $x_i$ 为核心对象，则称 $x_j$ 由 $x_i$ 密度直达。密度直达不具有对称性。
密度可达：对于 $x_i$ 和 $x_j$ ，如果存在样本序列 $p_1, p_2, …, p_T$ ，满足 $p_1 = x_i, p_T = x_j$ ，且 $\forall t \in [1, T)$ ，有 $p_{t+1}$ 能由 $p_t$ 密度直达，则称 $x_j$ 由 $x_i$ 密度可达。密度可达具有传递性，不具有对称性。
密度相连：对于 $x_i$ 和 $x_j$ ，如果存在核心对象样本 $x_k$ ，使得 $x_i$ 和 $x_j$ 均由 $x_k$ 密度可达，则称 $x_i$ 和 $x_j$ 密度相连。密度相连具有对称性。

从下图可以很容易看出理解上述定义，图中 $MinPts=5$ ，红色的点都是核心对象，因为其 $\epsilon$ -邻域至少有 5 个样本。黑色的样本是非核心对象。所有核心对象密度直达的样本在以红色核心对象为中心的超球体内，如果不在超球体内，则不能密度直达。图中用绿色箭头连起来的核心对象组成了密度可达的样本序列。在这些密度可达的样本序列的 $\epsilon $-邻域内所有的样本相互都是密度相连的。

DBSCAN

算法聚类思想

DBSCAN 的基本思想非常简单：将由密度可达关系得出最大密度相连的样本集合作为一簇。在这个簇中可以由一个或多个核心对象。有一个核心对象的情况很简单，这个簇里的所有非核心对象都在核心对象的 $\epsilon$-邻域内；而如果由多个核心对象，那么在簇里的任何一个核心对象的 $\epsilon$-邻域中一定有一个其他的核心对象，否则这两个核心对象无法密度可达。这些核心对象的 $\epsilon$-邻域里的所有的样本的集合组成一个 DBSCAN 簇。

那么如何找到这样的簇呢？DBSCAN 算法采用的方法很简单。首先随机选择一个未被归类的核心对象，然后从这个核心对象拓展它的所有的密度可达的对象，这些对象是一个簇；然后再去寻找下一个未被归类的核心对象并拓展；如此循环，直到所有的核心对象都被归类。这样运行完以后可能有少量的样本仍然未被归类，这些样本被视为噪声。

如果某个样本到两个核心对象的距离都小于 $\epsilon$ ，但这两个核心对象并不密度可达，即不属于同一个簇，那么这个样本的归类如何界定？通常的做法是先来后到，即这个样本被归类为第一次拓展到它的那一个类，DBSCAN 算法也因此不完全稳定。

基本步骤

假设有样本集 $D = \lbrace x_1, …, x_n \rbrace$ ，输入的邻域参数为 $(\epsilon, MinPts)$ ，那么 DBSCAN 算法步骤如下：

初始化核心对象集合 $\Omega = \emptyset$ ，初始化聚类簇数 $k = 0$ ，初始化未访问样本集 $\Gamma = D$ ，簇划分 $C = \emptyset$ 。
$i$ 从 $1$ 到 $n$ 遍历每一个样本，如果这个样本是核心对象则将其加入核心对象样本集合： $\Omega = \Omega \cup \lbrace x_i \rbrace$ 。
如果核心对象集合 $\Omega = \emptyset$ ，则算法结束，否则进入第 4 步。
从核心对象集合 $\Omega$ 中随机选择一个核心对象 $o$ ，初始化当前簇核心对象集合 $\Omega_{cur} = \lbrace o \rbrace$ ，初始化类别序号 $k = k + 1$ ，初始化当前簇样本集合 $C_k = \lbrace o \rbrace$ ，更新未访问样本集合 $\Gamma = \Gamma - \lbrace o \rbrace$ 。
如果当前簇核心对象集合 $\Omega_{cur} = \emptyset$ ，则当前聚类簇 $C_k$ 生成完毕，更新簇划分 $C = C \cup C_k$ ，更新核心对象集合 $\Omega = \Omega - C_k$ ，跳转到第 3 步。否则更新核心对象集合 $\Omega = \Omega - C_k$ 。
在当前簇核心对象集合 $\Omega_{cur}$ 中取出一个核心对象 $o’$ ，通过邻域距离阈值 $\epsilon$ 找出 $\epsilon$-邻域子样本集 $N_\epsilon(o’)$ ，令 $\Delta = N_\epsilon(o’) \cap \Gamma$ ，更新当前簇样本集合 $C_k = C_k \cup \Delta$ ，更新未访问样本集合 $\Gamma = \Gamma - \Delta$ ，更新 $\Omega_{cur} = \Omega_{cur} \cup (\Delta \cap \Omega) - o’$ ，进入第 5 步。

OPTICS 算法

前面所讲的 DBSCAN 算法对密度的设定是固定的，因此如果样本不同集群之间密度相差较大，那么 DBSCAN 算法便会存在对输入参数敏感的问题，在选择输入的 $(\epsilon, MinPts)$ 时会比较苦恼。于是便有了 OPTICS 算法，该算法解决了输入参数敏感的问题。

算法相关概念

在 DBSCAN 算法引入的概念的基础上， OPTICS 算法额外引入了两个概念定义：

核心距离(core-distance)：对于一个核心对象样本 $x_i$ 和给定的 $(\epsilon, MinPts)$ ，使得 $x_i$ 成为核心对象的最小邻域半径称为 $x$ 的核心距离，即如果 $N_{\epsilon}^i(x)$ 表示集合 $N_\epsilon(x)$ 中与节点 $x$ 第 $i$ 近邻的节点，那么有

$$cd(x_i) =dist(x_i, N _\epsilon ^{MinPts}(x_i))$$

可达距离(reachability-distance)：对于一个核心对象样本 $x_i$ 、另一个样本 $x_j$ 以及给定的 $(\epsilon, MinPts)$ ，$x_j$ 关于 $x_i$ 的可达距离定义为使得“ $x_i$ 为核心点”且“ $x_j$ 从 $x_i$ 直接密度可达” 同时成立的最小邻域半径，即

$$rd(x_i, x_j) = max \lbrace cd(x_i), dist(x_i, x_j) \rbrace$$

核心距离这个概念的引入的意义是解决 $\epsilon$ 固定的问题，即每一个点的核心距离会根据集群密度自动调整。某种意义上来讲，在 OPTICS 算法中提供的 $\epsilon$ 可以是无穷大（或者说不提供），在输入参数中仍然保留 $\epsilon$ 的意义是加快程序效率（否则对于任意一个样本，整个样本集都在它的密度直达范围内，遍历起来很费时间）。

基本步骤

假设有样本集 $D = \lbrace x_1, …, x_n \rbrace$ ，输入的邻域参数为 $(\epsilon, MinPts)$ ，那么 OPTICS 算法步骤如下：

初始化核心对象集合 $\Omega = \emptyset$ ，初始化未访问样本集 $\Gamma = D$ ，初始化结果有序队列 $p$ 、种子有序队列 $seeds$。
$i$ 从 $1$ 到 $n$ 遍历每一个样本，如果这个样本是核心对象则将其加入核心对象样本集合： $\Omega = \Omega \cup \lbrace x_i \rbrace$ 。
如果核心对象集合 $\Omega = \emptyset$ ，则算法结束，否则进入第 4 步。
从核心对象集合 $\Omega$ 中随机选择一个核心对象 $o$ ，将 $o$ 压入结果有序队列 $p$ 中，更新未访问样本集合 $\Gamma = \Gamma - \lbrace o \rbrace$ 。
通过邻域距离阈值 $\epsilon$ 找出 $\epsilon$-邻域子样本集 $N_\epsilon(o)$ ，令 $\Delta = N_\epsilon(o) \cap \Gamma$ ，将 $\Delta$ 集合中的元素按照可达距离依次压入种子有序队列 $seeds$ 。
如果种子有序队列 $seeds$ 为空，则跳转到第 3 步，否则，从 $seeds$ 中弹出可达距离最近的样本 $seed$ ，将 $seed$ 压入结果有序队列 $p$ 中，更新未访问样本集合 $\Gamma = \Gamma - \lbrace seed \rbrace$ 。
如果 $seed$ 不是核心对象，则跳转到第 6 步，否则，令 $\Delta = N_\epsilon(o) \cap \Gamma$ ，对于 $\Delta$ 中的每一个元素，如果它不存在于 $seeds$ 中，则压入其中，否则检查新的可达距离是否更近，如果是则更新。跳转到第 6 步。

通过 OPTICS 的结果进行聚类

由上述步骤可以看到，OPTICS 算法的结果不像大多数聚类算法一样给出聚类的结果，而是给出了一个有序队列 $p$ ，那么如何通过这个有序队列来得到我们想要的聚类结果呢？

首先我们可以把有序队列进行可视化，以可达距离为纵轴，按有序队列顺序绘制图像，如下：

optics

可以看到在图像上很明显的表现出了四个凹槽，每一个凹槽就代表了一个聚类。如何通过算法得到这样的结果呢？

设置 $\epsilon$ 阈值

一个很简单的方法是设置一个 $\epsilon$ 阈值，反映在图上则是绘制一条平行于横轴的直线，在这条横轴上方的点均视为噪声，而对于这条直线下方的一个凹槽，则将其视为一个簇。这个方法可以很简单的进行分类，缺点是分类结果会比较粗糙，而且对簇间密度差异较大的问题解决的并不完美（设置 $\epsilon$ 阈值实际上还是设置了固定的密度，与 DBSCAN 算法类似，只是因为从可视化结果上得出因此相对更加准确）。

计算陡度

另一个更加常用的方法是计算曲线的陡度。我们可以设置一个参数 $\xi$ ，当扫描到图像曲线的下降陡度大于 $\xi$ 时，意味着合并一个簇的开始；当扫描到图像曲线的上升陡度大于 $\xi$ 时，意味着合并一个簇的结束。这个做法由两个主要的有点：一是它摆脱了固定的密度，对样本簇间密度差异较大的情况由更好的表现；二是这种方法可以识别出簇的嵌套（例如我们首先扫描到一个下降的陡度意味着合并簇的开始，而在我们扫到这个簇的结束之前，又遇到了一个符合簇开始条件的陡度，说明簇之间存在嵌套）。

基于图的聚类

基于图的算法把样本数据看作图的顶点，根据数据点之间的距离构造边，形成带权重的图。通过图的切割实现聚类，即将图切分成多个子图，这些子图就是对应的簇。这种算法的典型是 Chinese Whisper 算法和谱聚类算法。（谱聚类看起来比较复杂，暂时先咕着）。

Chinese Whisper 算法

Chinese Whisper 算法这个名字源自一个同名的游戏，这个游戏的玩法是从队伍首端通过耳语或肢体语言传达一句话至队尾。这个算法的思路也非常相似，是通过相邻的点来进行类别的传递。

基本步骤

假设有样本集 $D = \lbrace x_1, …, x_n \rbrace$ ，输入相似度阈值 $\xi$ 和迭代次数 $n$，那么 Chinese Whisper 算法的步骤如下：

遍历样本集，将每一个样本单独作为一类，计算每两个样本之间的相似度，相似度高于阈值 $\xi$ 的样本之间建立无向边，边权为相似度。
将样本随机排序，遍历每一个样本，选取该样本的邻居中边权最大的那一个样本，将它的分类作为该样本的分类；如果邻居中有多个样本的分类相同，则该分类的权重为这些边权和，然后进行比较。
多次执行第 2 步迭代直到达到迭代次数 $n$ 。

在模型和阈值选择恰当的情况下，经过 10 次左右的迭代便能得到比较好的分类效果。

算法缺点

Chinese Whisper 算法的一个很大的缺点在于随机性很大，因为每次迭代是随机访问样本的，这就导致一些比较模糊的样本由于不同的遍历顺序会得到不同点分类结果。

chinesewhisper

如图所示的样本集，假设所有边权均为 1 ，那么，如果遍历次序为 $1 \rightarrow 2 \rightarrow 3$ ，那么节点 $\lbrace 1, 2 \rbrace$ 会先被归为一类，然后样本 $3$ 将归类到 $\lbrace 1, 2, 3 \rbrace$ 中；而如果遍历次序为 $4 \rightarrow 5 \rightarrow 3$ ，那么样本 $3$ 将被归类到 $\lbrace 3, 4, 5 \rbrace$ 中。

基于网格的聚类

基于网格的聚类是一种能有效发现各种形状的簇，同时降低了复杂度、对输入参数敏感的聚类算法，常用的又 CLIQUE 算法和 STING 算法。

CLIQUE 算法

CLIQUE 算法是基于网格的聚类算法，但它同时也结合了基于密度的聚类算法的思想。它是把多维空间按照步长划分为一个个网格，然后通过每一个网格的阈值来将它们分为稠密网格和非稠密网格。每当找到一个稠密网格，就从它开始向邻接的稠密网格开始拓展，这样就找到了一个聚类簇。这是 CLIQUE 算法的基本思想。

基本步骤

根据 CLIQUE 算法的基本思想，我们可以很简单的把这一算法的基本过程写出来：

假设有样本集 $D = \lbrace x_1, …, x_n \rbrace$ ，输入网格的步长 $\Delta$ 和密度的阈值 $\xi$ ，那么 CLIQUE 算法的步骤如下：

把样本集所在的数据空间划分根据输入网格的步长 $\Delta$ 划分为不相重叠的子单元集合，初始化稠密网格集合 $\Omega = \emptyset$ ，初始化聚类簇数 $k = 0$ 。
计算每一个网格 $\omega_i$ 的密度，根据输入密度阈值判断这个网格是否为稠密网格，如果是则加入稠密网格集合：$\Omega = \Omega \cup \lbrace \omega_i \rbrace$ 。
如果稠密网格集合 $\Omega = \emptyset$ ，则进入第 7 步，否则进入第 4 步。
从稠密网格集合 $\Omega$ 中随机选取一个稠密网格 $\omega$ ，初始化当前簇网格集合 $\Omega_{cur} = \lbrace \omega \rbrace$ ，初始化类别序号 $k = k + 1$ ，将网格 $\omega$ 标记为第 $k$ 个簇，更新稠密网格集合 $\Omega = \Omega - \lbrace \omega \rbrace$ 。
如果当前簇网格集合 $\Omega_{cur} = \emptyset$ ，则当前聚类簇 $C_k$ 生成完毕，跳转到第 3 步。否则进入第 6 步。
从当前簇网格集合 $\Omega_{cur}$ 中取出一个稠密网格 $\omega’$ ，获取 $\omega’$ 的所有稠密邻接网格集合 $\Gamma = N_\Delta(\omega’) \cap \Omega$ （假设用 $N_\Delta(\omega’)$ 表示 $\omega’$ 的所有邻接网格），将 $\Gamma$ 中的所有网格标记为第 $k$ 个簇，更新当前簇网格集合 $\Omega_{cur} = \Omega_{cur} \cup \Gamma - \omega’$ ，更新稠密网格集合 $\Omega = \Omega - \Gamma$ ，进入第 5 步。
遍历整个样本集 $D$ ，将每一个元素 $x_i$ 标记为它所在的网格的簇标记。

寻找稠密网格的优化方式

上述算法看起来效果不错，但当样本维数较高的时候，子空间的数量会指数级增长，如果仅用简单的遍历所有子空间来寻找稠密网格，时间复杂度会非常大。 Rakesh Agrawal 提出了一种“由下至上”的识别方法来优化时间复杂度。这种优化方式基于稠密网格的单调性，即：

如果一个 $k$ 维的网格是稠密网格，那么这个网格的所有 $k - 1$ 维子网格也都是稠密网格。

基于此，我们提出以下寻找稠密网格的方式：

遍历原始数据集，得到其所有的 $1$ 维的稠密网格单元。
当得到在 $k - 1$ 维上的稠密网格单元后，我们遍历所有这些单元，从中寻找 $k - 1$ 维稠密网格单元 $u_i$ 和 $u_j$ ，使得它们满足以下条件：

$$ \begin{align} u_i \cdot a_1 &= u_j \cdot a_1\\ u_i \cdot a_2 &= u_j \cdot a_2\\ &…\\ u_i \cdot a_{k - 2} &= u_j \cdot a_{k - 2}\\ u_i \cdot a_{k - 1} &< u_j \cdot a_{k - 1}\\ \end{align} $$

这里的 $u_i \cdot a_i$ 表示 $u_i$ 的第 $i$ 维，也就是 $u_i$ 和 $u_j$ 在前 $k - 2$ 维都是相同的，而最后一维不同（之所以用小于而非不等于是防止重复），那么它们在 $k$ 维空间应当是可以组合起来的，于是我们得到了候选的 $k$ 维稠密网格。

遍历一遍原始数据集，从候选的 $k$ 维稠密网格中确定真正的 $k$ 维稠密网格。如果 $k$ 已经达到数据样本维数，则算法结束，否则跳转到第 2 步。

STING 算法

STING 算法的思想是将搜索过程划分为层，每一层的一个网格都在下一层被划分为更小的网格。对每一个网格，我们计算它的统计信息。当我们需要查询符合某一条件的样本时，我们从第一层开始查找，对符合条件的网格，我们往下一层进行更细致的查找，直到最底层。这样的好处是，我们不用计算所有的样本，每一层都会抛弃掉不相关的那些样本，所需的计算量会越来越少。

虽然 STING 算法没有显示地给出聚类结果，但是每次查询的返回结果实际上就是符合某一条件的聚类。

sting

网格统计信息

我们提到 STING 算法会对网格计算他们的统计信息，这个信息当然可以随着问题的需要而改变。普遍来说，可以统计以下信息：

n: 网格中的样本数量
m: 网格中所有样本值的平均值
s: 网格中所有样本值的标准偏差
min: 网格中样本值的最小值
max: 网格中样本值的最大值

对于这些信息的计算，我们采用如下方式：

首先对最底层的网格进行计算。在这一层，直接利用原始样本数据进行计算。
当第 $k$ 层计算完毕，我们可以利用这一层的结果去计算 $k - 1$ 层的结果，即：

$$ \begin{align} n’ &= \sum_i n_i\\ m’ &= \frac{\sum_i m_i \cdot n_i}{n}\\ s’ &= \sqrt{\frac{\sum_i (s_i^2 + m_i^2) \cdot n_i}{n} - m^2}\\ min’ &= min(min_i)\\ max’ &= max(max_i)\\ \end{align} $$

算法步骤：

假设有样本集 $D = \lbrace x_1, …, x_n \rbrace$ ，输入参数网格的步长 $\Delta$ 以及要查询的属性值 $\alpha$ ，STING 算法步骤如下：

根据输入网格的步长 $\Delta$ 划分不同层次的网格，并计算网格的统计值，初始化网格集合 $\Omega$ 为最上层的网格。
根据属性值 $\alpha$ ，将 $\Omega$ 中的网格更新为符合 $\alpha$ 的网格。
查找当前层的下一层，将 $\Omega$ 中的网格更新为 $\Omega$ 中的网格的下一层细分网格。
当查找到最底层或符合需求则算法停止。