基於數據場劃分網格的自動聚類方法
2023-09-17 18:29:45
專利名稱：基於數據場劃分網格的自動聚類方法
技術領域：
本發明涉及聚類分析技術領域，尤其涉及一種基於數據場劃分網格的自動聚類方法。
背景技術：
聚類方法能夠根據數據本身的相似性，自動地將數據分成若干個小的簇，使每個簇內部的數據之間彼此相似，而與其他簇內的數據相異。通過這樣的自動聚合，聚類分析能夠幫助人們發現隱藏在數據背後的潛在知識，對於信息的處理和知識的發現有著非常重要的意義。目前，聚類方法已經被廣泛地應用於圖像處理、異常檢測、Web熱點發現、社區發現、 信用卡欺詐檢測、商務數據分析等方面。例如，在模式識別方面，通過對圖片特徵向量的處理，自動將一組動物的圖片自動歸類為羊、狗、蛇等；在異常檢測方面，通過對產品屬性的聚類，自動發現其中的次品；在市場研究方面，通過對用戶進行聚類來將用戶自動歸類，進而輔助決策者制定市場策略。現有的聚類方法為了能夠得到較好的處理效果大都採用了較為複雜的計算方式， 處理速度較慢，無法適用於大規模的數據處理。另外，噪聲也是影響聚類方法質量的一個重要因素。
發明內容
針對以上存在的技術問題，本發明的目的是基於數據場，提出了一種快速高效的自動聚類方法，以解決對大量數據進行聚類處理時的速度和效率問題。為達到上述目的，本發明採用下的技術方案包括以下步驟步驟1，讀取待進行聚類分析的所有數據，數據的維度為n，根據用戶提供的網格劃分參數k將數據空間等分為kn個網格，根並將每個數據分配到相應的網格中；步驟2，將數據場的影響因子ο設定為步驟1所劃分網格的最大邊長；步驟3，將每個網格看作一個具有一定質量的數據點，數據點的質量在數值上等於網格中包含的數據總數量，數據點的坐標為網格的重心坐標，計算由這些數據點相互作用形成的數據場在各個網格重心處的勢值和一階偏導絕對值；步驟4，遍歷步驟1劃分所得每個網格，如果其中某一網格的勢值取值大於該網格每個維度上所有直接相鄰網格的勢值取值，則認為該網格包含聚類中心；步驟5，分別以步驟4找到的每個包含聚類中心的網格為起點，搜索滿足條件的直接相鄰網格，再以搜索到的網格為起點繼續搜索滿足條件的直接相鄰網格，直到搜索不到滿足條件的直接相鄰網格為止，搜索得到的所有滿足條件的網格構成聚類簇；所述條件為， 勢值小於作為起點的網格，並且一階偏導絕對值大於作為起點的網格；步驟6，計算步驟5找到的所有聚類簇中所有網格的質量平均值，將該平均值作為噪聲閥值t ；步驟7，根據步驟6所得噪聲閥值t，將步驟5找到的各聚類簇中的所有質量小於噪聲閥值t的網格刪除；步驟8，當存在兩個或者以上聚類簇包含有相同的網格時，將這兩個或者以上聚類簇合併；步驟9，將所得各聚類簇作為聚類結果輸出。
本發明的技術方案與已有的聚類方法相比，利用劃分網格的方式將運算複雜度降低為0(k)，其中k為網格劃分參數，極大地提高了方案實施的處理速度；通過一階偏導來確定簇的中心和邊緣，可以有效地避免對噪聲的處理，從而使方法具有很好的健壯性。
圖1是數據場勢函數的變化曲線；圖2是數據場勢函數及一階偏導絕對值的變化曲線；圖3是本發明實施例二維數據的坐標分布示意圖；圖4是本發明實施例劃分網格示意圖；圖5是本發明實施例根據勢值找到的局部聚類中心示意圖；圖6是本發明實施例根據聚類中心找到的聚類網格簇示意圖；圖7是本發明實施例的聚類結果示意圖。
具體實施例方式受到物理學中場論的啟發，王樹良等提出數據場的思想。數據通過數據輻射將其數據能量從樣本空間輻射到整個母體空間，接受數據能量並被數據輻射所覆蓋的空間，叫做數據場。數據場可視為一個充滿數據能量的空間，數據通過自己的數據場，對場中的另一數據發射能量。數據場中的數據點之間會相互輻射能量，這些能量相互疊加形成數據場的勢。根據數據對象的不同，數據場的場強函數可以定義為多種形式，在本發明中採用核輻射衍生場，則相應的勢函數如公式(一)。、+ = tr— , ^^ 公式(一)其中，x，y為兩個數據點，σ為數據場的影響因子，I |X-y| I2為兩個數據點X，y之間的歐氏距離，m為數據點y的質量，e為數學常數。所求得丨表示數據點y在χ處的影響作用。公式(一)所定義的數據場勢值函數具有很好的衰減性(如附圖1中σ分別取值1、0. 5和2時的曲線)，適用於聚類方法根據相似性劃分簇的根本目的。附圖1中橫軸是數據場源點的距離，縱軸是m = 1時對應的勢值和一階偏導值。另外，由於數據場定義的勢函數具有很好的連續性，所以只要選取合適的影響因子，數據場就能夠很好地反映數據的分布特性。附圖2即為附圖3所示的數據集中劃線區域的勢值及一階偏導絕對值，橫軸是數據點的(圖3中豎直方向)屬性值，縱軸是勢值和一階偏導絕對值。從簇的邊緣到中心再到邊緣的變化過程中，數據場的勢值是一個先增後減的變化過程，並且在簇中心處取取最大值。數據場勢值的變化情況可以用一階導數來進行描述。在本發明中，數據場勢值的一階偏導根據公式(二)來進行計算，即
權利要求
1. 一種基於數據場劃分網格的自動聚類方法，其特徵在於，包括以下步驟 步驟1，讀取待進行聚類分析的所有數據，數據的維度為n，根據用戶提供的網格劃分參數k將數據空間等分為kn個網格，根並將每個數據分配到相應的網格中； 步驟2，將數據場的影響因子ο設定為步驟1所劃分網格的最大邊長； 步驟3，將每個網格看作一個具有一定質量的數據點，數據點的質量在數值上等於網格中包含的數據總數量，數據點的坐標為網格的重心坐標，計算由這些數據點相互作用形成的數據場在各個網格重心處的勢值和一階偏導絕對值；步驟4，遍歷步驟1劃分所得每個網格，如果其中某一網格的勢值取值大於該網格每個維度上所有直接相鄰網格的勢值取值，則認為該網格包含聚類中心；步驟5，分別以步驟4找到的每個包含聚類中心的網格為起點，搜索滿足條件的直接相鄰網格，再以搜索到的網格為起點繼續搜索滿足條件的直接相鄰網格，直到搜索不到滿足條件的直接相鄰網格為止，搜索得到的所有滿足條件的網格構成聚類簇；所述條件為，勢值小於作為起點的網格，並且一階偏導絕對值大於作為起點的網格；步驟6，計算步驟5找到的所有聚類簇中所有網格的質量平均值，將該平均值作為噪聲閥值t ；步驟7，根據步驟6所得噪聲閥值t，將步驟5找到的各聚類簇中的所有質量小於噪聲閥值t的網格刪除；步驟8，當存在兩個或者以上聚類簇包含有相同的網格時，將這兩個或者以上聚類簇合併；步驟9，將所得各聚類簇作為聚類結果輸出。
全文摘要
本發明提供了一種基於數據場劃分網格的自動聚類方法，將劃分所得每個網格看作一個具有質量的數據點，它們之間彼此相互影響形成數據場，所有數據點之間的相互疊加作用表現為數據場的勢值。本發明首先通過搜索數據場勢值的局部極大值來發現數據的簇中心，進而根據簇中心向周圍搜索並確定簇的邊緣，最終將整個簇搜索出來，可以被應用於圖像處理、社區發現、異常檢測、市場研究等領域。與現有的聚類方法相比，本方法具有處理速度快，並且對噪聲不敏感的特點。
文檔編號G06F17/30GK102184216SQ20111011454
公開日2011年9月14日 申請日期2011年5月4日 優先權日2011年5月4日
發明者王樹良, 陳亞森 申請人:武漢大學