[發明專利]層次聚類的方法及裝置

有效

• 申請號: 201410602569.5
• 申請日: 2014-10-31
• 公開（公告）號: CN104391879B
• 公開（公告）日: 2017-10-10
• 發明（設計）人: 陳志軍;代陽;楊松
• 申請（專利權）人: 小米科技有限責任公司
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 北京三高永信知識產權代理有限責任公司11138
• 代理人: 張所明

1.一種層次聚類的方法，其特征在于，所述方法包括：

獲取待聚類的數據對象集合，所述數據對象集合包括多個類，每個類對應于至少一個數據對象；

對第一類所對應的數據對象進行聚類，得到聚類結果，所述第一類所對應的數據對象個數超過第一預設閾值，所述聚類結果包括多個簇，每個簇包括至少一個數據對象；

根據聚類結果，對所述第一類所對應的數據對象進行篩選，得到所述第一類的代表數據對象；

基于所述第一類的代表數據對象以及第二類所對應的數據對象，計算類間距離；

基于所述類間距離，對所述數據對象集合進行層次聚類。

2.根據權利要求1所述的方法，其特征在于，根據聚類結果，對所述第一類所對應的數據對象進行篩選，得到所述第一類的代表數據對象包括：

根據所述多個簇所包括的數據對象，在每個簇中，將與所述簇的中心點距離最近的數據對象作為所述簇的代表數據對象；

將所述多個簇的代表數據對象作為所述第一類的代表數據對象。

3.根據權利要求1所述的方法，其特征在于，基于所述第一類的代表數據對象以及第二類所對應的數據對象，計算類間距離包括：

根據所述第一類中簇所包含數據對象的個數，獲取所述第一類的代表數據對象的權重；

基于所述第一類的代表數據對象、所述第一類的代表數據對象的權重以及第二類所對應的數據對象，計算類間距離。

4.根據權利要求3所述的方法，其特征在于，基于所述第一類的代表數據對象、所述第一類的代表數據對象的權重以及第二類所對應的數據對象，計算類間距離包括：

對于第一代表數據對象和第二代表數據對象，計算數據對象之間的第一距離，根據第一代表數據對象的權重和第二代表數據對象的權重，對所述第一距離進行加權處理，得到第一代表數據對象和第二代表數據對象之間的加權距離；或，

對于第一代表數據對象和所述第二類中的第三數據對象，計算數據對象之間的第二距離，根據第一代表數據對象的權重，對所述第二距離進行加權處理，得到第一代表數據對象和所述第三數據對象之間的加權距離。

5.根據權利要求1所述的方法，其特征在于，基于所述類間距離，對所述數據對象集合進行層次聚類包括：

基于所述類間距離，對所述數據對象集合中的多個類進行合并；

基于合并后的類，繼續執行對第一類的聚類和篩選，直到基于聚類和篩選的結果所計算得到的類間距離大于第二預設閾值，輸出層次聚類結果。

6.一種層次聚類的裝置，其特征在于，所述裝置包括：

獲取模塊，用于獲取待聚類的數據對象集合，所述數據對象集合包括多個類，每個類對應于至少一個數據對象；

第一聚類模塊，用于對第一類所對應的數據對象進行聚類，得到聚類結果，所述第一類所對應的數據對象個數超過第一預設閾值，所述聚類結果包括多個簇，每個簇包括至少一個數據對象；

篩選模塊，用于根據聚類結果，對所述第一類所對應的數據對象進行篩選，得到所述第一類的代表數據對象；

計算模塊，用于基于所述第一類的代表數據對象以及第二類所對應的數據對象，計算類間距離；

第二聚類模塊，用于基于所述類間距離，對所述數據對象集合進行層次聚類。

7.根據權利要求6所述的裝置，其特征在于，所述篩選模塊，用于根據所述多個簇所包括的數據對象，在每個簇中，將與所述簇的中心點距離最近的數據對象作為所述簇的代表數據對象；將所述多個簇的代表數據對象作為所述第一類的代表數據對象。

8.根據權利要求6所述的裝置，其特征在于，所述計算模塊，用于根據所述第一類中簇所包含數據對象的個數，獲取所述第一類的代表數據對象的權重；基于所述第一類的代表數據對象、所述第一類的代表數據對象的權重以及第二類所對應的數據對象，計算類間距離。

9.根據權利要求8所述的裝置，其特征在于，所述計算模塊，用于對于第一代表數據對象和第二代表數據對象，計算數據對象之間的第一距離，根據第一代表數據對象的權重和第二代表數據對象的權重，對所述第一距離進行加權處理，得到第一代表數據對象和第二代表數據對象之間的加權距離；或，用于對于第一代表數據對象和所述第二類中的第三數據對象，計算數據對象之間的第二距離，根據第一代表數據對象的權重，對所述第二距離進行加權處理，得到第一代表數據對象和所述第三數據對象之間的加權距離。