基于擴展隱層BP網絡的信息可視化聚類的研究

楊 旭，郭紹翠

YANG Xu1, GUO Shao-cui2

（1. 煙臺職業學院 信息工程系，煙臺 264670；2. 煙臺職業學院 開放教育學院，煙臺 264670）

0 引言

信息可視化（Information Visualization）是當前計算機科學的一個重要研究方向，它是利用計算機對抽象信息進行直觀地表示，以利于快速檢索信息和增強認知能力。信息可視化最早出現在1989年美國計算機學會組織的重要國際會議“用戶界面軟件與技術（UIST）”[1]的報告中，重點研究如何把抽象信息交互地、可視地表示出來。信息可視化的定義為：對抽象信息使用計算機支持的、交互的、可視化的表示形式以增強認知能力。信息可視化技術將為人們發現規律、增強認知、輔助決策、解釋現象提供強有力的工具。

20世紀80年代以來，隨著計算機技術、存儲技術和網絡技術的發展，人們可以掌握的信息類型越來越多，信息結構越來越復雜、信息更新越來越快，信息規模也越來越大，給人們獲取信息、理解信息、掌握信息帶來沉重負擔。因此，對于當前的可視化技術，海量多維信息與有限的屏幕空間已成為主要矛盾。

為了解決這一問題，當前的可視化技術如平行坐標系（parallel coordinates）[2]等主要采用聚類的方法，通過預先對數據進行重新組織，以減少需要繪制的圖形標記。常用的聚類算法一般都是基于歐氏距離的，以k-means算法及其變形為主，通過計算數據之間的“距離” ，將相近或者相似的數據歸為一類，并以統一的圖形表示。這種算法對處理數據量不大的簡單數據時較為有效，在應對復雜的海量信息時就顯得有些差強人意。

為了加快可視化的聚類過程，本文將擴展BP網絡用于復雜信息的聚類中，代替傳統的基于歐氏距離的聚類算法。該方法利用多維信息和其聚類結果構造相應的BP網絡模型，用已知聚類結果的多維信息作為樣本對算法進行驗證。實驗結果表明，該方法簡單高效，可以較為準確和快速的對數據進行分類。

1 擴展隱層BP網絡模型及其工作原理

擴展隱層的BP網絡模型及其訓練算法[3]是對傳統三層BP網絡模型的改進與擴展，其目的是在不改變神經網絡表達能力的基礎上，提高網絡的訓練精度與預測能力，同時增加網絡的靈活性，對外提供一個接口，方便與其它訓練算法相結合，發揮多種算法的優勢。

1.1 擴展隱層的BP網絡

Funahashi于1989年證明了這樣的一個定理：若輸入層和輸出層采用線性激活函數，隱層采用Sigmoid激活函數，則三層結構的BP網絡能夠以任意精度逼近任何有理函數。因此，在實際的應用中，一般采用三層結構的BP網絡，其輸入層和輸出層采用線性激活函數，隱層采用S（Sigmoid）型激活函數。

擴展BP網絡模型是對原傳統三層網絡結構一種擴展，其構造方法是在三層BP網絡的基礎上擴展一個新的隱層，稱其為輔助隱層。該隱層在原隱層之后添加，隱節點數與原隱層節點數相同，相當于對原隱層的一種復制。輔助隱層的激活函數采用線性函數，出于訓練效率的考慮忽略輔助隱層的閾值。擴展后的BP網絡的模型如圖1所示。

圖1 擴展隱層的BP網絡模型

1.2 擴展隱層BP網絡工作原理

擴展隱層的BP網絡訓練算法如下：

1）對原始三層結構的BP網絡進行訓練，確定權值，閾值等網絡參數。

2）動態擴展一個隱層，構造擴展隱層的BP網絡。利用蟻群算法對新增權值進行訓練，并確定其最終取值[4,5]。

設新增加了m個權值Pi,（1≤i≤m），Pi有N個隨機值，形成集合Ipi，h為螞蟻數目，Djk(Ipi)表示集合Ipi（1≤i≤m）中第j個元素Pj(Ipi)的信息量，Q(k)表示信息增量。則新增權值的具體訓練步驟如下：

1）初始化，令t和循環次數初始值Nc為零。設置最大循環次數Ncmax,令每個集合中每個元素的信息量Dj(Ipi)=C，且ΔDj(Ipi)=0，將全部螞蟻置于蟻巢。

2）啟動所有螞蟻，針對Ipi,螞蟻k(k=1,2…h)根據下式計算狀態轉移概率：

