一种基于节点置信半径的P2P网络分布式聚类方法

摘要

本发明公开一种基于节点置信半径的P2P网络分布式聚类方法；采用一种基于Fisher判别来确定聚类置信半径的分布式K-Means聚类算法，通过对每个P2P节点的数据进行自主学习，网络中节点通过分别应用Fisher线性判别率，确定同一类数据在节点上的稠密和稀疏分布，从而确定聚类的置信半径并指导下一步的聚类，根据网络上各个节点的数据分布动态地计算出置信半径，确定节点上的聚类置信半径，指导下一次聚类及聚类的迭代过程，在保证聚类效果的同时，减少分布式网络上聚类的迭代次数以节省带宽，提高网络的应用水平。

说明书

技术领域

本发明涉及计算机网络通信、数据挖掘及分布式聚类领域，尤其涉及一种P2P网络（对等网络）分布式聚类方法。

背景技术

聚类(Clustering) 分析是指对一个已给的数据对象集合，依照一定的规则将数据对象分成多类的过程，聚类使得同一聚类中的数据对象彼此尽可能相似，不同聚类中的数据对象彼此尽可能相异。迄今为止，人们已经提出了许多聚类方法，例如K-Means, DBSCAN, Cure, Birch等。在诸多的聚类方法中，K-Means是应用最广泛的方法之一，这是由于相比其他方法，K-Means方法具有方法简单易实现且聚类效果稳定的特点。

传统的K-Means聚类方法分析处理是基于单个中心服务器上的数据。近年来，文件共享、视频点播等分布式的P2P网络日渐成为互联网的主要应用，由于P2P网络是一种不依赖于集中服务器的对等网络，网络中的任意节点均可以作为服务器提供资源，也可以作为客户机下载资源，所以，在P2P网络中，数据资源散落地分布在网络各个节点上。由于站点在数据存储量、信息安全及隐私保护等方面的限制，把不同站点的海量或者隐私数据全部集中到某一个中心服务器进行全局聚类是不可能的，因此研究适用于分布式环境下的K-Means聚类方法尤其重要。

在P2P环境下的分布式聚类方法中，Eisenhardt等人提出一种Probe/Echo（探测/回应）机制的分布式聚类方法，该方法通过在网络中对节点聚类进行同步，取得较为精确的聚类效果，但这种方法的缺陷是网络带宽使用率高、带宽消耗非常大。Jin 等人提出了DFEKM方法，该方法通过计算聚类的置信半径方式来完成聚类，但该方法并没有提出一个合适的置信半径计算方法，对所有节点采用固定阈值参数来确定置信半径大小，由于聚类只能在分布式节点上局部地进行，该方法所设定的固定半径并没有考虑数据在节点上的分布式及局部性的特点，仍然需要较多的迭代数来完成聚类。

发明内容

为了节约分布式网路聚类所需带宽并尽可能保持聚类的精度，考虑到同一类的数据中存在稠密和稀疏的数据分布，如果在聚类过程中能保持稠密数据的类别属性不发生改变，则近似认为聚类基本完成，而不考虑稀疏数据对聚类的影响。应用此原理，考虑数据在P2P网络节点中的分布式状况，本发明提出一种基于节点置信半径的P2P网络分布式聚类方法，基于Fisher判别来确定聚类置信半径的分布式K-Means聚类算法，在保持聚类精度的同时，大幅减少分布式网络聚类过程中所需的迭代数，节约网络带宽。

本发明的技术方案是采用如下步骤：

步骤1：在网络中随机选择初始节点作为聚类发起节点，并且随机选择k个数据作为初始聚类中心；

步骤2：聚类发起节点将初始聚类中心作为Probe消息发送给其所有直接相邻的邻居节点，以便聚类发起节点自主地更新局部聚类中心并更新自身的聚类置信半径；每一个邻居节点也都继续Probe消息转发过程，并等待从其邻居节点接收Echo消息，以完成局部聚类；

步骤3：聚类发起节点等待其邻居节点回送Echo消息，若接收到其所有邻居节点的Echo消息，网络中所有节点的局部聚类已完成，转到步骤4，否则继续等待邻居节点回送Echo消息；其中，Echo消息中包含节点根据自身数据及结合它的直接相邻的邻居节点聚类数据所完成的局部聚类后所形成的局部聚类中心、所得局部聚类中每个类所包含的数据对象数，以及本节点是否需要继续迭代的逻辑变量；

步骤4：聚类发起节点将接收到的Echo消息中所包含的局部聚类信息与自身节点的局部聚类信息进行合并形成整个网络的聚类中心，并应用Fisher线性判别准则计算该节点的置信半径；

