基本介紹
- 中文名：疏化處理
- 外文名：Treatment
- 屬於：圖聚類分析與處理過程
- 內容：抽樣數據的處理
- 機制：L-spar、k-最近鄰圖
- 適用：小規模、小區域範圍的圖模型數據
圖聚類,數據抽樣,疏化處理的概述,疏化處理算法,
圖聚類
圖聚類是圖數據挖掘、分析及套用過程中可能會用到的一個關鍵技術。圖聚類通過將圖模型中的每個結點按照聚簇進行分類，可以提高同類別聚簇圖結點對象實體的關聯緊密性、降低不同類聚簇圖結點對象實體的關聯緊密性。隨著超大規模圖數據信息與處理機制的出現，如何高效地進行圖聚類分析與處理，以此來挖掘圖數據中的潛在有效數據信息，已成為人工智慧、數據挖掘等領域的熱點研究方向之一。國內外研究人員對圖聚類算法進行了廣泛的研究，提出了很多的圖聚類算法，包括經典聚類算法(如劃分式聚類算法)、層次式圖聚類算法、基於密度的圖聚類算法、最小生成圖樹聚類算法等。
數據抽樣
數據抽樣是圖聚類分析與處理機制中的一種高效數據處理方式。數據抽樣首先從整體數據集合中抽取局部樣本，然後對樣本數據進行數據挖掘、處理與分析。數據抽樣可以實現時間與挖掘處理結果的高性能比以及提高圖聚類分析與處理的有效性。
疏化處理的概述
在圖聚類分析與處理過程中，首先對圖模型中的結點和邊分別進行數據抽樣(疏化處理)，然後對疏化處理的結果進行圖聚類分析。作為圖聚類分析與處理機制中較為重要的一個環節，疏化處理機制已被套用於多個研究方向。針對小規模、小區域範圍的圖模型數據信息，現有的疏化處理機制主要包含L-spar、k-最近鄰圖等幾種方法。
這些方法在對小規模、小區域範圍的圖模型數據信息進行處理時，能夠得到很好的處理效果，但是在對較大規模、較大區域範圍的圖模型數據信息進行處理和套用於分散式集群計算環境時，處理效果比較差。隨著圖模型套用產品的不斷發展和套用規模的不斷擴大，圖模型的數據信息變得越來越複雜，依靠單一的計算環境對圖數據進行處理已不能滿足數據分析與處理的需要。針對這種情況，能夠通過與大規模計算機服務終端相關聯來對大規模數據進行分析與處理的MapReduce並行計算理論框架得到了廣泛套用。
哈希算法，是根據設定的哈希函式H(key)和處理衝突方法將一組關鍵字映像到一個有限的地址區間上，並以關鍵字在地址區間中的像作為記錄在表中的存儲位置，這種表稱為哈希表或散列，所得存儲位置稱為哈希地址或散列地址。最小哈希算法是哈希算法的一種，傳統的最小哈希算法(Minhash)主要套用於快速推算多個數據集合之間的相似程度，現已被套用於多個熱點研究領域，如文本操作、視頻數據處理等。Minhash算法主要依據Jaccard相似度進行相似推算。
以MapReduce架構理論為基礎，通過Minhash算法進行並行化分析，設計出一種基於並行計算的高效疏化處理算法，即MR-LSH算法。MR-LSH算法使用並行計算MapReduce框架結構對圖聚類分析稀疏化操作過程中的多個任務進行了高效的推算分析與處理，這些任務包括鄰居結點數據集合推算、Minhash算法簽名推演(對於每個結點而言)、每個結點之間的簽名哈希存儲以及圖聚類過程中的稀疏化處理計算。並在Hadoop計算環境下，對MR-LSH算法的性能進行了模擬實驗與分析，實驗結果表明，MR-LSH算法的套用能夠保證圖聚類稀疏化分析與處理機制的高效性。
疏化處理算法
依據模擬實驗中採用的圖模型稀疏化處理機制的不同，其圖模型稀疏化比率參數值e也隨之改變，為了應對不同數據信息量與分類的圖模型數據信息，其最佳e值也會有所不同，本實驗初始化e=0.15，然後進行相關操作。為了顯示出MR-LSH算法在超大規模、超大區域範圍的分散式集群計算環境下的高效性能，模擬實驗中採取多種並行計算環境下的執行算法。MR-LSH算法首先對Map任務階段與Reduce任務階段進行過程處理，其次對圖模型數據信息進行分析，實現圖聚類過程下稀疏化分析與處理機制。
從模擬實驗分析結果可知，對於超大規模、超大區域範圍的分散式集群計算環境下，使用Ha-doop並行計算平台能夠有效降低時間損失，從而使得Speedup得到大幅度提高。依據並行計算平台理論架構體系的原理，圖模型數據信息規模愈大時，其圖聚類過程稀疏化比率參數值就增大，且呈現線性關係;然而隨著分散式集群計算環境下各個結點的通信互動頻繁，也會消耗一定數據信息性能，在圖模型數據信息互動規模較小時，圖聚類過程稀疏化分析與處理機制會降低，其e參數值同比減小。與此同時，當Speedup與分散式集群計算環境逐漸增加時，其圖聚類過程稀疏化分析與處理機制會有所提高，其e參數值同比增加。
通過模擬實驗可知，新型的MR-LSH算法適用於超大規模、超大區域範圍的分散式集群計算環境下的圖數據信息，由於在MR-LSH算法中添加了排序組合機制，使得結點與鄰接結點之間的通信互動消耗得到降低，即圖數據信息規模愈大，其MR-LSH算法效率性價比愈高。
