[發(fā)明專利]一種基于最小生成樹的海量數(shù)據(jù)聚類處理方法

在審

• 申請?zhí)枺?/td>: 201710467400.7
• 申請日: 2017-06-20
• 公開（公告）號: CN107506778A
• 公開（公告）日: 2017-12-22
• 發(fā)明（設(shè)計）人: 程林;賀海磊;劉滿君;周勤勇;張彥濤;梁才浩;劉琛;江軼
• 申請（專利權(quán)）人: 清華大學(xué);中國電力科學(xué)研究院;國家電網(wǎng)公司;國網(wǎng)江蘇省電力公司電力科學(xué)研究院
• 主分類號: G06K9/62
• 分類號: G06K9/62
• 代理公司: 北京清亦華知識產(chǎn)權(quán)代理事務(wù)所(普通合伙)11201
• 代理人: 羅文群

技術(shù)領(lǐng)域

本發(fā)明一種基于最小生成樹的海量數(shù)據(jù)聚類處理方法，屬于分類學(xué)及數(shù)據(jù)挖掘算法技術(shù)領(lǐng)域。

背景技術(shù)

隨著計算機科學(xué)的進(jìn)步，越來越多的數(shù)據(jù)分析中由于樣本數(shù)量龐大，樣本點難以按照統(tǒng)一的分布形式描述，因此需要進(jìn)行前期的數(shù)據(jù)聚類處理。聚類是將一系列有關(guān)聯(lián)的數(shù)據(jù)對象彼此組合，從而構(gòu)成若干相關(guān)關(guān)系較強的數(shù)據(jù)集合的方法，使得在每一個數(shù)據(jù)集合中的多個對象彼此具有較為緊密的聯(lián)系關(guān)系。

目前常用的聚類方法包含k-means聚類方法、層次聚類法和模糊聚類算法等。這些方法多數(shù)依賴于初始狀態(tài)的選取，聚類依據(jù)完全依照樣本點之間的距離度量進(jìn)行判定，對一些有特定物理意義的樣本聚類效果并不好。

然而在機器學(xué)習(xí)領(lǐng)域及相關(guān)的應(yīng)用場景中，常常會出現(xiàn)物理意義大規(guī)模的數(shù)據(jù)訓(xùn)練模型的場景，如若不對數(shù)據(jù)進(jìn)行聚類處理，則訓(xùn)練過程對硬件在內(nèi)部存儲和計算速度均有較高的要求。此外，通過常用聚類方法得到的聚類結(jié)果難以融入物理意義的概念，因此得到的結(jié)果往往不盡人意，導(dǎo)致后續(xù)數(shù)據(jù)分析與模型訓(xùn)練工作出現(xiàn)較大誤差，進(jìn)而對相關(guān)研究的開展造成重大損失。為了改善這個問題，需要在傳統(tǒng)聚類方法的基礎(chǔ)上加以改善，使用新的方式對物理意義較強的樣本數(shù)據(jù)進(jìn)行處理，從而得到理想的數(shù)據(jù)結(jié)果。

在聚類算法中加入人工決策輔助是避免上述誤差的可行方法之一。常用聚類方法過程單一，計算過程冗長復(fù)雜，難以融入人工判斷決策的影響，因此本專利中使用了最小生成樹算法設(shè)計了一種改進(jìn)的樣本點聚類方法。最小生成樹算法是規(guī)劃應(yīng)用領(lǐng)域常用的算法之一，通過計算多個節(jié)點的最小生成樹可以實現(xiàn)工程應(yīng)用中建設(shè)費用或其他各方面性能最優(yōu)的設(shè)計方案，并且可以建立數(shù)據(jù)點的樹狀結(jié)構(gòu)，由于其簡明的特點方便決策者進(jìn)行分析，因此適合用于提升聚類方法的處理性能。

天氣條件信息在電力研究領(lǐng)域常用于各類分布式電源的出力預(yù)測問題中。然而，由于天氣條件種類多且數(shù)據(jù)繁雜，因此無法再實際計算中直接應(yīng)用。

發(fā)明內(nèi)容

本發(fā)明的目的是提出一種基于最小生成樹的海量數(shù)據(jù)聚類處理方法，通過普利姆算法和人工輔助決策實現(xiàn)海量數(shù)據(jù)的聚類處理，從而為后續(xù)數(shù)據(jù)分析工作提供支持。

本發(fā)明提出的基于最小生成樹的海量數(shù)據(jù)聚類處理方法，包括以下步驟：

(1)將待處理海量數(shù)據(jù)U轉(zhuǎn)化為節(jié)點矩陣A；

設(shè)定待處理海量數(shù)據(jù)U中的任意兩個數(shù)據(jù)之間的距離為dist(·,·)，將該距離dist(·,·)作為矩陣A的賦值，與節(jié)點矩陣A相對應(yīng)的是一個全連通圖，全連通圖的邊權(quán)重為dist(·,·)，并將該距離dist(·,·)作為任意兩個數(shù)據(jù)之間的邊權(quán)重，設(shè)待處理海量數(shù)據(jù)的數(shù)目為m，則節(jié)點矩陣A如下式所示：

(2)利用普利姆方法對節(jié)點矩陣A進(jìn)行處理，得到一個最小邊權(quán)重節(jié)點稀疏矩陣A_m：

A_m＝L_m+U_m

與上述節(jié)點稀疏矩陣A_m相對應(yīng)的是一個最小生成樹，其中L_m為A_m的下半部分，U_m為A_m的上半部分；

(3)分別統(tǒng)計上述步驟(2)中的矩陣L_m的第i行和第i列中與最小生成樹中的節(jié)點i相連的邊的數(shù)量D(U)，并將該數(shù)量D(U)記為節(jié)點矩陣A中相應(yīng)節(jié)點的度；

(4)根據(jù)上述數(shù)量D(U)，利用下式，計算與D(U)大于2的節(jié)點相連的邊的權(quán)重差異度量

其中，j和k分別為步驟(2)的最小生成樹中與節(jié)點i相連的節(jié)點；

(5)設(shè)定一個海量數(shù)據(jù)聚類處理的聚類值n，根據(jù)上述權(quán)重差異度量的大小，對相應(yīng)節(jié)點進(jìn)行排序，得到一個節(jié)點序列，將節(jié)點序列的前n-1個節(jié)點中邊權(quán)重最大的邊從上述步驟(2)的最小生成樹中刪除，得到n個互不相連的樹，每個樹中的節(jié)點構(gòu)成一個數(shù)據(jù)聚類，共得到n個數(shù)據(jù)聚類，即完成基于最小生成樹的海量數(shù)據(jù)聚類處理。

本發(fā)明提出的基于最小生成樹的海量數(shù)據(jù)聚類處理方法，其特點是：

本發(fā)明通過計算最小生成樹的普利姆算法，提出了海量數(shù)據(jù)的聚類處理方法，也適用于物理意義較強的多維樣本數(shù)據(jù)的聚類處理。由于使用了最小生成樹算法，因此該方法在計算過程中可以結(jié)合聚類技術(shù)中的距離度量作為樹支權(quán)重進(jìn)行解析，從而生成整體聯(lián)系最為緊密的最小生成樹。在此基礎(chǔ)上，結(jié)合清晰簡明的樣本點樹狀結(jié)構(gòu)，可以便于決策者進(jìn)行適當(dāng)?shù)娜斯ぽo助修正，最終得到理想的樣本簇分類。

本發(fā)明具有以下優(yōu)點：