[發明專利]基于分子內聚力理論的數據聚類方法

無效

• 申請號: 201110032779.1
• 申請日: 2011-01-30
• 公開（公告）號: CN102087667A
• 公開（公告）日: 2011-06-08
• 發明（設計）人: 余春艷;張棟;王秀;姜云飛;李建明
• 申請（專利權）人: 福州大學
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 福州元創專利商標代理有限公司 35100
• 代理人: 蔡學俊

技術領域

本發明涉及數據聚類技術領域，特別是一種基于分子內聚力理論的數據聚類方法。

背景技術

聚類是以數學公式為基礎的在不同對象之間的相似度的度量。聚類用來獲得彼此相似而與屬于其他聚類的對象不相似的對象的一種集合。例如，在數據挖掘領域中，用聚類法對數據中的模型和關系進行辨識，提取隱含其中有用的信息和知識。關于聚類算法有很多，如K-MEANS、CURE、DBSCAN、STING、EM、CLIQUE等。

K-means算法是目前為止應用最為廣泛的一種聚類算法，它用于解決某些公知的聚類問題。K-means算法被用于產生根據相似性的距離度量的聚類。K-means聚類算法遵循過分簡單的方法，通過事先固定的聚類的給定數目，如k個聚類，把固定的數據集進行分類。也就是說，該算法以選擇的k個對象為初始聚類的中心，初始的代表為一個簇，該過程繼續進行，根據其與各個簇中心的距離將每個對象重新賦給最近的簇。K-means的一個問題是，k的某個初始值只是根據估算值被賦值的。這樣的k值經常是錯誤的，對最終結果產生負面影響。即使重新初始化k值運行算法，算法可能會以更接近從數據所預期的聚類的數目的k值運行。但是這種重新運行K-means算法的方法不僅費時、低效、麻煩，且仍不能消除或明顯減小k值的負面影響。

發明內容

本發明的目的在于提供一種基于分子內聚力理論的數據聚類方法，該方法不用事先估計類別數目，提高了聚類結果的準確性。

為實現上述目的，本發明的技術方案是：一種基于分子內聚力理論的數據聚類方法，其特征在于：對于高維空間上具有N個數據點的數據集，設每個數據點為一個分子，設多個數據點形成的一個聚類為一個分子團，按如下步驟進行分子內聚力聚類：

步驟（1）：利用分子勢能公式分別計算兩兩數據點之間的內聚力能量值，并保存；

步驟（2）：各數據點根據步驟（1）計算得到的內聚力能量值并行尋找能使合并總能量降低且降到最低的數據點，與其合并為一個聚類，根據聚類完成的先后順序，當一個數據點A被另一數據點B合并為一個聚類后，所述數據點A不再主動尋找與其聚類的數據點，也不再以單個數據點形式作為其他數據點的聚類選擇對象；通過該步驟得到多個聚類和未找到使合并總能量降低數據點而無法聚類的數據點；

步驟（3）：步驟（2）得到的各數據點和聚類并行尋找能使合并總能量降低且降到最低的數據點或聚類，與其合并為一個新的聚類，根據聚類完成的先后順序，當一個數據點或聚類C被另一數據點或聚類D合并為一個新的聚類后，所述數據點或聚類C不再主動尋找與其聚類的數據點或聚類，也不再以原形式作為其他數據點或聚類的聚類選擇對象；

步驟（4）：重復步驟（3），直至所有數據點或聚類都無法使其他數據點或聚類能量降低；

步驟（5）：所有數據點聚類完成，并得到數據點最終的類簇及其類別數目。

本發明的有益效果是將待聚類數據點與分子進行類比，將分子內聚力理論應用于數據聚類過程，在聚類過程中不用事先估計類別數目，從而提高了聚類結果的準確性。

附圖說明

圖1是本發明實施例的工作流程圖。

具體實施方式

本發明基于分子內聚力理論的數據聚類方法，對于高維空間上具有N個數據點的數據集，設每個數據點為一個分子，設多個數據點形成的一個聚類為一個分子團，按如下步驟進行分子內聚力聚類：

步驟（1）：利用分子勢能公式分別計算兩兩數據點之間的內聚力能量值，并保存至能量矩陣中；

步驟（2）：各數據點根據步驟（1）計算得到的內聚力能量值并行尋找能使合并總能量降低且降到最低的數據點，與其合并為一個聚類，根據聚類完成的先后順序，當一個數據點A被另一數據點B合并為一個聚類后，所述數據點A不再主動尋找與其聚類的數據點，也不再以單個數據點形式作為其他數據點的聚類選擇對象；通過該步驟得到多個聚類和未找到使合并總能量降低數據點而無法聚類的數據點；

步驟（3）：步驟（2）得到的各數據點和聚類并行尋找能使合并總能量降低且降到最低的數據點或聚類，與其合并為一個新的聚類，根據聚類完成的先后順序，當一個數據點或聚類C被另一數據點或聚類D合并為一個新的聚類后，所述數據點或聚類C不再主動尋找與其聚類的數據點或聚類，也不再以原形式作為其他數據點或聚類的聚類選擇對象；

步驟（4）：重復步驟（3），直至所有數據點或聚類都無法使其他數據點或聚類能量降低；

步驟（5）：所有數據點聚類完成，并得到數據點最終的類簇及其類別數目。