增量式神經網絡聚類算法*

劉培磊，唐晉韜，謝松縣，王 挺

(1.國防科技大學 計算機學院， 湖南 長沙 410073；2.國防信息學院 信息化建設系 信息資源管理教研室， 湖北 武漢 430010)

?

增量式神經網絡聚類算法*

劉培磊1,2，唐晉韜1，謝松縣1，王 挺1

(1.國防科技大學 計算機學院， 湖南 長沙 410073；2.國防信息學院 信息化建設系 信息資源管理教研室， 湖北 武漢 430010)

神經網絡模型具有強大的問題建模能力，但是傳統的反向傳播算法只能進行批量監督學習，并且訓練開銷很大。針對傳統算法的不足，提出全新的增量式神經網絡模型及其聚類算法。該模型基于生物神經學實驗證據，引入新的神經元激勵函數和突觸調節函數，賦予模型以堅實的統計理論基礎。在此基礎上，提出一種自適應的增量式神經網絡聚類算法。算法中引入“勝者得全”式競爭等學習機制，在增量聚類過程中成功避免了“遺忘災難”問題。在經典數據集上的實驗結果表明：該聚類算法與K-means等傳統聚類算法效果相當，特別是在增量學習任務的時空開銷方面具有較大優勢。

神經網絡；增量學習；聚類算法；時間開銷

隨著互聯網和社交媒體的廣泛發展，大量無標注的數據源源不斷地產生[1-2]。這些數據的海量性、無標注性、實時性等特點給傳統的機器學習模型帶來了很大的挑戰[3]。傳統的神經網絡模型具有強大的問題建模能力，理論上含有足夠多隱藏層神經元的神經網絡可以逼近任意函數。但是主流的學習算法如反向傳播(Back Propergating，BP)算法，使用梯度下降的方法進行學習，是批量監督學習算法，即所有的訓練數據必須一次性全部輸入學習模型。而模型一旦訓練完畢，再碰到新的輸入數據時，只能將新數據與舊數據并在一起重新訓練模型。這個問題被稱為“遺忘災難”[4]，即新學習的內容會導致已經學習的內容被“遺忘”。 梯度下降的方法帶來的另一個問題是訓練的時間開銷很大，難以在線處理海量的實時性數據[5]。近年來，熱門的深度學習模型也面臨類似的計算時間開銷問題[6]，因此訓練規模較大的深度神經網絡往往需要使用大規模并行計算集群。自適應共振理論(Adaptive Resonance Theory，ART)模型提出了一套不錯的應對辦法，它可以快速地進行無監督聚類，并且具有增量學習的特性，在解釋人腦工作機制方面也做得比BP網絡更充分[4]。然而這種模型也面臨著自己的問題，一種典型的質疑是它的理論基礎不夠堅實，不完全符合統計學原理[7]。ART模型的神經元激勵函數、突觸連接權重的調節方法等都是經驗式的，缺少嚴格的數學理論支撐。

本文通過借鑒生物神經網絡的研究成果，提出了全新的增量神經網絡模型IncNet及其無監督聚類算法。主要貢獻包括三方面：引入新的神經元激勵函數和突觸連接權值調節函數，并闡明這些函數背后的統計學意義，使得IncNet模型建立在堅實的統計理論基礎之上，為神經網絡算法的研發提供一個新的視角和一次有益嘗試。在此基礎上提出一種全新的神經網絡無監督學習算法。鑒于神經網絡模型具有強大的問題建模能力，因此神經網絡上的無監督學習算法具有重要意義。實際上，深度學習取得成功的一個重要原因就在于將“無監督學習”引入訓練階段。

1 前提與假設

模型的性能與輸入數據樣本的分布特性是息息相關的，很多模型只有針對特定分布類型的數據才能取得最好的效果。比如貝葉斯網絡和支持向量機等都有一個“特征獨立性”的假設。基于生物學實驗證據，IncNet模型做出第1.1節的合理假設。

1.1 數據分布的假設

時空局部性假設：樣本分布在時間和空間維度上具有局部性的特性。