步骤5：聚类发起节点计算保留的上次聚类中心和本次聚类完成后所形成聚类中心的距离，若该距离小于置信半径并且接收到的逻辑变量都为false，则聚类过程结束；否则转到步骤2，开始下一轮聚类过程。

步骤2所述局部聚类过程具体是：

1）节点p_n从其邻居节点接受消息；

2）节点p_n进行消息判断，若为Echo消息，则进行步骤7）；否则为Probe消息，转步骤3）继续判断；

3）节点p_n进行是否首次收到Probe消息判断，如果否，则转步骤8）；如果是，则继续步骤4）；

4）节点p_n进行首次接收Probe消息处理，将消息处理数置1；将首次发送Probe消息的节点设为父节点p；

5）节点p_n将收到的Probe消息转发给除了父节点p以外的所有邻居节点；

6）节点p_n将自身包含的局部数据按照其到Probe消息中所含聚类中心的距离进行聚类，将每一个局部数据分类到聚类中心距离最小的某一个聚类中，计算节点p_n的局部聚类中心和置信半径；

7）邻居节点返回了Echo消息给节点p_n，节点p_n将接收消息处理数累加1；

8）邻居节点发送了Probe消息给节点p_n，节点p_n将接收消息处理数累加1，只对返回Echo消息的邻居节点进行局部聚类结果的合并；

9）节点p_n进行消息处理数判断，如果消息处理数不等于邻居数则转到步骤1）继续等待从邻居节点接收消息；否则执行步骤10）；

10）判断本节点p_n前后两次聚类中心的距离是否超过置信半径或者接收到Echo消息中所包含的逻辑变量不全为false，若判断正确，该节点或者其邻居节点进一步聚类，进行步骤11）；如果判断不成立，则执行步骤12）；

11）节点p_n将逻辑变量置true，以指示初始聚类节点继续下一个聚类迭代过程；

12）节点p_n将逻辑变量置false，节点p_n及以该节点为父节点p的其他节点已完成聚类；

13）节点p_n将接收到的Echo消息中所包含的聚类信息与本节点的聚类信息进行局部聚类中心的合并与更新，并形成节点p_n的Echo消息；

14）节点p_n发送Echo消息给父节点p。

本发明节约分布式网路聚类所需带宽并尽可能保持聚类的精度，考虑到同一类的数据中存在稠密和稀疏的数据分布，采用一种基于Fisher判别来确定聚类置信半径的分布式K-Means聚类算法，Fisher线性判别是模式识别中的分类方法，该方法通过寻找最佳分类线，将两类数据投影到分类线上，使得不同类数据之间的距离最大，并且使得类内的数据密集分布。网络中节点通过分别应用Fisher线性判别率，确定同一类数据在节点上的稠密和稀疏分布，从而确定聚类的置信半径并指导下一步的聚类，因此，本发明的有益效果是：通过对每个P2P节点的数据进行自主学习，根据网络上各个节点的数据分布动态地计算出置信半径，确定节点上的聚类置信半径，指导下一次聚类及聚类的迭代过程，在保证聚类效果的同时，减少分布式网络上聚类的迭代次数以节省带宽，最终提高网络的应用水平。

附图说明

图1是本发明方法的主流程图；

图2是节点消息处理流程图；

图3是节点消息传递图；

图4是本发明方法对一组数据对象进行聚类的数据分布图；

图5是聚类结束后聚类效果的比较图；

图6是聚类结束后所需迭代数比较图。

具体实施方式

参照图1，本发明应用Probe/Echo的消息传递机制，进行基于节点置信半径的分布式聚类，主要过程如下：

步骤101，初始化过程，在网络中随机选择初始节点作为聚类发起节点，并且随机选择k个数据作为初始聚类中心，接着执行步骤102；

步骤102，聚类发起节点将初始聚类中心作为Probe消息发送给其所有直接相邻的邻居节点（以下的邻居节点均指直接相邻的邻居节点），以便聚类发起节点自主地更新局部聚类中心并更新自身的聚类置信半径；每一个邻居节点也都继续Probe消息转发过程，并等待从其邻居节点接收Echo消息，以完成局部聚类。接着执行步骤103；

步骤103，聚类发起节点等待其邻居节点回送Echo消息，若接收到其所有邻居节点的Echo消息，说明网络所有节点的局部聚类已完成，转到步骤104，否则在步骤103继续等待邻居节点回送Echo消息。