3）重復(2)，直到蟻群全部到達食物源。

4）令t=t+m，Nc=Nc+1，利用螞蟻選擇的權值計算神經網絡的輸出值和差值，記錄當前最優解。根據以下公式更新各元素的信息量：

5）如果螞蟻收斂到一條路徑或Nc≥Ncmax，則算法結束，否則轉2）。

上述公式中，Q(k)表示信息強度是隨時間變化的，Q(k)=α*Q(k-1), 0＜α＜1在開始應設置較小值，然后逐漸增大，這樣可以保證蟻群算法在開始時有更多機會搜索其它路徑，防止早熟；逐步增加Q值，拉開各元素間的信息量差異，加快搜索速度，同時設置最大值Qmax，防止Q的取值無限增大。揮發系數ρ(t)也是一個可變量，ρ(t)=β*ρ(t-1), 1＜β,開始將其設置一個較小值，隨著訓練頻數的增加，ρ(t)值也相應變大，進一步拉開各元素之間的差異，加快訓練速度，與Q值一樣，也應為其設置一個上限值[6,7]。這兩個變量一個體現原始信息的重要性，一個體現螞蟻積累信息的重要性。

2 基于擴展BP網絡的信息聚類

擴展BP網絡需要與實際的應用相結合，根據具體情況構造相應的網絡模型。按照上一章節中的算法，首先根據聚類特征構造擴展BP網絡模型，然后選取部分具有代表性的海量信息生成樣本，用訓練樣本對該模型進行訓練，使之具備聚類能力，最后用該模型對海量信息進行聚類。基于BP網絡的聚類與傳統的基于歐氏距離的聚類算法相比，具有明顯的區別和優勢。傳統算法是一種反復迭代的過程，它根據數據之間的“距離”，將相似或者相近的數據歸為一類，這種算法對于簡單小型數據集比較有效。然而，可視化技術為了提示信息背后隱藏的關系、規律和模式，要處理的往往是那些復雜的大型數據集。傳統的在對這些數據反復迭代過程中，會消耗大量的時間，影響可視化技術的效率。而本文的方法，是對海量信息中的少量具有代表性的信息進行學習，具備分類能力后再對剩余信息分類，避免了復雜的迭代過程，節省了大量的時間。數據集越大，其高效性越明顯。

2.1 構造BP網絡模型

可視化的聚類過程中，一般都是用戶先確定聚類粒度，然后根據需要確定最終的數據集要被分成多少類。影響最終結果的因素就是多維信息本身，假設數據集包含N維信息，則這N維信息都是影響分類結果的主要因素。即N維信息為BP網絡的輸入，單條信息所屬類別為最終的輸出。由此可以構造相應的BP網絡模型，見圖2所示。

圖2 用于可視聚類的BP模型

2.2 生成訓練樣本

訓練樣本是影響BP網絡分類能力的重要因素，選取的合理性直接影響了BP網絡最終的預測能力。訓練樣本是數據集的一部分，必須具有高度的概括性，能夠代表所有數據的特征。因此，合理選取訓練樣本是一件比較困難的事情，訓練樣本選取過多，不會影響網絡的分類能力，但是影響訓練效率；樣本選取過少，則會使網絡無法學習數據集的所有特征，影響最終的分類能力。

本文采取隨機選取的方法確定訓練樣本，即在數據集中隨機選擇全部數據的1/7～1/5作為訓練樣本。這部分數據的分類情況事先是不知道的，需要加以確定。為了方便實驗，我們采用傳統的k-means方法對其分類。當然，聚類算法并不局限于k-means，可以用其它適合于可視化技術的聚類方法代替。

k-means 算法的主要思想如下：首先從n個數據對象任意選擇 k 個對象作為初始聚類中心；而對于所剩下其它對象，則根據它們與這些聚類中心的相似度（距離），分別將它們分配給與其最相似的（聚類中心所代表的）聚類；然后再計算每個所獲新聚類的聚類中心（該聚類中所有對象的均值）；不斷重復這一過程直到標準測度函數開始收斂為止。一般都采用均方差作為標準測度函數。 k個聚類具有以下特點：各聚類本身盡可能的緊湊，而各聚類之間盡可能的分開。使用k-means算法對隨機選取的數據進行分類，我們最終可以得到用于訓練擴展BP網絡的樣本。另外，需要保存當前的分類結果，這些分類信息是后續工作的基礎。

2.3 訓練

