[發(fā)明專(zhuān)利]一種并行AP傳播的XML大數(shù)據(jù)聚類(lèi)集成方法

有效

• 申請(qǐng)?zhí)枺?/td>: 201410171627.3
• 申請(qǐng)日: 2014-04-25
• 公開(kāi)（公告）號(hào): CN103942318B
• 公開(kāi)（公告）日: 2017-05-17
• 發(fā)明（設(shè)計(jì)）人: 蔣勇
• 申請(qǐng)（專(zhuān)利權(quán)）人: 湖南化工職業(yè)技術(shù)學(xué)院
• 主分類(lèi)號(hào): G06F17/30
• 分類(lèi)號(hào): G06F17/30;G06F9/44
• 代理公司: 北京科億知識(shí)產(chǎn)權(quán)代理事務(wù)所(普通合伙)11350
• 代理人: 湯東鳳

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

本發(fā)明屬于大數(shù)據(jù)集成方法應(yīng)用領(lǐng)域，尤其涉及一種并行AP傳播的XML大數(shù)據(jù)聚類(lèi)集成方法。

背景技術(shù)

目前，XML大數(shù)據(jù)也與其它類(lèi)型的大數(shù)據(jù)一樣，具有體積浩大、結(jié)構(gòu)復(fù)雜、生成速度快、價(jià)值巨大但密度低的特點(diǎn)，且數(shù)據(jù)量從MB到GB、TB、PB直至ZB，此外，它的數(shù)據(jù)呈現(xiàn)非凸特性且分布很不均勻，數(shù)據(jù)噪聲和孤立點(diǎn)多，而且許多數(shù)據(jù)以數(shù)據(jù)流的形式出現(xiàn)在Web中，因此，對(duì)這些速度變化快且具有很強(qiáng)的時(shí)效性的XML大數(shù)據(jù)，若采用傳統(tǒng)的算法進(jìn)行聚類(lèi)集成，則這些集成方法在解決XML大數(shù)據(jù)集存在明顯不足，其主要表現(xiàn)在：(1)占用的存儲(chǔ)空間大，預(yù)測(cè)速度慢，預(yù)測(cè)效果差；(2)在線機(jī)器學(xué)習(xí)困難，對(duì)小規(guī)模數(shù)據(jù)有效，對(duì)大規(guī)模數(shù)據(jù)效果差；(3)動(dòng)態(tài)性、實(shí)時(shí)性差，不能處理流數(shù)據(jù)；(4)算法由于缺乏先驗(yàn)知識(shí)，對(duì)XML數(shù)據(jù)分布的全局特點(diǎn)把握不準(zhǔn)，最后導(dǎo)致聚類(lèi)精度及聚類(lèi)結(jié)果得不到滿意的要求。

因此，發(fā)明一種并行AP傳播的XML大數(shù)據(jù)聚類(lèi)集成方法顯得非常必要。

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

本發(fā)明的目的是基于PC機(jī)分布式環(huán)境下提供一種并行AP傳播的XML大數(shù)據(jù)聚類(lèi)集成方法，旨在傳統(tǒng)的算法存在著占用的存儲(chǔ)空間大，預(yù)測(cè)速度慢，預(yù)測(cè)效果差，在線機(jī)器學(xué)習(xí)困難，對(duì)小規(guī)模數(shù)據(jù)有效，對(duì)大規(guī)模數(shù)據(jù)效果差處理效率低，對(duì)XML數(shù)據(jù)分布的全局特點(diǎn)把握不準(zhǔn)的問(wèn)題。本發(fā)明是這樣實(shí)現(xiàn)的，

一種并行AP傳播的XML大數(shù)據(jù)聚類(lèi)集成方法的必要技術(shù)方案：

本發(fā)明是這樣實(shí)現(xiàn)的，一種并行AP傳播的XML大數(shù)據(jù)聚類(lèi)集成方法包括，

步驟一：對(duì)每一個(gè)XML大數(shù)據(jù)進(jìn)行清洗、劃分和抽取等預(yù)處理；

步驟二：把抽取的子樹(shù)中所有關(guān)鍵詞看成該數(shù)據(jù)點(diǎn)特征描述；

步驟三：借鑒聚類(lèi)集成的基本思想；

步驟四：內(nèi)聯(lián)相似度大矩陣分解思想；

步驟五：實(shí)現(xiàn)最終的聚類(lèi)集成。

一種并行AP傳播的XML大數(shù)據(jù)聚類(lèi)集成方法的次要技術(shù)方案：