步骤104，聚类发起节点将接收到Echo消息中所包含的局部聚类信息与自身节点的局部聚类信息进行合并形成整个网络的聚类中心，并计算置信半径，完成一次K-Means聚类过程。Echo消息中包含节点根据自身数据及结合它的邻居节点聚类数据所完成的局部聚类后所形成的局部聚类中心、所得局部聚类中每个类所包含的数据对象数。接着执行步骤105；

步骤105，进行聚类结束条件判断，聚类发起节点计算保留的上次聚类中心和本次聚类完成后所形成聚类中心的距离，如果是第一次聚类就是初始聚类中心和本次完成聚类后形成的聚类中心之间的距离，如果不是第一次，显然是上次和本次的聚类中心之间的距离，如果距离小于置信半径并且接收到的Further变量都为false，说明所有节点的聚类结果较为稳定，聚类过程结束；否则转到步骤102，开始下一轮聚类过程。

其中，Probe消息中包含各个类的聚类中心；Echo消息中包含节点根据自身数据及结合它的直接相邻的邻居节点聚类数据所完成的局部聚类后所形成的局部聚类中心、所得局部聚类中每个类所包含的数据对象数，以及本节点是否需要继续迭代的逻辑变量Further（逻辑变量，表示节点是否需要再次迭代，其取值只有true和false），如果节点的前后两次聚类中心距离大于本节点的置信半径，Further为true，表示需要继续进行下一次迭代；相反，则设置Further为false。

其中，节点置信半径的计算应用Fisher线性判别准则，Fisher线性判别是模式识别中的分类方法，该方法通过寻找最佳分类线，将两类数据投影到分类线上，使得不同类数据之间的距离最大，并且使得类内的数据密集分布。网络中节点通过分别应用Fisher线性判别率，确定同一类数据在节点上的稠密和稀疏分布，从而确定聚类的置信半径并指导下一步的聚类。Fisher线性判别准则应用如下：假设某一类数据对象共有                                                个数据对象，考虑将其分为两类问题，假设个数据对象的中心为，对个数据对象，分别计算其到中心的距离，并按照升序排列，得到一个按照距离排序的集合，及其对应的数据对象集合为。其中，是到按照到聚类中心距离排序的第i个数据对象，其到中心的距离为。Fisher线性判别率表示为：

                             （1）

其中，和分别表示所有数据对象以X_r为分隔点的两个聚类均值距离以及距离方差和。

                           （2）

                             （3）

其中，是到的数据对象上到的距离均值；相似地，是到上的距离均值。则是到的数据对象上到的距离方差，是到上的距离方差。则是为以 和为两类的Fisher线性判别率。

所有数据对象集上的Fisher线性判别率越大，说明通过该方法得到的两类数据越明显，从而找到以聚类中心的数据稠密与稀疏的分界点。当fisher判别率最大时，假设为，此时的为聚类的最佳分隔数据点，所得置信半径为：

                               （4）

参照图2，基于节点Fisher置信半径的P2P网络分布式聚类过程中，某个节点（假设为p_n）的Probe/Echo消息及局部聚类处理过程具体如下：

步骤201，节点p_n从其邻居节点接受消息；接着执行步骤202；

步骤202，节点p_n进行消息判断，如果为Echo消息，则进行步骤207；否则为Probe消息，转步骤203继续判断；

步骤203，节点p_n进行是否首次收到Probe消息判断，如果不是首次接收到Probe消息，则进行步骤208；如果是首次接收Probe消息，则继续步骤204；

步骤204，节点p_n进行首次接收Probe消息处理，将消息处理数（接收变量）置1；将首次发送Probe消息的节点设为父节点，假设为p节点。接着执行步骤205；

步骤205，节点p_n将收到的Probe消息转发给除了父节点p以外的所有邻居节点；接着执行步骤206；

步骤206，节点p_n将自身包含的局部数据按照其到Probe消息中所含聚类中心的距离进行聚类，将每一个局部数据分类到聚类中心距离最小的某一个聚类中，然后应用公式（5）计算节点p_n的局部聚类中心，以及应用公式（1）-（4）计算节点p_n的置信半径；接着执行步骤207；

步骤207，邻居节点返回了Echo消息给节点p_n，节点p_n将接收消息处理数累加1。继续执行步骤208；

步骤208，邻居节点发送了Probe消息给节点p_n，节点p_n将接收消息处理数累加1，说明该邻居节点不是将节点p_n作为父节点，因此不需要将该邻居的局部聚类结果返回给节点p_n来完成聚类消息的合并；即网络中的节点只对返回Echo消息的邻居节点进行局部聚类结果的合并，从而保证聚类结果的唯一性。接着执行步骤209；