本文采用擴展BP網絡模型對可視化數據進行聚類。按照前面的介紹，其訓練過程大體分為兩個步驟，即初次訓練和再次訓練，其本質是兩種訓練算法的交叉使用，發揮每種算法的優勢。

第一步是用傳統的訓練算法對三層結構的BP網絡進行訓練[8,9]。設定訓練步數，目標精度，訓練函數(trainrp)，激活函數等訓練參數，對BP網絡進行初次訓練。第二步是在三層結構的基礎上，擴展一個新的隱層，并使用線性激活函數，用蟻群算法對新增權值進行訓練，確定具體值。這一過程需要事先設定最大循環數，螞蟻數，初始信息量，信息增量，權值范圍，揮發系統等參數，然后按照2.2章節中的算法對擴展BP網絡進行訓練。經過兩種算法的交叉訓練后，擴展BP網絡已經較好的學習了多維數據集中的潛在關系和規律，具備了對整個數據集分類的能力。

擴展BP網絡的訓練過程看似復雜，涉及兩種算法，兩次訓練，訓練過程也要多次迭代。但與傳統的k-means等聚類算法相比，還是具有一定的優勢：

1）傳統的算法思想簡單，但計算復雜，需要對數據集的所有數據進行迭代操作，當數據復雜，維數多，數據量較大時，聚類時間明顯變長，效率嚴重下降。而基于擴展BP網絡的聚類算法則僅對數據集的部分樣本進行訓練，雖然也有迭代過程，但由于訓練樣本數據量小，網絡結構相對簡單，整體的訓練時間并不長，效率較高。

2）傳統算法的優勢在于小型數據集，在處理規模較小的信息時，優勢明顯。而本文的聚類算法則適用于大型的數據集，通過對部分樣本進行學習就可以具備分類能力，可以直接計算后續樣本的所屬分類，避免了繁瑣的迭代過程。

當然，本文算法也有自身的不足之處，就是訓練樣本不好選取。K-means直接對全部數據分類，錯分問題不嚴重。而基于BP網絡的聚類算法如果訓練樣本選取不當，則無法學習數據集的全部特征，無法正確分類，容易產生錯分現象。

2.4 對數據集分類

擴展BP網絡經過訓練后會具備分類能力，可以直接用于可視化數據集的分類。隨著信息技術的發展，人們收集信息的能力越來越強，手中掌握的信息量也越來越大，迫切需要有效的信息處理方法。本文使用的擴展BP網絡可以有效的解決這一問題，快速對海量復雜數據集進行分類。

但是，在分類過程中，由于BP網絡本身具有一些有確定因素，預測結果有可能產生一些異常值，比如，分類結果不在給定范圍之內。雖然這種情況較少，但也會給實際的分類帶來不利影響。有兩種方法可以解決這一問題，一種是改進BP網絡本身，使其具有一定的糾錯能力，當輸出異常時及時糾正。另外一種是利用傳統聚類方法對這些異常信息直接分類。

本文采用了第二種方法，因為這種方法相對于第一種算法更為準確，只是會犧牲少許時間。此種方法的工作原理是：在用k-means算法對數據集的部分數據分類，產生訓練樣本的時候，我們已經保存相應的分類信息。可以以此為基礎，利用k-means算法直接對少量異常信息重新分類，由此去除異常現象。

3 實驗

本文設計了一組實驗，檢驗擴展BP網絡在可視化數據分類中的可行性。很多學者在研究可視化技術時，為了方便實驗，專門整理了一組數據作為公用測試集。本文選取了其中一組數據集UVW，用該數據集檢驗本文算法的正確性，該數據集共有6維信息，149769條數據，這6維信息分別是X,Y,Z,U,V,W。鑒于篇幅所限，僅列舉部分示例數據，見表1。為了方便與傳統算法對比，本文同時使用k-means算法與擴展BP網絡兩種方法對該數據集分類，并用數據對比了實驗結果。

首先，用k-means算法對這149769條數據直接分類，保存分類結果，記錄消耗時間，以方便對比。在此過程中產生的聚類結果可以作為后續BP網絡的檢驗樣本。

表1 多維信息訓練樣本（部分）

接下來，根據UVW數據集的特點，構造相應的擴展BP網絡模型。該數據集共有6維，其相應的網絡模型如圖，有6個輸入節點，分別對應每維數據，隱層節點根據經驗設置為5，輸出節點為1,代表最終分類結果。選取數據集中20000條數據，使用k-means算法對這些數據分類生成訓練樣本。用傳統的訓練算法對三層BP網絡進行訓練，實驗環境和參數設置如下：本次實驗的硬件環境為：CPU：P42.0，內存：1G，軟件環境為Matlab 6.5。Matlab的參數設置為：隱層傳遞函數采用tansig ,輸出層傳遞函數采用purelin ,訓練函數采用trainrp，訓練步數為1000，目標精度為0.001。訓練完成后訓練精度達到0.00074420。

