法律状态公告日
法律状态信息
法律状态
2020-07-28
授权
授权
2018-06-26
实质审查的生效 IPC(主分类):G06K9/62 申请日:20170921
实质审查的生效
2018-06-01
公开
公开
技术领域
本发明属于大数据聚类领域,具体涉及一种解决大数据聚类的基于视觉原理的聚类方法。
背景技术
聚类是依据数据的某种相似性(如结构或趋势)将数据划分为不同组别的知识发现方法。衡量数据间的相似度是聚类的基础,通常各个点之间的相似度以矩阵形式存储,对于大规模或是分布式数据此方式将导致数据传输量巨大,计算效率缓慢,甚至由于矩阵巨大无法存储的问题。
导致这些问题产生的原因是由于相似度以稠密矩阵的方式存储,数据量以原数据体量的平方速度增加。
目前已有的大数据聚类算法有以下两种:
以kmeans为代表的给定类个数的划分型聚类方法:该类方法在给定类数的前提下,衡量各个点与各类中心的相似度,判定点的归属,并迭代计算各个类中心。此种方法计算复杂度为线性,适合在大数据情形使用,但需要事先明确总体类数,同时各个类的数据分布需要满足球形分布,而且算法的稳定性与起始点的选取紧密相关。因此,虽然该类算法在大部分大数据平台上已经实现(Spark和petuum),但很难满足大数据聚类的需要。
另一类是DBSCAN基于密度的聚类方法:该方法通过衡量各个点在给定范围的点密度,确定点和给定范围内的点的连接关系,实现相同类内的元素相连接。此种方法适合在图模型中实现,可以实现任意形状的类的识别,但方法需要人为设定合适范围和密度的阈值,才能得到较好的聚类结果。这点在大数据和分布式情形下很难得到满足,因此该方法也很难满足聚类的需要。
聚类问题是人工智能、机器学习的等信息处理方法的基础,已有很多优秀的聚类算法,但在大数据计算环境下很难实现,而已有的大数据聚类方法却难以满足使用需要。
发明内容
本发明的目的在于克服聚类算法中相似度矩阵的生成和存储问题,提供一种解决大数据聚类的基于视觉原理的聚类方法,该方法通过对原有数据进行给定精度的无损多尺度编码,实现数据的多尺度、多维度的网格化存储,基于各尺度编码判断编码和邻域编码的相似度,利用连通性分析,实现多尺度的聚类,提供多尺度的聚类结果。在数据编码过程中,利用了视觉原理,该原理符合韦伯定律,即感觉的差别阈限随原刺激量的变化而变化。
为了达到上述目的,本发明包括以下步骤:
步骤一,确定编码精度:根据不同应用场景,设定不同的编码精度ε,ε的大小显示了编码与原始数据之间的误差;
步骤二,确定编码位数与最小尺度,最大尺度:由编码精度ε计算出编码的最大尺度σmax 与最小尺度σ0,同时可以得到编码的长度L;
步骤三,原数据编码:将原数据集以编码精度ε进行编码,除返回聚类结果步外,之后的计算步骤将都在编码上进行;
步骤四,单尺度聚类分析:包括四个部分,编码集的截断操作、相邻编码查找、连通性分析和聚类结果解码;
第五步,增加尺度数,σ=σ+1,重复步骤四操作,直到最大尺度σmax。
所述步骤二中,d维的原始数据集χ中的任意元素χ∈Pδ,对于x的每一维>(t)∈[at,bt],t∈[1,d],最大尺度σmax满足
最小尺度σ0通常为1,编码的位数L=σmax×d。
所述步骤三中,对原始数据中的每个元素进行S/D编码,获得原始编码集X,x∈Ξ,Pε(·)>
e=Pε(x),e=[e(1)e(2)...e(L)]
其中,
所述步骤四的具体方法如下:
第一步,截断操作会根据当前的尺度,对编码集中的各个编码进行截断,获取该尺度下的编码集;
第二步,在当前尺度的编码集的基础上,进行各个编码的同尺度相邻编码查找,组成与相邻编码相连的图数据;
第三步,之后利用上一步图数据进行连通性分析,得到的最大连通子图为聚类结果;
第四步,再将聚类结果解码,从编码回归到原数据。
所述第二步中,若二维数据的1近邻八邻域2尺度距离编码通常[0001][0010][0011],构造提取同一维度数值的模板编码
编码e近邻编码集合Xe为,
u∈Xe,ut∈{et-,et,et+}ε
其中,∧表示逻辑与操作,
所述第三步中,图Gσ=(Xσ,Eσ),对Gσ进行连通性分析,得到kσ个最大连通子图,即
与现有技术相比,本发明通过对原有数据进行给定精度的无损多尺度编码,实现数据的多尺度、多维度的网格化存储,基于各尺度编码判断编码和邻域编码的相似度,利用连通性分析,实现多尺度的聚类,提供多尺度的聚类结果。在数据编码过程中,利用了视觉原理,该原理符合韦伯定律,即感觉的差别阈限随原刺激量的变化而变化。
附图说明
图1为本发明的编码过程举例示意图;其中(a)显示了二维点(1,5)和(5,3)的位置和不同尺度编码示意;(b)显示了二维点以尺度2编码的过程;
图2为本发明相邻编码查找举例示意图;
图3为小规模数据集聚类结果示意图;其中,(a)为行为原始数据集,(b)行为kmeans 聚类结果,(c)行为density-peak聚类结果,(d)行为本发明聚类方法聚类结果;
图4为2015年1-6月纽约出租车行车记录示意图;
图5为大规模数据聚类结果示意图;其中,(a)为本发明聚类方法在各个尺度的聚类结果, (b)为本发明对应kmeans聚类的类数选取的对应聚类结果,(c)为kmeans聚类方法在k=10, k=100和k=10000时的聚类结果。
具体实施方式
下面结合附图对本发明做进一步说明。
Step1确定S/D编码精度:根据不同应用场景,设定不同的编码精度ε,ε的大小显示了编码与原始数据之间的误差;
Step2确定S/D编码的位数、最大尺度与最小尺度:d维的原始数据集χ中的任意元素 χ∈Pδ,对于x的每一维x(t)∈[at,bt],t∈[1,d],最大尺度σmax满足
最小尺度σ0通常为1,编码的位数L=σmax×d;
Step3对原始数据中的每个元素进行S/D编码,获得原始编码集X:x∈Ξ,Pε(·)为S/D编码函数,
e=Pε(x),e=[e(1)e(2)...e(L)]
其中,[·]2表示数字的二进制形式,
Step4单尺度聚类分析:根据视觉观察的原理,对编码集X进行多尺度观察,视距调整过程符合韦伯定律,尺度数σ从最小尺度数σ0开始。具体操作步骤包括四个部分,编码集的截断操作、相邻编码查找、连通性分析和聚类结果解码;
Step4.1截断操作会根据当前的尺度σ,对编码集X中的各个编码进行截断,
得到的该尺度编码组成该尺度下的编码集Xσ;
Step4.2在编码集Xσ的基础上,进行同尺度相邻编码查找,已知需要计算的距离编码集ed,该距离编码集由编码的相邻特性、数据维度和当前尺度数决定,如二维数据的1近邻八邻域2>
编码e近邻编码集合Xe为,
u∈Xe,ut∈{et-,et,et+}ε
其中,∧表示逻辑与操作,
Step4.3图Gσ=(Xσ,Eσ),对Gσ进行连通性分析,得到kσ个最大连通子图,即
Step4.4查找各个编码内包括的原数据,将聚类结果从编码回归到原数据;
Step5增加尺度数,σ=σ+1,重复Step4操作,直到最大尺度σmax。
实验结果:
小数据集验证实验:在多个小数据集上进行聚类,使用kmeans、density-peak和本发明方法,实验结果如图3所示。对于第一种直线、第三种圆环和第四种螺旋线的数据,density-peak 和本发明方法相比kmeans可以得到较好的结果;而对第二种高斯分布的数据,本发明算法有较好的聚类结果。
大规模数据实验:
大规模数据选取由纽约出租车管理局提供的2015年1-6月收集的8,500万条纽约出租车纪录二维地理坐标数据,数据整体示意图如图4所示。将使用Spark平台提供的kmeans聚类方法与本发明方法进行聚类,获得当地交通区域分块情况。
由图5可以看出,本发明方法的聚类结果基本保留了当地交通繁忙路段的分区情况,在不同尺度分区的精细程度不同,而kmeans算法的聚类结果仅仅根据数据之间的距离划分,并没有各个区域之间交通繁忙程度的关联性。
机译: AP基于神经网络的基于强化学习的聚类方法和基于神经网络的协作通信基于强化学习的聚类方法
机译: 利用多层次聚类方法对图像进行大数据聚类以优化人脸识别过程
机译: 利用多层次聚类方法对图像进行大数据聚类以优化人脸识别过程