受限玻爾茲曼機結合聚類的特異點挖掘方法

董鑫 夏文瀚 倪健 黃強 聶斌

摘 要：為了減少高維數(shù)據(jù)“維數(shù)災難”對聚類效果的影響，將高斯受限玻爾茲曼機與DBSCAN算法相結合。首先利用高斯受限玻爾茲曼機對訓練數(shù)據(jù)進行降維，然后采用DBSCAN算法識別降維后的數(shù)據(jù)特異點，最后利用UCI數(shù)據(jù)集中的數(shù)據(jù)進行實驗驗證，并開發(fā)了相應演示系統(tǒng)。實驗選取UCI數(shù)據(jù)集中的3組數(shù)據(jù)進行驗證，結果發(fā)現(xiàn)，該方法準確率分別為0.778、0.714、0.900，分別比DBSCAN算法提高了0.19、0.514、0.186，效果優(yōu)于DBSCAN算法。因此高斯受限玻爾茲曼機與DBSCAN算法結合不僅能提高識別結果準確度，而且能提升識別效率。

關鍵詞：受限玻爾茲曼機;聚類算法;特異點

DOI：10. 11907/rjdk. 191551 開放科學（資源服務）標識碼（OSID）：

中圖分類號：TP391文獻標識碼：A 文章編號：1672-7800（2020）002-0136-04

英標：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)督學習手段，其目的是將相似的數(shù)據(jù)點劃分到同一類中，將不相似的數(shù)據(jù)點劃分到不同的類中或歸于噪聲類。然而在實際應用領域，數(shù)據(jù)變得越來越復雜、維度越來越高，難以實現(xiàn)正確的分類。針對高維數(shù)據(jù)“維數(shù)災難”問題，本文探求高斯受限玻爾茲曼機與DBSCAN算法結合的方法，著力于減少高維數(shù)據(jù)“維數(shù)災難”對聚類效果的影響。

1943 年，心理學家McCulloch和數(shù)學家 Pitts等[1]提出了神經(jīng)元數(shù)學模型，簡稱為MP模型，1949 年Hebb[2]首次提出使用神經(jīng)網(wǎng)絡進行學習的設想，1958年Rosenblatt[3]提出感知器模型及配套的學習訓練方法。之后由于感知器存在種種缺陷，神經(jīng)網(wǎng)絡應用陷入低潮，但隨著神經(jīng)網(wǎng)絡新模型和新算法相繼出現(xiàn)，如Hopfield 神經(jīng)網(wǎng)絡[4]、玻爾茲曼機[5]等，神經(jīng)網(wǎng)絡再次引起研究人員關注。

2006 年，Geoffrey Hinton[6]提出深度信念網(wǎng)絡（Deep Belief Nets，DBN）模型，該模型既可以對數(shù)據(jù)的概率分布進行建模，也可以對數(shù)據(jù)作類別分析[6-7]。DBN 也可稱為生成模型，經(jīng)過有效的模型訓練，以最大的概率生成訓練數(shù)據(jù)。從模型結構圖來說，深度信念網(wǎng)絡由受限玻爾茲曼機（Restricted Boltzmann Machines，RBM）堆疊而成，RBM 逐層探測數(shù)據(jù)內部規(guī)律，識別數(shù)據(jù)獨特特征，判別數(shù)據(jù)真實類別[8]。目前，RBM因自身強大的特征提取能力及作為深度信念網(wǎng)絡的基本構成模塊，引起了機器學習界密切關注，在眾多領域得到了廣泛應用[9]。

在涉及向量計算的實際應用中，隨著維數(shù)增加，常出現(xiàn)計算量呈指數(shù)倍增長的“維數(shù)災難”，學者們對該問題從不同角度進行了研究。葉福蘭[10]提出基于核函數(shù)的高維離散數(shù)據(jù)聚類算法;針對高維空間中數(shù)據(jù)分布的稀疏性和空間特性，李慧敏等[11]設計了一種基于信息熵的相似性度量方法，取得了較好的聚類效果;為解決傳統(tǒng)DBSCAN方法對高維數(shù)據(jù)不適用的問題，姜洪權等[12]提出一種基于KPCA與DBSCAN的高維非線性特征數(shù)據(jù)聚類分析技術。

