面向海量数据近似快速聚类和索引方法

1.一种基于分块递归信息传递的聚类方法，其特征在于包括如下步骤：
输入包括N个数据对象的集合，这些对象之间的相似度矩阵SN×N，其中 S[i，j]≤0(i＝1ΛN，j＝1ΛN)，我们对其进行基于分块递归信息传递的聚类：
1)将相似度矩阵SN×N平均分成k部分，接着对每部分再平均分成m部分，... 并照此类推下去：
$S=\left(\begin{array}{ccc}\left(\begin{array}{ccc}{S}_{11}& L& S_{1m}\\ M& O& M\\ S_{m1}& L& S_{\mathrm{mm}}\end{array}\right)& L& \left(\begin{array}{cc}L& S_{1k}\\ O& M\end{array}\right)\\ M& O& M\\ \left(\begin{array}{cc}M& O\\ S_{k1}& L\end{array}\right)& L& \left(\begin{array}{cc}O& M\\ L& S_{\mathrm{kk}}\end{array}\right)\end{array}\right)$
2)把子矩阵S11，S22，L Smm，L Skk通过基于消息传播的AP聚类方法迭代计 算，得到k个消息传播子矩阵A11，A22，L，Amm，L Akk；
3)将步骤2)中的消息传播子矩阵A11，A22，L，Amm，L Akk在对角线上合并，将其 余部分设为0，得到整个数据集的消息传播矩阵A′：
$A^{\prime }=\left(\begin{array}{ccc}\left(\begin{array}{ccc}{A}_{11}& L& A_{1m}\\ M& O& M\\ A_{m1}& L& A_{\mathrm{mm}}\end{array}\right)& L& 0\\ M& O& M\\ 0& L& \left(\begin{array}{cc}O& M\\ L& A_{\mathrm{kk}}\end{array}\right)\end{array}\right)$
除A11，A22，L，Amm，L Akk以外，消息传播矩阵A′的其余部分为0；
4)以A′作为递归分块信息传递的聚类方法的起始信息传递矩阵AN×N，作为 迭代起点再利用AP聚类方法得到最终聚类结果。
2.根据权利要求1所述的一种基于分块递归信息传递的聚类方法，其特征在 于所述的对相似度矩阵SN×N划分成为k部分：其中，k或m必须是大于1，小 于C是所期望类的数目的最大值，子矩阵S11，S22，L Smm，L Skk都是方阵， 子矩阵S11…Sk-1，k-1的大小都是子矩阵Skk的大小是
3.根据权利要求1所述的一种基于分块递归信息传递的聚类方法，其特征在 于所述的基于消息传播的AP聚类方法迭代计算方法的步骤如下：
(1)根据以下公式更新节点之间的R：
$r(i,k)\leftarrow s(i,k)-\underset{k^{\prime }s.t.k^{\prime }\ne k}{\max }\{a(i,k^{\prime })+s(i,k^{\prime })\}---1$
(2)根据以下公式更新节点之间的A：
$a(i,k)\leftarrow \min \{0,r(k,k)+\underset{i^{\prime }s.t.i^{\prime }\notin \{i,k\}}{\Sigma }\max \{0,r(i^{\prime },k)\left\}\right\}---2$
$a(k,k)\leftarrow \underset{i^{\prime }s.t.i^{\prime }\ne k}{\Sigma }\max \{0,r(i^{\prime },k)\}---3$
(3)不断重复步骤(1)和步骤(2)过程，直到收敛，或达到了最大迭代次 数。
4.一种基于近似计算的海量数据聚类方法，其特征在于包括如下步骤：
输入包括N个数据对象的集合，这些对象之间的相似度矩阵为SN×N，其中 S[i，j]≤0(i＝1ΛN，j＝1ΛN)。我们对其进行近似的快速信息传递的聚类：
1)给定大规模数据集合X，其中包含p个数据点，根据代表性最大的原则随 机挑选q个综合能力强的数据点，q远小于p，对这q个节点之间的形成的距 离矩阵应用AP聚类算法，得到其聚类结果；
2)通过步骤1)得到了n个聚类集合，分别为C1，C2，L，Cn，在每个聚类集合 中计算节点离聚类质心最小距离min_distance[ci]，对于剩下的p-q个节点再进 行分类，数据集中其余数据点i划分到某个cj类的规则如下，当该节点离开n个 聚类质心的距离小于某个min_distance[ci]时，则将这个节点纳入ci聚类集合；
3)如果还有m个节点通过步骤2)无法纳入任何聚类集合，当m小于设定 阈值，则对m个节点直接应用原始的AP聚类算法；当m大于设定阈值，则 重复递归调用使用步骤1)和步骤2)，分别得到聚类结果；
4)将步骤2)和步骤3)得到的聚类结果进行合并，对每个类中的结果重新计 算，从而得到每个类的最佳聚类中心。
5.根据权利要求4所述的一种基于近似计算的海量数据聚类方法，其特征 在于，所述的数据集中其余数据点i划分到某个cj类的规则如下：
1)distance(i，cj)＜max_distance(cj)；
2)distance(i，cj)＝min(distance(i，c1)，distance(i，c2)，...，distance(i，cn))。

暂无