步骤209，节点p_n进行消息处理数判断，如果消息处理数不等于邻居数则转到步骤201继续等待从邻居节点接收消息；否则执行步骤210。

步骤210，判断本节点p_n前后两次聚类中心的距离是否超过置信半径或者接收到Echo消息中所包含的Further变量不全为false，若判断正确，说明该节点或者其邻居节点需要进一步聚类，进行步骤211；如果判断不成立，则执行步骤212；

步骤211，节点p_n将Further置true，以指示初始聚类节点继续下一个聚类迭代过程。接着执行步骤212；

步骤212，节点p_n将Further置false，说明节点p_n及以该节点为父节点的其他节点已完成聚类，不需要初始聚类节点继续下一个聚类迭代过程。接着执行步骤213；

步骤213，节点p_n将接收到的Echo消息中所包含的聚类信息与本节点的聚类信息应用以下公式（5）-（7）进行局部聚类中心的合并与更新，并形成节点p_n的Echo消息。接着执行步骤214；

局部聚类中心的合并与更新的公式如下：

                                  (5)

             （6）

                          （7）

其中，代表网络中某个节点p_n的第j类的局部聚类中心；X是节点p_n中的数据对象；代表节点p_n的第j类的数据对象数；代表节点p_n的第i个邻居节点内第j个聚类的局部聚类中心；代表节点p_n的第i个邻居节点内第j个聚类的数据对象数；N代表节点p_n收到返回Echo消息的邻居数。和分别是进过局部聚类合并更新后的节点p_n的第j类的局部聚类中心和数据对象数，这和与逻辑变量Further作为节点p_n的Echo信息的参数返回给它的父节点。

步骤214，节点p_n发送Echo消息给父节点p，结束节点p_n的消息处理和局部聚类过程。

以下参见图3的节点消息传递图来进一步具体说明网络中节点所处理的整个聚类过程：首先，假设节点A为随机选择的初始聚类节点，然后在节点数据中随机选择k个数据作为初始聚类中心。其次，节点A发送Probe消息给他的所有邻居节点B、C、D，并等待B、C、D节点回送Echo消息，以完成一次聚类过程。B、C、D也与节点A的做法类似，向它们自己的邻居节点重复转发Probe消息及等待他的邻居回送Echo消息完成局部聚类过程。接着，当A节点收到B、C、D节点的回送Echo消息后，说明除了A节点，网络所有节点的局部聚类都已完成，A开始进行最后的聚类合并计算。再次，A节点将接收到的Echo消息中所包含的局部聚类信息与自身节点的局部聚类信息应用公式（5）-（7）进行合并，形成整个网络的聚类中心；并应用公式（1）-（4）计算A节点的置信半径，完成一次K-Means聚类过程。最后，A节点进行聚类结束条件判断，计算保留的上次聚类中心和本次聚类完成后所形成聚类中心的距离。如果是第一次聚类就是初始聚类中心和本次完成聚类后形成的聚类中心之间的距离，如果不是第一次聚类，则是上次保留的聚类中心和本次形成的聚类中心之间的距离。如果这个距离小于置信半径并且接收到的B、C、D节点返回Echo消息中Further变量都为false，说明所有节点的聚类结果较为稳定，聚类过程结束；否则再次发送Probe消息给它所有的邻居节点B、C、D，开始下一轮聚类过程。

以上是节点A作为聚类发起点所完成的聚类过程。在Probe/Echo消息传递的过程中，结合图3，以节点C为例，网络中其他节点都完成如下行为：

步骤1. 首先，节点C等待从它的邻居A，D，F，G接收消息。

步骤2. 节点C收到消息后进行判断，如果是Echo消息，则进行步骤7；否则为Probe消息，转步骤3继续判断；

步骤3．节点C进行是否首次收到Probe消息判断，如果不是首次接收到Probe消息，则进行步骤8；如果是首次接收Probe消息，假设首次接受的Probe消息来自节点A，继续步骤4；

步骤4．节点C进行首次接收Probe消息处理，将消息处理数（received变量）置1；并且将首次发送Probe消息的节点A设为父亲节点，接着执行步骤5；

步骤5．节点C将收到的Probe消息转发给，除了父节点A以外的所有邻居节点F，G，D；接着执行步骤6。假设D已经接收了节点A的首次Probe消息，因此节点D不做处理，只是把D节点的消息处理数累加1 。由于D除了父节点A外只有节点C是邻居节点，在收到节点C的Probe消息后， D节点将形成局部聚类结果作为Echo消息返回给A节点。

