一种面向大数据中任意形状数据簇的快速聚类方法.pdf

(19)中华人民共和国国家知识产权局(12)发明专利申请(10)申请公布号CN106844692A(43)申请公布日2017.06.13(21)申请号201710059010.6(22)申请日2017.01.23(71)申请人武汉万般上品信息技术有限公司地址430070湖北省武汉市东湖新技术开发区光谷大道303号光谷芯中心2-07栋201-03室(72)发明人李宗鹏黄浩(74)专利代理机构武汉科皓知识产权代理事务所(特殊普通合伙)42222代理人鲁力(51)Int.Cl.G06F17/30(2006.01)权利要求书1页说明书3页附图2页(54)发明名称一种面向大数据中任意形状数据簇的快速聚类方法(57)摘要本发明公开了一种面向大数据中任意形状数据簇的快速聚类方法；通过对海量数据进行采样，并且对采样点的位置根据原始数据分布进行合理调整，实现在压缩数据集中数据样本数量的同时，能够有效保留原始数据集的形状信息。接下来在数据集上使用现有的任意形状聚类算法进行处理，得到最终的聚类结果。本发明能够使得在采样数据集上的聚类结果与在原始数据集上的聚类结果基本一致。相较于现有的对大数据的任意形状处理方法，本发明的方法能够在保持结果准确的前提下，极大的压缩方法的运行时间，因而比现有方法更加高效。CN106844692ACN106844692A权利要求书1/1页1.一种面向大数据的快速聚类方法，其特征在于，对于含有N个数据样本的大数据集D＝{d1,d2,…,dN}，给定采样比例r，具体包括：步骤1：设定迭代次数t与常数c；从原始数据集中随机采样M＝N*r个样本作为初始代表点集合X＝{x1,x2,…,xM}；并迭代地在更新每个样本的位置，在每一次迭代中，对于代表点样本xi，其新的坐标为：循环本步骤，迭代t次，转至下一步骤；步骤2：给定阈值τ，将每个原始数据样本划分给与其距离最近的代表点；对于任意代表点xi，都对应着一个属于该代表点的原始样本集合，令该集合为其中包含ki个原始样本；对于每个代表点样本，更新其位置信息；具体来说，对于代表点样本xi，其新位置为：迭代执行本步骤将直到所有代表点的位移量总和小于τ，转至下一步骤；步骤3：使用现有的任意形状聚类算法在采样数据集上进行聚类，并将对代表点数据集的聚类结果映射回原始数据集；具体来说，对于每个代表点xi及其对应的原始样本集合对每一个原始样本都贴上与代表点相同的类别标签。2.根据权利要求1所述的一种面向大数据的快速聚类方法，其特征在于，步骤1中迭代更新代表点位置的方法，迭代次数t≤10。3.根据权利要求1所述的一种面向大数据的快速聚类方法，其特征在于，步骤2中根据原始数据样本分布更新代表点位置的方法，对于标准化在[0,1]区间的数据集，阈值τ≤0.01。2CN106844692A说明书1/3页一种面向大数据中任意形状数据簇的快速聚类方法技术领域[0001]本发明属于数据挖掘领域，尤其涉及一种面向大数据中任意形状数据簇的快速聚类方法。背景技术[0002]在大数据环境下，有很多的应用场景需要使用到任意形状聚类算法来解决实际问题。例如，在处理地图等地理信息数据时，地图中的山脉，河流等地形往往呈现出各种不规则的形状，可以使用任意形状聚类算法来识别这些地形地貌。在医药学领域，生物的蛋白质的空间结构也是非常不规则的，使用任意形状聚类算法可以有效的识别蛋白质的空间结构，帮助研究者更好的认知蛋白质的组成、功能等。具体来说，聚类算法通过一个数据集中各个数据样本之间的相似性，将相似的数据样本划分到同一个聚类中，从而实现将原始数据集的样本划分为多个聚类的目标。一般来说，聚类算法更加倾向于用欧式距离来度量两个样本之间的相似性。[0003]传统的一般聚类算法往往倾向于将数据集切分成各种凸型，超球型聚类，因此这类聚类算法并不适用于任意形状聚类场景，而现有的任意形状聚类算法由于要对数据集进行比较复杂的分析，因此都具有较高的时间复杂度。这些特征使得现有的聚类算法、任意形状聚类算法都不适合应用于大数据环境下的任意形状聚类问题。[0004]因此，需要设计面向大数据的任意形状聚类方法，用于对大数据进行聚类。一种可行的思路是通过对原始数据集进行采样，减少需要处理的样本数量，从而实现快速聚类。由于聚类算法通过分析数据样本之间的距离作为相似性来实现对样本的聚类。因此，如何在采样的基础上，能够维持原始数据集的形状信息是关键与难点。发明内容[0005]为了解决上述技术问题，本发明提出了一种面向大数据的快速聚类方法。其思路是对原始的海量数据进行采样，并在采样数据集上运行任意形状聚类算法，从而减少需要处理的数据量，达到提升算法效率的目的。由于聚类算法主要是通过数据集中数据样本分布的形状信息来对数据样本进行聚类，因此，为了能够实现在采样数据集上的准确聚类，需