所謂局部性是指相似的樣本在時間段內和空間位置上比較接近。以時間局部性為例，樣本在時間軸上不是隨機分布的，而是簇狀聚集的。對應到現實中，事件往往具有突發性[8]。因此，在事件發生的特定時間段上就可以采集到大量的類似樣本，而在這個時間之前或者之后采集到的類似樣本量就很少。空間局部性的含義與時間局部性類似。

1.2 神經元激勵函數

神經元激勵函數如式(1)所示。其中，xi是樹突輸入，wi是突觸連接的權值，f(x)是神經元的興奮值，ci是常數。

(1)

神經學文獻表明，一個神經元只有在被激發的時候才會從軸突上釋放信號物質，而沒被激發的神經元是不釋放任何信號物質的[9]。因此IncNet模型認為未激發的神經元不傳遞信號，而傳統模型認為未激發的神經元表示 “0”信號[10]。式(1)的統計意義將會在第2.1.2節進行詳細解釋。

1.3 突觸連接權值調節機制

在真實的生物神經網絡中，兩個神經元之間由多個突觸連接在一起，并且新的刺激會不斷地生成新的突觸。 傳統神經網絡模型一般將這些突觸簡化為單一連接，其中隱含的假設是這些突觸的總強度值是單個突觸的線性疊加[6]。 而來自神經學的證據表明：連接強度的增長率不是恒定的，而是與當前已有連接強度成負相關的關系[11]。 因此IncNet模型中的突觸連接權值非線性增長，如式(2)所示，其中，w表示連接強度，si表示第i次刺激信號生成的突觸數。公式(2)的統計學意義將會在第2.3節解釋。

(2)

1.4 神經網絡的自組織機制

生物神經網絡中每個神經元只能知道自身及其直接連接的神經元的信息，即每個神經元知道的信息都是局部的[4]。而BP算法則要求知道整個網絡的全局信息，這一點在生物學上難以實現[5]。生物神經網絡實際上通過眾多神經元的自組織來構建，其中主要的機制之一就是側向競爭。生物神經元的競爭機制比較復雜，IncNet模型將側向競爭簡化為“勝者得全”的方式。這種編碼方式又稱為 “祖母細胞(grandmother cell)”編碼[12]，即單個輸入樣本最終映射到單個神經元，受到神經學實驗證據的支持。

與“祖母細胞”編碼相對應的是傳統神經元模型使用的“集體編碼(population coding)”方式[12]，即每個輸入樣本需要多個神經元共同合作來編碼。但是，傳統神經元模型面臨的一個重要問題是“異或”問題[13]，即單層神經網絡無法表示非線性函數。而IncNet模型中的單層網絡可以解決異或問題，第2.1.4節將會詳細敘述。

2 模型與算法

基于第1節的前提與假設，本節提出IncNet模型。在詳細介紹問題抽象和模型本身的同時，著重闡述模型的統計學意義。

2.1 模型

2.1.1 問題抽象

IncNet模型面對的問題可以抽象為：對于任意一個輸入樣本x=(xi)，如何讓某個神經元編碼這個樣本，以便下次遇到類似輸入樣本的時候，這個神經元會被最大限度地激發。這種編碼本質上是神經元通過特定的方案來加強樹突連接強度，從而“記住”這個樣本。BP神經網絡是通過問題空間的梯度下降搜索來逼近這個神經網絡編碼方案的，這導致時間開銷很大[5]，并且找到的編碼方案很可能是局部最優點而非全局最優點。

那么能否通過計算的方式直接找到這個全局最佳編碼呢？在第1節的前提與假設成立的情況下，理論上是可以通過計算直接找到這全局最優編碼方案的。考慮最簡單的樣本x=(x1,x2),其中xi是[0,1]區間的任意值。現實中每個神經元的樹突分支資源(可以形成的突出數量)是有限的，因此問題就變為：一個神經元怎樣將其恒定的突觸分支資源分配到x1和x2，才能使得自身輸入向量x被最大限度地激發呢？這是一個典型的資源優化配置問題，如果突觸連接強度是線性增長的，那么神經元傾向于將所有突觸分支資源都分配給數值最大的元素xi，達不到“記住”輸入模式x的目的。因此資源必須分散到每個輸入信號xi，此時式(2)應該是一個單調增長的凸函數。將式(1)、式(2)聯立，并加入樹突分支資源守恒的約束條件可以得到式(3)。問題抽象為：求出使得f(si)取得最大值的si。很明顯最佳的si與xi應該是正相關的。

