[發(fā)明專利]聚類方法及相關(guān)裝置

有效

• 申請(qǐng)?zhí)枺?/td>: 201410097422.5
• 申請(qǐng)日: 2014-03-14
• 公開（公告）號(hào): CN103914518B
• 公開（公告）日: 2017-05-17
• 發(fā)明（設(shè)計(jì)）人: 陳志軍;張濤;張波;王琳
• 申請(qǐng)（專利權(quán)）人: 小米科技有限責(zé)任公司
• 主分類號(hào): G06F17/30
• 分類號(hào): G06F17/30;G06K9/62
• 代理公司: 北京弘權(quán)知識(shí)產(chǎn)權(quán)代理事務(wù)所(普通合伙)11363
• 代理人: 逯長明,陳蕾

1.一種聚類方法，其特征在于，包括：

根據(jù)類間的Rank-Order距離，進(jìn)行類的迭代合并；

獲取類內(nèi)各個(gè)對(duì)象間的距離；

根據(jù)所述類內(nèi)對(duì)象間的距離計(jì)算所述類內(nèi)的各個(gè)對(duì)象間距離的距離平均值；

將所述距離平均值進(jìn)行歸一化，得到所述類的類內(nèi)聚合度；

針對(duì)迭代合并得到的每個(gè)類，將類內(nèi)對(duì)象間的距離小于所述類內(nèi)聚合度的對(duì)象劃分成一個(gè)新的類，并更新類的數(shù)量；

當(dāng)更新后的類的數(shù)量比更新前的類的數(shù)量少時(shí)，返回執(zhí)行根據(jù)類間的Rank-Order距離進(jìn)行類的迭代合并的步驟，直到更新前后的類的數(shù)量不變時(shí)，得到聚類結(jié)果，所述聚類結(jié)果包括包含多個(gè)對(duì)象的類和包含單個(gè)對(duì)象的類。

2.根據(jù)權(quán)利要求1所述的方法，其特征在于，所述針對(duì)迭代合并得到的每個(gè)類，將類內(nèi)對(duì)象間的距離小于所述類內(nèi)聚合度的對(duì)象劃分成一個(gè)新類，更新類的數(shù)量，采用如下方式：

將類內(nèi)對(duì)象間的距離小于所述類內(nèi)聚合度的對(duì)象進(jìn)行連通標(biāo)記；

根據(jù)所述連通標(biāo)記確定所述類內(nèi)的連通分量；

根據(jù)所述連通分量將所述類拆分成新類，并更新類的數(shù)量。

3.根據(jù)權(quán)利要求1所述的方法，其特征在于，所述根據(jù)類間的Rank-Order距離，進(jìn)行類的迭代合并，采用如下方式：

獲取類間Rank-Order距離，以及獲取類間Rank-Order歸一化距離；

當(dāng)類間的Rank-Order距離小于距離閾值，且所述類間的Rank-Order歸一化距離小于1時(shí)，合并所述類。

4.一種聚類裝置，其特征在于，包括：

迭代合并單元，用于根據(jù)類間的Rank-Order距離，進(jìn)行類的迭代合并；

獲取單元，用于利用類內(nèi)各個(gè)對(duì)象間的距離獲得迭代合并后的類對(duì)應(yīng)的類內(nèi)聚合度；

劃分單元，用于針對(duì)迭代合并得到的每個(gè)類，將類內(nèi)對(duì)象間的距離小于所述類內(nèi)聚合度的對(duì)象劃分成一個(gè)新的類，并更新類的數(shù)量；

判斷單元，用于當(dāng)更新后的類的數(shù)量比更新前的類的數(shù)量少時(shí)，控制所述迭代合并單元執(zhí)行根據(jù)類間的Rank-Order距離進(jìn)行類的迭代合并，直到更新前后的類的數(shù)量不變時(shí)，得到聚類結(jié)果，所述聚類結(jié)果包括包含多個(gè)對(duì)象的類和包含單個(gè)對(duì)象的類；

所述獲取單元包括：

第二獲取子單元，用于獲取類內(nèi)各個(gè)對(duì)象間的距離；

第二計(jì)算子單元，用于根據(jù)所述類內(nèi)對(duì)象間的距離，計(jì)算所述類內(nèi)的各個(gè)對(duì)象間距離的距離平均值；

歸一化子單元，將所述距離平均值進(jìn)行歸一化，得到所述類的類內(nèi)聚合度。

5.根據(jù)權(quán)利要求4所述的裝置，其特征在于，所述劃分單元包括：

第一判斷子單元，用于判斷所述類內(nèi)對(duì)象間的距離是否小于所述類內(nèi)聚合度；

標(biāo)記子單元，用于當(dāng)所述類內(nèi)對(duì)象間的距離小于所述類內(nèi)聚合度時(shí)，將所述類內(nèi)對(duì)象間的距離對(duì)應(yīng)的對(duì)象進(jìn)行連通標(biāo)記；

確定子單元，用于根據(jù)所述連通標(biāo)記確定所述類內(nèi)的連通分量；

拆分子單元，用于根據(jù)所述連通分量將所述類拆分成新類，并更新類的數(shù)量。

6.根據(jù)權(quán)利要求4所述的裝置，其特征在于，所述迭代合并單元包括：

第三獲取子單元，用于獲取類間Rank-Order距離，以及獲取類間Rank-Order歸一化距離；

合并子單元，用于當(dāng)類間的Rank-Order距離小于距離閾值，且所述類間Rank-Order歸一化距離小于1時(shí)，合并所述類。

7.一種終端設(shè)備，其特征在于，包括：

處理器；

用于存儲(chǔ)處理器可執(zhí)行指令的存儲(chǔ)器；

其中，所述處理器被配置為：

根據(jù)類間的Rank-Order距離，進(jìn)行類的迭代合并；

獲取類內(nèi)各個(gè)對(duì)象間的距離；

根據(jù)所述類內(nèi)對(duì)象間的距離計(jì)算所述類內(nèi)的各個(gè)對(duì)象間距離的距離平均值；

將所述距離平均值進(jìn)行歸一化，得到所述類的類內(nèi)聚合度；

針對(duì)迭代合并得到的每個(gè)類，將類內(nèi)對(duì)象間的距離小于所述類內(nèi)聚合度的對(duì)象劃分成一個(gè)新的類，并更新類的數(shù)量；

當(dāng)更新后的類的數(shù)量比更新前的類的數(shù)量少時(shí)，返回執(zhí)行根據(jù)類間的Rank-Order距離進(jìn)行類的迭代合并的步驟，直到更新前后的類的數(shù)量不變；

當(dāng)更新前后的類的數(shù)量不變時(shí)，得到聚類結(jié)果，所述聚類結(jié)果包括包含多個(gè)對(duì)象的類和包含單個(gè)對(duì)象的類。