基于RBM快速學習算法聚類是無監(jiān)督的，適合不含類標記的大規(guī)模數(shù)據(jù)。RBM 算法已成功應用于分類、回歸、降維、特異點識別等不同的機器學習問題 [13-16]。為了構建RBM 算法與聚類算法結合識別特異點的方法，研究如何減少高維數(shù)據(jù)“維數(shù)災難”對聚類效果的影響，本文提出將高斯受限玻爾茲曼機與DBSCAN聚類算法結合的方法。首先采用高斯受限玻爾茲曼機降維，使維數(shù)對聚類效果的影響顯著減小，再結合DBSCAN聚類，檢測和發(fā)現(xiàn)特異點。

1 RBM模型與DBSCAN算法介紹

1.1 RBM模型介紹

受限玻爾茲曼機（Restricted Boltzmann Machine，RBM）是深度概率模型中最常見的組件之一。RBM本身不是一個深層模型，相反，它有一層潛變量，可表示學習輸入[17]。

RBM是一類具有兩層結構、對稱連接且無自反饋的隨機神經(jīng)網(wǎng)絡模型，層間全連接，層內無連接，標準的RBM是基于能量的模型[18]。二值RBM雖在圖像領域已取得極好的成果，也是應用最廣泛的 RBM 模型，但在實際應用中還存在不足。

高斯受限玻爾茲曼機與傳統(tǒng)二值受限玻爾茲曼機不同，它是實值數(shù)據(jù)上的受限玻爾茲曼機。在高斯 RBM 模型中可見層的變量服從高斯分布，隱層變量與二值 RBM 相同，服從二值分布。在給定隱層變量的情況下，可見層變量的分布是高斯專家乘積模型，每一個專家服從高斯分布，相應地，在給定可見層變量的情況下，隱層變量也是二值專家乘積模型[19]。

1.2 DBSCAN算法

DBSCAN算法[20]是經(jīng)典的基于密度的聚類算法，基本原理是通過尋找數(shù)據(jù)點密度相連的最大集合尋找聚類最終結果。與劃分及層次聚類方法不同，它將簇定義為密度相連的點的最大集合，能夠把具有足夠高密度的區(qū)域劃分為簇，并可在噪聲空間數(shù)據(jù)庫中發(fā)現(xiàn)任意形狀的聚類[21]。

其優(yōu)點主要體現(xiàn)于：①聚類速度快并且能夠處理任意形狀和大小的簇[22]，能夠發(fā)現(xiàn)數(shù)據(jù)集中的噪聲，多次運行結果相對穩(wěn)定;②不需要輸入待劃分的聚類個數(shù);③算法中聚類簇的形狀沒有偏倚[23]。同時缺點包括：①參數(shù)較難確定[24]，當簇的密度不均勻（變化較大）時很難發(fā)現(xiàn)所有的簇[25-26];②對于高維數(shù)據(jù)，由于傳統(tǒng)歐幾里得距離不能很好地處理高維數(shù)據(jù)，無法很好地定義距離。

2 RBM模型與DBSCAN算法融合

本文提出的基于受限玻爾茲曼機與聚類方法結合挖掘特異點的模型如圖1所示，該模型由兩部分組成，即頂層高斯受限玻爾茲曼機和底層DBSCAN。高斯受限玻爾茲曼機由兩層結構組成，一層可見層，一層隱藏層。首先將原始數(shù)據(jù)集進行歸一化處理，然后再將歸一化后的訓練數(shù)據(jù)集輸入高斯受限波爾茲曼機的可見層，得到經(jīng)過高斯受限玻爾茲曼機訓練后的數(shù)據(jù)集，最后將經(jīng)過訓練的數(shù)據(jù)集輸入DBSCAN中挖掘特異點。

與傳統(tǒng)DBSCAN算法相比，經(jīng)高斯受限玻爾茲曼機調整參數(shù)后，訓練后的數(shù)據(jù)集更適合DBSCAN算法進行特異點分析，從而可獲得比傳統(tǒng)DBSCAN算法更好的效果。

