本发明公开了聚类实现方法及系统。包括：由主控节点对样本分块，并将分块样本分配给至少两个计算节点，由各计算节点并行参与计算，将本地样本归属到对应聚类中，并对每一个聚类统计本地各样本的样本值的和值传送给合并节点，再由合并节点得到每一个聚类的虚拟聚类中心点信息，并传送给主控节点，由主控节点判断是否进行聚类中心点更新，以及是否启动下一轮聚类计算。本发明通过多个节点参与聚类实现过程，在聚类计算及合并过程中通过采用多个节点并行处理，解决了现有技术对海量数据无法实现聚类处理及处理效率低的问题。
步骤1、主控节点对样本分块，并将分块样本分配给至少两个计算节点，将分配的分块样本和每一个聚类的聚类中心点信息传送给每个所述计算节点；
步骤2、每个所述计算节点分别计算分配的分块样本中每个样本在样本空间中的对应样本点与各聚类中心点的距离，将每个样本归属到所述距离最小的对应聚类中心点所属聚类；对每一个聚类分别统计本地属于该聚类的样本数量以及计算属于该聚类的各样本的样本值的和值，并传送所述样本数量和所述和值给合并节点；
步骤3、所述合并节点对每一个聚类根据每个所述计算节点传送的所述样本数量和所述和值，求取均值，得到每一个聚类的虚拟聚类中心点信息，并传送给所述主控节点；
步骤4、所述主控节点根据接收的每一个聚类的虚拟聚类中心点信息和当前保存的每一个聚类的聚类中心点信息以及设定的中心点更新策略，当确定出至少由一个聚类的虚拟聚类中心点信息更新当前保存的该聚类的聚类中心点信息时，发送本次更新后的和本次未更新的每一个聚类的聚类中心点信息给所述至少两个计算节点，重复上述步骤2和步骤3；
当确定出每一个聚类的聚类中心点信息都不再更新时，将最后一次更新后的聚类中心点信息作为每一个聚类的实际聚类中心点信息；
所述合并节点至少包括两个；由所述主控节点预先分配每个合并节点进行合并的对应聚类；且合并节点的最大数量与聚类的数量相等；
由所述主控节点预先分配每个合并节点进行合并的对应聚类，包括：
由所述主控节点给每个所述合并节点分配至少一个进行合并的聚类。
2.如权利要求1所述的聚类实现方法，其特征在于，还包括：
所述主控节点将每一个聚类的所述实际聚类中心点信息传送给每个所述计算节点； 每个所述计算节点分别计算分配的分块样本中每个样本在样本空间中的对应样本点与各实际聚类中心点的距离，将每个样本归属到所述距离最小的对应实际聚类中心点所属聚类，并返回样本标识与所属聚类的聚类标识给所述主控节点；
所述主控节点根据每个所述计算节点返回的样本标识与所属聚类的聚类标识，确定出每个样本所属聚类。
3.如权利要求1或2所述的聚类实现方法，其特征在于，步骤2中所述传送所述样本数量和所述和值给合并节点，具体包括：所述计算节点根据每个合并节点进行合并的对应聚类，将本地统计出的属于所述对应聚类的样本数量以及计算出的属于所述对应聚类的各样本的样本值的和值，上报给对应的合并节点；或者每个合并节点根据自身进行合并的对应聚类，分别向每个所述计算节点请求上传所述对应聚类的统计信息；每个所述计算节点向每个合并节点返回其请求的所述对应聚类在本地统计出的样本数量以及计算出的属于所述对应聚类的各样本的样本值的和值。
步骤1、主控节点对样本分块，并将分块样本分配给至少两个计算节点，将分配的分块样本和每一个聚类的聚类中心点信息传送给每个所述计算节点；
步骤2、每个所述计算节点分别计算分配的分块样本中每个样本在样本空间中的对应样本点与各聚类中心点的距离，将每个样本归属到所述距离最小的对应聚类中心点所属聚类；分别统计本地属于每一个聚类的样本数量以及计算属于该聚类的各样本包含的每一个样本属性的属性值的和值，并传送所述样本数量、以及携带聚类标识和样本属性标识的所述和值给合并节点；
步骤3、所述合并节点对每一个聚类的每一个样本属性根据每个所述计算节点传送的所述样本数量和所述和值，计算出每一个聚类的每一个样本属性的属性值的均值，并传送给所述主控节点； 步骤4、所述主控节点根据接收的每一个聚类的每一个样本属性的属性值的均值，得到每一个聚类的虚拟聚类中心点信息，并根据当前保存的每一个聚类的聚类中心点信息以及设定的中心点更新策略，当确定出至少由一个聚类的虚拟聚类中心点信息更新当前保存的该聚类的聚类中心点信息时，发送本次更新后的和本次未更新的每一个聚类的聚类中心点信息给所述至少两个计算节点，重复上述步骤2和步骤3；当确定出每一个聚类的聚类中心点信息都不再更新时，将最后一次更新后的聚类中心点信息作为每一个聚类的实际聚类中心点信息；
所述合并节点至少包括两个；由所述主控节点预先分配每个合并节点进行合并的对应聚类的对应样本属性；且合并节点的最大数量与所述聚类的数量和所述样本的样本属性的数量的乘积相等；
由所述主控节点预先分配每个合并节点进行合并的对应样本属性，包括：
由所述主控节点给每个所述合并节点分配至少一个聚类的进行合并的一个样本属性。
5.如权利要求4所述的聚类实现方法，其特征在于，还包括：
所述主控节点将每一个聚类的所述实际聚类中心点信息传送给每个所述计算节点；
每个所述计算节点分别计算分配的分块样本中每个样本在样本空间中的对应样本点与各实际聚类中心点的距离，将每个样本归属到所述距离最小的对应实际聚类中心点所属聚类，并返回样本标识与所属聚类的聚类标识给所述主控节点；
所述主控节点根据每个所述计算节点返回的样本标识与所属聚类的聚类标识，确定出每个样本所属聚类。
6.如权利要求4或5所述的聚类实现方法，其特征在于，步骤2中所述传送所述样本数量、以及携带聚类标识和样本属性标识的所述和值给合并节点，具体包括： 所述计算节点根据每个合并节点进行合并的对应聚类的对应样本属性，将本地统计出的对应聚类的样本数量以及计算出的对应聚类的所述对应样本属性的属性值的和值，上报给对应的合并节点；或者每个合并节点根据自身进行合并的对应聚类的对应样本属性，分别向每个所述计算节点请求上传所述对应聚类的对应样本属性的统计信息；每个所述计算节点根据每个所述合并节点请求的对应聚类的对应样本属性，向每个合并节点返回本地统计出的对应聚类的样本数量、以及计算出的该聚类的所述对应样本属性的属性值的和值，并携带与所述和值对应的聚类标识和样本属性标识。
7.一种聚类实现系统，其特征在于，包括：主控节点、至少两个计算节点及合并节点；
所述主控节点，用于对样本分块，并将分块样本分配给所述至少两个计算节点，将分配的分块样本和每一个聚类的聚类中心点信息传送给每个所述计算节点；以及接收所述合并节点传送的每一个聚类的虚拟聚类中心点信息；并根据接收的每一个聚类的虚拟聚类中心点信息和当前保存的每一个聚类的聚类中心点信息以及设定的中心点更新策略，当确定出至少由一个聚类的虚拟聚类中心点信息更新当前保存的该聚类的聚类中心点信息时，发送本次更新后的和本次未更新的每一个聚类的聚类中心点信息给所述至少两个计算节点，当确定出每一个聚类的聚类中心点信息都不再更新时，将最后一次更新后的聚类中心点信息作为每一个聚类的实际聚类中心点信息；
所述计算节点，用于分别计算分配的分块样本中每个样本在样本空间中的对应样本点与各聚类中心点的距离，将每个样本归属到所述距离最小的对应聚类中心点所属聚类；对每一个聚类分别统计本地属于该聚类的样本数量以及计算属于该聚类的各样本的样本值的和值，并传送所述样本数量和所述和值给合并节点； 所述合并节点，用于对每一个聚类根据每个所述计算节点传送的所述样本数量和所述和值，求取均值，得到每一个聚类的虚拟聚类中心点信息，并传送给所述主控节点；
所述合并节点至少包括两个，所述合并节点的最大数量与所述聚类的数量相等；
所述主控节点还用于，预先给每个合并节点分配至少一个进行合并的聚类。
8.如权利要求7所述的聚类实现系统，其特征在于，所述所述主控节点还用于，将每一个聚类的所述实际聚类中心点信息传送给每个所述计算节点；以及根据每个所述计算节点返回的样本标识与所属聚类的聚类标识，确定出每个样本所属聚类；
每个所述计算节点还用于，分别计算分配的分块样本中每个样本在样本空间中的对应样本点与各实际聚类中心点的距离，将每个样本归属到所述距离最小的对应实际聚类中心点所属聚类，并返回样本标识与所属聚类的聚类标识给所述主控节点。
9.如权利要求7所述的聚类实现系统，其特征在于，所述计算节点和所述合并节点全部为不同的节点；或者全部计算节点或部分计算节点为合并节点；或者
10.一种聚类实现系统，其特征在于，包括：主控节点、至少两个计算节点及合并节点；
所述主控节点，用于对样本分块，并将分块样本分配给至少两个计算节点，将分配的分块样本和每一个聚类的聚类中心点信息传送给每个所述计算节点；以及接收所述合并节点传送的每一个聚类的每一个样本属性的属性值的均值；并根据接收的每一个聚类的每一个样本属性的属性值的均值，得到每一个聚类 的虚拟聚类中心点信息，根据当前保存的每一个聚类的聚类中心点信息以及设定的中心点更新策略，当确定出至少由一个聚类的虚拟聚类中心点信息更新当前保存的该聚类的聚类中心点信息时，发送本次更新后的和本次未更新的每一个聚类的聚类中心点信息给所述至少两个计算节点；当确定出每一个聚类的聚类中心点信息都不再更新时，将最后一次更新后的聚类中心点信息作为每一个聚类的实际聚类中心点信息；
所述计算节点，用于分别计算分配的分块样本中每个样本在样本空间中的对应样本点与各聚类中心点的距离，将每个样本归属到所述距离最小的对应聚类中心点所属聚类；分别统计本地属于每一个聚类的样本数量以及计算属于该聚类的各样本包含的每一个样本属性的属性值的和值，并传送所述样本数量、以及携带聚类标识和样本属性标识的所述和值给合并节点；
所述合并节点，用于对每一个聚类的每一个样本属性根据每个所述计算节点传送的所述样本数量和所述和值，计算出每一个聚类的每一个样本属性的属性值的均值，并传送给所述主控节点；
所述合并节点至少包括两个，所述合并节点的最大数量与所述聚类的数量和所述样本的样本属性的数量的乘积相等；
所述主控节点还用于，预先给每个合并节点分配至少一个聚类的进行合并的一个样本属性。
11.如权利要求10所述的聚类实现系统，其特征在于，所述主控节点还用于，将每一个聚类的所述实际聚类中心点信息传送给每个所述计算节点；以及根据每个所述计算节点返回的样本标识与所属聚类的聚类标识，确定出每个样本所属聚类；
每个所述计算节点，还用于分别计算分配的分块样本中每个样本在样本空间中的对应样本点与各实际聚类中心点的距离，将每个样本归属到所述距离最小的对应实际聚类中心点所属聚类，并返回样本标识与所属聚类的聚类标识给所述主控节点。
12.如权利要求10所述的聚类实现系统，其特征在于，所述计算节点和所述合并节点全部为不同的节点；或者全部计算节点或部分计算节点为合并节点；或者
聚类实现方法及系统
技术领域
[0001] 本发明涉及数据挖掘领域，尤其涉及海量样本数据的聚类实现方法及相应系统。
背景技术
[0002] 在当前数据挖掘领域，已有的聚类算法可以分为几类，包括基于划分的方法，基于层次的方法，基于密度的方法，基于网格的方法以及基于模型的方法等。
[0003] 进行数据挖掘时，需要将对全部数据进行逐条计算及分析，算法时间复杂度高。海量数据是对各种聚类算法的一个挑战。已有的聚类算法大都还只是停留在实验室阶段，对于海量数据，有些算法或者不能进行有效处理，或者处理效率很低。
[0004] Kmeans算法是一种基于距离的聚类实现方法，通过计算样本点之间的距离，以判断样本之间的类群关系。
[0005] Kmeans算法的基本原理为：
[0006] 根据设置的聚类，为每一个聚类指定一个初始的聚类中心点(即初始随机指定样本空间中的样本点为一个聚类的聚类中心点)；分别计算数据库中的每一个样本在样本空间中的对应样本点与每一个聚类中心点的距离，将每一个样本归属到距离最小的对应聚类中心点所属聚类中。对每一个聚类分别统计本地属于该聚类的样本数量以及计算属于该聚类的各样本的样本值的和值，用和值除以样本数量求取均值，得到本轮计算中每一个聚类的对应虚拟聚类中心点；再计算每一个聚类的虚拟聚类中心点与对应的聚类中心点之间的距离，具体的距离计算方法可以采用现有技术数据挖掘中可以采用的欧氏距离计算法、巴氏距离计算法以及马氏距离计算法等，当两者之间的距离大于设定的距离阈值时，用每一个聚类的虚拟聚类中心点更新其对应的聚类中心点，开始下一轮计算，直到每一个聚类的聚类中心点都不再需要更新后，结束流程，将最后一次更新后的聚类中心点作为每一个聚类的实际聚类中心点。最后输出每一个聚类的实际聚类中心点，以及每个样本所归属的聚类。
[0007] 上述聚类实现方法，对于少量样本，可以方便地在单机上实现。但对于海量样本而言，一方面由于单机内存容量有限，不可能读入海量的样本数据；另一方面，由于聚类过程中需要进行聚类中心点的多轮更新计算过程，处理时间很长，在实际的数据业务应用中，效率很低。
[0008] 因此，对于实际应用中海量数据的处理，如何有效地提升处理效率是数据挖掘中需要加以解决的一个主要问题。
发明内容
[0009] 本发明实施例提供聚类实现方法及聚类实现系统，通过采用多个节点并行处理，解决现有技术对海量数据无法实现聚类处理及处理效率低的问题。
[0010] 本发明实施例提供的一种聚类实现方法包括：
[0011] 步骤1、主控节点对样本分块，并将分块样本分配给至少两个计算节点，将分配的分块样本和每一个聚类的聚类中心点信息传送给每个所述计算节点；
[0012] 步骤2、每个所述计算节点分别计算分配的分块样本中每个样本在样本空间中的对应样本点与各聚类中心点的距离，将每个样本归属到所述距离最小的对应聚类中心点所属聚类；对每一个聚类分别统计本地属于该聚类的样本数量以及计算属于该聚类的各样本的样本值的和值，并传送所述样本数量和所述和值给合并节点；
[0013] 步骤3、所述合并节点对每一个聚类根据每个所述计算节点传送的所述样本数量和所述和值，求取均值，得到每一个聚类的虚拟聚类中心点信息，并传送给所述主控节点；
[0014] 步骤4、所述主控节点根据接收的每一个聚类的虚拟聚类中心点信息和当前保存的每一个聚类的聚类中心点信息以及设定的中心点更新策略，当确定出至少由一个聚类的虚拟聚类中心点信息更新当前保存的该聚类的聚类中心点信息时，发送本次更新后的和本次未更新的每一个聚类的聚类中心点信息给所述至少两个计算节点，重复上述步骤2和步骤3；当确定出每一个聚类的聚类中心点信息都不再更新时，将最后一次更新后的聚类中心点信息作为每一个聚类的实际聚类中心点信息。
[0015] 本发明实施例提供的另一种聚类实现方法，包括：
[0016] 步骤1、主控节点对样本分块，并将分块样本分配给至少两个计算节点，将分配的分块样本和每一个聚类的聚类中心点信息传送给每个所述计算节点；
[0017] 步骤2、每个所述计算节点分别计算分配的分块样本中每个样本在样本空间中的对应样本点与各聚类中心点的距离，将每个样本归属到所述距离最小的对应聚类中心点所属聚类；分别统计本地属于每一个聚类的样本数量以及计算属于该聚类的各样本包含的每一个样本属性的属性值的和值，并传送所述样本数量、以及携带聚类标识和样本属性标识的所述和值给合并节点；
[0018] 步骤3、所述合并节点对每一个聚类的每一个样本属性根据每个所述计算节点传送的所述样本数量和所述和值，计算出每一个聚类的每一个样本属性的属性值的均值，并传送给所述主控节点；
[0019] 步骤4、所述主控节点根据接收的每一个聚类的每一个样本属性的属性值的均值，得到每一个聚类的虚拟聚类中心点信息，并根据当前保存的每一个聚类的聚类中心点信息以及设定的中心点更新策略，当确定出至少由一个聚类的虚拟聚类中心点信息更新当前保存的该聚类的聚类中心点信息时，发送本次更新后的和本次未更新的每一个聚类的聚类中心点信息给所述至少两个计算节点，重复上述步骤2和步骤3；当确定出每一个聚类的聚类中心点信息都不再更新时，将最后一次更新后的聚类中心点信息作为每一个聚类的实际聚类中心点信息。
[0020] 本发明实施例提供的一种聚类实现系统，包括：主控节点、至少两个计算节点及合并节点；
[0021] 所述主控节点，用于对样本分块，并将分块样本分配给所述至少两个计算节点，将分配的分块样本和每一个聚类的聚类中心点信息传送给每个所述计算节点；以及[0022] 接收所述合并节点传送的每一个聚类的虚拟聚类中心点信息；并根据接收的每一个聚类的虚拟聚类中心点信息和当前保存的每一个聚类的聚类中心点信息以及设定的中心点更新策略，当确定出至少由一个聚类的虚拟聚类中心点信息更新当前保存的该聚类的聚类中心点信息时，发送本次更新后的和本次未更新的每一个聚类的聚类中心点信息给所述至少两个计算节点，当确定出每一个聚类的聚类中心点信息都不再更新时，将最后一次更新后的聚类中心点信息作为每一个聚类的实际聚类中心点信息；
[0023] 所述计算节点，用于分别计算分配的分块样本中每个样本在样本空间中的对应样本点与各聚类中心点的距离，将每个样本归属到所述距离最小的对应聚类中心点所属聚类；对每一个聚类分别统计本地属于该聚类的样本数量以及计算属于该聚类的各样本的样本值的和值，并传送所述样本数量和所述和值给合并节点；
[0024] 所述合并节点，用于对每一个聚类根据每个所述计算节点传送的所述样本数量和所述和值，求取均值，得到每一个聚类的虚拟聚类中心点信息，并传送给所述主控节点。
[0025] 本发明实施例提供的另一种聚类实现系统，包括：主控节点、至少两个计算节点及合并节点；
[0026] 所述主控节点，用于对样本分块，并将分块样本分配给至少两个计算节点，将分配的分块样本和每一个聚类的聚类中心点信息传送给每个所述计算节点；以及[0027] 接收所述合并节点传送的每一个聚类的每一个样本属性的属性值的均值；并根据接收的每一个聚类的每一个样本属性的属性值的均值，得到每一个聚类的虚拟聚类中心点信息，根据当前保存的每一个聚类的聚类中心点信息以及设定的中心点更新策略，当确定出至少由一个聚类的虚拟聚类中心点信息更新当前保存的该聚类的聚类中心点信息时，发送本次更新后的和本次未更新的每一个聚类的聚类中心点信息给所述至少两个计算节点；当确定出每一个聚类的聚类中心点信息都不再更新时，将最后一次更新后的聚类中心点信息作为每一个聚类的实际聚类中心点信息；
[0028] 所述计算节点，用于分别计算分配的分块样本中每个样本在样本空间中的对应样本点与各聚类中心点的距离，将每个样本归属到所述距离最小的对应聚类中心点所属聚类；分别统计本地属于每一个聚类的样本数量以及计算属于该聚类的各样本包含的每一个样本属性的属性值的和值，并传送所述样本数量、以及携带聚类标识和样本属性标识的所述和值给合并节点；
[0029] 所述合并节点，用于对每一个聚类的每一个样本属性根据每个所述计算节点传送的所述样本数量和所述和值，计算出每一个聚类的每一个样本属性的属性值的均值，并传送给所述主控节点。
[0030] 本发明提供的聚类实现方法及系统中，将待处理的样本分块后分配给不同的计算节点处理，解决了海量数据无法全部由单机读入内存进行计算处理的问题；本发明提供的聚类实现方法中，采用了至少两个计算节点并行地参与聚类计算过程，加快了计算速度；再通过合并节点进行有效合并，充分利用系统中各节点的计算资源，有效解决了现有技术对海量数据无法实现聚类处理及处理效率低的问题。
附图说明
[0031] 图1为本发明实施例提供的聚类实现方法一的步骤流程图；
[0032] 图2为本发明实施例提供的聚类实现方法一的实际应用流程图；
[0033] 图3为本发明实施例提供的聚类实现方法二的步骤流程图；
[0034] 图4为本发明实施例提供的聚类实现方法二的实际应用流程图；
[0035] 图5为本发明实施例提供的与聚类实现方法一相对应的聚类实现系统结构示意图；
[0036] 图6为本发明实施例提供的与聚类实现方法二相对应的聚类实现系统结构示意图。
具体实施方式
[0037] 下面结合附图，对本发明提供的聚类实现方法流程及聚类实现系统结构进行详细说明。
[0038] 参见图1，为本发明实施例提供的聚类实现方法一的步骤流程图，包括下列步骤：
[0039] 步骤S101、主控节点对样本分块，并将分块样本分配给至少两个计算节点，将分配的分块样本和每一个聚类的聚类中心点信息传送给每个计算节点；
[0040] 步骤S102、每个计算节点分别计算分配的分块样本中每个样本在样本空间中的对应样本点与各聚类中心点的距离，将每个样本归属到距离最小的对应聚类中心点所属聚类；对每一个聚类分别统计本地属于该聚类的样本数量以及计算属于该聚类的各样本的样本值的和值，并传送样本数量和和值给合并节点；
[0041] 步骤S103、合并节点对每一个聚类根据每个计算节点传送的样本数量及和值，求取均值，得到每一个聚类的虚拟聚类中心点信息，并传送给主控节点；
[0042] 步骤S104、主控节点根据接收的每一个聚类的虚拟聚类中心点信息和当前保存的每一个聚类的聚类中心点信息以及设定的中心点更新策略，当确定出至少由一个聚类的虚拟聚类中心点信息更新当前保存的该聚类的聚类中心点信息时，发送本次更新后的和本次未更新的每一个聚类的聚类中心点信息给所述至少两个计算节点，重复上述步骤S102和步骤S103；当确定出每一个聚类的聚类中心点信息都不再更新时，将最后一次更新后的聚类中心点信息作为每一个聚类的实际聚类中心点信息。
[0043] 参见图2，为本发明实施例提供的上述聚类实现方法一的实际应用流程图，包括：
[0044] 步骤S201、主控节点对样本分块并将分块样本分配给各计算节点；以及根据聚类数量(假设为K个聚类)在样本空间中任选K个聚类中心点，作为每个聚类的初始的聚类中心点。
[0045] 实际中，主控节点根据参与计算的计算节点数量(假设为N个)，将待处理的全部样本分成相应数量的分块(N个分块)，并将每一个分块样本分配给不同的计算节点。
[0046] 步骤S202、主控节点将分配的分块样本和每一个聚类的聚类中心点信息传送给每个计算节点。
[0047] 其中，每一个聚类的聚类中心点信息可以写入配置文件，分别传送给各计算节点。
[0048] 步骤S203、每个计算节点并行地分别计算分配的分块样本中每个样本在样本空间中的对应样本点与各聚类中心点的距离，并进行距离比较，将本地每个样本归属到距离最小的对应聚类中心点所属聚类。
[0049] 步骤S204、每个计算节点并行地对每一个聚类分别统计本地属于该聚类的样本数量以及计算属于该聚类的各样本的样本值的和值，并传送样本数量及和值给合并节点。
[0050] 实际应用中，为了加快合并速度，可以采用多个合并节点并行合并的方式。并由主控节点预先分配每个合并节点进行合并的对应聚类。一个合并节点至少合并一个聚类，当然，一个合并节点也可以合并两个或多个聚类。
[0051] 一般情况下，进行数据挖掘的样本包含有多个样本属性，计算各样本的样本值的和值时，是对每一个样本属性，分别计算样本属性的属性值的和值。例如，假设有三个样本，分别为样本1、样本2和样本3属于同一个聚类，每一个样本包含有三个样本属性，分别为属性a、属性b和属性c，该三个样本对应的属性值如下：
[0052] 样本1：a1、b1、c1；
[0053] 样本2：a2、b2、c2；
[0054] 样本3：a3、b3、c3；
[0055] 则计算出的样本值的和值为a1+a2+a3，b1+b2+b3，c1+c2+c3。
[0056] 传送样本数量及和值给合并节点的具体方法可以有如下两种：
[0057] 方法一：由主控节点将各合并节点进行合并的对应聚类，预先通知给各计算节点，各计算节点根据每个合并节点进行合并的对应聚类，将本地统计出的属于对应聚类的样本数量以及计算出的属于该对应聚类的各样本的样本值的和值，上报给对应的合并节点；
[0058] 方法二：由每个合并节点向每个计算节点收集信息。即：每个合并节点根据自身进行合并的对应聚类，分别向每个计算节点请求上传对应聚类的统计信息；每个计算节点向每个合并节点返回其请求的对应聚类在本地统计出的样本数量以及计算出的属于对应聚类的各样本的样本值的和值。
[0059] 步骤S205、合并节点对每一个聚类根据每个计算节点传送的样本数量及和值，求取均值，得到每一个聚类的虚拟聚类中心点信息，并传送给主控节点。
[0060] 其中，均值的计算，就是对每一个聚类，将每个计算节点传送的对应该聚类的和值进行累加，得到总和值，再累加每个计算节点传送的对应该聚类的样本数量，得到样本总数量，用总和值除了样本总数量，得到该聚类的本轮计算的均值，即为该聚类的本轮计算的虚拟聚类中心点信息。
[0061] 步骤S206、主控节点根据接收的每一个聚类的虚拟聚类中心点信息和当前保存的每一个聚类的聚类中心点信息，计算每一个聚类的虚拟聚类中心点和其当前的聚类中心点之间的距离，并与设定的距离阈值比较。
[0062] 步骤S207、主控节点对每一个聚类分别判断计算出的距离是否大于设定的距离阈值；只要存在一个聚类，其计算出的对应距离大于设定的距离阈值，执行步骤S208，仅当全部聚类计算出的对应距离都小于设定的距离阈值时，执行步骤S209。
[0063] 步骤S208、主控节点将计算出的距离值大于设定阈值的对应聚类的虚拟聚类中心点信息更新当前保存的该聚类的聚类中心点信息，发送本次更新后的和本次未更新的每一个聚类的聚类中心点信息给计算节点，转至步骤S203；
[0064] 步骤S209、主控节点将最后一次更新后的聚类中心点信息作为每一个聚类的实际聚类中心点信息。
[0065] 一实施方式中，主控节点获取到每一个聚类的实际聚类中心点信息后，还可以利用各计算节点并行计算出每一个样本所属聚类，具体为：
[0066] 所述主控节点将每一个聚类的实际聚类中心点信息传送给每个计算节点；
[0067] 每个计算节点分别计算分配的分块样本中每个样本在样本空间中的对应样本点与各实际聚类中心点的距离，将每个样本归属到距离最小的对应实际聚类中心点所属聚类，并返回样本标识与所属聚类的聚类标识给主控节点；
[0068] 主控节点根据每个计算节点返回的样本标识与所属聚类的聚类标识，确定出每个样本所属聚类。
[0069] 上述聚类实现方法一中，采用了两个以上的计算节点并行地参与聚类计算，提高了计算效率。且每个计算节点仅处理一部分样本数据，解决了海量数据由单机无法实现处理的问题。且可以按照聚类数量设置相应数量的合并节点，使合并过程也并行化，进一步提高合并处理速度。
[0070] 参见图3，为本发明实施例提供的聚类实现方法二的步骤流程图，包括下列步骤：
[0071] 步骤S301、主控节点对样本分块，并将分块样本分配给至少两个计算节点，将分配的分块样本和每一个聚类的聚类中心点信息传送给每个计算节点；
[0072] 步骤S302、每个计算节点分别计算分配的分块样本中每个样本在样本空间中的对应样本点与各聚类中心点的距离，将每个样本归属到所述距离最小的对应聚类中心点所属聚类；分别统计本地属于每一个聚类的样本数量以及计算属于该聚类的各样本包含的每一个样本属性的属性值的和值，并传送样本数量、以及携带聚类标识和样本属性标识的和值给合并节点；
[0073] 步骤S303、合并节点对每一个聚类的每一个样本属性根据每个计算节点传送的样本数量及和值，计算出每一个聚类的每一个样本属性的属性值的均值，并传送给主控节点；
[0074] 步骤S304、主控节点根据接收的每一个聚类的每一个样本属性的属性值的均值，得到每一个聚类的虚拟聚类中心点信息，并根据当前保存的每一个聚类的聚类中心点信息以及设定的中心点更新策略，当确定出至少由一个聚类的虚拟聚类中心点信息更新当前保存的该聚类的聚类中心点信息时，发送本次更新后的和本次未更新的每一个聚类的聚类中心点信息给所述至少两个计算节点，重复上述步骤S302和步骤S303；当确定出每一个聚类的聚类中心点信息都不再更新时，将最后一次更新后的聚类中心点信息作为每一个聚类的实际聚类中心点信息。
[0075] 参见图4，为本发明实施例提供的上述聚类实现方法二的实际应用流程图，包括：
[0076] 步骤S401、主控节点对样本分块并将分块样本分配给各计算节点；以及根据聚类数量(假设为K个聚类)在样本空间中任选K个聚类中心点，作为每个聚类的初始的聚类中心点。
[0077] 实际中，主控节点根据参与计算的计算节点数量(假设为N个)，将待处理的全部样本分成相应数量的分块(N个分块)，并将每一个分块样本分配给不同的计算节点。
[0078] 步骤S402、主控节点将分配的分块样本和每一个聚类的聚类中心点信息传送给每个计算节点。
[0079] 步骤S403、每个计算节点分别计算分配的分块样本中每个样本在样本空间中的对应样本点与各聚类中心点的距离，将每个样本归属到所述距离最小的对应聚类中心点所属聚类。
[0080] 步骤S404、每个计算节点并行地分别统计本地属于每一个聚类的样本数量以及计算属于该聚类的各样本包含的每一个样本属性的属性值的和值，并传送样本数量、以及携带聚类标识和样本属性标识的和值给合并节点。
[0081] 同上例，实际应用中，为了加快合并速度，可以采用多个合并节点并行合并的方式。并由主控节点预先分配每个合并节点进行合并的对应聚类的对应样本属性。一个合并节点至少合并一个聚类的一个样本属性，当然，一个合并节点也可以合并两个或多个样本属性。
[0082] 传送样本数量、以及携带聚类标识和样本属性标识的所述和值给合并节点的具体方法可以有如下两种：
[0083] 方法一：由主控节点将各合并节点进行合并的对应样本属性，预先通知给各计算节点，所述计算节点根据每个合并节点进行合并的对应聚类的对应样本属性，将本地统计出的对应聚类的样本数量以及计算出的对应聚类的对应样本属性的属性值的和值，上报给对应的合并节点；
[0084] 方法二：由每个合并节点向每个计算节点收集信息。每个合并节点根据自身进行合并的对应聚类的对应样本属性，分别向每个计算节点请求上传对应聚类的对应样本属性的统计信息；每个计算节点向每个合并节点返回本地统计出的对应聚类的样本数量、以及计算出的对应聚类的对应样本属性的属性值的和值，并携带与和值对应的聚类标识和样本属性标识。
[0085] 步骤S405、合并节点对每一个聚类的每一个样本属性根据每个计算节点传送的样本数量及和值，计算出每一个聚类的每一个样本属性的属性值的均值，并传送给主控节点。
[0086] 其中，均值的计算，就是对每一个聚类的每一个样本属性，将计算节点传送的对应该聚类的该样本属性的和值进行累加，得到总和值，再累加计算节点传送的对应该聚类的样本数量，得到样本总数量，用总和值除了样本总数量，得到该聚类该样本属性的属性值的均值。
[0087] 步骤S406、主控节点根据接收的每一个聚类的每一个样本属性的属性值的均值，得到每一个聚类的虚拟聚类中心点信息，计算每一个聚类的虚拟聚类中心点和其当前的聚类中心点之间的距离，并与设定的距离阈值比较。
[0088] 步骤S407、主控节点对每一个聚类分别判断计算出的距离是否大于设定的距离阈值；只要存在一个聚类，其计算出的对应距离大于设定的距离阈值，执行步骤S408，仅当全部聚类计算出的对应距离都小于设定的距离阈值时，执行步骤S409。
[0089] 步骤S408、主控节点将计算出的距离值大于设定阈值的对应聚类的虚拟聚类中心点信息更新当前保存的该聚类的聚类中心点信息，发送本次更新后的和本次未更新的每一个聚类的聚类中心点信息给计算节点，转至步骤S403；
[0090] 步骤S409、主控节点将最后一次更新后的聚类中心点信息作为每一个聚类的实际聚类中心点信息。
[0091] 一实施方式中，主控节点获取到每一个聚类的实际聚类中心点信息后，还可以利用各计算节点并行计算出每一个样本所属聚类，具体为：
[0092] 所述主控节点将每一个聚类的实际聚类中心点信息传送给每个计算节点；
[0093] 每个计算节点分别计算分配的分块样本中每个样本在样本空间中的对应样本点与各实际聚类中心点的距离，将每个样本归属到距离最小的对应实际聚类中心点所属聚类，并返回样本标识与所属聚类的聚类标识给主控节点；
[0094] 主控节点根据每个计算节点返回的样本标识与所属聚类的聚类标识，确定出每个样本所属聚类。
[0095] 上述聚类实现方法二中，采用了两个以上的计算节点并行地参与聚类计算，提高了计算效率。且每个计算节点仅处理一部分样本数据，解决了海量数据由单机无法实现处理的问题。且可以按照样本属性数量设置相应数量的合并节点，使合并过程也并行化，进一步提高合并处理速度。相对于上述聚类实现方法一，由于样本的样本属性一般为50-100个，最多设置的合并节点数量可以是聚类数量乘以样本属性数量的乘积，因此，可以有大量的合并节点参与合并处理，大大提高并行处理效率。
[0096] 上述聚类实现方法中，可以采用Map/Reduce函数来实现。在各计算节点中采用Map函数并行地参与聚类计算，输出本地属于各聚类的样本数量以及各聚类包含的各样本的样本值的和值，并传送给合并节点。合并节点采用Reduce函数，针对每一个聚类根据每个计算节点传送的样本数量及和值，求取均值，得到每一个聚类的虚拟聚类中心点信息。Map/Reduce函数中的Key和Value对，根据实际需要处理的对象及处理结果分别确定。
[0097] 上述方法一中：
[0098] Map函数的处理过程：每个Map函数处理一条样本数据，计算该样本数据与各聚类初始中心点(或各聚类的上一次中心点)的距离，得到距离最近的一个中心点。Map函数的输出：key为距离最近的中心点的标识，value为对应的样本数据。
[0099] 每一个计算节点可以采用Combiner函数进行本地合并，收集所有key相同的样本数据，输出key为该中心点的标识，value为样本数据的各属性分别向量求和的和值以及样本个数。
[0100] 合并节点运行reduce函数，Reduce函数的输入为combiner函数的输出。Reduce函数处理过程为，将相同key的value收集，求得向量求和和个数求和，再得到均值：即向量求和/个数求和，得到新的中心点。Reduce函数的输出为：输出key为新的中心点标识，value为新中心点数据，将结果写入配置文件，作为下一次重复执行的初始中心点。
[0101] 上述方法二中：
[0102] 计算节点运行Map函数及Combiner函数过程同上，不同之处在于Combiner函数的输出是：将key设为中心点标识_属性名称，value为该属性值的求和及个数和。合并节点运行reduce函数，Reduce函数的输入为combiner函数的输出。Reduce处理过程，求得中心点标示_属性名称的均值，输出至配置文件。
[0103] 基于同一发明构思，根据本发明上述实施例提供的聚类实现方法一，本发明提供一种相应的聚类实现系统，其结构示意图如图5所示，包括：主控节点51、至少两个计算节点52及合并节点53；
[0104] 主控节点51，用于对样本分块，并将分块样本分配给计算节点52，将分配的分块样本和每一个聚类的聚类中心点信息传送给每个计算节点52；以及接收合并节点53传送的每一个聚类的虚拟聚类中心点信息；并根据接收的每一个聚类的虚拟聚类中心点信息和当前保存的每一个聚类的聚类中心点信息以及设定的中心点更新策略，当确定出至少由一个聚类的虚拟聚类中心点信息更新当前保存的该聚类的聚类中心点信息时，发送本次更新后的和本次未更新的每一个聚类的聚类中心点信息给计算节点52，当确定出每一个聚类的聚类中心点信息都不再更新时，将最后一次更新后的聚类中心点信息作为每一个聚类的实际聚类中心点信息；
[0105] 计算节点52，用于分别计算分配的分块样本中每个样本在样本空间中的对应样本点与各聚类中心点的距离，将每个样本归属到距离最小的对应聚类中心点所属聚类；对每一个聚类分别统计本地属于该聚类的样本数量以及计算属于该聚类的各样本的样本值的和值，并传送样本数量及和值给合并节点53；
[0106] 合并节点53，用于对每一个聚类根据每个计算节点传送的样本数量及和值，求取均值，得到每一个聚类的虚拟聚类中心点信息，并传送给主控节点51。
[0107] 一具体实施例中，主控节点51还用于，将获得的每一个聚类的实际聚类中心点信息传送给每个计算节点52；以及根据每个计算节点52返回的样本标识与所属聚类的聚类标识，确定出每个样本所属聚类；
[0108] 每个计算节点52还用于，分别计算分配的分块样本中每个样本在样本空间中的对应样本点与各实际聚类中心点的距离，将每个样本归属到所述距离最小的对应实际聚类中心点所属聚类，并返回样本标识与所属聚类的聚类标识给主控节点51。
[0109] 一实施例中，合并节点53至少包括两个，合并节点53的最大数量与聚类的数量相等。
[0110] 主控节点51还用于，预先给每个合并节点53分配至少一个进行合并的聚类。
[0111] 图5中，示意出各计算节点52和各合并节点53分别为不同的节点。实际应用中，计算节点52和合并节点53除全部为不同的节点外，还可以是：
[0112] 每一个计算节点52或部分计算节点52为合并节点53；或者部分计算节点52为部分合并节点53。
[0113] 基于同一发明构思，根据本发明上述实施例提供的聚类实现方法二，本发明提供一种相应的聚类实现系统，其结构示意图如图6所示，包括：主控节点61、至少两个计算节点62及合并节点63；
[0114] 主控节点61，用于对样本分块，并将分块样本分配给至少两个计算节点，将分配的分块样本和每一个聚类的聚类中心点信息传送给每个计算节点62；以及接收合并节点63传送的每一个聚类的每一个样本属性的属性值的均值；并根据接收的每一个聚类的每一个样本属性的属性值的均值，得到每一个聚类的虚拟聚类中心点信息，根据当前保存的每一个聚类的聚类中心点信息以及设定的中心点更新策略，当确定出至少由一个聚类的虚拟聚类中心点信息更新当前保存的该聚类的聚类中心点信息时，发送本次更新后的和本次未更新的每一个聚类的聚类中心点信息给计算节点62；当确定出每一个聚类的聚类中心点信息都不再更新时，将最后一次更新后的聚类中心点信息作为每一个聚类的实际聚类中心点信息；
[0115] 计算节点62，用于分别计算分配的分块样本中每个样本在样本空间中的对应样本点与各聚类中心点的距离，将每个样本归属到距离最小的对应聚类中心点所属聚类；分别统计本地属于每一个聚类的样本数量以及计算属于该聚类的各样本包含的每一个样本属性的属性值的和值，并传送样本数量、以及携带聚类标识和样本属性标识的和值给合并节点63；
[0116] 合并节点63，用于对每一个聚类的每一个样本属性根据计算节点传送的样本数量及和值，计算出每一个聚类的每一个样本属性的属性值的均值，并传送给主控节点61。
[0117] 一实施例中，主控节点61还用于，将每一个聚类的实际聚类中心点信息传送给每个计算节点62；以及根据每个计算节点62返回的样本标识与所属聚类的聚类标识，确定出每个样本所属聚类；
[0118] 计算节点62，还用于分别计算分配的分块样本中每个样本在样本空间中的对应样本点与各实际聚类中心点的距离，将每个样本归属到所述距离最小的对应实际聚类中心点所属聚类，并返回样本标识与所属聚类的聚类标识给主控节点61。
[0119] 一实施例中，合并节点63至少包括两个，合并节点的最大数量与聚类的数量和样本的样本属性的数量的乘积相等。
[0120] 主控节点61还用于，预先给每个合并节点分配至少一个聚类的进行合并的一个样本属性。
[0121] 图6中，示意出各计算节点62和各合并节点63分别为不同的节点。实际应用中，计算节点62和合并节点63除全部为不同的节点外，还可以是：
[0122] 每一个计算节点62或部分计算节点62为合并节点；或者部分计算节点62为部分合并节点63。
[0123] 本发明提供的聚类实现方法及系统中，将待处理的样本分块后分配给不同的计算节点处理，解决了海量数据无法全部由单机读入内存进行计算处理的问题；本发明提供的聚类实现方法中，采用了至少两个计算节点并行地参与聚类计算过程，加快了计算速度；再通过合并节点进行有效合并，充分利用系统中各节点的计算资源，有效解决了现有技术对海量数据无法实现聚类处理及处理效率低的问题。
[0124] 显然，本领域的技术人员可以对本发明进行各种改动和变型而不脱离本发明的精神和范围。这样，倘若本发明的这些修改和变型属于本发明权利要求及其等同技术的范围之内，则本发明也意图包含这些改动和变型在内。
