一種MapReduce平臺上的海量高維數據聚類方法
2023-05-11 08:52:41 1
專利名稱：一種MapReduce平臺上的海量高維數據聚類方法
技術領域：
本發明屬於雲計算與數據挖掘技術領域，具體涉及一種利用MapReduce分布式計算框架對海量高維數據的進行聚類的方法。
背景技術：
高維數據的分析一直是數據挖據中的難題，當維度達到一定高度時，很多對低維數據很有效的聚類方法便不再適用。對於海量高維數據來說，分析和挖掘更涉及到內存和硬碟的限制。近年來，MapReduce及其開源版本Hadoop的研究非常活躍。許多單機算法都在 Hadoop上予以重新實現，為各種算法處理海量數據提供了高可用性和可擴展性。Mahout是Apache旗下基於Hadoop的一個開源項目，提供一些可擴展的機器學習領域經典算法在Hadoop上的實現，包括聚類、分類、推薦過濾、頻繁子項挖掘。Mahout將很多數據挖掘的經典算法，例如K-means，貝葉斯分類，SVM等在Hadoop-MapReduce平臺上重新實現，使得這些傳統算法具有並行處理海量數據的能力。通過使用HadoopJahout中的各種數據挖據算法可以有效地擴展到分布式集群中。但是，在Mahout中針對坐標的聚類方法例如K-means，往往是面向低維數據，在對海量高維數據進行聚類時往往會出現內存不足，性能不佳等問題。
發明內容
本發明的目的是針對海量高維數據的聚類問題，提出一種利用MapReduce分布式計算框架對海量高維數據的進行高效聚類的方法，為用戶提供可定製性和可擴展性，並優化算法效率。本發明提出的高維數據聚類方法，利用Hadoop分布式計算框架，結合切格處理和高效距離計算，對海量高維數據進行分布式並行聚類，實現了高可擴展性和可定製性，提高了聚類的效率和實際應用價值。首先對一些基本概念進行介紹和定義
定義1. MapReduce =MapReduce是谷歌提出的分布式並行計算框架，它讓程式設計師只需關注數據的處理，而數據的分布式存儲和容錯都交給計算框架來解決。在MapReduce平臺上的計算過程中，數據首先被切分到集群的不同節點上，以Key— Value的形式存儲在分布式文件系統中；計算過程主要分為兩個階段:Map階段和Reduce階段。集群中的每臺機器都有一些幾個Map和Reduce任務，Map過程是生成一些<key，value〉，共享同一個key的 <key, value)由同一個Reduce來處理。而我們所使用的Hadoop是MapReduce的開源實現， 由Apache基金會開發。定義2. K-mediods算法=K-Hiediods算法是一種基於坐標的聚類算法，算法基本過程是首先選擇一些中心點代表每個類，之後按每個點與中心點的距離將所有點分配到類中，再將每個類中的所有點坐標求中位數得到新的類中心點，反覆迭代，直到中心點不再變化。K-mediods算法類似於K-Means算法，但克服了 K-Means算法對孤立點的敏感性。定義3.切格設初始數據中的每個點都有D維，本方法將每一維切成N等份(N由用戶指定)，切分完畢後，，每個點都落入唯一的格子中，所有格子在每一維的坐標都是W，N )的一個整數。本發明在聚類過程中使用所有非空格子代替初始點集進行聚類。定義4.記錄在處理過程中，本發明用每一行記錄代表一個點或一個非空格子的所有維坐標。例如「0 7 6 3 5」，代表一個5維格子的坐標。定義5.用ASCII碼計算歐氏距離在計算歐式的距離過程中，由於每一維的切格數N往往小於128，一般情況下常常小於10，可以用每一行記錄的各有效位的ASCII碼直接相減，再求平方和得到歐式距離。例如N=10，兩個格子坐標行分別為「7 5 6 2」和「4 6 8 0」，可以用兩行的單數位ASCII碼直接相減，不用將每個坐標字符轉換為數字再相減，大大提高了計算效率；
根據以上定義，給定海量高維數據集合，每一行為一個點的D維坐標，本發明提出的聚類方法是基於以下性質的
(1)在將每一維切成N格後，每個點都落入唯一的D維格子中，N越大，每個D維格子中的點越少，用D維格子進行聚類與用原始點集進行聚類的結果越接近。(2)由於非空的D維格子數量小於原始點集的數量，而且D維格子的所有坐標均為整數，而原始點集的坐標往往為浮點數，所以數據規模必然下降。(3)在K-mediods迭代聚類過程中，當所有中心點坐標不再變化，每個D維格子已經分配給固定的類，聚類過程完畢。(4)在計算歐式距離時，當坐標值小於128，用兩個ASCII碼直接相減和兩個數字相減求距離結果是一樣的。基於以上性質，本發明方法利用切格和高效距離計算方法，在MapReduce平臺上實現海量高維數據聚類，整個聚類過程具體步驟為
(1)對於輸入的海量高維數據(假設為D維)進行預處理，首先是對原數據各維進行標準化，之後將每一維切成N格，生成非空D維格子的集合；
(2)以步驟(1)輸出的結果作為輸入，實現MapReduce平臺上的K-mediods並行算法， 通過迭代計算對所有非空的D維格子進行聚類；
(3)將步驟(2)得出的D維格子聚類的結果還原成原始的D維數據聚類結果，並按照用戶的需求進行最終整理輸出。整個聚類過程步驟(1)中，所述預處理的操作如下
(1)由用戶指定每一維切成幾格，假設切成N格。N越大，聚類效果越精確，但聚類時間會更長。N越小，聚類的時間越短，但聚類效果會較差；N由用戶根據需求自己設定；
(2)利用MapReduce計算每一維的最大值和最小值Map過程讀入所有數據，將每行記錄中每一維分別輸出，而每個Reduce處理所有記錄在某一維上的坐標，並計算出所有點在此維的最大值和最小值；
(3)利用操作(2)的結果，將原始數據每個坐標標準化即映射為
範圍內的整數。(2)在步驟(1)輸出的所有沈維格子中隨機選擇1500個格子作為最初的中心點。(3)將步驟(1)輸出的所有沈維格子在MapReduce分布式平臺上進行聚類。在計算距離時，用兩個格子坐標記錄中的0，2，4-50為的ASCII碼直接相減求平方和得到歐氏距離。(4)用當前每個類中所有格子在每一維上坐標求中位數，作為新的類中心點坐標。 更新所有的中心點坐標。(5)重複步驟(3)、(4)直到所有中心點坐標不再變化。(6)將已經聚好類的沈維格子還原成原本的點集。並按用戶的需求輸出最終結^ ο
權利要求
1.一種MapReduce平臺上的海量高維數據聚類方法，其特徵在於具體步驟如下(1)對於輸入的海量高維數據進行預處理，設高維數據為D維，首先是對原數據各維進行標準化，之後將每一維切成N格，生成非空的D維格子集合；(2)以步驟(1)輸出的結果作為輸入，實現MapReduce平臺上的K-mediods並行算法， 通過迭代計算對D維格子集合進行聚類；(3)將步驟(2)得出的D維格子聚類的結果還原成原始的D維點集聚類結果，並按照用戶的需求進行最終整理及輸出。
2.根據權利要求1所述的聚類方法，其特徵在於步驟(1)中所述預處理的操作如下(1)由用戶指定每一維切成幾格，假設切成N格，N由用戶指定；(2)利用MapReduce計算每一維的最大值和最小值；(3)利用操作(2)的結果，將原始高維數據標準化，即將每個坐標映射為[0，N)之間的某個整數；(4)去除坐標重複的D維格子；(5)將去重後的數據上傳到HDFS上。
3.根據權利要求1所述的聚類方法，其特徵在於步驟(2)中所述K-mediods過程的操作如下(1)首先在所有的D維格子中選出一些類中心點，作為最初的中心點集合，每個中心點管轄一個類；(2)將中心點集合分發到集群中所有機器的本地硬碟上；(3)分類計算每個D維格子離哪個中心點最近，將格子分配給與其距離最近的中心點所管轄的類中；(4)更新中心點集合計算每個類中所有格子坐標在每一維上的中位數，作為新的中心點坐標，並輸出；(5)按照操作(4)的輸出生成新的中心點集合，並分發到集群中所有機器的本地硬碟上，取代之前的集合；(6)重複操作(3)、(4)和(5)，直到中心點集合中的所有坐標都不再改變；(7)輸出聚類結果。
4.根據權利要求1所述的聚類方法，其特徵在於步驟(3)中所述還原輸出過程的操作如下(1)通過點與格子進行匹配，格子與類的關係，輸出每個點屬於哪個類；(2)收集每個類中的所有點，並將其輸出；(3)按用戶需求進行調整，輸出最終結果。
全文摘要
本發明屬於雲計算與數據挖掘技術領域，具體為一種MapReduce平臺上的海量高維數據聚類方法。該方法首先對原始數據的每一維進行分割，用切分好的非空小格代替原數據中的點集進行聚類，減小數據規模。利用MapReduce的開源實現，使得聚類過程可以在分布式集群上並行完成，克服了單機算法在存儲和計算上的限制。聚類過程採用K-mediods算法的思想，並提出高效的歐式距離計算方法。本發明適用於處理海量高維數據，用戶可以根據集群的計算能力、算法的時間期望以及對聚類精確性的要求對算法進行手動調整，滿足了不同用戶的需要。
文檔編號G06F17/30GK102222092SQ20111014898
公開日2011年10月19日 申請日期2011年6月3日 優先權日2011年6月3日
發明者何震瀛, 廖松博, 汪衛 申請人:復旦大學