基於中心索引的海量高維數據的聚類方法
2023-05-11 09:00:26 2
專利名稱：基於中心索引的海量高維數據的聚類方法
技術領域：
本發明涉及一種聚類方法，尤其是一種基於中心索引的海量高維數據的聚類方法，屬於數據聚類的技術領域。
背景技術：
聚類是一種重要的數據分析手段，它按照一定的要求和規律對數據集中的數據對象進行區分和分類，進而把一個沒有類別標記的數據集按照某種準則劃分成若干個子集(類)，並使相似的數據對象儘可能地歸為一類、不相似的數據對象儘可能地劃分到不同的類中。與此同時，隨著信息技術的迅猛發展，聚類所面臨的不僅是數據量越來越大的問題，更重要的還是數據的高維度問題。換句話說，由於數據來源的豐富多樣，圖文聲像甚至視頻都逐漸成為聚類處理的目標對象，這些特殊對象的屬性信息往往要從數十個甚至數百個方面來表現，其每一個屬性都成為數據對象的一個維，對高維數據的聚類分析，已成為眾多領域研究方向之一。K-means方法不僅對低維數據的聚類非常有效，而且對高維數據的聚類也有很好的支持。近年來的研究表明，對高維數據的聚類可以歸為兩類，一類是基於密度的聚類方法，另一類就是基於k-means的聚類方法。k-means聚類方法將η個數據對象劃分為k個聚類，以便使得所獲得的聚類滿足:同一聚類中的對象相似度較高，而不同聚類中的對象相似度較小。聚類相似度是利用各聚類中對象的均值所獲得一個「中心對象」(引力中心)來進行計算的。為了更好的刻畫數據，對於海量數據，很小的k值意義不大。對於海量數據，k通常具有較大的值，例如超出數萬都很普遍。這樣對於海量高維數據，k-means的計算代價非
母曰蟲吊印貝。
發明內容
本發明的目的是克服現有技術中存在的不足，提供一種基於中心索引的海量高維數據的聚類方法，其能有效縮短海量數據的聚類時間，降低海量數據的聚類代價。按照本發明提供的技術方案，所述基於中心索引的海量高維數據的聚類方法，所述海量高維數據的聚類方法包括如下步驟:
a、在包含海量高維數據的數據集中選取k個中心點，並按照距離將所選取的k個中心點聚類分成m個分區，m個分區中每個分區包含若干聚類點；
b、獲取上述m個分區中每個分區對應的中心點和半徑，並將每個分區對應的中心點作為索引輸入；
C、將上述數據集中的數據點與上述m個分區中每個分區對應的中心點進行距離比較，得到所需的選定分區及選定分區中心點；其中，所述選定分區中心點為選定分區的中心點，所述選定分區中心點與所述數據集中的數據點的距離最近；
d、將數據集中的數據點與選定分區內的聚類點進行距離比較，以對所述數據集中的數據點進行分析聚類。所述步驟d中，選定分區的半徑為rl，未選定分區的半徑為r2 ;數據集中的數據點到選定分區的距離為dl，到未選定分區的距離為d2;若d2彡dl+ rl+ r2，則對於未選定分區中任意一點，到數據集中的數據點的距離要大於選定分區中任意一聚類點到數據集中的數據點的距離時，數據集中的數據點僅與選定分區內的聚類點進行距離比較，以進行所需的分析聚類。所述步驟a中，聚類成分區的數量m遠遠小於中心點的個數k。本發明的優點:增加了對選取k個中心點的聚類過程，聚類的結果作為索引的依據，通過裁減中心點減少了比較需要的計算代價，能有效縮短海量數據的聚類時間，降低海量數據的聚類代價。
圖1為本發明將k個中心點聚類成m個分區後的示意圖。圖2為本發明中獲取m個分區的中心點後的示意圖。圖3為本發明計算並比較數據點與分區的中心點的距離的示意圖。圖4為本發明得到選定分區，並將數據點與選定分區的聚類點進行距離比較後的示意圖。圖5為本發明的一種仿真比較示意圖。圖6為本發明的另一種仿真比較示意圖。
具體實施例方式下面結合具體附圖和實施例對本發明作進一步說明。為了能夠降低k-menns聚類方法對海量高維數據的聚類開銷，本發明的聚類方法包括如下步驟，具體地，包括:
a、在包含海量高維數據的數據集中選取k個中心點，並按照距離將所選取的k個中心點聚類分成m個分區，m個分區中每個分區包含若干聚類點；
本發明實施例中，k個中心點為在海量高維數據的數據集中隨機選取，依照k-means的聚類方法，根據距離將k個中心點聚類分成m個分區，其中，聚類得到分區的數量m遠遠小於選取中心點的數量k ;聚類得到的每個分區均包含若干個聚類點；
b、獲取上述m個分區中每個分區對應的中心點和半徑，並將每個分區對應的中心點作為索引輸入；
本發明實施例中，根據每個分區的平均值來計算得到每個分區的中心點，所述半徑為每個分區內對應分區的中心點到每個分區中最遠點的距離，所述獲取每個分區中心點的中心點及半徑的方法與k-means聚類方法相同；
C、將上述數據集中的數據點與上述m個分區中每個分區對應的中心點進行距離比較，得到所需的選定分區及選定 分區中心點；其中，所述選定分區中心點為選定分區的中心點，所述選定分區中心點與所述數據集中的數據點的距離最近；
k-means聚類方法中是根據歐式距離來進行聚類；本發明實施例中，所述數據集中的數據點為包含海量高維數據的數據集中的任意一點，根據所述數據點與上述每個分區中心點的距離比較，來獲取選定分區點與選定分區中心點。d、將數據集中的數據點與選定分區內的聚類點進行距離比較，以對所述數據集中的數據點進行分析聚類。所述步驟d中，選定分區的半徑為rl，未選定分區的半徑為r2 ;數據集中的數據點到選定分區的距離為dl，到未選定分區的距離為d2;若d2彡dl+ rl+ r2，則對於未選定分區中任意一點，到數據集中的數據點的距離要大於選定分區中任意一聚類點到數據集中的數據點的距離時，數據集中的數據點僅與選定分區內的聚類點進行距離比較，以進行所需的分析聚類。若不進行上述限制，通過一次距離比較找到的選定中心點不一定是真正最近的，真正最近的中心點就會被裁減掉了。添加上述限制後，得到的是真正的最近點。本發明是增加了對選取k個中心點的聚類過程，聚類的結果作為索引的依據，通過裁減中心點減少了比較需要的計算代價。由於每個分區中的聚類點即為初始選定的k個中心點，因此，根據數據點與分區中聚類點的距離比較進行聚類，能夠實現與k-means聚類結果相類似的聚類目的。本發明實施例中，由於在選定分區與未選定分區之間，通過距離與半徑的比較，省去一些未選定分區中聚類點與數據集中的數據點的比較過程，從而能夠有效地降低對海量高維數據的聚類開銷。具體地,本發明實施例中，在MapReduce (MapReduce是一種編程模型,用於大規模數據集(大於1TB)的並行運算)中實現基於索引的k-means算法。首先把輸入數據裝換成二進位格式並且得到最初的中心，即得到k個中心點。之後反覆調用map函數和reduce函數。每次循環中，在map初始化階段，會給中心加索引。在map函數中，把點分到距離它們最近的聚類中，之後在reduce函數中重新計算新的中心。實施例1 圖廣圖4為本發明的一個仿真實例示意圖，其中，為將k個中心點聚類為5個分區，即m=5。計算每個分區的中心點與半徑，對於包含海量高維數據的數據集中的給定點P，計算給定點P與每個分區的中心點的距離，以獲取與給定點P距離最近的分區中心點及對應的分區，即能得到選定分區及選定分區中心點。當獲得選定分區及選定分區中心點後，計算給定點P與所述選定分區內聚類點的距離，根據k-means的聚類方法可知，根據給定點P與聚類點的距離，能夠實現對數據集中數據點的聚類。在本發明實施例中，對於獲得選定分區後，給定點P是否需要與未選定分區內聚類點進行距離比較，可以根據給定點P與選定分區、未選定分區之間的關係來確定；當給定點P只需要與選定分區內的聚類點或部分未選定分區內的聚類點進行距離比較以作為聚類分析的依據時，能夠大大縮小進行聚類的開銷。實施例2
本實施例中，以高維音頻數據作為研究對應，實施環境包括14臺電腦的集群，每臺電腦有兩個晶片，雙核(2.70 GHz)，CPUSE5400，4GB內存，使用Iinux作業系統。Hadoop版本為0.20.3，MapReduce系統的所有實驗都使用Javal.6。其中，音頻資料庫包括從網際網路上下載的大約十萬首MP3歌曲，這些歌曲中大部分是流行音樂，剩下的是古典和民間音樂。從音頻數據中提取主要特徵並且得到26維的數據集。一個26維空間中的點代表一首歌的一個框架。數據集總共包括167876767個26維向量。基準程序是Mahout的k-means實現,它是由Apache開發的著名的機器學習庫。對I萬首歌的音頻數據進行聚類，k分別為50，500和5000，為了去除環境的影響，這個實驗在單個計算機上進行。所述用於計算計算機的配置和前面的集群的數據結點的配置相同。運行時間的比較如表I所示:
表I運行時間與聚類個數的對照
權利要求
1.一種基於中心索引的海量高維數據的聚類方法，其特徵是，所述海量高維數據的聚類方法包括如下步驟: (a)、在包含海量高維數據的數據集中選取k個中心點，並按照距離將所選取的k個中心點聚類分成m個分區，m個分區中每個分區包含若干聚類點； (b)、獲取上述m個分區中每個分區對應的中心點和半徑，並將每個分區對應的中心點作為索引輸入； (C)、將上述數據集中的數據點與上述m個分區中每個分區對應的中心點進行距離比較，得到所需的選定分區及選定分區中心點；其中，所述選定分區中心點為選定分區的中心點，所述選定分區中心點與所述數據集中的數據點的距離最近； (d)、將數據集中的數據點與選定分區內的聚類點進行距離比較，以對所述數據集中的數據點進行分析聚類。
2.根據權利要求1所述的基於中心索引的海量高維數據的聚類方法，其特徵是:所述步驟(d)中，選定分區的半徑為rl，未選定分區的半徑為r2;數據集中的數據點到選定分區的距離為dl，到未選定分區的距離為d2;若d2彡dl+ rl+ r2，則對於未選定分區中任意一點，到數據集中的數據點的距離要大於選定分區中任意一聚類點到數據集中的數據點的距離時，數據集中的數據點僅與選定分區內的聚類點進行距離比較，以進行所需的分析聚類。
3.根據權利要求1所述的基於中心索引的海量高維數據的聚類方法，其特徵是:所述步驟(a)中，聚類成分 區的數量m遠遠小於中心點的個數k。
全文摘要
本發明涉及一種基於中心索引的海量高維數據的聚類方法，其包括如下步驟a、在包含海量高維數據的數據集中選取k個中心點，並按照距離將所選取的k個中心點聚類分成m個分區；b、獲取上述m個分區的中心點和半徑，並將每個分區對應的中心點作為索引輸入；c、將上述數據集中的數據點與上述m個分區中每個分區對應的中心點進行距離比較，得到所需的選定分區及選定分區中心點；所述選定分區中心點為選定分區的中心點，所述選定分區中心點與所述數據集中的數據點的距離最近；d、將數據集中的數據點與選定分區內的聚類點進行距離比較，以對所述數據集中的數據點進行分析聚類。本發明能有效縮短海量數據的聚類時間，降低海量數據的聚類代價。
文檔編號G06F17/30GK103150372SQ20131007501
公開日2013年6月12日 申請日期2013年3月8日 優先權日2013年3月8日
發明者李秋虹, 趙航濤 申請人:江蘇唯實科技有限公司