分布式高维数据的近似聚类

### 分布式高维数据的近似聚类 #### 1. 引言 聚类是数据挖掘的主要任务之一，它旨在将数据集划分为不同的组（即簇），同时最大化簇内相似度并最小化簇间相似度。传统的聚类算法需要完全访问待分析的数据，所有数据必须位于处理数据的站点。然而，如今大量异构、复杂的数据存储在通过局域网或广域网相互连接的不同独立工作的计算机上，例如分布式移动网络、传感器网络或超市连锁店等。此外，一些国际公司的数据分布在不同地区，由于带宽限制或安全等原因，数据无法传输到中央站点。 许多现实世界的分布式数据集由高维特征向量建模的对象组成，如在分布式非结构化文档集合中应用聚类算法时，可创建向量空间模型，每个文档由高维特征向量表示，类似的情况还出现在图像检索和分子生物学等领域。 为了从分布式数据中提取知识，而无需事先统一数据，催生了分布式数据库知识发现（DKDD）这一新兴研究领域。本文提出了一种通用方法，用于从分布在多个站点的高维特征向量中提取知识，具体展示了该方法在分布式密度聚类中的优势。该方法通过一定数量的字节尽可能准确地描述局部特征向量，将这些近似值发送到服务器站点，基于合适的距离函数进行全局服务器聚类。 #### 2. 相关工作 - **集体层次聚类算法**：针对垂直分布数据集提出的“集体层次聚类算法”，采用单链接聚类，本文主要关注水平分布数据集。 - **基于质心的层次聚类技术**：通过合并局部生成的聚类层次结构，为高维水平分布数据集提供了一种基于质心的层次聚类技术，但该方法仅适用于基于距离的层次分布式聚类方法，而本文旨在引入一种通用方法。 - **基于密度的分布式聚类算法**：基于密度分区聚类算法DBSCAN提出的基于密度的分布式聚类算法，通过确定合适的局部对象代表其他局部对象，基于这些代表执行全局DBSCAN算法，这些方法是为DBSCAN量身定制的。 本文的目标是引入一种适用于分布式数据挖掘（DDM）的通用方法，展示其在分布式聚类算法中的优势。与上述特定的分布式聚类方法不同，本文的方法不受本地客户端数量增加的影响，仅取决于允许的总传输成本，即从本地客户端传输到服务器的字节数。为了降低传输成本，接下来将介绍一种合适的客户端侧近似技术来描述高维特征向量。 #### 3. 客户端侧近似 ##### 3.1 数据集近似 本部分的目标是通过一些（扁平）目录页面粗略描述整个数据集，保守地近似整个数据空间。寻找最小边界矩形（MBRs）的问题与聚类相关，这里主要关注将数据空间划分为矩形长方体，类似于索引结构中的目录页面，这些长方体应尽可能呈方形，以实现高效的查询处理。通过应用k - 均值聚类算法，可以实现各边长度变化较小的长方体。该算法将数据集近似为k个质心，每个向量分配到其最近的质心，分配到同一质心的所有特征向量形成一个簇，并由该簇所有向量的MBR近似。由于簇的质心往往接近MBR的中心，这些MBR的形状趋于方形，间接最小化了k个MBR的空间对角线的平均长度。 ##### 3.2 特征向量近似 在将本地数据空间划分为由MBR表示的k个簇后，将每个特征向量v相对于其对应的最小边界矩形MBRCluster(v)的左下角进行表示。 **定义1 特征向量** 一个d维特征向量$v = (v_1, ..., v_d)^t \in \mathbb{R}^d$的每个特征$v_i$由字节序列$<b_{i,1}, ..., b_{i,m}>$表示，其中每个字节由w位组成。特征值$v_i$的计算公式为： $v_i = \sum_{j = 1}^{m} val(b_{i,j})$，其中$val(b_{i,j}) = b_{i,j} \cdot 2^{w(m - j)}$ 为了清晰起见，假设d维特征向量的每个特征由长度为m的字节串表示。将通过保守的近似层次结构描述每个特征向量，在每一层使用更多字节更精确地近似特征向量，遍历整个近似层次结构可重构正确的特征向量。 客户端首先计算v的所有字节$b_{i,j}$的字节排名，然后将最有意义的字节与位置信息一起发送到服务器。 **定义2 排名和近似函数** 设W是所有长度为$m \cdot d$的字节序列的集合，$v = (v_1, ..., v_d)^t \in \mathbb{R}^d$是一个特征向量，每个特征$v_i$由字节序列$<b_{i,1}, ..., b_{i,m}>$表示。需要一个字节排名函数$f_{rank}: \mathbb{R}^d \to W$和一个特征向量近似函数$f_{app}: W \times \{0, ..., m \cdot d\} \to [\mathbb{R} \times \mathbb{R}]^d$，满足以下属性： - $f_{rank}(v) = <b_1, ..., b_{m \cdot d}>$，其中$b_l = b_{\pi(i,j)}$，$\pi_{rank}: \{1, ..., d\} \times \{1, ..., m\} \to \{1, ..., m \cdot d\}$是双射排名函数。 - $f_{app}(f_{rank}(v), 0) = MBRCluster(v)$，$f_{app}(f_{rank}(v), L_1) \subseteq f_{app}(f_{rank}(v), L_2)$当且仅当$L_1 \geq L_2$，且$f_{app}(f_{rank}(v), m \cdot d) = v$ 服务器收到一定数量的L字节后，可以计算近似区域$A = f_{app}(f_{rank}(v), L)$。以下介绍三种高维特征向量的近似技术： **3.2.1 面向字节的近似（BOA）** 由于每个特征的第一个字节包含最重要的信息，通过双射函数$\pi: \{1, ..., d\} \times \{1, ..., m\} \to \{1, ..., m \cdot d\}$根据字节的j位置对字节$b_{i,j}$进行排名，即$\pi(i,j) < \pi(i',j')$当且仅当$(j < j')$或$(j = j'$且$i < i')$。 服务器计算近似区域$a = f_{app}(f_{rank}(v), L) = [l_1, u_1] \times ... \times [l_d, u_d]$如下： $l_i = \be