可扩展并行聚类与分布式数据集相似性挖掘

### 可扩展并行聚类与分布式数据集相似性挖掘 在数据挖掘领域，并行算法和数据集相似性是两个重要的研究方向。并行算法能够提高数据处理的效率，而数据集相似性的挖掘则有助于更好地理解和分析数据。下面将详细介绍相关的技术和实验结果。 #### 并行AutoClass算法 并行AutoClass（P - AutoClass）是基于贝叶斯方法的AutoClass算法的并行实现，旨在处理大型数据集中的最优分类问题。该算法在分布式内存多指令流多数据流（MIMD）计算机上通过数据分区和局部计算来实现。 - **并行update_wts函数** - 在AutoClass中，每个数据项的类成员关系以概率形式表示，权重用于表达这种关系。 - update_wts函数计算每个活动类中每个数据项的权重$w_{ij}$，使其成为相对于当前参数化的归一化类概率。 - 并行版本的该函数首先在每个处理元素上计算数据集本地分区中每个数据项的权重$w_{ij}$，并对每个类$j$的权重$w_j$（$w_j = \sum_{i} w_{ij}$）进行求和。 - 然后，所有处理器之间交换部分$w_j$值，并在每个处理器中进行求和，以确保每个处理器中的值相同。这一过程使用全局归约操作（Allreduce）实现，该操作将所有进程中的本地副本求和，并将结果广播到所有处理器。 ```mermaid graph LR A[计算本地权重$w_{ij}$] --> B[本地求和$w_j$] B --> C[交换$w_j$值] C --> D[全局求和$w_j$] ``` - **并行update_parameters函数** - update_parameters函数为每个类计算一组类后验参数值，这些值指定了类在各个属性上的分布。 - 该函数由三个嵌套循环组成，外部循环扫描所有类，中间循环分析每个类的所有属性，内部循环读取所有数据项并使用其值计算类参数。 - 在并行化时，所有处理器并行执行参数的部分计算，然后在每个处理器上收集所有本地值，用于计算分类参数的全局值。同样使用全局归约操作实现参数值的交换。 ```mermaid graph LR A[并行计算本地参数] --> B[收集本地值] B --> C[全局归约计算全局参数] ``` P - AutoClass使用消息传递接口（MPI）工具包在Meiko Computing Surface 2上实现，基于顺序AutoClass C的3.3版本。由于MPI的广泛可用性，P - AutoClass几乎可以在从超级计算机到PC集群的所有并行机器上运行。 #### 实验结果 在Meiko CS 2上进行了实验，该计算机最多连接10个SPARC处理器，采用胖树拓扑结构，通信带宽为50 Mbytes/s。使用了一个由100000个元组组成的合成数据集，每个元组包含两个实属性。实验中使用了从5000个元组到整个数据集的不同数据分区，并要求系统从不同数量的簇开始寻找最佳聚类。 - **执行时间**：随着使用的处理器数量增加，P - AutoClass的总执行时间显著减少，尤其是对于大型数据集。数据集越大，时间增益越明显。 | 处理器数量 | 5000元组 | 10000元组 | 20000元组 | 30000元组 | 40000元组 | 50000元组 | 100000元组 | | --- | --- | --- | --- | --- | --- | --- | --- | | 1 | 较长 | 较长 | 较长 | 较长 | 较长 | 较长 | 较长 | | 2 | 减少 | 减少 | 减少 | 减少 | 减少 | 减少 | 减少 | | 4 | 进一步减少 | 进一步减少 | 进一步减少 | 进一步减少 | 进一步减少 | 进一步减少 | 进一步减少 | | 8 | 显著减少 | 显著减少 | 显著减少 | 显著减少 | 显著减少 | 显著减少 | 显著减少 | | 10 | 继