聚類方法和設備的製作方法
2023-06-10 14:31:26
專利名稱：聚類方法和設備的製作方法
技術領域：
本發明涉及數據挖掘領域，更具體地涉及聚類方法。
背景技術：
作為數據挖掘的重要組成部分，聚類分析在處理大規模數據中成為不可或缺的重要工具。聚類分析是一種重要的人類活動。通過適當聚類，事物才便於研究，事物的內部規律才可能為人類所掌握。在很多應用中，聚類分析作為一種數據預處理過程，是進一步分析和處理數據的基礎。聚類分析已經廣泛地用於許多應用領域，包括市場研究、模式識別、數據分析和圖像處理。聚類可以幫助市場分析人員根據購買模式從顧客中發現不同的顧客群。在生物學中，聚類能用來推導植物和動物分類，根據相似功能進行分類。但是，傳統的聚類算法對樣本的分布形狀敏感，不能滿足大規模數據集和不同樣本形狀的需求。
發明內容
為了解決上述問題之一，本發明提出了一種聚類方法，包括以下步驟在數據集中選取聚類中心，對於每個所述聚類中心確定特徵點集合；根據所述特徵點集合將所述數據集中的數據劃分到聚類中；根據所述劃分到聚類中的數據與所述特徵點集合的關係確定新的特徵點集合；根據所述新的特徵點集合確定聚類結果。
根據本發明的實施例，確定新的特徵點集合的步驟包括根據所述數據與所述特徵點集合的關係確定所述特徵點集合中的特徵點的修正值；根據所述特徵點的當前值與所述特徵點的修正值確定新的特徵點。
根據本發明的實施例，根據所述數據與所述特徵點集合的關係確定新的特徵點集合的步驟之後還包括判斷所述新的特徵點集合與之前的特徵點集合中的特徵點的值是否相同；如果所述新的特徵點集合與之前的特徵點集合中的特徵點的值相同，則根據所述新的特徵點集合確定聚類結果；如果所述新的特徵點集合與之前的特徵點集合中的特徵點的值不同，則重複根據所述新的特徵點集合將所述數據劃分到聚類中的步驟以及確定新的特徵點集合的步驟。
根據本發明的實施例，根據所述特徵點集合將所述數據集中的數據劃分到聚類中的步驟包括計算所述數據與所述特徵點集合的加權距離；將所述數據劃分到所述加權距離最小的聚類。
根據本發明的實施例，計算所述數據與所述特徵點集合的加權距離的步驟包括根據離散係數確定所述數據與所述特徵點的距離的權值。
根據本發明的實施例，所述數據與所述特徵點的距離d的權值根據以下公式得出w(d)＝e-F×d，其中d為數據與特徵點的距離，F為所述離散係數，w(d)為所述數據與所述特徵點的距離的權值。
根據本發明的實施例，所述數據與特徵點集合的加權距離通過以下公式得出其中，x為所述數據，c為所述特徵點集合，ci為特徵點集合c中的特徵點，其中i＝1，2......m，m為所述特徵點集合中的特徵點的數目，d(x，ci)為數據x與特徵點ci的距離，w(d(x，ci))為數據x與特徵點ci的距離的權值，D(x，c)為所述數據x與所述特徵點集合c的加權距離。
根據本發明的實施例，所述確定新的特徵點集合的步驟包括確定新的特徵點集合使得所述特徵點在所述聚類中更加均勻地分布。
根據本發明的實施例，所述特徵點的修正值通過以下公式獲得其中，x為數據，ci為所述特徵點的當前值，ci』為所述特徵點的修正值，其中i＝1，2，......m，m為所述特徵點集合中的特徵點的數目，d(x，ci)為數據x與特徵點ci的距離，w(d(x，ci))為數據x與特徵點ci的距離的歸一化值，cn為所述特徵點集合中距離數據x距離最近的特徵點。
根據本發明的實施例，所述新的特徵點通過以下公式獲得Ci″＝(i×ci′+(m-i)×ci)/m，其中，ci為所述特徵點的當前值，ci』為所述特徵點的修正值，ci」為所述新的特徵點，其中i＝1，2，......m，m為所述特徵點集合中的特徵點的數目。
根據本發明的實施例，在數據集中選取聚類中心的步驟包括在所述數據集中隨機選取所述聚類中心。
根據本發明的實施例，對於每個所述聚類中心確定特徵點集合的步驟包括將所述特徵點集合中的特徵點的初始值均確定為與所述聚類中心重合。
本發明還提出了一種設備，包括初始化模塊、聚類模塊、特徵點更新模塊和聚類結果確定模塊。其中，所述初始化模塊用於在數據集中選取聚類中心，對於每個所述聚類中心確定特徵點集合；所述聚類模塊用於根據所述特徵點集合將所述數據集中的數據劃分到聚類中；所述特徵點更新模塊用於根據所述劃分到聚類中的數據與所述特徵點集合的關係確定新的特徵點集合；所述聚類結果確定模塊用於根據所述新的特徵點集合確定聚類結果。
根據本發明的實施例，所述特徵點更新模塊包括特徵點修正模塊和特徵點擾動模塊。其中，所述特徵點修正模塊用於根據所述數據與所述特徵點集合的關係確定所述特徵點集合中的特徵點的修正值；所述特徵點擾動模塊用於根據所述特徵點的當前值與所述特徵點的修正值確定新的特徵點。
根據本發明的實施例，該設備還包括判斷模塊，其用於判斷所述新的特徵點集合與之前的特徵點集合中的特徵點的值是否相同；所述聚類結果確定模塊用於在所述判斷模塊判斷所述新的特徵點集合與之前的特徵點集合中的特徵點的值相同時，根據所述新的特徵點集合確定聚類結果；所述聚類模塊還用於在所述判斷模塊判斷所述新的特徵點集合與之前的特徵點集合中的特徵點的值不同時，根據所述新的特徵點集合將所述數據劃分到聚類中；所述特徵點更新模塊還用於在所述判斷模塊判斷所述新的特徵點集合與之前的特徵點集合中的特徵點的值不同時，在所述聚類模塊將所述數據劃分到聚類中之後，確定新的特徵點集合。
根據本發明的實施例，所述聚類模塊包括加權模塊和劃分模塊。其中，所述加權模塊用於計算所述數據與所述特徵點集合的加權距離；所述劃分模塊用於將所述數據劃分到所述加權距離最小的聚類。
根據本發明的實施例，所述特徵點更新模塊還用於確定新的特徵點集合使得所述特徵點在所述聚類中更加均勻地分布。
本發明所提出的聚類方法和設備對數據集不敏感，並且算法複雜度和傳統算法在同一數量級。
本發明上述的和/或附加的方面和優點從下面結合附圖對實施例的描述中將變得明顯和容易理解，其中 圖1為根據本發明的一個實施例的聚類方法的流程圖； 圖2為根據本發明的一個實施例的設備的結構示意圖。
具體實施例方式 下面詳細描述本發明的實施例，所述實施例的示例在附圖中示出。下面通過參考附圖描述的實施例是示例性的，僅用於解釋本發明，而不能解釋為對本發明的限制。
本發明提出了一種聚類方法，或稱聚類算法，如圖1所示為本發明的聚類方法的一個實施例的流程圖。如圖1所示，該實施例100包括以下步驟 S101在數據集中選取聚類中心，對於每個聚類中心確定特徵點集合。
作為本發明的一個實施例，可以在數據集中隨機選取聚類中心。例如，如果數據集需要劃分為k個聚類，則隨機選取k個聚類中心。當然，這僅是本發明的一個示例，也可以採用其他的方法確定聚類中心。
特徵點集合中可以包括多個特徵點，為了便於描述，在下文中稱為m個特徵點。作為本發明的一個實施例，m個特徵點的初始值確定為均與聚類中心重合。
S102根據特徵點集合將數據集中的數據劃分到聚類中。
作為本發明的一個實施例，可以通過引入離散係數F計算數據點與特徵點集合的加權距離。
例如，距離d的權值可以通過以下公式得出 w(d)＝e-F×d，其中，d為數據點與特徵點的距離，F為離散係數，w(d)為距離d的權值。
作為本發明的一個實施例，數據點x與特徵點集合的加權距離可以通過以下公式得出 其中，D(x，c)為數據點x與特徵點集合的加權距離，x為數據點，c為特徵點集合，ci為特徵點集合c中的特徵點，其中i＝1，2......m，m為特徵點集合中的特徵點的數目，d(x，ci)為數據點x與特徵點ci的距離，w(d(x，ci))為數據x與特徵點ci的距離的權值。
作為本發明的一個實施例，選取加權距離最小的特徵點集合，將數據x劃分到該特徵點集合所對應的聚類中。
S103根據劃分到聚類中的數據與特徵點集合的關係確定新的特徵點集合。
作為本發明的一個實施例，確定新的特徵點以使得特徵點儘量均勻地分布在相應的聚類中，每個特徵點沿著同類更密集的方向移動，同類的特徵點應相互排斥。
作為本發明的一個實施例，首先確定特徵點的修正值，然後使用該修正值對特徵點施加擾動來獲得新的特徵點。
例如，假定上一次迭代中得到的聚類特徵點集合為c(c1，c2，...，cm)，則特徵點集合的修正值C′(c′1，c′2，...，c′m)為 其中，x為數據點，ci為特徵點的當前值，ci』為特徵點的修正值，其中i＝1，2，......m，m為特徵點集合中的特徵點的數目，d(x，ci)為數據x與特徵點ci的距離，w(d(x，ci))為數據x與特徵點ci的距離的歸一化值，cn為所述特徵點集合中距離數據x距離最近的特徵點。
例如，上次得到的特徵點集合為m重特徵點Ci(ci1，ci2，...，cim)，則下次迭代生成的特徵點的修正值也為m重特徵點Ci′(ci1′，ci2′，...，cim′)，其中i＝1，2，......，k，k為聚類中心的數目。通過施加擾動來獲得新的特徵點集合Ci″，例如可以通過以下公式獲得 Ci″＝(i×Ci′+(m-i)×Ci)/m， 其中，ci為所述特徵點的當前值，ci』為所述特徵點的修正值，ci」為所述新的特徵點，其中i＝1，2，......m，m為所述特徵點集合中的特徵點的數目。
步驟S104判斷新的特徵點集合與原特徵點集合是否相同。如果相同，則執行步驟S105；如果不同，則重複執行步驟S102和S103。
也就是，重複進行對數據點劃分聚類以及確定新的特徵點的步驟，直到特徵點的值不再發生變化。
S105根據所述新的特徵點集合確定聚類結果。例如，該聚類結果可以包括根據最後得到的特徵點集合對數據集劃分聚類；以及，將最後得到的特徵點集合進行運算，如加權平均等等，得到聚類中心。
如圖2所示為本發明的設備的一個實施例的結構示意圖。如圖2所示，該設備200包括初始化模塊201、聚類模塊202、特徵點更新模塊203和聚類結果確定模塊204。
其中，初始化模塊201用於在數據集中選取聚類中心，對於每個聚類中心確定特徵點集合。
聚類模塊202用於根據特徵點集合將數據集中的數據劃分到聚類中。
特徵點更新模塊203用於根據劃分到聚類中的數據與特徵點集合的關係確定新的特徵點集合。
聚類結果確定模塊205用於根據新的特徵點集合確定聚類結果。
作為本發明的一個實施例，特徵點更新模塊203包括特徵點修正模塊2031和特徵點擾動模塊2032。
其中，特徵點修正模塊2031用於根據數據與特徵點集合的關係確定特徵點集合中的特徵點的修正值。
特徵點擾動模塊2032用於根據特徵點的當前值與特徵點的修正值確定新的特徵點。
作為本發明的一個實施例，該設備200還包括判斷模塊204，其用於判斷新的特徵點集合與之前的特徵點集合中的特徵點的值是否相同。
在上述實施例中，聚類結果確定模塊205用於在判斷模塊204判斷新的特徵點集合與之前的特徵點集合中的特徵點的值相同時，根據新的特徵點集合確定聚類結果。
在上述實施例中，聚類模塊202還用於在判斷模塊204判斷新的特徵點集合與之前的特徵點集合中的特徵點的值不同時，根據新的特徵點集合將數據劃分到聚類中。
在上述實施例中，特徵點更新模塊203還用於在判斷模塊204判斷新的特徵點集合與之前的特徵點集合中的特徵點的值不同時，在聚類模塊202將數據劃分到聚類中之後，確定新的特徵點集合。
作為本發明的一個實施例，聚類模塊202包括加權模塊2021和劃分模塊2022。
其中，加權模塊2021用於計算數據與特徵點集合的加權距離。
劃分模塊2022用於將數據劃分到加權距離最小的聚類。
作為本發明的一個實施例，特徵點更新模塊203還用於確定新的特徵點集合使得特徵點在聚類中更加均勻地分布。
本發明所提出的聚類方法和設備使用特徵點集合代替聚類中心，並使用重合點擾動方法，可以使得特徵點在聚類中儘量均勻地分布，從而使得該聚類處理適用於不同的樣本形狀，對數據集不敏感。同時，該聚類算法的時間複雜度和空間複雜度與傳統的聚類算法保持在同一數量級，沒有增加實現的複雜度。
儘管已經示出和描述了本發明的實施例，對於本領域的普通技術人員而言，可以理解在不脫離本發明的原理和精神的情況下可以對這些實施例進行多種變化、修改、替換和變型，本發明的範圍由所附權利要求及其等同限定。
權利要求
1、一種聚類方法，其特徵在於，包括以下步驟
在數據集中選取聚類中心，對於每個所述聚類中心確定特徵點集合；
根據所述特徵點集合將所述數據集中的數據劃分到聚類中；
根據所述劃分到聚類中的數據與所述特徵點集合的關係確定新的特徵點集合；
根據所述新的特徵點集合確定聚類結果。
2、根據權利要求1所述的聚類方法，其特徵在於，確定新的特徵點集合的步驟包括
根據所述數據與所述特徵點集合的關係確定所述特徵點集合中的特徵點的修正值；
根據所述特徵點的當前值與所述特徵點的修正值確定新的特徵點。
3、根據權利要求1所述的聚類方法，其特徵在於，根據所述數據與所述特徵點集合的關係確定新的特徵點集合的步驟之後還包括
判斷所述新的特徵點集合與之前的特徵點集合中的特徵點的值是否相同；
如果所述新的特徵點集合與之前的特徵點集合中的特徵點的值相同，則根據所述新的特徵點集合確定聚類結果；
如果所述新的特徵點集合與之前的特徵點集合中的特徵點的值不同，則重複根據所述新的特徵點集合將所述數據劃分到聚類中的步驟以及確定新的特徵點集合的步驟。
4、根據權利要求1所述的聚類方法，其特徵在於，根據所述特徵點集合將所述數據集中的數據劃分到聚類中的步驟包括
計算所述數據與所述特徵點集合的加權距離；
將所述數據劃分到所述加權距離最小的聚類。
5、根據權利要求4所述的聚類方法，其特徵在於，計算所述數據與所述特徵點集合的加權距離的步驟包括
根據離散係數確定所述數據與所述特徵點的距離的權值。
6、根據權利要求5所述的聚類方法，其特徵在於，所述數據與所述特徵點的距離d的權值根據以下公式得出
w(d)＝e-F×d，
其中d為數據與特徵點的距離，F為所述離散係數，w(d)為所述數據與所述特徵點的距離的權值。
7、根據權利要求6所述的聚類方法，其特徵在於，所述數據與特徵點集合的加權距離通過以下公式得出
其中，x為所述數據，c為所述特徵點集合，ci為特徵點集合c中的特徵點，其中i＝1，2......m，m為所述特徵點集合中的特徵點的數目，d(x，ci)為數據x與特徵點ci的距離，w(d(x，ci))為數據x與特徵點ci的距離的權值，D(x，c)為所述數據x與所述特徵點集合c的加權距離。
8、根據權利要求1或2所述的聚類方法，其特徵在於，所述確定新的特徵點集合的步驟包括
確定新的特徵點集合使得所述特徵點在所述聚類中更加均勻地分布。
9、根據權利要求8所述的聚類方法，其特徵在於，所述特徵點的修正值通過以下公式獲得
其中，x為數據，ci為所述特徵點的當前值，ci』為所述特徵點的修正值，其中i＝1，2，......m，m為所述特徵點集合中的特徵點的數目，d(x，ci)為數據x與特徵點ci的距離，w(d(x，ci))為數據x與特徵點ci的距離的歸一化值，cn為所述特徵點集合中距離數據x距離最近的特徵點。
10、根據權利要求9所述的聚類方法，其特徵在於，所述新的特徵點通過以下公式獲得
ci″＝(i×ci′+(m-i)×ci)/m，
其中，ci為所述特徵點的當前值，ci』為所述特徵點的修正值，ci」為所述新的特徵點，其中i＝1，2，......m，m為所述特徵點集合中的特徵點的數目。
11、根據權利要求1所述的聚類方法，其特徵在於，在數據集中選取聚類中心的步驟包括
在所述數據集中隨機選取所述聚類中心。
12、根據權利要求1所述的聚類方法，其特徵在於，對於每個所述聚類中心確定特徵點集合的步驟包括
將所述特徵點集合中的特徵點的初始值均確定為與所述聚類中心重合。
13、一種設備，其特徵在於，包括初始化模塊、聚類模塊、特徵點更新模塊和聚類結果確定模塊，其中，
所述初始化模塊用於在數據集中選取聚類中心，對於每個所述聚類中心確定特徵點集合；
所述聚類模塊用於根據所述特徵點集合將所述數據集中的數據劃分到聚類中；
所述特徵點更新模塊用於根據所述劃分到聚類中的數據與所述特徵點集合的關係確定新的特徵點集合；
所述聚類結果確定模塊用於根據所述新的特徵點集合確定聚類結果。
14、根據權利要求13所述的設備，其特徵在於，所述特徵點更新模塊包括特徵點修正模塊和特徵點擾動模塊，其中，
所述特徵點修正模塊用於根據所述數據與所述特徵點集合的關係確定所述特徵點集合中的特徵點的修正值；
所述特徵點擾動模塊用於根據所述特徵點的當前值與所述特徵點的修正值確定新的特徵點。
15、根據權利要求13所述的設備，其特徵在於，還包括判斷模塊，其用於判斷所述新的特徵點集合與之前的特徵點集合中的特徵點的值是否相同；
所述聚類結果確定模塊用於在所述判斷模塊判斷所述新的特徵點集合與之前的特徵點集合中的特徵點的值相同時，根據所述新的特徵點集合確定聚類結果；
所述聚類模塊還用於在所述判斷模塊判斷所述新的特徵點集合與之前的特徵點集合中的特徵點的值不同時，根據所述新的特徵點集合將所述數據劃分到聚類中；
所述特徵點更新模塊還用於在所述判斷模塊判斷所述新的特徵點集合與之前的特徵點集合中的特徵點的值不同時，在所述聚類模塊將所述數據劃分到聚類中之後，確定新的特徵點集合。
16、根據權利要求13所述的設備，其特徵在於，所述聚類模塊包括加權模塊和劃分模塊，其中，
所述加權模塊用於計算所述數據與所述特徵點集合的加權距離；
所述劃分模塊用於將所述數據劃分到所述加權距離最小的聚類。
17、根據權利要求13或14所述的設備，其特徵在於，所述特徵點更新模塊還用於確定新的特徵點集合使得所述特徵點在所述聚類中更加均勻地分布。
全文摘要
本發明提出了一種聚類方法和設備。該方法包括以下步驟在數據集中選取聚類中心，對於每個所述聚類中心確定特徵點集合；根據所述特徵點集合將所述數據集中的數據劃分到聚類中；根據所述劃分到聚類中的數據與所述特徵點集合的關係確定新的特徵點集合；根據所述新的特徵點集合確定聚類結果。本發明所提出的聚類方法和設備對數據集不敏感，並且沒有增加算法的複雜度。
文檔編號G06F17/30GK101556621SQ20091020345
公開日2009年10月14日 申請日期2009年5月21日 優先權日2009年5月21日
發明者曹先彬, 中 汪, 許言午, 彤 李, 博 寧, 林人俊, 吳長俠 申請人:中國科學技術大學