(3)

這種突觸資源分配方案不同于ART等傳統模型，ART對單個神經元的樹突連接強度做了歸一化處理，即單個神經元的所有樹突連接強度的總和是一個恒定值[6]。而IncNet模型中式(2)決定了單個神經元所有樹突連接強度總和不恒定，恒定的是單個神經元樹突分支資源總和。通過這種方式，IncNet模型將神經編碼問題轉化為了資源優化配置問題。

2.1.2 神經元激勵函數的統計意義

假設一個物體有許多特征，并且某一時刻只有其中的n個特征是可見的，那么在此條件下可以正確認定這個物體的概率是多少呢？可以計算出這個概率是：

P(O)=P(O1+O2+…+Ox)=1-P(O1O2…On)= 1-P(O1)P(O2)…

其中，O和Ai分別表示物體及物體的一個特征發生這個隨機事件。這個式子可以進一步簡化為式(4)，其中xi=lgP(Oi)。

(4)

對照式(1)中的神經元激勵函數可以看出：神經元和樹突的信號量分別對應概率P(O)和P(Oi)。即神經元信號可以表示物體的發生概率，而樹突信號表示物體某個特征發生的概率，因此式(1)具有統計學意義。

2.1.3 突觸連接強度的統計意義

式(2)中的突觸連接權值變化曲線同樣具有統計意義。根據樣本分布的時空局部性假設，樣本在時間分布上具有時間局部性的特點。假設一個信號出現一次時對應的特征具有某個置信度c，當這個信號多次重復出現的時候，特征信號的置信度c也會增高。具體來說，假設一個信號到目前為止出現了m次，那么與式(4)的推理過程類似，可以得到相應特征的置信度為：

w=c3(1-e-c4m)

(5)

對照式(2)、式(5)可知，突觸連接的強度對應物體某一特征的置信度，這個置信度隨著刺激信號的重復出現而持續地非線性增長。

2.1.4 側向競爭與“異或問題”

傳統的單層感知機存在“異或問題”，即單層感知機無法表示簡單的異或函數，這意味著這個模型的表示能力非常有限[13]。但是在IncNet模型中，單層網絡就可以表示異或函數，如圖1所示。實際上可以證明，單層網絡的IncNet模型可以表示任意布爾函數。

(6)

具體來說，任意邏輯表達式可以轉換成式(6)的形式，其中aj是原子公式或者其否定形式。由于輸入向量是由互斥的神經元對構成，如圖1所示，pi可以使用輸出層的單個神經元來表示。只要輸出層神經元之間是“或”或者“異或”的關系，P就可以使用單層網絡來表示。由于輸出層神經元也是互斥的，這個“異或”關系很容易達成。實際上，可以認為圖1中的神經元y1，y2和y3分別表示異或函數真值表中的一行，所以圖1的網絡就可以表示“異或”函數。而異或函數真值表中輸出為0的那些行可以用抑制性神經元(即“與非門”)來表示或者省略。

圖1 單層網絡表示異或函數Fig.1 Single layer network representing “XOR” function

從圖1中可以看出，競爭導致IncNet的每一層神經元向量都是稀疏的[14]。單個神經元僅能表示邏輯函數真值表中的一行，而傳統模型中單個神經元即可表示整個線性邏輯函數。與傳統模型相比，Incnet模型表示能力更強，而代價是需要更多數量的神經元。從信息論的角度看，IncNet模型中的神經元脈沖信號是單值而非二值的，即一個神經元只能表示半比特信息，一比特信息需由兩個互斥的神經元來表示。

2.2聚類算法

2.2.1 框架概述

模型如圖1所示，形式上與單層感知機比較類似，但是IncNet模型輸入向量中的元素存在互斥性而非獨立的。并且輸出層神經元之間存在“勝者得全”的側向競爭。關鍵的不同在于IncNet模型精心選取的神經元激勵函數和突觸連接權值調節函數使得這個神經網絡模型建立在了較為嚴格的統計學基礎上。而BP網絡和ART網絡等傳統模型的神經元激勵函數一般是通過經驗設定的，通常來說激勵函數是一個S型的曲線即可。ART模型的突觸連接權值調節函數也是經驗式的，并且突觸強度會采取歸一化的措施。BP網絡則完全沒有突觸連接權值調節函數，是根據誤差梯度下降的原則來“試探”得到突觸連接權值的。