步骤6．节点C将自身包含的局部数据按照其到Probe消息中所含聚类中心的距离进行聚类，将每一个局部数据分类到聚类中心距离最小的某一个聚类中，然后应用公式（5）计算节点C的局部聚类中心，以及应用公式（1）-（4）计算节点C的置信半径；接着执行步骤9；

步骤7．邻居节点F，G形成局部聚类并返回Echo消息给节点C，节点C在每一个邻居节点返回Echo后，都将Recived消息处理数累加1。继续执行步骤9；

步骤8．若邻居节点发送了Probe消息给节点C，假设为D节点，则将节点C的Recived消息处理数累加1。因为邻居节点D的父节点是节点A，因此在节点D完成局部聚类后，不需要将该邻居的局部聚类结果返回给节点C来完成聚类消息的合并，而是将节点D的局部聚类结果返回给它的父节点节点A，从而保证聚类结果的唯一性。接着执行步骤9；

步骤9．节点C进行消息处理数判断，如果消息处理数不等于邻居数则转到步骤1继续等待从邻居节点接收消息；否则执行步骤10。

步骤10，判断节点C前后两次聚类中心的距离是否超过置信半径，或者接收到Echo消息中所包含的Further变量不全为false。若判断正确，说明该节点或者其邻居节点需要进一步聚类，进行步骤11；如果判断不成立，则执行步骤12；

步骤11，节点C将Further置true，以指示初始聚类节点A继续下一个聚类迭代过程。接着执行步骤13；

步骤12，节点C将Further置false，说明节点C及以该节点为父节点的其他节点已完成局部聚类，不需要初始聚类节点A继续下一个聚类迭代过程。接着执行步骤13；

步骤13，节点C将接收到的Echo消息中所包含的聚类信息与本节点的聚类信息应用公式（5）-（7）进行局部聚类中心的合并与更新，并形成节点C的Echo消息；

步骤14，节点C发送Echo消息给父节点A，此时结束节点C的消息处理和局部聚类过程。

鉴于上述具体实施方式的技术方案，以下提供本发明的一个实施例。

实施例

从3类2维高斯混合分布中取60000个数据作为数据对象，所采用的高斯分布的均值分别为：（0，0），（6，2），（8，8），协方差矩阵均为二维单位矩阵，同时设置500个网络节点，将60000个数据对象平均分配给500个网络节点，聚类的k值设为3。

图4描述了所用60000个数据作为数据聚类对象的分布图。其中，不同的颜色和形状代表不同高斯分布的数据，菱形、星形和三角形代表高斯分布数据的均值在（0，0），（6，2），（8，8），协方差矩阵为二维单位矩阵的三类数据。

应用以上数据到500个网络节点上，分别对DFEKM方法和本发明方法分别运行50次所得到的结果如图5和图6所示，其中DFEKM所采用的置信半径阈值固定为0.05，本发明方法在聚类过程中采用fisher线性判别率来动态获取节点数据的置信半径。

图5是聚类结束后聚类精度比较图，其中作为精度衡量标准的PMM（percentage membership mismatch）定义如下：

                     （5）

其中代表数据点在原始数据中所属类别，代表x通过分布式聚类后所属类别，则代表原始数据通过分布式聚类算法聚类后所得到的结果与原始数据之间的误差率。 的值越小，说明聚类结果越接近原始数据。在图5中，虚线代表实验数据经过DFEKM聚类后与实验数据本身相比较的PMM值；实线代表实验数据经过本发明方法聚类后与实验数据本身相比较的PMM值。从图中可以看到，应用DFEKM和本发明方法所取得的PMM最大值分别为1.25和2.47，运行50次的平均PMM值分别为0.20和0.24，可以发现两种方法与原始数据的最大误差率都小于2.5%，平均误差率都小于0.25%,说明本发明方法在聚类效果的精度上十分可观，而且本发明方法非常接近DFEKM聚类方法的聚类结果。

图6描述了运行聚类方法所需的迭代次数，这反映了聚类方法在网络中所需的带宽数，迭代数越多，所消耗的带宽越多。在图中，实线代表本发明方法运行50次每次的所需迭代数。实验发现本发明方法所需最大迭代数为4，所需迭代数的均值为1.82。虚线代表运行DFEKM聚类方法50次所得迭代数，实验发现该方法所得最大迭代数为6，迭代数均值为2.52。可以看出，本发明方法在带宽使用上较DFEKM聚类方法有将近30%的提升。

从图5、6中可以看到，本发明方法相比DFEKM方法，在保持了较高聚类精度的同时，大幅节约了网络带宽，从而提高了分布式P2P网络的使用效果。