在高斯受限玻爾茲曼機中，參數(shù)設置非常重要，參數(shù)的選擇對最后結果會造成很大影響。它并不是簡單地對數(shù)據(jù)進行降維，還要保證經(jīng)過訓練后的數(shù)據(jù)集適合DBSCAN算法進行特異點挖掘工作。設置的參數(shù)包括隱藏層層數(shù)、訓練周期和每周期訓練數(shù)據(jù)大小。對于隱藏層層數(shù)設置，本文將未經(jīng)訓練的數(shù)據(jù)集維數(shù)除以2，之后以該數(shù)為基準上下調整，直至得到滿意的結果，確定最后參數(shù)。后兩個參數(shù)的設置比較簡單，經(jīng)過多次實驗探索，發(fā)現(xiàn)訓練周期設置在500～1 000內訓練，每周期訓練數(shù)據(jù)大小略高于訓練數(shù)據(jù)集數(shù)據(jù)大小時，訓練速度快、效果穩(wěn)定。

在DBSCAN算法中距離半徑[ε]和點數(shù)閾值MinPts也需要設置。一般可以用觀察第k個最近鄰距離（k距離）的方法確定這兩個參數(shù)。對于屬于某個簇的點，如果k不大于簇的樣本個數(shù)，則k距離很小。然而，對于不在簇中的點（噪聲），k距離將相對擴大。因此，對于任意一個正整數(shù)k，計算所有數(shù)據(jù)點k的距離，然后以遞增順序將它們排序，繪制排序后的k距離值，將看到k距離的急劇變化轉折點，該點對應的距離一般對應于合適的[ε]值。如果此時選取k值為MinPts，則k距離小于[ε]的點將被標記為核心對象，其它點將被標記為邊界對象或噪聲。利用k距離方法得到的[ε]值取決于k，但是并不隨著k的改變而劇烈變化。如果k值很小，則少量噪聲點將被標記為簇;如果k值太大，則數(shù)量小于k的簇可能被標記為噪聲。最初DBSCAN算法選取k=4，然后根據(jù)實驗結果再進行調參，一般選3或5即可確定是否需要更改參數(shù)。

3 實驗驗證與分析

實驗中將改進后的算法與傳統(tǒng)DBSCAN算法作比較，從檢測召回率、精確度和F值上對比算法性能。本實驗采用的數(shù)據(jù)集全部來自UCI機器數(shù)據(jù)庫。共選取3個數(shù)據(jù)集進行訓練和測試，分別為：威斯康星州乳腺癌（診斷）數(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ù)據(jù)集進行測試，從而更好地評估改進后的算法效果。

使用整個數(shù)據(jù)集，在DBSCAN算法的數(shù)據(jù)中加入10個特異點;對于用于算法改進后的數(shù)據(jù)，分別將每個數(shù)據(jù)集的70%作為訓練數(shù)據(jù)集，30%作為測試數(shù)據(jù)集，然后在訓練數(shù)據(jù)集中加入其數(shù)據(jù)總量5%的特異點，測試數(shù)據(jù)集中加入其數(shù)據(jù)總量20%的特異點，特異點所有維度均勻分布在U（0，1）上隨機生成。實驗前將數(shù)據(jù)集進行預處理，將數(shù)據(jù)集統(tǒng)一歸一化至[0，1]。數(shù)據(jù)類別標簽分為兩種情況，一種是大于1的整數(shù)，代表正常類，另一種是-1，代表特異點。

然后利用已處理的數(shù)據(jù)進行實驗，實驗用改進算法和傳統(tǒng)DBSCAN算法進行對比。通過對以上3個數(shù)據(jù)集進行特異點挖掘分析，實驗結果如表1所示（精確度（P值）、召回率（R值）、F值均保留三位有效數(shù)字）。

通過表1可看出，改進后的算法（RBM-DBSCAN）比改進前的算法（DBSCAN）在P值、R值、F值上均有更好表現(xiàn)。

4 RBM與聚類算法融合挖掘特異點系統(tǒng)實現(xiàn)

本系統(tǒng)主要用于實現(xiàn)RBM與聚類算法融合過程及融合算法的可視化結果呈現(xiàn)。

4.1 系統(tǒng)總界面實現(xiàn)

系統(tǒng)總界面包括項目簡介、原始DBSCAN算法實現(xiàn)數(shù)據(jù)聚類、融合算法實現(xiàn)數(shù)據(jù)聚類、作者信息等內容，為體現(xiàn)數(shù)據(jù)維數(shù)不固定性及算法本質，融合算法實現(xiàn)聚類部分還包括單層網(wǎng)絡聚類與雙層網(wǎng)絡聚類，其中單層網(wǎng)絡供低維數(shù)據(jù)使用，雙層網(wǎng)絡供高維數(shù)據(jù)使用。

