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

有效

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

技術領域

本公開涉及數據挖掘領域，特別涉及一種層次聚類的方法及裝置。

背景技術

在數據挖掘領域中，通常需要對大量的數據進行分析，以獲取有價值的分析結果。聚類算法是數據挖掘領域中用于分析數據的一種重要算法，該算法用于將由多個數據組成的集合按照數據的不同類別進行分類，其目的是盡可能地將相似度較大的數據聚合成一類，以方便后續的數據分析。其中，層次聚類是較常用的一種聚類算法。

相關技術在實現層次聚類的方法時，是通過計算兩個類之間的距離，即類間距離，從而將類間距離小于一定值的兩個類合并為一個新類。由于每個類可能包含不止一個數據對象，因此，在計算類間距離時，需將一個類中的所有數據對象與另一個類的所有數據對象進行兩兩計算，對所有的計算結果進行統計，得到平均值或最小值，將其作為類間距離，從而根據類間距離實現后續的聚類。

在實現本公開的過程中，發明人發現相關技術至少存在以下問題：

相關技術中，通過計算類間距離實現層次聚類時，其計算量過大，當類中包含的數據對象很多時，將會耗費過多的時間和資源，并且，由于每個類中可能包含不屬于該類的數據對象，即噪聲，使用該數據對象進行類間距離的計算并形成新類之后，可能會引入更多的噪聲，導致聚類結果較差，不利于后續的數據分析。

發明內容

為克服相關技術中存在的問題，本公開提供一種層次聚類的方法及裝置。

根據本公開實施例的第一方面，提供一種層次聚類的方法，包括：

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

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

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

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

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

結合第一方面，在第一方面的第一種可能的實現方式中，根據聚類結果，對所述第一類所對應的數據對象進行篩選，得到所述第一類的代表數據對象包括：

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

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

結合第一方面，在第一方面的第二種可能的實現方式中，基于所述第一類的代表數據對象以及第二類所對應的數據對象，計算類間距離包括：

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

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

結合第一方面的第二種可能的實現方式，在第一方面的第三種可能的實現方式中，基于所述第一類的代表數據對象、所述第一類的代表數據對象的權重以及第二類所對應的數據對象，計算類間距離包括：

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

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

結合第一方面的第三種可能的實現方式，在第一方面的第四種可能的實現方式中，基于所述類間距離，對所述數據對象集合進行層次聚類包括：

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

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

根據本公開實施例的第二方面，提供一種層次聚類的裝置，包括：

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

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