平码五不中公式规律
  • / 20
  • 下载费用:30 金币  

聚类方法及相关装置.pdf

关 键 ?#21097;?/dt>
方法 相关 装置
  专利查询网所有资源均是用户自行上传分享,仅供网友学习交流,未经上传用户书面授权,请勿作他用。
摘要
申请专利号:

CN201410097422.5

申请日:

2014.03.14

公开号:

CN103914518A

公开日:

2014.07.09

当前法律状态:

授权

有效性:

有权

法?#19978;?#24773;: 授权|||实质审查的生效IPC(主分类):G06F 17/30申请日:20140314|||公开
IPC分类号: G06F17/30; G06K9/62 主分类号: G06F17/30
申请人: 小米科技有限责任公司
发明人: 陈志军; 张涛; 张波; 王琳
地址: 100085 北京市海淀区清河中街68号华润五彩城购物中心二期13层
优?#28909;ǎ?/td>
专利代理机构: 北京弘权知识产权代理事务所(普通合伙) 11363 代理人: 逯长明;陈蕾
PDF完整版下载: PDF下载
法律状态
申请(专利)号:

CN201410097422.5

授权公告号:

103914518B||||||

法律状态公告日:

2017.05.17|||2014.08.06|||2014.07.09

法律状态类型:

授权|||实质审查的生效|||公开

摘要

本公开实施例公开了一种聚类方法及相关装置,所述聚类方法在利用类间的Rank-Order距离对符合条件的类进行合并,从而减少类的数量;然后,利用类内各个对象之间的距离计算类内聚合度,将类内对象间的距离小于所述类内聚合度的对象拆分成新的类,直到所有的类都拆分完。然后,将拆分后的类重新进?#26800;?#20195;合并和拆分,直到各个类无法再拆分,确定出包含多个对象的聚类及包含单个对象的类,从而实?#32440;?#32858;类过程中相异性比较大的对象剔除掉,提高聚类结果的准确率。尤其,当数据集中的对象比较多,但属于同一类的对象比较少时,聚类结果的准确率比较高。

权利要求书

权利要求书
1.  一种聚类方法,其特征在于,包括:
根据类间的Rank-Order距离,进行类的迭代合并;
利用类内各个对象间的距离获得迭代合并后的类对应的类内聚合度;
针对迭代合并得到的每个类,将类内对象间的距离小于所述类内聚合度的对象划分成一个新的类,并更新类的数量;
?#22791;?#26032;后的类的数量比更新前的类的数量少时,返回执行根据类间的Rank-Order距离进行类的迭代合并的?#34903;瑁?#30452;到更新前后的类的数量不变时,得到聚类结果,所述聚类结果包括包含多个对象的类和包含单个对象的类。

2.  根据权利要求1所述的方法,其特征在于,所述利用类内各个对象间的距离获得迭代合并后的类对应的类内聚合度,采用如下方式:
获取类内各个对象间的距离;
根据所述类内对象间的距离计算所述类内的各个对象间距离的距离平均值,得到所述类的类内聚合度。

3.  根据权利要求1所述的方法,其特征在于,所述利用类内各个对象间的距离获得迭代合并后的类对应的类内聚合度,采用如下方式:
获取类内各个对象间的距离;
根据所述类内对象间的距离计算所述类内的各个对象间距离的距离平均值;
将所述距离平均值进行归一化,得到所述类的类内聚合度。

4.  根据权利要求2或3所述的方法,其特征在于,所述针对迭代合并得到的每个类,将类内对象间的距离小于所述类内聚合度的对象划分成一个新类,更新类的数量,采用如下方式:
将类内对象间的距离小于所述类内聚合度的对象进行连通标记;
根据所述连通标记确定所述类内的连通分量;
根据所述连通分量将所述类拆分成新类,并更新类的数量。

5.  根据权利要求1所述的方法,其特征在于,所述根据类间的Rank-Order距离,进行类的迭代合并,采用如下方式:
获取类间Rank-Order距离,以及获取类间Rank-Order归一化距离;
当类间的Rank-Order距离小于距离阈值,且所述类间的Rank-Order归一化距离小于1时,合并所述类。

6.  一种聚类装置,其特征在于,包括:
迭代合并单元,用于根据类间的Rank-Order距离,进行类的迭代合并;
获取单元,用于利用类内各个对象间的距离获得迭代合并后的类对应的类内聚合度;
划分单元,用于针对迭代合并得到的每个类,将类内对象间的距离小于所述类内聚合度 的对象划分成一个新的类,并更新类的数量;
判断单元,用于?#22791;?#26032;后的类的数量比更新前的类的数量少时,控制所述迭代合并单元执行根据类间的Rank-Order距离进行类的迭代合并,直到更新前后的类的数量不变时,得到聚类结果,所述聚类结果包括包含多个对象的类和包含单个对象的类。

7.  根据权利要求6所述的装置,其特征在于,所述获取单元包括:
第一获取子单元,用于获取类内各个对象间的距离;
第一计算子单元,用于计算所述类的各个对象间的距离的距离平均值,得到所述类内聚合度。

8.  根据权利要求6所述的装置,其特征在于,所述获取单元包括:
第二获取子单元,用于获取类内各个对象间的距离;
第二计算子单元,用于根据所述类内对象间的距离,计算所述类内的各个对象间距离的距离平均值;
归一化子单元,将所述距离平均值进行归一化,得到所述类的类内聚合度。