在此基礎上，擴展一個隱層，用蟻群算法對該BP網絡進行二次訓練，確定新增權值，提高訓練精度。蟻群算法的參數設置如下：Q(0)=40,Qmax=80,N=20, ρ(0)=0.15,h=50,ρma x=0.50,Pi∈[-0.5,0.5], Ncmax=100,Dj(Ipi)=40,1≤i≤u, 1≤j≤20。以上參數，Q，Qmax，N，h,Ncmax,Dj(Ipi)是根據問題規模隨機選取的,選取依據是訓練時間不能過長；在蟻群算法中，參數ρmax一般建議取0.5。BP網絡經過初次訓練，與最優解的差距已經縮小，過渡矩陣與單位陣較為接近，因此， 的取值范圍可以限定在一個較小的范圍內，本文取Pi∈[-0.5,0.5]；利用上述參數對擴展BP網絡模型進行訓練，訓練結束后，對數據集中的所有檢驗樣本進行分類，并保存分類結果，統計時間。最后，對于產生的那些異常數據，即分類結果超出給定范圍的數據，本文使用傳統算法重新定位其所屬類別，消除異常。

兩種聚類方法的最終結果如表2所示，本文從實驗數據數量，消耗時間，出現異常(分類結果超出給定范圍)，錯分數據(分類不正確)，和錯分率幾個方面作了對比。從實驗結果中可知，基于擴展隱層BP網絡的聚類算法相對于傳統算法具有省時高效的特點，特別適用于大規模數據集，數據集越大，效果越明顯。但由于BP網絡本身具有一些不確定因素，導致該方法存在異常數據和錯分現象，但相對于龐大的數據量，錯分率還是相對較低的。由于可視化技術本身目的是為了揭示規律，觀察整體趨勢，并不關心單條數據，因此，本文提出的基于擴展BP網絡的可視化聚類算法是高效的，可行的。

表2 實驗對比結果

4 結論

實驗證明，本文介紹的基于擴展BP網絡的可視化信息聚類方法是完全可行的。這種方法適合于大型的可視化數據多維數據集。相對于傳統的聚類文獻，它的效率更高，尤其是對海量信息的聚類，通過對少量數據的學習，就具備了分類能力，節省了大量時間。同時，本文也考慮到了異常的存在，用傳統k-means算法消除了該現象。本文算法也存在需要改進的地方，如樣本選取問題，本文采用了隨機選取的辦法，但該方法不能保證所選數據可以覆蓋數據集的所有分類特征，這也是本文要進一步研究的工作。

[1]Robertson G,Card SK,Mackinlay JD.The cognitive coprocessor architecture for interactive user interfaces.Proceedings of UIST'89,ACM Symposium on User Interface Software and Technology 1989,10-18.

[2]A.Inselberg and B. Dimsdale. Parallel coordinates：A tool for visualizing multidimensional geometry.Proc.of Visualization'90, pages 361-78,1990.

[3]劉新平,唐磊,金有海.擴展隱層的誤差反傳訓練算法研究[J].計算機集成制造系統,2008,14(11)：2284-2288.

[4]洪炳熔,金飛虎,高慶吉,基于蟻群算法的多層前饋神經網絡[J].哈爾濱工業大學學報,2003,35(7)：323-825.

[5]Colorni A,Dorigo M,Maniezzo V,et al. Distributed optimization by ant colonies[A].Proceedings of ECAL91(European Conference on Artificial Life)[C].Paris,France：1991：134-142.

[6]陸崚,沈潔,秦玲.蟻群算法求解連續空間優化問題的一種方法[J].軟件學報,2002,13(12)：2314-2323.

[7]黃翰,郝志峰,吳春國,秦勇.蟻群算法的收斂速度分析[J].計算機學報,2007,30(8)：1344-1353.

[8]C.Zhang,W.Wu,X.H.Chen,Y.Xiong.Convergence of BP algorithm for product unit neural networks with exponential weights[J].Neurocomputing.2008,12,72：513-520.

[9]W.Wu,H.M.Shao,D.Qu,Strong convergence for gradient methods for BP networks training,in：Proceedings of the International Conference on Neural Networks and Brains,2005：332-334.