進(jìn)一步，在步驟一，先對(duì)XML文檔集中的每一個(gè)XML大數(shù)據(jù)進(jìn)行清洗、劃分和抽取等預(yù)處理，求出抽取的每個(gè)子樹(shù)從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)的所有路徑，并以路徑作為消歧的輸入源對(duì)歧義詞進(jìn)行消歧處理，求取每個(gè)關(guān)鍵詞的語(yǔ)義相關(guān)度及上下文語(yǔ)義相關(guān)相似度；

進(jìn)一步，在步驟二，把消歧處理后的每一個(gè)子樹(shù)中所有的關(guān)鍵詞看成是該數(shù)據(jù)點(diǎn)的特征描述，這樣所有的數(shù)據(jù)點(diǎn)組成的XML文檔集就是n個(gè)n×n維特征空間向量；

進(jìn)一步，在步驟三，借鑒聚類(lèi)集成的基本思想，用隨機(jī)子空間分類(lèi)器作為基聚類(lèi)器構(gòu)建K個(gè)分類(lèi)器，K個(gè)分類(lèi)器并行地從n個(gè)n×n特征向量空間中隨機(jī)抽取m樣本數(shù)據(jù)進(jìn)行訓(xùn)練以求得其分類(lèi)，其方法是對(duì)新樣本集建立一個(gè)無(wú)向圖，每個(gè)樣本點(diǎn)是圖的一個(gè)頂點(diǎn)，圖的邊是頂點(diǎn)間的連線，它表示文檔之間的相似度，其相似度采用標(biāo)記語(yǔ)義樹(shù)的方法求得，并按照它們組成的邊的權(quán)重最小、一條路徑的加權(quán)之和最大的原則把圖劃分成不同的路徑，路徑的劃分采用K-鄰近法，這樣把劃分的每一條路徑組成一個(gè)類(lèi)別，所有不同的劃分路徑組成K個(gè)初始分類(lèi)。

進(jìn)一步，在步驟四，從初始的簇集結(jié)果出發(fā)，按照簇集、簇和數(shù)據(jù)點(diǎn)三者之間的相互關(guān)系來(lái)構(gòu)建內(nèi)聯(lián)相似度矩陣，通過(guò)設(shè)計(jì)的并行的LANCZOS—QR算法求解其特征值對(duì)應(yīng)的特征向量來(lái)獲得低維向量的嵌入；

進(jìn)一步，在步驟五，通過(guò)設(shè)計(jì)的基于系統(tǒng)能量的AP算法并行地實(shí)現(xiàn)最終的聚類(lèi)集成。

本發(fā)明提供的并行AP傳播的XML大數(shù)據(jù)聚類(lèi)集成方法為了擴(kuò)大聚類(lèi)成員的差異性、提高聚類(lèi)的性能，選用并行隨機(jī)子空間的基聚類(lèi)器來(lái)進(jìn)行初始訓(xùn)練，這樣不會(huì)因XML文檔數(shù)量成倍增加而影響聚類(lèi)的質(zhì)量和額外增加聚類(lèi)的時(shí)間，解決了高維、大數(shù)據(jù)集非凸的聚類(lèi)問(wèn)題；引入消歧處理，消除了XML文檔中因語(yǔ)義相關(guān)環(huán)境與內(nèi)容不一致所引起的歧義難題，同時(shí)綜合語(yǔ)義相似度與路徑相似度，解決了XML文檔相似度計(jì)算不準(zhǔn)確對(duì)初始聚類(lèi)結(jié)果的影響；從初始聚類(lèi)成員中形成的簇集、簇和數(shù)據(jù)點(diǎn)三者之間的相互關(guān)系來(lái)構(gòu)建內(nèi)聯(lián)相似度矩陣后，采用精化LANCZOS雙對(duì)角化策略把矩陣投影于低維空間，并通過(guò)設(shè)計(jì)的并行LANCZOS-QR算法來(lái)求解矩陣的特征值和對(duì)應(yīng)的特征向量，避免因數(shù)據(jù)規(guī)模大，數(shù)據(jù)的計(jì)算量成倍增加而增加算法的時(shí)間復(fù)雜度；利用系統(tǒng)能量理論，把待集成的基本聚類(lèi)劃分結(jié)果看成一個(gè)系統(tǒng)，系統(tǒng)的能量就是不同聚類(lèi)結(jié)果之間的能量組合，通過(guò)設(shè)計(jì)出系統(tǒng)能量的AP傳播算法并行實(shí)現(xiàn)能量的最優(yōu)組合，提高了聚類(lèi)集成方法的效率，彌補(bǔ)以往聚類(lèi)集成方法的不足。

附圖說(shuō)明

圖1是本發(fā)明提供的并行AP傳播的XML大數(shù)據(jù)聚類(lèi)集成方法方法流程圖。