9.  根据权利要求7或8所述的装置,其特征在于,所述划分单元包括:
第一判断子单元,用于判断所述类内对象间的距离是否小于所述类内聚合度;
标记子单元,用于当所述类内对象间的距离小于所述类内聚合度时,将所述类内对象间的距离对应的对象进行连通标记;
确定子单元,用于根据所述连通标记确定所述类内的连通分量;
拆分子单元,用于根据所述连通分量将所述类拆分成新类,并更新类的数量。

10.  根据权利要求6所述的装置,其特征在于,所述迭代合并单元包括:
第三获取子单元,用于获取类间Rank-Order距离,以及获取类间Rank-Order归一化距离;
合并子单元,用于当类间的Rank-Order距离小于距离阈值,且所述类间Rank-Order归一化距离小于1时,合并所述类。

11.  一种终端设备,其特征在于,包括:
处理器;
用于存储处理器可执行指令的存储器;
其中,所述处理器被配置为:
根据类间的Rank-Order距离,进行类的迭代合并;
利用类内各个对象间的距离获得迭代合并后的类对应的类内聚合度;
针对迭代合并得到的每个类,将类内对象间的距离小于所述类内聚合度的对象划分成一个新的类,并更新类的数量;
?#22791;?#26032;后的类的数量比更新前的类的数量少时,返回执行根据类间的Rank-Order距离进行类的迭代合并的?#34903;瑁?#30452;到更新前后的类的数量不变;
?#22791;?#26032;前后的类的数量不变时,得到聚类结果,所述聚类结果包括包含多个对象的类和包含单个对象的类。

说明书

