[發(fā)明專利]Hadoop框架下高維海量數(shù)據(jù)GMM聚類方法

有效

• 申請?zhí)枺?/td>: 201310047023.3
• 申請日: 2013-01-25
• 公開（公告）號: CN103077253A
• 公開（公告）日: 2013-05-01
• 發(fā)明（設(shè)計(jì)）人: 崔江濤;李林;司蓁;彭延國;史瑋;陳煜;崔小利;王博
• 申請（專利權(quán)）人: 西安電子科技大學(xué)
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 陜西電子工業(yè)專利中心 61205
• 代理人: 田文英;王品華

1.Hadoop框架下高維海量數(shù)據(jù)GMM聚類方法，包括如下步驟：

(1)組建局域網(wǎng)

將多臺計(jì)算機(jī)連接到同一局域網(wǎng)中，每臺計(jì)算機(jī)作為一個(gè)節(jié)點(diǎn)，建立能夠相互通信的集群；

(2)建立Hadoop平臺

對集群中的每個(gè)節(jié)點(diǎn)配置Hadoop0.20.2文件，通過文件中屬性參數(shù)dfs.namenode和dfs.datanode的設(shè)置，使集群中包含一個(gè)名字節(jié)點(diǎn)和多個(gè)數(shù)據(jù)節(jié)點(diǎn)；通過文件中屬性參數(shù)mapred.jobtracker和mapred.tasktracker的設(shè)置，使集群中包含一個(gè)調(diào)度節(jié)點(diǎn)和多個(gè)任務(wù)節(jié)點(diǎn)，建立開源的Hadoop平臺；

(3)上傳數(shù)據(jù)到集群

使用Hadoop分布式文件命令dfs-put將待聚類數(shù)據(jù)集上傳至Hadoop平臺的各個(gè)節(jié)點(diǎn)上；

(4)初始聚類

采用KMeans聚類方法，對集群中節(jié)點(diǎn)上的數(shù)據(jù)進(jìn)行初始粗略聚類，得到初始的聚類；

(5)計(jì)算各聚類的參數(shù)和判別函數(shù)

5a)計(jì)算初始的聚類每一個(gè)類的均值；

5b)統(tǒng)計(jì)初始聚類每一個(gè)類中數(shù)據(jù)的個(gè)數(shù)，用統(tǒng)計(jì)的數(shù)據(jù)個(gè)數(shù)除以待聚類數(shù)據(jù)集中數(shù)據(jù)的總數(shù)，得到初始聚類每一個(gè)類的權(quán)重；

5c)計(jì)算初始的聚類每一個(gè)類的方差；

5d)計(jì)算判別函數(shù)

按照下式計(jì)算高斯概率密度值：

G=exp(-(x-ui)Σi-1(x-ui)/2)(2π)d|Σi|]]>

其中，G表示高斯概率密度的值，x表示待聚類數(shù)據(jù)集中的任意一個(gè)向量數(shù)據(jù)，u_i表示第i個(gè)類的均值，i表示聚類中的第i個(gè)類，∑_i表示第i個(gè)類的方差，exp表示以e為底的指數(shù)運(yùn)算；

按照下式計(jì)算判別函數(shù)的值：

L=Σx∈Dlog(Σi=1KpiG(x|ui,Σi))]]>

其中，L表示判別函數(shù)值，x表示待聚類數(shù)據(jù)集中的任意一個(gè)向量數(shù)據(jù)，D表示待聚類數(shù)據(jù)集，K表示聚類中類的個(gè)數(shù)，i表示聚類中的第i個(gè)類，p_i表示第i個(gè)類在聚類中的權(quán)重，G表示第i個(gè)類的高斯概率密度值，u_i表示第i個(gè)類的均值，Σ_i表示第i個(gè)類的方差；

(6)判斷聚類是否完成

判斷判別函數(shù)的值是否在設(shè)定域值之內(nèi)，若在閾值內(nèi)，則聚類結(jié)束，執(zhí)行步驟(10)，若不在閾值內(nèi)，表示聚類尚未結(jié)束，執(zhí)行步驟(7)；

(7)重新聚類

7a)啟動第一個(gè)Map任務(wù)，掃描待聚類數(shù)據(jù)集，每次讀入一條數(shù)據(jù)；

7b)對每次讀入的數(shù)據(jù)，采用以下公式計(jì)算讀入的數(shù)據(jù)到聚類中每個(gè)類的概率值：

γ(x,i)=piG(x|ui,Σi)Σh=1KPhG(x|uh,Σh)]]>

其中，γ(x，i)表示待聚類數(shù)據(jù)集中數(shù)據(jù)x到聚類中第i個(gè)類的概率值，p_i表示第i個(gè)聚類在待聚類數(shù)據(jù)集中的權(quán)重，G為第i個(gè)聚類的概率密度函數(shù)值，x表示待聚類數(shù)據(jù)集中的數(shù)據(jù)，u_i表示第i個(gè)聚類的均值，Σ_i表示第i個(gè)聚類的方差，K表示聚類的個(gè)數(shù)，h表示聚類中的第h個(gè)類，P_h表示第h個(gè)聚類在待聚類數(shù)據(jù)集中的權(quán)重，u_h表示第h個(gè)類的均值，∑_h表示第h個(gè)聚類的方差；

7c)選取概率值中的最大值，將步驟7a)讀入數(shù)據(jù)分配到最大值對應(yīng)的類；

7d)判斷是否讀取完待聚類數(shù)據(jù)集，若未讀取完，則執(zhí)行步驟7a)，若讀取完，則表示得到了新聚類，執(zhí)行步驟(8)；

(8)計(jì)算新聚類中每一個(gè)類的均值、權(quán)重

啟動第一個(gè)Reduce任務(wù)，計(jì)算第一個(gè)Map任務(wù)傳入的聚類數(shù)據(jù)，按照步驟5a)的計(jì)算方法獲得新聚類中每一個(gè)類的均值，按照步驟5b)的計(jì)算方法獲得新聚類中每一個(gè)類的權(quán)重；

(9)計(jì)算新聚類中每一個(gè)類的方差

9a)啟動第二個(gè)Map任務(wù)，第二次掃描待聚類數(shù)據(jù)集，每次讀入一條數(shù)據(jù)；

9b)對每次讀入的數(shù)據(jù)，采用以下公式計(jì)算Map/Reduce中間值：

D_mid＝(x-u)²

其中，D_mid表示Map/Reduce中間值，x表示步驟9a)讀入的一條數(shù)據(jù)，u表示x所屬類的均值；

9c)啟動第二個(gè)Reduce任務(wù)，對9b)的中間值先求和，再求和的根，獲得新聚類的方差；

9d)判斷是否讀取完待聚類數(shù)據(jù)集，若未讀取完，則執(zhí)行步驟9a)，若讀取完，執(zhí)行步驟(5)；

(10)輸出聚類結(jié)果

聚類結(jié)束后，聚類中每一個(gè)類的均值、權(quán)重、方差作為聚類結(jié)果輸出。