2.2.2 算法流程

聚類算法的整體思想是：尋找與當前樣本最相似的聚類，根據當前樣本調整這個聚類的質心使之變得與當前樣本更接近。IncNet聚類算法避免了像BP算法一樣在問題空間上進行誤差梯度下降式搜索，所有的樣本只需要逐個進入模型訓練一遍即可，因此理論上訓練速度會非常快。聚類算法的具體過程如圖2所示。每個神經元表示一個聚類，輸入樣本依次進入IncNet網絡模型進行檢索，根據匹配的相似度和一個閾值參數共同決定是否新建一個新的神經元或者更新現有的神經元。這個閾值參數實際上控制著聚類的粒度和聚類的數量。

圖2 聚類算法流程圖Fig.2 Process of clustering algorithm

根據式(2)可知，在聚類過程中突觸連接強度是單調增長的，所以新學習的知識不會導致已經學習的舊知識的遺忘，從而避免了BP算法中存在的“遺忘災難”問題[4]。ART模型對連接強度進行了歸一化處理，因此它的突觸連接強度不是單調增長的，這導致ART模型只能在一定程度上調和 “遺忘災難”的問題而無法徹底解決該問題。ART模型對連接強度進行歸一化處理是為了避免學習過程中的“偏置”，即最先學習的知識會占據優勢。而正如第2.1.3節所述，在時空局部性假設成立的前提下，這種“偏置”在IncNet模型中具有重要的統計意義。

2.3 意義

IncNet模型是一個純粹的產生式模型，并且每個神經元只與它直接連接的神經元之間交換信息，因此模型具有良好的可擴展性。IncNet模型可以縱向擴展成包含多個層次的深度網絡，相鄰的層間可以采取類似卷積網絡的結構：每個神經元只與前一層的部分神經元連接，而不是全連接。并且IncNet模型從理論上提供了這樣一個有益的結論：對符合時空局部性假設的樣本數據，存在更快速的辦法來進行神經網絡的無監督學習。這對深度學習中無監督預訓練具有重要意義。傳統深度網絡中，這種預訓練一般是通過梯度下降的方法來進行的，因此時間復雜度很高。此外，IncNet模型在生物神經學方面也有一定的意義。相比BP模型，IncNet模型與現有神經學實驗證據吻合度更高。并且作為一個產生式模型， IncNet更容易在生物學和物理學層面進行實現[4]。

3 實驗及分析

為了檢驗新算法的實際效果和時空開銷，在兩個常用的數據集上與目前主流聚類算法進行比較。這兩個數據集原本是為批量學習任務設計的，但是通過將整個數據集分多次輸入一個學習模型也可以用來檢測增量式學習模型的性能。整個實驗分兩部分：3.2節將每個數據集視為批量數據，檢測新算法在批量學習任務中的性能。3.3節基于3.2節的實驗結果，著重分析對比新算法與傳統算法在增量式任務上的表現。

3.1 數據集與評價指標

目前IncNet模型只能處理離散型數據，并且沒有對程序框架進行時間開銷方面的優化。在實現的時候進行了一定程度的簡化，比如式(3)的最優解與向量元素之間的約束關系相關，實現的時候將其近似地簡化為si=cxi, 即分配的資源數量與輸入信號強度成正比例關系。另外，IncNet模型是通過相似度閾值來控制聚類粒度的，而K-means等算法是通過設置聚類數量來控制聚類粒度的。實驗中的做法是：先將IncNet的聚類數調節到一個適中數值，然后其他所有算法都將聚類數調整到同一數量進行比較。

Weka是著名機器學習平臺[15]，實驗選擇了Weka平臺中的經典聚類算法K-means和期望最大化(Expectation Maximization, EM)作為比較對象，使用的數據集是來自Weka中的vote和breast-cancer兩個數據集。實驗使用精度作為評價指標。具體地說，將標注好的數據集的標簽全部去掉，再使用不同聚類模型對這些數據進行聚類。假設對于第i個聚類，其中相同標簽數量最多的樣本有ni個，而所有聚類的總數量有n個，那么精度為：