说明书聚类方法及相关装置
技术领域
本公开涉及计算机技术领域,特别是涉及一种聚类方法及相关装置。
背景技术
聚类是将物理或抽象对象的集合分成由类似的对象组成的多个类的过程,即将对象分类到不同的类(簇)的过程,同一个类中的对象有很大的相似性,不同类间的对象有很大的相异性。下文使用“类”的概念,需要说明的是,本文?#23567;?#31867;”与“簇”的含义相同。
例如,聚类方法用于人脸?#35745;?#30340;分类时,将属于同一个人的?#35745;?#20998;为一类,相关的聚类方法采用Rank-Order距离度量两张人?#25345;?#38388;的相似性,能够将同一个人的?#35745;?#32858;集在一起。但是,?#24065;?#25512;?#35745;?#20013;包含的人脸数量比较多,且每个人的?#35745;?#27604;较少时,此种聚类方法的聚类结果准确率非常低。
发明内容
为克服相关技术中存在的问题,本公开提供一种聚类方法及相关装置,以提高聚类结果准确率。
为?#31169;?#20915;上述技术问题,本公开实施例公开了如下技术方案:
根据本公开实施例的第一方面,提供一种聚类方法,包括:
根据类间的Rank-Order距离,进行类的迭代合并;利用类内各个对象间的距离获得迭代合并后的类对应的类内聚合度;针对迭代合并得到的每个类,将类内对象间的距离小于所述类内聚合度的对象划分成一个新的类,并更新类的数量?#22351;备?#26032;后的类的数量比更新前的类的数量少时,返回执行根据类间的Rank-Order距离进行类的迭代合并的?#34903;瑁?#30452;到更新前后的类的数量不变时,得到聚类结果,所述聚类结果包括包含多个对象的类和包含单个对象的类。
结合第一方面,在第一方面的第一种可能的实现方式中,所述利用类内各个对象间的距离获得迭代合并后的类对应的类内聚合度,采用如下方式:
获取类内各个对象间的距离;根据所述类内对象间的距离,计算所述类内的各个对 象间距离的距离平均值,得到所述类的类内聚合度。
结合第一方面,在第一方面的第二种可能的实现方式中,所述利用类内各个对象间的距离获得迭代合并后的类对应的类内聚合度,采用如下方式:
获取类内各个对象间的距离;根据所述类内对象间的距离,计算所述类内的各个对象间距离的距离平均值;将所述距离平均值进行归一化,得到所述类的类内聚合度。
结合第一方面的第一种实现方式或第一方面的第二种实现方式,在第一方面的第三种实现方式中,所述针对迭代合并得到的每个类,将类内对象间的距离小于所述类内聚合度的对象划分成一个新类,更新类的数量,采用如下方式:
将所述类内对象间的距离小于所述类内聚合度对象进行连通标记;根据所述连通标记确定所述类内的连通分量;根据所述连通分量将所述类拆分成新类,并更新类的数量。
结合第一方面,在第一方面的第四种可能的实现方式中,所述根据类间的Rank-Order距离,进行类的迭代合并,采用如下方式:
获取类间Rank-Order距离,以及获取类间Rank-Order归一化距离;当类间的Rank-Order距离小于距离阈值,且所述类间的Rank-Order归一化距离小于1时,合并所述类;当合并后的类的数量小于合并前的类的数量时,执行获取合并后的类间Rank-Order距离,以及类间Rank-Order归一化距离的?#34903;琛?
根据本公开实施例的第二方面,提供一种聚类装置,包括:
迭代合并单元,用于根据类间的Rank-Order距离,进行类的迭代合并;获取单元,用于利用类内各个对象间的距离获得迭代合并后的类对应的类内聚合度;划分单元,用于针对迭代合并得到的每个类,将类内对象间的距离小于所述类内聚合度的对象划分成一个新的类,并更新类的数量;判断单元,用于?#22791;?#26032;后的类的数量比更新前的类的数量少时,控制所述迭代合并单元执行根据类间的Rank-Order距离进行类的迭代合并,直到更新前后的类的数量不变时,得到聚类结果,所述聚类结果包括包含多个对象的类和包含单个对象的类。
结合第二方面,在第二方面的第一种可能的实现方式中,所述获取单元包括:
第一获取子单元,用于获取类内各个对象间的距离;第一计算子单元,用于计算所述类的各个对象间的距离的平均值,得到所述类内聚合度。
结合第二方面,在第二方面的第二种可能的实现方式中,所述获取单元包括:
第二获取子单元,用于获取类内各个对象间的距离;第二计算子单元,用于根据所述类内对象间的距离,计算所述类内的各个对象间距离的距离平均值;归一化子单元,将所述距离平均值进行归一化,得到所述类的类内聚合度。
结合第二方面的第一种可能的实现方式或第二方面的第二种可能的实现方式,在第二方面的第三种可能的实现方式中,所述划分单元包括:
第一判断子单元,用于判断所述类内对象间的距离是否小于所述类内聚合度;标记子单元,用于当所述类内对象间的距离小于所述类内聚合度时,将所述类内对象间的距离对应的对象进行连通标记;确定子单元,用于根据所述连通标记确定所述类内的连通分量;拆分子单元,用于根据所述连通分量将所述类拆分成新类,并更新类的数量。
结合第二方面,在第二方面的第四种可能的实现方式中,所述迭代合并单元包括:
第三获取子单元,用于获取类间Rank-Order距离,以及获取类间Rank-Order归一化距离;合并子单元,用于当类间的Rank-Order距离小于距离阈值,且所述类间Rank-Order归一化距离小于1时,合并所述类;第二判断子单元,用于当合并后的类的数量小于合并前的类的数量时,控制所述第三获取子单元执行获取更新后的类间Rank-Order距离,以及类间Rank-Order归一化距离的?#34903;琛?
根据本公开实施例的第二方面,提供一种终端设备,包括:
处理器;用于存储处理器可执行指令的存储器;
其中,所述处理器被配置为:
根据类间的Rank-Order距离,进行类的迭代合并;利用类内各个对象间的距离获得迭代合并后的类对应的类内聚合度;针对迭代合并得到的每个类,将类内对象间的距离小于所述类内聚合度的内对象划分成一个新的类,并更新类的数量?#22351;备?#26032;后的类的数量比更新前的类的数量少时,返回执行根据类间的Rank-Order距离进行类的迭代合并的?#34903;瑁?#30452;到更新前后的类的数量不变时,得到聚类结果,所述聚类结果包括包含多个对象的类和包含单个对象的类。
本公开的实施例提供的技术方案可以包括以下有益效果:所述聚类方法在利用类间的Rank-Order距离对符合条件的类进行合并,从而减少类的数量;然后,利用类内各个对象之间的距离计算类内聚合度,将类内对象间的距离小于所述类内聚合度的对象拆分成新的类,直到所有的类都拆分完。然后,将拆分后的类重新进?#26800;?#20195;合并和拆分,直到各个类无法再拆分,确定出包含多个对象的聚类及包含单个对象的类,从而实?#32440;?#32858;类过程中相异性 比较大的对象剔除掉,提高聚类结果的准确率。尤其,当数据集中的对象比较多,但属于同一类的对象比较少时,聚类结果的准确率比较高。
应当理解的是,以上的一般描述和后文的?#38468;?#25551;述仅是示例性的,并不能限制本公开。
附图说明
此处的附图被并入说明书中并构成本说明书的一部分,示出了符合本发明的实施例,并与说明书一起用于解释本发明的原理。
图1是多个对象的序列?#21028;?#31034;意图;
图2根据一示例性实施例示出的一种聚类方法的流程图;
图3是图2中?#34903;鑃110的一种示例性实施例的流程图;
图4是图2中?#34903;鑃110的另一种示例性实施例的流程图;
图5是图2中?#34903;鑃120的一种示例性实施例的流程图;
图6是图2中?#34903;鑃130的一种示例性实施例的流程图;
图7是是根据一示例性实施例示出的一种聚类装置的框图;
图8是根据一示例性实施例示出的一种终端设备的框图;
图9是根据一示例性实施例示出的一?#22336;?#21153;器的框图。
通过上述附图,已示出本公开明确的实施例,后文中将有更详细的描述。这些附图并不是为了通过任何方式限制本公开构思的范围,而是通过参考特定实施例为本领域技术人员说明本公开的概念。
具体实施方式
这里将详细地对示例性实施例进行说明,其示例表示在附图?#23567;?#19979;面的描述涉及附图时,除非另有表示,不同附图中的相同数?#30452;?#31034;相同或相似的要素。以下示例性实施例中所描述的实施方式并不代表与本发明相一致的所有实施方式。相反,它们仅是与如所附权利要求书中所详述的、本发明的一些方面相一致的装置和方法的例子。
在对本公开的示例性实施例进行说明之前,首先介绍Rank-Order距离的相关知识,计算对象间的距离(例如,余弦相似度、欧式距离等),按照距离的大小将各个对象进行 重新?#21028;潁?#24471;到一个序?#23567;?#20551;设有n个对象,分别为i1、i2、i3、i4、i5、i6……in,以对象i1为基准对象,计算其它各个对象与对象i1之间的距离,并按距离的大小进行?#21028;潁?#24471;到图1所?#38236;?#24207;列O1;以对象i2为基准对象,计算其它各个对象与基准对象i2之间的距离,得到图1所?#38236;?#24207;列O2。
根据序列O1中对象i1和i2之间的邻居对象在序列O2中的序号计算,对象i1和i2之间的非对称Rank-Order距离D(i1,i2),具体根据图1的示例,对象i1、i3、i4、i2在O2中的序号分别为5、2、4、0,则根据公式1计算D(i1,i2):
D(i1,i2)=Σx=0O1(i2)O2(f1(X))=O2(i1)+O2(i3)+O2(i4)+O2(i2)=5+2+4+0=11---(11)]]>
公式1中,O2(i1)表示对象i1在序列O2中的序号,O2(i3)表示对象i3在序列O2中的序号,O2(i4)表示对象i4在序列O2中的序号,O2(i2)表示对象i2在序列O2中的序号。
同理计算得到对象i1和i2之间的非对称Rank-Order距离D(i2,i1),然后,根据公式2计算得到对象i1和i2之间归一化之后的Rank-Order距离DR(i1,i2):
DR(i1,i2)=D(i1,i2)+D(i2,i1)min(O1(i2),O2(i1))---(2)]]>
所述DR(i1,i2)表示归一化后的对象间的Rank-Order距离,类间的Rank-Order距离与对象间的Rank-Order距离算法相同,一个类为基准类然后按照类间距离对各个类进行重新?#21028;潁?#31867;间距离如公式(3)所示:
d(Ci,Cj)=mind(a,b)∀a∈Ci,b∈Cj---(3)]]>
公式(3)中Ci和Cj表示类。
类间Rank-Order距离的计算公式如公式(4)所示:
DR(Ci,Cj)=D(Ci,Cj)+D(Cj,Ci)min(OCi(Cj),OCj(Ci))---(4)]]>
公式(4)中D(Ci,Cj)表示类Ci与类Cj之间的非对称Rank-Order距离,D(Cj,Ci)表示类Cj与类Ci之间的非对称Rank-Order距离;OCi(Cj)表示以Ci为基准类的序列中类Cj的序号,表示以类Cj为基准类的序列中类Ci的序号。
根据类间距离DR(Ci,Cj)计算得到类间归一化Rank-Order距离DN(Ci,Cj),其中,类间归一化距离的计算公式如公式(5)所示:
DN(Ci,Cj)=1φ(Ci,Cj)·d(Ci,Cj),]]>
φ(Ci,Cj)=1|Ci|+|Cj|Σa∈CiCj1KΣk=1Kd(a,fa(k))---(5)]]>
公式(5)中,d(Ci,Cj)表示类Ci和类Cj之间的距离,|Ci|和|Cj|表示类内的对象个数,K是常数,fa(k)表示对象a第k个邻居对象,φ(Ci,Cj)表示两个类中距离它们的最近的K个对象之间的平均距离。
假设对象是人脸图像,本公开提供的所述聚类方法能够将属于同一个人的图像聚集在一起形成一个聚类。将人脸图像中的特征转换成一组向量,因此,对象间的距离即向量之间的距离。当然,本公开提供的聚类方法也可以应用于其它的数据。
图2是根据一示例性实施例示出的一种聚类方法的流程图,如图1所示,聚类方法应用于终端中,可以包括以下?#34903;瑁?
在?#34903;鑃110中,根据类间的Rank-Order距离,进行类的迭代合并。
计算两两类之间的Rank-Order距离,将Rank-Order距离小于第一距离阈值的类进行合并。所述第一距离阈值可以根据数据类型确定,还可以根据试验结果确定。
如图3所示,?#34903;鑃110可以包括以下?#34903;瑁?
在?#34903;鑃111中,获取类间Rank-Order距离,以及获取类间Rank-Order归一化距 离。
假设初始的人脸图像的数目是N,将每一个人脸图像作为一个单独的类,则初始的类的数量为N个,并设定距离阈值t和常数K。针对任意的类Ci和Cj,根据上述的公式(1)~(5),计算得到类间Rank-Order距离DR(Ci,Cj)和类间归一化Rank-Order距离DN(Ci,Cj)。初始类的数量为N,则最后得到一个N×N的DR(Ci,Cj)矩阵和一个N×N的DN(Ci,Cj)矩阵,其中,DR(Ci,Cj)矩阵中每个向量表示对应的类之间的Rank-Order距离,例如,矩阵中的Cij表示类Ci和Cj间的Rank-Order距离,DN(Ci,Cj)矩阵中的向量Cij表示类Ci和Cj间的Rank-Order归一化距离。
在?#34903;鑃112中,当类间的Rank-Order距离小于距离阈值,且所述类间的Rank-Order归一化距离小于1时,合并所述类。
从DR(Ci,Cj)矩阵中选出小于距离阈值t的DR(Ci,Cj),以及从DN(Ci,Cj)矩阵中选出小于1的DN(Ci,Cj)。当DR(Ci,Cj)<t,且DN(Ci,Cj)<1时,确定类Ci和Cj相似性较大能够,即类Ci和Cj为候选合并类,然后合并全部的候选合并类。当DR(Ci,Cj)≥t,表明类Ci和Cj相似性较小;当DN(Ci,Cj)≥1时,表明类间离散度较大。
在?#34903;鑃120中,利用类内各个对象间的距离计算迭代合并后的类对应的类内聚合度。
在本公开的一个实施例中,如图4所示,?#34903;鑃120可以包括以下?#34903;瑁?
在?#34903;鑃121中,获取类内各个对象间的距离。所述对象间的距离可以是余弦相似度、欧式距离或杰卡德距离?#21462;?
需要说明的是,本公开中采用余弦相似度cosθ计算对象间的距离时,将对象间的距离定义为1-cosθ,即对象间的距离越小,对象的相似性越大。
在?#34903;鑃122中,计算所述类内各个对象间距离的距离平均值,得到所述类的类内聚合度。
假设类内的对象为n个,根据计算得到的类内任意两个对象之间的距离,得到n×n的距离矩阵d,矩阵中每个点表明对应的两个对象间的距离,例如矩阵d中的向量dij表示类内的第i个对象和第j个对象之间的距离。此?#34903;?#21363;计算矩阵d中各个向量的平均值d_aver。
在本公开的另一个实施例中,如图5所示,?#34903;鑃120可以包括以下?#34903;瑁?
在?#34903;鑃123中,获取类内各个对象间的距离。
在?#34903;鑃124中,根据所述类内对象间的距离计算所述类内的各个对象间距离的距离平均值。
在?#34903;鑃125中,将所述距离平均值进行归一化,得到所述类的类内聚合度。
将距离平均值将d_aver进行归一化,就是将d_aver归纳到一个范围中[dleft,dright],dleft和dright是阈值,例如,dleft可以是0.6,dright可以是0.75。例如,归一化公式如公式(6)所示:
d_aver=dleft,d_aver<dleftdright,d_aver>drightd_aver,dleftd_averdright---(6)]]>
例如,当计算得到距离平均值为0.5时,归一化后得到的类内聚合?#20219;?.6?#22351;本?#31163;平均值为0.65时,归一化后得到的类内聚合?#20219;?.65?#22351;本?#31163;平均值为0.78时,归一化后得到的类内聚合?#20219;?.75。
本公开实施例中,采用(1-余弦相似度)来度量类内聚合度,因此类内聚合度越小表明类内的对象越聚集、相似性越大,因此,将类内聚合度归一化到一个区间内,例如,[0.6,0.75];当类内聚合度在归一化的区间内时,根据类内聚合度对类内的对象进行划分,当类内聚合度不在归一化的区间内时,根据该区间的阈值对类内的对象进行划分,从而实?#32440;?#31867;内聚合度数?#21040;?#22823;的类(即,类内离散度较大的类)能够?#23454;?#22320;划分成多个类,这样,能够避免将类内聚合度较小的类划分过多的类。
在?#34903;鑃130中,针对迭代合并得到的每个类,将类内对象间的距离小于所述类内聚合度的对象划分成一个新的类,并更新类的数量。
对于根据Rank-Order距离迭代合并后的每个类,根据类内对象间的距离及类内聚合度,对每个类进行划分,得到新的类,至此完成一次迭代,然后执行?#34903;鑃140。
在本公开的一个实施例中,如图6所示,?#34903;鑃130可以包括以下?#34903;瑁?
在?#34903;鑃131中,将类内对象间的距离小于所述类内聚合度的对象进行连通标记。
对于类内的任一对象,查询所述类内对象距离矩阵内该对象与类内的其它对象间的距离是否小于所述类内聚合度,如果类内对象间的距离小于所述类内聚合度,表明对象间的相似性较大,可以划分到同一个类?#23567;?#27492;时,可以将所述距离对应的两个对象作连 通标记,例如,两个人脸图像间的距离dij小于类内聚合度时,将第i个对象和第j个对象连通。
当所述类内对象间的距离大于所述类内聚合度时,表明对象间的相似性较小,不适合划分到同一个类中,不作任何标记。
在?#34903;鑃132中,根据所述连通标记确定所述类内的连通分量。
将能够连通的对象作为一个连通分量,从而判断类内的全部对象能够划分成几个连通分量。
在?#34903;鑃133中,根据所述连通分量将所述类拆分成新类,并更新类的数量。
将每个连通分量对应的对象划分到一个新的类中,也就是一个类中包含几个连通分量,就将此大类划分成几个新的类,并相应的增加类的数量。通过划分连通分量能够实?#32440;?#19968;个聚类中不属于该类的对象划分出来,即从聚类中剔除离群对象。
在?#34903;鑃140中,判断更新后的类的数量是否小于更新前的类的数量。如果是,返回执行?#34903;鑃110;否则,进入?#34903;鑃150。
?#22791;?#26032;后的类的数量比更新前类的数量少时,返回执行?#34903;鑃110,根据类间的Rank-Order距离进行类的迭代合并的?#34903;瑁?#30452;到更新前后的类的数量不变。
对类进行基于Rank-Order距离合并,然后进行划?#20013;?#31867;作为一次迭代,假设合并前类的数量为6个,基于Rank-Order距离合并后变为4个类,再对合并后的4个类进行拆分最终得到5个类,则更新后类的数量是5个,更新前类的数量是6个,更新后的数量小于更新前的数量,返回继续执?#26800;?#20195;。
如果更新后的类的数量小于更新前类的数量,表明类内离散度较大,即类内的对象聚集不够紧密,可能存在离群对象,需要通过继续对拆分后的类进?#26800;?#20195;合并,以及划分类,直到更新后的类的数量不大于更新前的类的数量。
?#22791;?#26032;前后的类的数量相等时,在?#34903;鑃150中,得到聚类结果,所述聚类结果包括包含多个对象的类和包含单个对象的类。
更新后的类的数量等于更新前的类的数量时,表明类内没有可剔除的离群点。最终得到的聚类结果是包含多个对象的类,以及包含单个对象的类。包含多个对象的类内的多个对象是同一人的人脸图像。只包含单个对象的类,是从利用Rank-Order距离进?#26800;?#20195;合并后的类中剔除的离群的对象。
本实施例提供的聚类方法,在利用Rank-Order距离合并类之后,又利用类内对象间距离(例如1-余弦相似度、欧式距离等)度量两个对象的相似性,将相似性较小(相异性较大)的对象从所述类中剔除(作为新的类),相当于剔除类中的噪声点,从而提高了聚类准确率。尤其,当数据集中的对象比较多,但属于同一类的对象比较少时,聚类结果的准确率比较高。
下面以具体的试验数据说明本公开的聚类方法的显著效果,如表1所示:
表1

