[發明專利]數據聚類方法和裝置

在審

• 申請號: 201310733986.9
• 申請日: 2013-12-26
• 公開（公告）號: CN103699653A
• 公開（公告）日: 2014-04-02
• 發明（設計）人: 季鐸
• 申請（專利權）人: 沈陽航空航天大學
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 北京康信知識產權代理有限責任公司 11240
• 代理人: 吳貴明;張永明

技術領域

本發明涉及計算機領域，具體而言，涉及一種數據聚類方法和裝置。

背景技術

聚類是一種數據集合的劃分方法，其主要過程是根據一定的相似性或距離計算函數按照距離相近的樣本劃分到相同的類中，而距離較遠的樣本劃分到不同的類中的原則自動地將數據集分成若干類（簇）。由于聚類是一種無指導的學習方法，無需耗費大量的人力、物力，因此自動聚類技術已成為最有效的信息處理手段之一。

雖然聚類的用途很廣泛，但傳統的層次聚類算法的時間復雜度和空間復雜度高，對于大規模聚類問題運行速度慢，并對硬件的要求很高，需要用到服務器，無法在PC機上完成。傳統的層次聚類算法，分為基于矩陣和基于優先隊列兩種，其相對最簡單的單鏈接層次聚類的時間復雜度都分別達到了O(n³)和O(n²log?n)，二者的空間復雜度為O(n²)。由此可見，傳統的層次聚類算法的時間復雜度和空間復雜度都比較高，對于大規模聚類問題，特別是在通用的PC計算機上很難完成。目前，有一些處理大規模數據聚類的方法，如CURE和CURD，但算法過于復雜，需要預先對樣本數據進行復雜分析，不適合在PC計算機上實現大規模數據聚類。

因此，從理論上和實用上的需求出發，研制一種面向普通PC計算機的大規模數據的層次聚類算法成為了急需解決的新課題。

發明內容

本發明實施例提供了一種數據聚類方法和裝置，以至少解決傳統聚類過程中運行速度慢的技術問題。

根據本發明實施例的一個方面，提供了一種數據聚類方法，包括：重復執行以下步驟直到完成對待聚類的樣本集合中的所有樣本的聚類，其中，當前待聚類樣本集合的初始值為待聚類的樣本集合中的每個樣本：根據樣本距離排序關系在當前待聚類樣本集合中查找第一樣本集合和/或第二樣本集合，其中，第一樣本集合和第二樣本集合中的每個成員包含以下至少之一：樣本、樣本集合，其中，樣本集合包括多個樣本，第一樣本集合中的每個成員各自形成一個階梯簇；第二樣本集合中的每個成員自身滿足聚類條件，但與第二樣本集合中的其他成員或者與第一樣本集合中的成員之間不滿足聚類條件；并行對第一樣本集合中的每個成員和/或第二樣本集合中的每個成員執行聚類操作，每個成員執行完成聚類操作后形成一個樣本集合；根據聚類操作所得到的樣本集合對當前待聚類樣本集合中的成員進行更新。

作為一種可選的方案，在重復執行步驟直到完成對待聚類的樣本集合中的所有樣本的聚類之前，還包括：獲取待聚類的樣本集合中的每兩個樣本之間的距離；按照距離的大小對待聚類的樣本集合中的每兩個樣本形成的樣本對進行排序，形成樣本距離排序關系。

作為一種可選的方案，根據樣本距離排序關系在當前待聚類樣本集合中查找第一樣本集合包括：若當前待聚類樣本集合中的多個成員滿足以下條件，則將滿足以下條件的多個成員記錄為第一樣本集合中的一個成員：當前待聚類樣本集合中的多個成員按照樣本距離排序關系中記錄的排序順序依次滿足聚類條件，且與當前待聚類樣本集合中的其他成員不滿足聚類條件。

作為一種可選的方案，根據樣本距離排序關系在當前待聚類樣本集合中查找第二樣本集合包括：若當前待聚類樣本集合中的相鄰兩個成員滿足以下條件，則將滿足以下條件的多個成員記錄為第二樣本集合中的一個成員：當前待聚類樣本集合中的相鄰兩個成員之間滿足聚類條件，且與當前待聚類樣本集合中的其他成員不滿足聚類條件。

作為一種可選的方案，根據聚類操作所得到的樣本集合對當前待聚類樣本集合中的成員進行更新包括：將當前待聚類樣本集合中的成員更新為聚類操作所得到的樣本集合；或者將當前待聚類樣本集合中除未參與聚類操作的成員之外的成員更新為聚類操作所得到的樣本集合，并在更新后的當前待聚類樣本集合中保留未參與聚類操作的成員。

作為一種可選的方案，其特征在于，聚類條件包括以下至少之一：樣本與樣本之間的距離滿足第一預定閾值；樣本與樣本集合之間的距離滿足第二預定閾值；樣本集合與樣本集合之間的距離滿足第三預定閾值。

作為一種可選的方案，距離包括以下至少之一：最近距離，最遠距離。