(7)

3.2 批量學習任務實驗結果

3.2.1 數據集vote上的批量學習效果

投票數據集vote來自1984年美國國會的投票記錄[16]，共包含435個樣本數據，每個樣本包含16個布爾類型的屬性。本實驗中主要檢測聚類算法的批量學習性能，vote數據集一次性全部輸入每個模型進行訓練，實驗結果見表1。

表1 vote數據集上的結果

可以看出，在聚類粒度相同的前提下，IncNet模型的精度和時間開銷都介于K-means與EM之間。這個結論在聚類數分別為8和5時都是成立的，稍有不同的是較小的聚類數會導致時間開銷的降低。

3.2.2 數據集breast-cancer上的批量學習效果

乳腺癌數據集breast-cancer 于1988年發布，來自南斯拉夫的醫學中心大學腫瘤學院[17]，共包含286個樣本，每個樣本包含9個枚舉類型的屬性。作為批量學習任務，breast-cancer數據集一次性全部輸入每個模型進行訓練，實驗結果見表2。

表2 breast-cancer數據集上的結果

可以看出這三個模型在breast-cancer數據集上的表現與vote數據集上的表現非常類似，IncNet模型的精度和時間開銷仍然介于K-means與EM之間。在兩個數據集上的實驗結果表明：在批量學習任務上，IncNet模型具有與K-means、EM等常用聚類算法相當的精度和時間開銷。

3.3 增量學習任務上的效果

增量學習與批量學習的主要區別是已經訓練好的模型對待新輸入數據的方式。增量學習模型直接在已有模型基礎上進行學習。而批量學習模型則需要拋棄已有模型，將新數據與舊數據并在一起重新學習。將一個數據集比如vote分為多次輸入學習模型，實際上這就變為一個增量學習任務了。極端情況下，vote數據集可以分435次輸入，即每次只輸入一條新的數據。

K-means與EM是批量學習模型，因為它們需要在一次性輸入的所有數據上進行反復迭代。為了檢驗它們在增量學習任務上的性能，可以通過下述方式將其改造為增量學習模型：將已經學習過的樣本數據存儲起來，每當遇到新輸入的數據，就將新數據與存儲的舊數據并在一起重新訓練模型。在這種條件下，IncNet、K-means與EM的精度仍然如表1和表2所示。此時IncNet的時空開銷不變，但是K-means與EM的時空開銷發生了較大變化。具體說來，它們產生了額外的存儲n個樣本的空間開銷。而K-means與EM模型在表1與表2中的時間開銷就變為它們學習最后單獨一條樣本數據時的時間開銷，因此總的時間開銷要比表中數值大得多。可見，在增量學習任務上，IncNet的精度與常用聚類算法相當，但是在時間和空間開銷上具有很大的優勢。

4 結論

本文通過借鑒生物神經學實驗證據，提出了全新的增量式神經網絡模型及其聚類算法。通過引入新的神經元激勵函數與突觸連接權值調節函數，賦予神經網絡學習算法以嚴格的統計意義。嘗試將神經網絡強大的問題表示能力與統計學習理論進行結合，為新型神經網絡學習算法的研發提供了新的視角。在此基礎上提出了一種快速增量無監督聚類算法。在經典數據集上的實驗結果表明，在批量學習任務中，IncNet與K-means等算法的精度和時空開銷相當。但是在增量式學習任務中，IncNet模型在時空開銷方面具有較大優勢。

References)

[1] Xie S X, Wang T. Construction of unsupervised sentiment classifier on idioms resources[J]. Journal of Central South University, 2014, 21(4): 1376-1384.

[2] Wang X, Jia Y, Chen R, et al. Improving text categorization with semantic knowledge in Wikipedia[J]. IEICE Transection on Information System， 2013, 96(12): 2786-2794.

[3] 張志, 廖瑛, 余越. BP神經網絡在極移預報中的應用[J]. 國防科技大學學報, 2015, 37(2): 156-160.

