董鑫 夏文瀚 倪健 黃強(qiáng) 聶斌
摘 要:為了減少高維數(shù)據(jù)“維數(shù)災(zāi)難”對(duì)聚類效果的影響,將高斯受限玻爾茲曼機(jī)與DBSCAN算法相結(jié)合。首先利用高斯受限玻爾茲曼機(jī)對(duì)訓(xùn)練數(shù)據(jù)進(jìn)行降維,然后采用DBSCAN算法識(shí)別降維后的數(shù)據(jù)特異點(diǎn),最后利用UCI數(shù)據(jù)集中的數(shù)據(jù)進(jìn)行實(shí)驗(yàn)驗(yàn)證,并開發(fā)了相應(yīng)演示系統(tǒng)。實(shí)驗(yàn)選取UCI數(shù)據(jù)集中的3組數(shù)據(jù)進(jìn)行驗(yàn)證,結(jié)果發(fā)現(xiàn),該方法準(zhǔn)確率分別為0.778、0.714、0.900,分別比DBSCAN算法提高了0.19、0.514、0.186,效果優(yōu)于DBSCAN算法。因此高斯受限玻爾茲曼機(jī)與DBSCAN算法結(jié)合不僅能提高識(shí)別結(jié)果準(zhǔn)確度,而且能提升識(shí)別效率。
關(guān)鍵詞:受限玻爾茲曼機(jī);聚類算法;特異點(diǎn)
DOI:10. 11907/rjdk. 191551 開放科學(xué)(資源服務(wù))標(biāo)識(shí)碼(OSID):
中圖分類號(hào):TP391文獻(xiàn)標(biāo)識(shí)碼:A 文章編號(hào):1672-7800(2020)002-0136-04
英標(biāo):Mining Specific Points Based on Restricted Boltzmann Machine and Clustering Method
英作:DONG Xin, XIA Wen-han, NI Jian, HUANG Qiang, NIE Bin
英單:(College of Computer Science, Jiangxi University of Traditional Chinese Medicine, Nanchang 330004,China)
Abstract: In order to combine the restricted Gaussian Boltzmann machine with the DBSCAN algorithm, singular point recognition is realized. The restricted Gaussian Boltzmann machine is combined with the DBSCAN algorithm. Firstly, the restricted Gaussian Boltzmann machine is used to reduce the dimension of the training data, then the dimension-reduced data is identified by the DBSCAN algorithm for singular point identification. Finally, the data in the UCI data set is used for experimental verification, and the demonstration system is developed accordingly. The experiment selected three sets of data in the UCI data set. The accuracy of the method was 0.778, 0.714, and 0.900, respectively, which were 0.19, 0.514, and 0.186 higher than the DBSCAN algorithm. Experimental results show that the proposed method outperforms the DBSCAN algorithm. The combination of the restricted Gaussian Boltzmann machine and the DBSCAN algorithm not only improves the accuracy of the recognition results, but also improves the recognition efficiency.
Key Words: restricted Boltzmann machine; clustering algorithm; outlier point
0 引言
聚類是一種無監(jiān)督學(xué)習(xí)手段,其目的是將相似的數(shù)據(jù)點(diǎn)劃分到同一類中,將不相似的數(shù)據(jù)點(diǎn)劃分到不同的類中或歸于噪聲類。然而在實(shí)際應(yīng)用領(lǐng)域,數(shù)據(jù)變得越來越復(fù)雜、維度越來越高,難以實(shí)現(xiàn)正確的分類。針對(duì)高維數(shù)據(jù)“維數(shù)災(zāi)難”問題,本文探求高斯受限玻爾茲曼機(jī)與DBSCAN算法結(jié)合的方法,著力于減少高維數(shù)據(jù)“維數(shù)災(zāi)難”對(duì)聚類效果的影響。
1943 年,心理學(xué)家McCulloch和數(shù)學(xué)家 Pitts等[1]提出了神經(jīng)元數(shù)學(xué)模型,簡稱為MP模型,1949 年Hebb[2]首次提出使用神經(jīng)網(wǎng)絡(luò)進(jìn)行學(xué)習(xí)的設(shè)想,1958年Rosenblatt[3]提出感知器模型及配套的學(xué)習(xí)訓(xùn)練方法。之后由于感知器存在種種缺陷,神經(jīng)網(wǎng)絡(luò)應(yīng)用陷入低潮,但隨著神經(jīng)網(wǎng)絡(luò)新模型和新算法相繼出現(xiàn),如Hopfield 神經(jīng)網(wǎng)絡(luò)[4]、玻爾茲曼機(jī)[5]等,神經(jīng)網(wǎng)絡(luò)再次引起研究人員關(guān)注。
2006 年,Geoffrey Hinton[6]提出深度信念網(wǎng)絡(luò)(Deep Belief Nets,DBN)模型,該模型既可以對(duì)數(shù)據(jù)的概率分布進(jìn)行建模,也可以對(duì)數(shù)據(jù)作類別分析[6-7]。DBN 也可稱為生成模型,經(jīng)過有效的模型訓(xùn)練,以最大的概率生成訓(xùn)練數(shù)據(jù)。從模型結(jié)構(gòu)圖來說,深度信念網(wǎng)絡(luò)由受限玻爾茲曼機(jī)(Restricted Boltzmann Machines,RBM)堆疊而成,RBM 逐層探測(cè)數(shù)據(jù)內(nèi)部規(guī)律,識(shí)別數(shù)據(jù)獨(dú)特特征,判別數(shù)據(jù)真實(shí)類別[8]。目前,RBM因自身強(qiáng)大的特征提取能力及作為深度信念網(wǎng)絡(luò)的基本構(gòu)成模塊,引起了機(jī)器學(xué)習(xí)界密切關(guān)注,在眾多領(lǐng)域得到了廣泛應(yīng)用[9]。
在涉及向量計(jì)算的實(shí)際應(yīng)用中,隨著維數(shù)增加,常出現(xiàn)計(jì)算量呈指數(shù)倍增長的“維數(shù)災(zāi)難”,學(xué)者們對(duì)該問題從不同角度進(jìn)行了研究。葉福蘭[10]提出基于核函數(shù)的高維離散數(shù)據(jù)聚類算法;針對(duì)高維空間中數(shù)據(jù)分布的稀疏性和空間特性,李慧敏等[11]設(shè)計(jì)了一種基于信息熵的相似性度量方法,取得了較好的聚類效果;為解決傳統(tǒng)DBSCAN方法對(duì)高維數(shù)據(jù)不適用的問題,姜洪權(quán)等[12]提出一種基于KPCA與DBSCAN的高維非線性特征數(shù)據(jù)聚類分析技術(shù)。
基于RBM快速學(xué)習(xí)算法聚類是無監(jiān)督的,適合不含類標(biāo)記的大規(guī)模數(shù)據(jù)。RBM 算法已成功應(yīng)用于分類、回歸、降維、特異點(diǎn)識(shí)別等不同的機(jī)器學(xué)習(xí)問題 [13-16]。為了構(gòu)建RBM 算法與聚類算法結(jié)合識(shí)別特異點(diǎn)的方法,研究如何減少高維數(shù)據(jù)“維數(shù)災(zāi)難”對(duì)聚類效果的影響,本文提出將高斯受限玻爾茲曼機(jī)與DBSCAN聚類算法結(jié)合的方法。首先采用高斯受限玻爾茲曼機(jī)降維,使維數(shù)對(duì)聚類效果的影響顯著減小,再結(jié)合DBSCAN聚類,檢測(cè)和發(fā)現(xiàn)特異點(diǎn)。
1 RBM模型與DBSCAN算法介紹
1.1 RBM模型介紹
受限玻爾茲曼機(jī)(Restricted Boltzmann Machine,RBM)是深度概率模型中最常見的組件之一。RBM本身不是一個(gè)深層模型,相反,它有一層潛變量,可表示學(xué)習(xí)輸入[17]。
RBM是一類具有兩層結(jié)構(gòu)、對(duì)稱連接且無自反饋的隨機(jī)神經(jīng)網(wǎng)絡(luò)模型,層間全連接,層內(nèi)無連接,標(biāo)準(zhǔn)的RBM是基于能量的模型[18]。二值RBM雖在圖像領(lǐng)域已取得極好的成果,也是應(yīng)用最廣泛的 RBM 模型,但在實(shí)際應(yīng)用中還存在不足。
高斯受限玻爾茲曼機(jī)與傳統(tǒng)二值受限玻爾茲曼機(jī)不同,它是實(shí)值數(shù)據(jù)上的受限玻爾茲曼機(jī)。在高斯 RBM 模型中可見層的變量服從高斯分布,隱層變量與二值 RBM 相同,服從二值分布。在給定隱層變量的情況下,可見層變量的分布是高斯專家乘積模型,每一個(gè)專家服從高斯分布,相應(yīng)地,在給定可見層變量的情況下,隱層變量也是二值專家乘積模型[19]。
1.2 DBSCAN算法
DBSCAN算法[20]是經(jīng)典的基于密度的聚類算法,基本原理是通過尋找數(shù)據(jù)點(diǎn)密度相連的最大集合尋找聚類最終結(jié)果。與劃分及層次聚類方法不同,它將簇定義為密度相連的點(diǎn)的最大集合,能夠把具有足夠高密度的區(qū)域劃分為簇,并可在噪聲空間數(shù)據(jù)庫中發(fā)現(xiàn)任意形狀的聚類[21]。
其優(yōu)點(diǎn)主要體現(xiàn)于:①聚類速度快并且能夠處理任意形狀和大小的簇[22],能夠發(fā)現(xiàn)數(shù)據(jù)集中的噪聲,多次運(yùn)行結(jié)果相對(duì)穩(wěn)定;②不需要輸入待劃分的聚類個(gè)數(shù);③算法中聚類簇的形狀沒有偏倚[23]。同時(shí)缺點(diǎn)包括:①參數(shù)較難確定[24],當(dāng)簇的密度不均勻(變化較大)時(shí)很難發(fā)現(xiàn)所有的簇[25-26];②對(duì)于高維數(shù)據(jù),由于傳統(tǒng)歐幾里得距離不能很好地處理高維數(shù)據(jù),無法很好地定義距離。
2 RBM模型與DBSCAN算法融合
本文提出的基于受限玻爾茲曼機(jī)與聚類方法結(jié)合挖掘特異點(diǎn)的模型如圖1所示,該模型由兩部分組成,即頂層高斯受限玻爾茲曼機(jī)和底層DBSCAN。高斯受限玻爾茲曼機(jī)由兩層結(jié)構(gòu)組成,一層可見層,一層隱藏層。首先將原始數(shù)據(jù)集進(jìn)行歸一化處理,然后再將歸一化后的訓(xùn)練數(shù)據(jù)集輸入高斯受限波爾茲曼機(jī)的可見層,得到經(jīng)過高斯受限玻爾茲曼機(jī)訓(xùn)練后的數(shù)據(jù)集,最后將經(jīng)過訓(xùn)練的數(shù)據(jù)集輸入DBSCAN中挖掘特異點(diǎn)。
與傳統(tǒng)DBSCAN算法相比,經(jīng)高斯受限玻爾茲曼機(jī)調(diào)整參數(shù)后,訓(xùn)練后的數(shù)據(jù)集更適合DBSCAN算法進(jìn)行特異點(diǎn)分析,從而可獲得比傳統(tǒng)DBSCAN算法更好的效果。
在高斯受限玻爾茲曼機(jī)中,參數(shù)設(shè)置非常重要,參數(shù)的選擇對(duì)最后結(jié)果會(huì)造成很大影響。它并不是簡單地對(duì)數(shù)據(jù)進(jìn)行降維,還要保證經(jīng)過訓(xùn)練后的數(shù)據(jù)集適合DBSCAN算法進(jìn)行特異點(diǎn)挖掘工作。設(shè)置的參數(shù)包括隱藏層層數(shù)、訓(xùn)練周期和每周期訓(xùn)練數(shù)據(jù)大小。對(duì)于隱藏層層數(shù)設(shè)置,本文將未經(jīng)訓(xùn)練的數(shù)據(jù)集維數(shù)除以2,之后以該數(shù)為基準(zhǔn)上下調(diào)整,直至得到滿意的結(jié)果,確定最后參數(shù)。后兩個(gè)參數(shù)的設(shè)置比較簡單,經(jīng)過多次實(shí)驗(yàn)探索,發(fā)現(xiàn)訓(xùn)練周期設(shè)置在500~1 000內(nèi)訓(xùn)練,每周期訓(xùn)練數(shù)據(jù)大小略高于訓(xùn)練數(shù)據(jù)集數(shù)據(jù)大小時(shí),訓(xùn)練速度快、效果穩(wěn)定。
在DBSCAN算法中距離半徑[ε]和點(diǎn)數(shù)閾值MinPts也需要設(shè)置。一般可以用觀察第k個(gè)最近鄰距離(k距離)的方法確定這兩個(gè)參數(shù)。對(duì)于屬于某個(gè)簇的點(diǎn),如果k不大于簇的樣本個(gè)數(shù),則k距離很小。然而,對(duì)于不在簇中的點(diǎn)(噪聲),k距離將相對(duì)擴(kuò)大。因此,對(duì)于任意一個(gè)正整數(shù)k,計(jì)算所有數(shù)據(jù)點(diǎn)k的距離,然后以遞增順序?qū)⑺鼈兣判颍L制排序后的k距離值,將看到k距離的急劇變化轉(zhuǎn)折點(diǎn),該點(diǎn)對(duì)應(yīng)的距離一般對(duì)應(yīng)于合適的[ε]值。如果此時(shí)選取k值為MinPts,則k距離小于[ε]的點(diǎn)將被標(biāo)記為核心對(duì)象,其它點(diǎn)將被標(biāo)記為邊界對(duì)象或噪聲。利用k距離方法得到的[ε]值取決于k,但是并不隨著k的改變而劇烈變化。如果k值很小,則少量噪聲點(diǎn)將被標(biāo)記為簇;如果k值太大,則數(shù)量小于k的簇可能被標(biāo)記為噪聲。最初DBSCAN算法選取k=4,然后根據(jù)實(shí)驗(yàn)結(jié)果再進(jìn)行調(diào)參,一般選3或5即可確定是否需要更改參數(shù)。
3 實(shí)驗(yàn)驗(yàn)證與分析
實(shí)驗(yàn)中將改進(jìn)后的算法與傳統(tǒng)DBSCAN算法作比較,從檢測(cè)召回率、精確度和F值上對(duì)比算法性能。本實(shí)驗(yàn)采用的數(shù)據(jù)集全部來自UCI機(jī)器數(shù)據(jù)庫。共選取3個(gè)數(shù)據(jù)集進(jìn)行訓(xùn)練和測(cè)試,分別為:威斯康星州乳腺癌(診斷)數(shù)據(jù)集(Breast Cancer Wisconsin (Diagnostic) Data Set,BCW)、葡萄酒數(shù)據(jù)集(Wine Data Set,Wine)、Parkinson數(shù)據(jù)集(Parkinson Data Set,PK),其維數(shù)分別為30、13、22。本實(shí)驗(yàn)采用多個(gè)維度的數(shù)據(jù)集進(jìn)行測(cè)試,從而更好地評(píng)估改進(jìn)后的算法效果。
使用整個(gè)數(shù)據(jù)集,在DBSCAN算法的數(shù)據(jù)中加入10個(gè)特異點(diǎn);對(duì)于用于算法改進(jìn)后的數(shù)據(jù),分別將每個(gè)數(shù)據(jù)集的70%作為訓(xùn)練數(shù)據(jù)集,30%作為測(cè)試數(shù)據(jù)集,然后在訓(xùn)練數(shù)據(jù)集中加入其數(shù)據(jù)總量5%的特異點(diǎn),測(cè)試數(shù)據(jù)集中加入其數(shù)據(jù)總量20%的特異點(diǎn),特異點(diǎn)所有維度均勻分布在U(0,1)上隨機(jī)生成。實(shí)驗(yàn)前將數(shù)據(jù)集進(jìn)行預(yù)處理,將數(shù)據(jù)集統(tǒng)一歸一化至[0,1]。數(shù)據(jù)類別標(biāo)簽分為兩種情況,一種是大于1的整數(shù),代表正常類,另一種是-1,代表特異點(diǎn)。
然后利用已處理的數(shù)據(jù)進(jìn)行實(shí)驗(yàn),實(shí)驗(yàn)用改進(jìn)算法和傳統(tǒng)DBSCAN算法進(jìn)行對(duì)比。通過對(duì)以上3個(gè)數(shù)據(jù)集進(jìn)行特異點(diǎn)挖掘分析,實(shí)驗(yàn)結(jié)果如表1所示(精確度(P值)、召回率(R值)、F值均保留三位有效數(shù)字)。
通過表1可看出,改進(jìn)后的算法(RBM-DBSCAN)比改進(jìn)前的算法(DBSCAN)在P值、R值、F值上均有更好表現(xiàn)。
4 RBM與聚類算法融合挖掘特異點(diǎn)系統(tǒng)實(shí)現(xiàn)
本系統(tǒng)主要用于實(shí)現(xiàn)RBM與聚類算法融合過程及融合算法的可視化結(jié)果呈現(xiàn)。
4.1 系統(tǒng)總界面實(shí)現(xiàn)
系統(tǒng)總界面包括項(xiàng)目簡介、原始DBSCAN算法實(shí)現(xiàn)數(shù)據(jù)聚類、融合算法實(shí)現(xiàn)數(shù)據(jù)聚類、作者信息等內(nèi)容,為體現(xiàn)數(shù)據(jù)維數(shù)不固定性及算法本質(zhì),融合算法實(shí)現(xiàn)聚類部分還包括單層網(wǎng)絡(luò)聚類與雙層網(wǎng)絡(luò)聚類,其中單層網(wǎng)絡(luò)供低維數(shù)據(jù)使用,雙層網(wǎng)絡(luò)供高維數(shù)據(jù)使用。
4.2 調(diào)整參數(shù)實(shí)現(xiàn)
本系統(tǒng)中最關(guān)鍵的是參數(shù)調(diào)整,參數(shù)調(diào)整的好壞直接影響算法結(jié)果。由于參數(shù)的不固定性,故本系統(tǒng)為使用者提供輸入框,讓用戶在框中輸入?yún)?shù),然后傳到算法中并調(diào)用算法實(shí)現(xiàn)數(shù)據(jù)聚類。以原始DBSCAN算法對(duì)數(shù)據(jù)聚類,進(jìn)行參數(shù)調(diào)整的界面為例進(jìn)行展現(xiàn),如圖2所示。
在參數(shù)傳入界面內(nèi),點(diǎn)擊“開始訓(xùn)練”按鈕進(jìn)行算法調(diào)用與運(yùn)行,之后將展示算法運(yùn)行結(jié)果,如圖3所示。
4.3 其它功能實(shí)現(xiàn)
除核心功能外,系統(tǒng)還有一些輔助功能,如展示項(xiàng)目簡介、作者信息、退出系統(tǒng)等。本部分闡述的界面腳本已將該算法功能基本實(shí)現(xiàn),達(dá)到了算法功能可視化的目的。
5 結(jié)語
本文初步研究了受限玻爾茲曼機(jī)結(jié)合聚類挖掘特異點(diǎn)的方法,加深了對(duì)受限玻爾茲曼機(jī)在特異點(diǎn)挖掘應(yīng)用上的認(rèn)識(shí)。本文首先進(jìn)行高斯受限玻爾茲曼機(jī)降維,使維數(shù)對(duì)聚類效果的影響顯著降低,再結(jié)合DBSCAN聚類,檢測(cè)和發(fā)現(xiàn)特異點(diǎn),并用實(shí)驗(yàn)驗(yàn)證該方法有效,最后利用wxPython實(shí)現(xiàn)算法可視化和算法所需功能。未來研究將進(jìn)一步加強(qiáng)高維數(shù)據(jù)降維,探索更有效的深度融合方法。
參考文獻(xiàn):
[1] MCCULLOCH W S, PITTS W. A logical calculus of the ideas immanent in nervous activity[J].? Bulletin of Mathematical Biology, 1990, 52(1-2):99-115.
[2] HEBB D O. In the organization of behavior, a neuropsychological theory[M].? New York: John Wiley, 1949.
[3] ROSENBLATT F. The perceptron: a probabilistic model for information storage and organization in the brain[M]. Cambirdge:MIT Press, 1988.
[4] HOPFIELD J J. Neural networks and physical systems with emergent collective computational abilities[J]. Proceedings of the National Academy of Sciences of the United States of America, 1982, 79(8):2554-2558.
[5] ACKLEY D H, HINTON G E, SEJNOWSKI T J. A learning algorithm for Boltzmann? machines*[J]. Cognitive Science,1985,9(1):147-169.
[6] Hinton G H,SEJNOWSKI T J,ACKLEY D H. Bolzmann machines:constraint satisfaction networks that learn[R]. Technical Report CMU-CS,1995:84-11.
[7] 劉建偉,黎海恩,周佳佳,等. 概率圖模型的表示理論綜述[J]. 電子學(xué)報(bào),2016,44 (5):1219-1226.
[8] 彭麗霞.? 深度信念網(wǎng)絡(luò)的模型選擇問題研究[D]. 成都:西南交通大學(xué),2018.
[9] 羅劍江. 受限玻爾茲曼機(jī)的改進(jìn)及其應(yīng)用[D]. 廣州:廣東工業(yè)大學(xué),2017.
[10] 葉福蘭. 基于核函數(shù)的高維離散數(shù)據(jù)聚類算法研究與應(yīng)用[J]. 長春工程學(xué)院學(xué)報(bào):自然科學(xué)版,2018,19(3):79-81.
[11] 李慧敏,李川. 高維數(shù)據(jù)聚類中相似性度量算法的改進(jìn)[J]. 內(nèi)蒙古統(tǒng)計(jì),2018,(2):21-25.
[12] 姜洪權(quán),王崗,高建民, 等. 一種適用于高維非線性特征數(shù)據(jù)的聚類算法及應(yīng)用[J]. 西安交通大學(xué)學(xué)報(bào),2017,51(12):49-55,90.
[13] 吳證,周越,杜春華,等. 組合主成分分析的受限波爾茲曼機(jī)神經(jīng)網(wǎng)絡(luò)的降維方法[J]. 上海交通大學(xué)學(xué)報(bào),2008,42(4):559-563.
[14] CHANDRA S,KUMAR S,JAWAHAR C V. Learning multiple non-linear sub-spaces using K-RBMs[C].? 2013 IEEE Conference on Computer Vision and Pattern Recognition, 2778-2785.
[15] YUAN M L, TANG H J, LI H Z. Real-time keypoint recognition using restricted Boltzmann machine[J].? IEEE Transactions on Neural Networks and Learning Systems, 2014, 25(11):2119-2126.
[16] CHEN Y L, LU L J, LI X B. Application of continuous restricted Boltzmann machine to identify multivariate geochemical anomaly [J]. Journal of Geochemical Exploration,2014,140:56-63.
[17] SMONLENSKY P. Information processing in dynamical systems:Foundations of harmony theory[J].? Parallel Distributed Processing,1986,1(6):194-281.
[18] 劉建偉,劉媛,羅雄麟. 玻爾茲曼機(jī)研究進(jìn)展[J]. 計(jì)算機(jī)研究與發(fā)展,2014,51(1):1-16.
[19] 沈卉卉,李宏偉. 基于受限玻爾茲曼機(jī)的專家乘積系統(tǒng)的一種改進(jìn)算法[J]. 電子與信息學(xué)報(bào),2018,(9):2173-2181.
[20] 劉維. 數(shù)據(jù)挖掘中聚類算法綜述[J]. 江蘇商論,2018,(7):120-125.
[21] 馮振華,錢雪忠,趙娜娜.? Greedy DBSCAN:一種針對(duì)多密度聚類的DBSCAN改進(jìn)算法[J]. 計(jì)算機(jī)應(yīng)用研究,2016,(9):2693-2696+2700.
[22] 莊夏. 基于DBSCAN和Kmeans的用戶地理位置聚類算法研究[J]. 數(shù)字化用戶,2018,24(1):34-35,131.
[23] 宋董飛,徐華. DBSCAN算法研究及并行化實(shí)現(xiàn)[J]. 計(jì)算機(jī)工程與應(yīng)用,2018,54(24):52-56,122.
[24] 周紅芳,王鵬.? DBSCAN算法中參數(shù)自適應(yīng)確定方法的研究[J].? 西安理工大學(xué)學(xué)報(bào),2012,(3):289-292.
[25] 李雙慶,慕升弟. 一種改進(jìn)的DBSCAN算法及其應(yīng)用[J].? 計(jì)算機(jī)工程與應(yīng)用,2014,(8):72-76.
[26] 秦佳睿,徐蔚鴻,馬紅華,等. 自適應(yīng)局部半徑的DBSCAN聚類算法[J]. 小型微型計(jì)算機(jī)系統(tǒng),2018,39(10):2186-2190.
(責(zé)任編輯:江 艷)