表1中,P表示聚类结果的准确率,R表示聚类结果中的召回率,CR表示聚类结果中每个类平均拥有的人脸图像数量。
从表1中的结果可以看出,情景1中所有的图像中共包含的人脸数量是2291,而所有的图像中包含562个不同的人,则平均每个人对应4.07个人脸图像,即所有图像中平均有4.07个人脸图像属于同一个人,相关的仅用Rank-Order距离聚类的聚类结果中,准确率是86.1%。而采用本公开的聚类方法得到的聚类准确率为99.1%,?#23545;?#39640;于仅用Rank-Order距离聚类的准确率。情景2和情景3中,采用本公开的聚类方法的准确率也都高于仅用Rank-Order距离聚类的准确率。
相应于上述的聚类方法实施例,本公开提供了聚类装置。
图7是根据一示例性实施例示出的一种聚类装置示意图。请参照图7,该装置包括迭代合并单元100、获取单元200、划分单元300和判断单元400。
迭代合并单元100被配置为根据类间的Rank-Order距离,进行类的迭代合并。
在本公开的一个实施例中,迭代合并单元100可以包括第三获取子单元和合并子单元;
所述第三获取子单元被配置为获取类间Rank-Order距离,以及获取类间 Rank-Order归一化距离。
所述合并子单元被配置为当类间的Rank-Order距离小于距离阈值,且所述类间Rank-Order归一化距离小于1时,分别合并符合条件的类。
获取单元200被配置为利用类内各个对象间的距离获得迭代合并后的类对应的类内聚合度。
在本公开的一个实施例中,所述获取单元200可以包括第一获取子单元和第一计算子单元;
所述第一获取子单元被配置为获取类内各个对象间的距离。
所述第一计算子单元被配置为计算所述类的各个对象间的距离的平均值,得到所述类内聚合度。
在本公开的另一个实施例中,所述获取单元200可以包括第二获取子单元、第二计算子单元和归一化子单元;
所述第二获取子单元被配置为获取类内各个对象间的距离。所述第二获取子单元和所述第一获取子单元的功能及实现方式相同。
所述第二计算子单元被配置为根据所述类内对象间的距离,计算所述类内的各个对象间距离的距离平均值。
归一化子单元被配置为将所述距离平均值进行归一化,得到所述类的类内聚合度。
划分单元300被配置为针对迭代合并得到的每个类,将类内对象间的距离小于所述类内聚合度的对象划分成一个新的类,并更新类的数量。
在本公开的一个实施例中,所述划分单元可以包括第一判断子单元、标记子单元、确定子单元和拆分子单元。
所述第一判断子单元被配置为判断所述类内对象间的距离是否小于所述类内聚合度。
所述标记子单元被配置为将类内对象间的距离小于所述类内聚合度的对象进行连通标记。
所述确定子单元被配置为根据所述连通标记确定所述类内的连通分量。
所述拆分子单元被配置为根据所述连通分量将所述类拆分成新类,并更新类的数量。
判断单元400被配置为判断更新后的类的数量是否比更新前的类的数量少?#22351;备?#26032;后的类的数量比更新前的类的数量少时,所述迭代合并单元执行根据类间的Rank-Order距离进行类的迭代合并,直到更新前后类的数量不变时,得到聚类结果,所述聚类结果包括包含多个对象的类和包含单个对象的类。
本实施例提供的聚类装置,由迭代合并单元依据类间的Rank-Order距离对符合条件的类进行合并,从而减少类的数量;再利用获取单元根据类内各个对象之间的距离计算类内聚合度;然后,由拆分单元将类内对象间的距离小于所述类内聚合度的对象拆分成新的类,直到所有的类都拆分完。再由判断单元将拆分后的类重新进?#26800;?#20195;合并和拆分,直到各个类无法再拆分得到包含多个对象的聚类及包含单个对象的类,从而实?#32440;?#32858;类过程中相异性比较大的对象剔除掉,提高聚类结果的准确率。尤其,当数据集中的对象比较多,但属于同一类的对象比较少时,聚类结果的准确率比较高。
关于上述实施例中的装置,其中各个模块执行操作的具体方式已经在有关该方法的实施例中进行了详细描述,此处将不做详细阐述说明。
图8是根据一示例性实施例示出的一种用于聚类的终端设备800的框图。例如,终端设备800可以?#19988;?#21160;电话,计算机,数字广播终端,消息收发设备,游戏控制台,平板设备,医疗设备,健身设备,个人数?#31181;?#29702;?#21462;?
参照图8,终端设备800可以包括以下一个或多个组件:处理组件802,存储器804,电源组件806,多媒体组件808,音频组件810,输入/输出(I/O)的接口812,传感器组件814,以及通信组件816。
处理组件802通常控制终端设备800的整体操作,诸如与显示,电话呼叫,数据通信,相机操作和记录操作相关联的操作。处理组件802可以包括一个或多个处理器820来执行指令,以完成上述的方法的全部或部分?#34903;琛?#27492;外,处理组件802可以包括一个或多个模块,便于处理组件802和其他组件之间的?#25442;ァ?#20363;如,处理组件802可以包括多媒体模块,以方便多媒体组件808和处理组件802之间的?#25442;ァ?
存储器804被配置为存储各种类型的数据以支持在设备800的操作。这些数据的示例包括用于在终端设备800上操作的任何应用程序或方法的指令,联系人数据,电话簿数据,消息,?#35745;?#35270;?#26723;取?#23384;储器804可以由任何类型的?#36164;?#24615;或?#19988;资源?#20648;设备或者它们的组合实现,如静态随机存取存储器(SRAM),电可擦除可编程只读存储器(EEPROM),可擦除可编程只读存储器(EPROM),可编程只读存储器(PROM),只读存储器(ROM),磁存储器,快闪存储器,?#25490;?#25110;光盘。
电源组件806为终端设备800的各种组件提供电力。电源组件806可以包括电源管理?#20302;常?#19968;个或多个电源,及其他与为终端设备800生成、管理和分配电力相关联的组件。
多媒体组件808包括在所述终端设备800和用户之间的提供一个输出接口的屏幕。在一些实施例中,屏幕可以包括液晶显示器(LCD)和触摸面板(TP)。如果屏幕包括触摸面板,屏幕可以被实现为触摸屏,以接收来自用户的输入信号。触摸面板包括一个或多个触摸传感器以感测触摸、滑动和触摸面板上的?#36136;啤?#25152;述触摸传感器可以不仅感测触摸或滑动动作的边界,而?#19968;?#26816;测与所述触摸或滑动操作相关的?#20013;?#26102;间和压力。在一些实施例中,多媒体组件808包括一个前置摄像头和/或后置摄像头。当设备800处于操作模式,如?#32435;?#27169;式或视?#30340;?#24335;时,前置摄像头和/或后置摄像头可以接收外部的多媒体数据。每个前置摄像头和后置摄像头可以是一个固定的光学透镜?#20302;?#25110;具有焦距和光学变焦能力。
音频组件810被配置为输出和/或输入音频信号。例如,音频组件810包括一个麦克风(MIC),当终端设备800处于操作模式,如呼?#24515;?#24335;、记录模式和语音识别模式时,麦克风被配置为接收外部音频信号。所接收的音频信号可以被进一步存储在存储器804或经由通信组件816发送。在一些实施例中,音频组件810还包括一个扬声器,用于输出音频信号。
I/O接口812为处理组件802和外围接口模块之间提供接口,上述外围接口模块可以是键盘,点击轮,按钮?#21462;?#36825;些按钮可包括但不限于:主页按钮、音量按钮、启动按钮和锁定按钮。
传感器组件814包括一个或多个传感器,用于为终端设备800提供各个方面的状态评估。例如,传感器组件814可以检测到设备800的打开/关闭状态,组件的相对定位,例如所述组件为终端设备800的显示器和小键盘,传感器组件814还可以检测终端设备800或终端设备800一个组件的位置改变,用户与终端设备800接触的存在或不存在,终端设备800方位或加速/减速和终端设备800的温度变化。传感器组件814可以包括接近传感器,被配置用来在没有任何的物理接触时检测附近物体的存在。传感器组件814还可以包括光传感器,如CMOS或CCD图像传感器,用于在?#19978;?#24212;用中使用。在一些实施例中,该传感器组件814还可以包括加速度传感器,陀螺仪传感器,磁传感器,压力传感器或温度传感器。
通信组件816被配置为便于终端设备800和其他设备之间有线或无线方式的通信。终端设备800可以接入基于通信标准的无线网络,如WiFi,2G、3G或4G,或它们的组 合。在一个示例性实施例中,通信部件816经由广播信道接收来自外部广播管理?#20302;?#30340;广播信号或广播相关信息。在一个示例性实施例中,所述通信部件816还包括近场通信(NFC)模块,?#28304;?#36827;短程通信。例如,在NFC模块可基于射频识别(RFID)技术,红外数据协会(IrDA)技术,超宽带(UWB)技术,蓝牙(BT)技术和其他技术来实现。
在示例性实施例中,终端设备800可以被一个或多个应用专用集成电路(ASIC)、数?#20013;?#21495;处理器(DSP)、数?#20013;?#21495;处理设备(DSPD)、可编程逻辑器件(PLD)、现场可编程门阵列(FPGA)、控制器、微控制器、微处理器或其他电子元件实现,用于执行上述方法。
在示例性实施例中,?#22266;?#20379;了一种包括指令的非临时性计算机可读存储介?#21097;?#20363;如包括指令的存储器804,上述指令可由终端设备800的处理器820执行以完成上述方法。例如,所述非临时性计算机可读存储介质可以是ROM、随机存取存储器(RAM)、CD-ROM、磁带、软盘和光数据存储设备?#21462;?
一?#22336;?#20020;时性计算机可读存储介?#21097;?#24403;所述存储介质中的指令由移动终端的处理器执行时,使得移动终端能够执行一种聚类方法,所述方法包括:
根据类间的Rank-Order距离,进行类的迭代合并;利用类内各个对象间的距离获得迭代合并后的类对应的类内聚合度;针对迭代合并得到的每个类,将类内对象间的距离小于所述类内聚合度的对象划分成一个新的类,并更新类的数量?#22351;备?#26032;后的类的数量比更新前的类的数量少时,返回执行根据类间的Rank-Order距离进行类的迭代合并的?#34903;瑁?#30452;到更新前后的类的数量不变时,得到聚类结果,所述聚类结果包括包含多个对象的类和包含单个对象的类。
可选地,所述利用类内各个对象间的距离获得迭代合并后的类对应的类内聚合度,采用如下方式:
获取类内各个对象间的距离;根据所述类内对象间的距离计算所述类内的各个对象间距离的距离平均值,得到所述类的类内聚合度。
可选地,所述利用类内各个对象间的距离获得迭代合并后的类对应的类内聚合度,采用如下方式:
获取类内各个对象间的距离;根据所述类内对象间的距离计算所述类内的各个对象间距离的距离平均值;将所述距离平均值进行归一化,得到所述类的类内聚合度。
可选地,所述针对迭代合并得到的每个类,将类内对象间的距离小于所述类内聚合 度的对象划分成一个新类,更新类的数量,采用如下方式:
将类内对象间的距离小于所述类内聚合度的对象进行连通标记;根据所述连通标记确定所述类内的连通分量;根据所述连通分量将所述类拆分成新类,并更新类的数量。
可选地,所述根据类间的Rank-Order距离,进行类的迭代合并,采用如下方式:
获取类间Rank-Order距离,以及获取类间Rank-Order归一化距离;当类间的Rank-Order距离小于距离阈值,且所述类间的Rank-Order归一化距离小于1时,合并所述类。
图9是本发明实施例中服务器的结构示意图。例如,该服务器1900可因配置或性能不同而产生比较大的差异,可以包括一个或一个以上中央处理器(central processing units,CPU)1922(例如,一个或一个以上处理器)和存储器1932,一个或一个以上存储应用程序1942或数据1944的存储介质1930(例如一个或一个以上海量存储设备)。其中,存储器1932和存储介质1930可以是短暂存储或?#24535;?#23384;储。存储在存储介质1930的程序可以包括一个或一个以上模块(图示没标出),每个模块可以包括对终端设备中的一系列指令操作。更进一步地,中央处理器1922可以设置为与存储介质1930通信,在服务器1900上执行存储介质1930中的一系列指令操作。
服务器1900还可以包括一个或一个以上电源1926,一个或一个以上有线或无线网络接口1950,一个或一个以上输入输出接口1958,一个或一个以上键盘1956,和/或,一个或一个以上操作?#20302;?941,例如Windows ServerTM,Mac OS XTM,UnixTM,LinuxTM,FreeBSDTM等?#21462;?
在示例性实施例中,?#22266;?#20379;了一种包括指令的非临时性计算机可读存储介?#21097;?#20363;如存储器1932或存储介质1930,上述指令可由终端设备的处理器1922执行以完成上述方法。例如,所述非临时性计算机可读存储介质可以是ROM、随机存取存储器(RAM)、CD-ROM、磁带、软盘和光数据存储设备?#21462;?
一?#22336;?#20020;时性计算机可读存储介?#21097;?#24403;所述存储介质中的指令由终端设备的处理器执行时,使得终端设备能够执行一种聚类方法,所述方法包括:
根据类间的Rank-Order距离,进行类的迭代合并;利用类内各个对象间的距离获得迭代合并后的类对应的类内聚合度;针对迭代合并得到的每个类,将类内对象间的距离小于所述类内聚合度的对象划分成一个新的类,并更新类的数量?#22351;备?#26032;后的类的数量比更新前的类的数量少时,返回执行根据类间的Rank-Order距离进行类的迭代合并的?#34903;瑁?#30452;到更新前后的类的数量不变时,得到聚类结果,所述聚类结果包括包含多个对 象的类和包含单个对象的类。
可选地,所述利用类内各个对象间的距离获得迭代合并后的类对应的类内聚合度,采用如下方式:
获取类内各个对象间的距离;根据所述类内对象间的距离计算所述类内的各个对象间距离的距离平均值,得到所述类的类内聚合度。
可选地,所述利用类内各个对象间的距离获得迭代合并后的类对应的类内聚合度,采用如下方式:
获取类内各个对象间的距离;根据所述类内对象间的距离计算所述类内的各个对象间距离的距离平均值;将所述距离平均值进行归一化,得到所述类的类内聚合度。
可选地,所述针对迭代合并得到的每个类,将类内对象间的距离小于所述类内聚合度的对象划分成一个新类,更新类的数量,采用如下方式:
将类内对象间的距离小于所述类内聚合度的对象进行连通标记;根据所述连通标记确定所述类内的连通分量;根据所述连通分量将所述类拆分成新类,并更新类的数量。
可选地,所述根据类间的Rank-Order距离,进行类的迭代合并,采用如下方式:
获取类间Rank-Order距离,以及获取类间Rank-Order归一化距离;当类间的Rank-Order距离小于距离阈值,且所述类间的Rank-Order归一化距离小于1时,合并所述类。
应当理解的是,本发明并不局限于上面已经描述并在附图中示出的精?#26041;?#26500;,并且可以在不脱离其范围进行各?#20013;?#25913;?#36879;?#21464;。本发明的范围仅由所附的权利要求来限制。
需要说明的是,在本文中,诸如“第一”和“第二”等之类的关系术语仅仅用来将一个实体或者操作与另一个实体或操作区分开来,而不一定要求或者暗示这些实体或操作之间存在任何这种实际的关系或者顺序。而且,术语“包括”、“包含”或者其任何其他变体意在涵盖非排他性的包含,从而使得包括一系列要素的过程、方法、物品或者设备不仅包括那些要素,而?#19968;?#21253;括没有明确列出的其他要素,或者是还包括为这种过程、方法、物品或者设备所固有的要素。在没有更多限制的情况下,由语句“包括一个……”限定的要素,并不排除在包括所述要素的过程、方法、物品或者设备中还存在另外的相同要素。

关于本文
本文标题:聚类方法及相关装置.pdf
链接地址:http://www.pqiex.tw/p-6115586.html
关于我们 - 网站声明 - 网站地图 - 资源地图 - 友情链接 - 网站客服 - 联系我们

[email protected] 2017-2018 zhuanlichaxun.net网站版权所有
经营许可证编号:粤ICP备17046363号-1 
 


收起
展开
平码五不中公式规律 多宝二分彩走势图 幸运赛车助手 星空棋牌台州游戏大厅 双色球历史上的140期 大庆冠通棋牌麻将免费 23号福建十一选五开奖结果查询今天 微信如何发起彩票合买 l辽宁11选5 排列三最准确的跟号计划 中国福彩3d