ZHANG Zhi, LIAO Ying, YU Yue. Application of BP neural network model in prediction of polar motion[J]. Journal of National University of Defense Technology, 2015, 37(2):156-160.(in Chinese)

[4] Grossberg S. Adaptive resonance theory: how a brain learns to consciously attend, learn, and recognize a changing world[J]. Neural Networks, 2012, 37: 1-47.

[5] Rumelhart D E, McClelland J L. Parallel distributed processing: exploration in the microstructure of cognition[M]. USA: MIT Press, 1988.

[6] Hinton G E, Osindero S, Teh Y W. A fast learning algorithm for deep belief nets[J]. Neural Computation, 2006, 18: 1527-1554.

[7] Warren S S. Why statisticians should not FART [EB/OL]. (1995)[2015-09-10]. ftp://ftp.sas.com/pub/neural/fart.txt.

[8] Liu P L, Tang J T, Wang T. Information current in Twitter: which brings hot events to the world[C]// Proceedings of 22nd International World Wide Web, 2013： 111-112.

[9] Hodgkin A L, Huxley A F. A quantitative description of membrane current and its application to conduction and excitation in nerve[J]. Bulletin of Mathematical Biology, 1990, 52(1/2): 25-71.

[10] 劉開宇, 侯振挺. 一類具M-P型非線性二元神經網絡模型的周期解[J]. 國防科技大學學報, 2008, 30(4): 129-132.LIU Kaiyu, HOU Zhenting. The periodic solution of a neural networks of two neurons with McCulloch-Pitts nonlinearity[J]. Journal of National University of Defense Technology, 2008, 30(4): 129-132. (in Chinese)

[11] Bienenstock E L, Cooper L N, Munro P W. Theory for the development of neuron selectivity: orientation specificity and binocular interaction in visual cortex[J].Journal of Neuroscience the Official, 1982, 2(1): 32-48.

[12] Gross C G. Genealogy of the “grandmother cell”[J]. Neuroscientist, 2002, 8(5): 512-518.

[13] Minsky S P. Perceptrons: an introduction to computational geometry[M]. UAS: MIT Press, 1972.

[14] Olshausen B A. Sparse codes and spikes[J]. MIT Press, 2002: 257-272.

[15] Hall M, Frank E, Holmes G, et al. The WEKA data mining software: an update[J].ACM Sigkdd Explorations Newsletter, 2009, 11(1): 10-18.

[16] Schlimmer J C. Concept acquisition through representational adjustment[D]. USA: University of California, 1987.

[17] Tan M, Eshelman L. Using weighted networks to represent classification knowledge in noisy domains[C]//Proceedings of the Fifth International Conference on Machine Learning, 1988: 121-134.

Incremental clustering algorithm of neural network

LIU Peilei1,2, TANG Jintao1, XIE Songxian1, WANG Ting1

(1. College of Computer, National University of Defense Technology, Changsha 410073, China;2. Teaching and Research Section of Information Resource Management, Department of Information Construction,Academy of National Defense Information, Wuhan 430010, China)

Neural network model is powerful in problem modelling. But the traditional back propagating algorithm can only execute batch supervised learning, and its time expense is very high. According to these problems, a novel incremental neural network model and the corresponding clustering algorithm were put forward. This model was supported by biological evidences, and it was built on the foundation of novel neuron’s activation function and the synapse adjusting function. Based on this, an adaptive incremental clustering algorithm was put forward, in which mechanisms such as “winner-take-all” were introduced. As a result, “catastrophic forgetting” problem was successfully solved in the incremental clustering process. Experiment results on classic datasets show that this algorithm’s performance is comparable with traditional clustering models such as K-means. Especially, its time and space expenses on incremental tasks are much lower than traditional clustering models.

neural network; incremental learning; clustering algorithm; time expense

10.11887/j.cn.201605021

http://journal.nudt.edu.cn

2015-09-28

國家自然科學基金資助項目(61532001，61472436)

劉培磊(1984—)，男，江蘇連云港人，博士研究生，E-mail：plliu@nudt.edu.cn；王挺(通信作者)，男，教授，博士，博士生導師，E-mail：tingwang@nudt.edu.cn

TP393

A

1001-2486(2016)05-137-06