4.2 調整參數(shù)實現(xiàn)

本系統(tǒng)中最關鍵的是參數(shù)調整，參數(shù)調整的好壞直接影響算法結果。由于參數(shù)的不固定性，故本系統(tǒng)為使用者提供輸入框，讓用戶在框中輸入?yún)?shù)，然后傳到算法中并調用算法實現(xiàn)數(shù)據(jù)聚類。以原始DBSCAN算法對數(shù)據(jù)聚類，進行參數(shù)調整的界面為例進行展現(xiàn)，如圖2所示。

在參數(shù)傳入界面內，點擊“開始訓練”按鈕進行算法調用與運行，之后將展示算法運行結果，如圖3所示。

4.3 其它功能實現(xiàn)

除核心功能外，系統(tǒng)還有一些輔助功能，如展示項目簡介、作者信息、退出系統(tǒng)等。本部分闡述的界面腳本已將該算法功能基本實現(xiàn)，達到了算法功能可視化的目的。

5 結語

本文初步研究了受限玻爾茲曼機結合聚類挖掘特異點的方法，加深了對受限玻爾茲曼機在特異點挖掘應用上的認識。本文首先進行高斯受限玻爾茲曼機降維，使維數(shù)對聚類效果的影響顯著降低，再結合DBSCAN聚類，檢測和發(fā)現(xiàn)特異點，并用實驗驗證該方法有效，最后利用wxPython實現(xiàn)算法可視化和算法所需功能。未來研究將進一步加強高維數(shù)據(jù)降維，探索更有效的深度融合方法。

參考文獻：

[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]. 電子學報，2016，44 （5）：1219-1226.

[8] 彭麗霞.? 深度信念網(wǎng)絡的模型選擇問題研究[D]. 成都：西南交通大學，2018.

[9] 羅劍江. 受限玻爾茲曼機的改進及其應用[D]. 廣州：廣東工業(yè)大學，2017.

[10] 葉福蘭. 基于核函數(shù)的高維離散數(shù)據(jù)聚類算法研究與應用[J]. 長春工程學院學報：自然科學版，2018，19（3）：79-81.

[11] 李慧敏，李川. 高維數(shù)據(jù)聚類中相似性度量算法的改進[J]. 內蒙古統(tǒng)計，2018，（2）：21-25.

[12] 姜洪權，王崗，高建民， 等. 一種適用于高維非線性特征數(shù)據(jù)的聚類算法及應用[J]. 西安交通大學學報，2017，51（12）：49-55，90.

[13] 吳證，周越，杜春華，等. 組合主成分分析的受限波爾茲曼機神經(jīng)網(wǎng)絡的降維方法[J]. 上海交通大學學報，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]. 計算機研究與發(fā)展，2014，51（1）：1-16.

[19] 沈卉卉，李宏偉. 基于受限玻爾茲曼機的專家乘積系統(tǒng)的一種改進算法[J]. 電子與信息學報，2018，（9）：2173-2181.

[20] 劉維. 數(shù)據(jù)挖掘中聚類算法綜述[J]. 江蘇商論，2018，（7）：120-125.

[21] 馮振華，錢雪忠，趙娜娜.? Greedy DBSCAN：一種針對多密度聚類的DBSCAN改進算法[J]. 計算機應用研究，2016，（9）：2693-2696+2700.

[22] 莊夏. 基于DBSCAN和Kmeans的用戶地理位置聚類算法研究[J]. 數(shù)字化用戶，2018，24（1）：34-35，131.

[23] 宋董飛，徐華. DBSCAN算法研究及并行化實現(xiàn)[J]. 計算機工程與應用，2018，54（24）：52-56，122.

[24] 周紅芳，王鵬.? DBSCAN算法中參數(shù)自適應確定方法的研究[J].? 西安理工大學學報，2012，（3）：289-292.

[25] 李雙慶，慕升弟. 一種改進的DBSCAN算法及其應用[J].? 計算機工程與應用，2014，（8）：72-76.

[26] 秦佳睿，徐蔚鴻，馬紅華，等. 自適應局部半徑的DBSCAN聚類算法[J]. 小型微型計算機系統(tǒng)，2018，39（10）：2186-2190.

（責任編輯：江 艷）