[發(fā)明專利]一種基于MCMC的并行分類方法

有效

• 申請?zhí)枺?/td>: 201210563427.3
• 申請日: 2012-12-21
• 公開（公告）號: CN102999477A
• 公開（公告）日: 2013-03-27
• 發(fā)明（設(shè)計）人: 遲學斌;周純葆;郎顯宇;王玨;鄧筍根
• 申請（專利權(quán)）人: 中國科學院計算機網(wǎng)絡(luò)信息中心
• 主分類號: G06F17/18
• 分類號: G06F17/18
• 代理公司: 北京億騰知識產(chǎn)權(quán)代理事務(wù)所 11309
• 代理人: 陳霽

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

本發(fā)明涉及數(shù)據(jù)分類技術(shù)，尤其涉及一種基于MCMC的并行分類方法。

背景技術(shù)

針對數(shù)據(jù)分類問題，目前存在許多分類方法，單一的分類方法主要包括：決策樹、貝葉斯、人工神經(jīng)網(wǎng)絡(luò)、K-近鄰、支持向量機和基于關(guān)聯(lián)規(guī)則的分類等。另外還有用于組合單一分類方法的集成學習方法，如Bagging方法和Boosting方法等。

在諸多分類方法中，貝葉斯分類算法是一類利用概率統(tǒng)計知識進行分類的算法。當面對大數(shù)據(jù)的分類問題時，基于統(tǒng)計學的貝葉斯算法就顯現(xiàn)出了它的優(yōu)勢。貝葉斯算法基本思想是通過貝葉斯規(guī)則（參見公式1）進行參數(shù)后驗證概率推斷的過程。P(H|E)=P(E|H)·P(H)R(E)]]>（公式1）

其中，E是可利用的數(shù)據(jù)，H是需要關(guān)注的參數(shù)，在分類問題中就是個體屬于某一類的概率，P(E)是數(shù)據(jù)的非條件概率，P(H)是參數(shù)的先驗概率，P(E|H)是似然估計，P(H|E)是參數(shù)的后驗概率。

貝葉斯算法中參數(shù)的后驗概率推斷可以利用MCMC(Markov?Chain?MonteCarlo,馬爾科夫鏈蒙特卡羅)算法，其中我們所關(guān)注的參數(shù)作為狀態(tài)空間，搜索狀態(tài)空間形成的馬爾科夫鏈的平穩(wěn)概率分布就是參數(shù)的后驗概率分布。馬爾可夫鏈（Markov?Chain），描述了一種狀態(tài)序列，其每個狀態(tài)值取決于其前面一個狀態(tài)。馬爾可夫鏈是具有馬爾可夫性質(zhì)的隨機變量x_1,x_2,x_3…的一個數(shù)列。這些變量的范圍，即它們所有可能取值的集合，被稱為“狀態(tài)空間”，而X_n的值則是在時間n的狀態(tài)。如果X_{n+1}對于過去狀態(tài)的條件概率分布僅是X_n的一個函數(shù)，則P(X_{n+1}＝x|X_1=x_1，X_2=x_2,...,X_n=x_n)=P(X_{n+1}＝x|X_n=x_n)。這里X為過程中的某個狀態(tài)。上面這個恒等式可以被看作是馬爾可夫性質(zhì)。

MCMC算法的主要缺點就是容易陷入局部最優(yōu)，因此利用MC³(MetropolisCoupled?Markov?Chain?Monte?Carlo,多鏈耦合馬爾科夫鏈蒙特卡羅)算法來解決數(shù)據(jù)的分類問題，MC³算法可以有效地的避免MCMC算法陷入局部最優(yōu)的情況。MC³算法利用多條馬爾科夫鏈同時進行MCMC計算，通過交換馬爾科夫鏈的狀態(tài)信息達到避免MCMC算法陷入局部最優(yōu)的情況。然而面對巨大的數(shù)據(jù)量，MCMC算法本身十分耗時，MC³算法就更加的耗時。

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

本發(fā)明的目的是提供一種基于MCMC的并行分類方法，用于解決現(xiàn)有技術(shù)中MCMC算法在面對巨大的數(shù)據(jù)量時出現(xiàn)的上述問題。

為實現(xiàn)上述目的，本發(fā)明提供了一種基于MCMC的并行分類方法，應(yīng)用于包括N行處理器和P列處理器構(gòu)成的運算系統(tǒng)中，每個處理器至少包含一條馬爾科夫鏈和一個特征，同一行中的P個處理器具有相同的馬爾科夫鏈，同一列中的N個處理器具有相同的個體特征，該方法步驟包括：

根據(jù)初始狀態(tài)計算似然估計；

根據(jù)似然估計計算出參數(shù)的后驗概率；

根據(jù)所述后驗概率進行MCMC模擬運算，以當前狀態(tài)為基礎(chǔ)，產(chǎn)生新狀態(tài)；

根據(jù)所述新狀態(tài)計算接受概率，并通過第一隨機數(shù)產(chǎn)生器產(chǎn)生第一隨機數(shù)，所述同一行中的處理器具有相同的第一隨機數(shù)產(chǎn)生器；

判斷所述接受概率和所述第一隨機數(shù)的比較結(jié)果，當所述第一隨機數(shù)小于所述接受概率時，則下一時刻的狀態(tài)為所述新狀態(tài)，否則保持原狀態(tài)不變；

通過第二隨機數(shù)產(chǎn)生器產(chǎn)生同一列處理器中準備進行交換的馬爾科夫鏈的標號，所述每個處理器具有相同的第二隨機數(shù)產(chǎn)生器；