基于競爭神經網(wǎng)絡的全局K-Medoids聚類算法研究*

曹 勇，王兆輝，高 琦, 甄麗紅

(1.山東大學 機械工程學院CAD/CAM研究所，濟南 250061；2.山東省科技發(fā)展服務推進中心，濟南 250101)

0 引言

聚類是十大常見數(shù)據(jù)挖掘技術之一，屬于無監(jiān)督分類技術，它通過將數(shù)據(jù)分成不同的組，使組內數(shù)據(jù)間相似度大，而組間數(shù)據(jù)差異大。常見的聚類算法分為基于劃分、層次、密度、網(wǎng)格和模型的方法[1]。其中由Kaufman[2]提出的K-Medoids算法是基于劃分的方法的典型代表，它以樣本中的原始數(shù)據(jù)作為聚類中心，可以避免離群點對聚類結果的影響，但是該算法對初始點比較敏感，容易陷入局部最優(yōu)。Park[3]提出的簡單快速的K-Medoids算法，可以有效的提升聚類精度，但該算法在對大規(guī)模數(shù)據(jù)進行聚類分析時耗時比較長。Aristidis L[4]提出的全局K-Means算法，可以有效的避免聚類結果依賴于初始中心點的選擇和算法過早收斂，防止陷入局部最優(yōu)。但由于全局算法串行迭代搜索的本質，使得算法在對大規(guī)模數(shù)據(jù)進行聚類分析時同樣耗時比較長。而神經網(wǎng)絡并行計算的特性使得它在面對大規(guī)模和高維數(shù)據(jù)聚類問題具有很大的計算優(yōu)勢。競爭型神經網(wǎng)絡是一類非常典型的無監(jiān)督學習聚類算法，Kohonen等[5-7]提出的基于競爭神經網(wǎng)絡和基于SOM的聚類算法是其中的典型代表。算法通過訓練網(wǎng)絡的結構參數(shù)，根據(jù)數(shù)據(jù)之間的相似性對數(shù)據(jù)進行自動分類，但這類聚類算法只能提供粗糙的聚類方案，并不能提供最終的精確聚類信息。

本文擬將競爭神經網(wǎng)絡和全局K-Medoids算法結合起來用于樣本聚類分析。將Aristidis L提出的全局思想應用于K-Medoids算法，避免算法陷入局部最優(yōu)的情況。此外，利用神經網(wǎng)絡快速并行計算的優(yōu)點來解決全局K-Medoids算法串行迭代的缺點，加快算法的全局搜索速度?；谏鲜鲈?，本文提出基于競爭神經網(wǎng)絡的全局K-Medoids聚類算法。

1 算法介紹

1.1 競爭神經網(wǎng)絡算法

競爭神經網(wǎng)絡是一種無監(jiān)督學習方法的神經網(wǎng)絡，其主要思想是基于競爭學習，通過網(wǎng)絡輸出層中各個神經元之間相互競爭來獲得對輸入模式的響應機會，且只有一個神經元成為勝利者[8]。整個網(wǎng)絡由m個神經元構成的輸入層和n個神經元構成的輸出層組成，其網(wǎng)絡的連接權重為：

W={wij|i=1,2,...,m;j=1,2,...,n}>

(1)

其中，wij為第i個輸入神經元與第j個輸出神經元之間的權重。

對于N個樣本，其輸入模式為：

X={Xi|i=1,2,...,N}>,Xi=(xi1,xi2,...,xim)

其中，xij為樣本Xi的第j維屬性值。

(2)

其中，bj為第j個輸出神經元的閾值。

根據(jù)競爭機制，輸出層中狀態(tài)最好的神經元取得勝利，其狀態(tài)值為1，其余競爭均失敗，對應狀態(tài)值為0，則對應的輸出模式Yk為二值向量：

(3)

對于獲勝的神經元而言，根據(jù)Kohonen學習規(guī)則更新與其相關的連接權重，假設學習速率為η，則根據(jù)下式調整權重Δwij：

(4)

競爭神經網(wǎng)絡算法流程如圖1所示。

圖1 競爭神經網(wǎng)絡算法流程圖

1.2 全局K-Medoids聚類算法

全局K-Medoids聚類算法是以數(shù)據(jù)樣本中的原始樣本作為聚類中心，然后利用某種距離度量函數(shù)來度量樣本之間的相似性，將相似性大的樣本聚成一類。對于樣本{Xi,Xj}>的相似性度量函數(shù)為歐拉距離，如式(5)所示，其相似度為距離的倒數(shù)，如式(6)所示。

(5)

Sim=1/dXi,Xj

(6)

對于N個樣本{X1,X2,...,XN}>的聚類問題，其相異度矩陣如下：

特別地，dXi,Xi=0,dXi,Xj=dXj,Xi。

聚類數(shù)為K的聚類問題，其目標函數(shù)為最小距離平方和Fc，如下：

s.t.

C={Ci|i=1,2,…,K}
C1∪C2∪…∪CK=X,Ci∩Cj=?,1≤i≠j≤K
0<|Ci|

全局K-Medoids算法流程如圖2所示。

圖2 全局K-Medoids算法流程圖

2 競爭神經網(wǎng)絡全局K-Medoids聚類算法

2.1 文本序列數(shù)據(jù)的屬性描述方式

由于神經網(wǎng)絡數(shù)值向量輸入模式的要求，需要提出一種數(shù)值屬性的表達方式來描述文本序列，使該算法適合于文本序列數(shù)據(jù)的聚類分析。對文本序列數(shù)據(jù)的聚類問題，如劉書暖等[9-12]提出的工藝路線的聚類問題，基于神經網(wǎng)絡的聚類方法研究尚顯不足。針對神經網(wǎng)絡不能處理文本序列數(shù)據(jù)的缺點，提出一種將文本序列數(shù)據(jù)轉換成數(shù)值數(shù)據(jù)的方法，從而使該方法適用于文本序列數(shù)據(jù)的聚類分析問題。本文提出將文本序列間的相似性作為描述文本序列的方式，利用最長公共子文本序列(Longest Common Sequence，LCS)算法[13]進行文本序列間相似度計算。算法具體內容如下：

對于兩個文本序列Xm=(x1,x2,...,xm)與Xn=(x1,x2,...,xn)，它們之間最長公共子文本序列為：LCS(Xm,Xn)={l1,l2...,li,...,lr}>，其中l(wèi)i=xk,m=xg,n,xk,m∈Xm且xg,n∈Xn，xk,m為文本序列Xm中的第k個元素，則文本序列Xm與Xn之間的相似度為：

(7)

dX1,Xi=1/Sim

(8)

其中，|Xm|為文本序列Xm中元素的個數(shù)。

根據(jù)上述計算，則文本序列數(shù)據(jù)的數(shù)值屬性描述方式如下：

Xi=(dX1,Xi,dX2,Xi,...,dXi,Xi,...,dXN,Xi)

其中，dXj,Xi為文本序列Xi的第j維屬性值。

則對于一組文本序列數(shù)據(jù)X={X1,X2,...,XN}>，按照上述方法，可將其轉換成用數(shù)值性屬性描述的數(shù)據(jù)，樣本總體可表示為：

2.2 算法總體流程

根據(jù)上述步驟，整個算法的流程如圖3所示。

圖3 本文算法流程圖

3 實例驗證

為驗證本文算法和所提文本序列的屬性描述方式的有效性，選擇K-Medoids算法和全局K-Medoids算法，根據(jù)聚類質量指標和算法運行的時間，利用UCI數(shù)據(jù)庫中的實驗數(shù)據(jù)和某機加工企業(yè)的工藝數(shù)據(jù)庫中的工藝路線數(shù)據(jù)與本文所提算法進行對比驗證。實驗環(huán)境為：Intel i5 CPU 3.20 GHz，RAM 4GB，Windows7操作系統(tǒng)， MATLAB 2014Ra。

3.1 實例1

數(shù)據(jù)來源于UCI machine learning repository數(shù)據(jù)庫，共8組，均為數(shù)值數(shù)據(jù)。為了消除由于數(shù)據(jù)屬性量綱的差異對結果造成的影響，在進行聚類分析前，先將原始數(shù)據(jù)各個維度的屬性值進行歸一化處理，在這里采用最大最小歸一法，其公式為：

(9)

其中，xij為第i個樣本第j維的原始值，xij*為第i個樣本第j維的歸一值，xmin為所有樣本第j維度上的最小值，xmax為所有樣本第j維度上的最大值。

對實驗數(shù)據(jù)，運行三種算法，其結果如表1所示。表中，N為樣本總數(shù)，d為樣本屬性維數(shù)，K為聚類數(shù)目，E為聚類質量指標，即聚類距離平方和，T為算法的運行時間。由表1可知，3種算法中：①K-Medoids算法的聚類質量最差，這是由于受到初始聚類中心的影響，算法容易陷入局部最優(yōu)；②全局K-Medoids算法相對于K-Medoids算法，能夠有效提升聚類的質量，但是在面對樣本數(shù)據(jù)量較大的時候，上述兩種算法的搜索效率均不高；③本文所提算法的聚類效果最好，而且在面對樣本數(shù)據(jù)量較大(樣本量N≥4000)的時候，算法的效率相對于K-Medoids算法平均提升49.2%，相對于全局K-Medoids算法平均提升41.2%。

從實驗中可知，本文所提算法能夠有效的提升數(shù)值數(shù)據(jù)聚類分析時的質量，而且在面對大樣本量的數(shù)值數(shù)據(jù)的聚類分析時，算法的效率能夠得到大幅度提升。

3.2 實例2

為進一步驗證本文算法對文本序列數(shù)據(jù)聚類分析的有效性，收集某機加工企業(yè)工藝路線數(shù)據(jù)中的5類107種零件的工藝路線，利用文獻[14]所提到的編碼方案對工藝路線進行編碼，部分工藝路線如表2所示。

首先根據(jù)經驗公式(10)確定聚類數(shù)的范圍：

(10)

然后從K=1,2,...,M，依次運行應用K-Medoids聚類算法、全局K-Medoids聚類算法和本文算法，記錄對應的聚類誤差，繪制聚類誤差與聚類數(shù)目圖，如圖4所示。其中，K為聚類數(shù)目，E為聚類誤差。

圖4 聚類數(shù)和聚類誤差圖

由圖4可知，K-Medoids算法的聚類誤差最大，而相比于K-Medoids算法，全局K-Medoids算法和本文算法能夠獲得質量更好的聚類方案。此外，從圖中可以看出，上述3種算法在K=1到K=5時聚類誤差平均下降速度最快，因此，取合理的聚類數(shù)目為K=5，這與實例2中的實際零件類別數(shù)是一致的。針對于聚類數(shù)K=5，實驗結果如下：對應K-Medoids算法的聚類距離平方和為365.81，算法運行時間為0.33s；全局K-Medoids算法的聚類距離平方和為356.11，算法運行時間為0.03s；本文算法的聚類距離平方和為349.48，算法運行時間為2.42s。由上述結果可知，本文算法的聚類質量最佳，能夠獲得更優(yōu)的聚類方案。

因此，結合提出的文本序列數(shù)據(jù)的描述方式，本文所提算法能夠有效的處理文本序列數(shù)據(jù)的聚類問題。

表1 3種算法聚類分析結果

表2 零件工藝路線和編碼

4 結論

(1)通過神經網(wǎng)絡并行計算的特性加快大規(guī)模數(shù)據(jù)聚類的速度，在數(shù)據(jù)量大于4000時，相比于K-Medoids算法，效率平均提升49.2%，相比于全局K-Medoids算法，效率平均提升41.2%。

(2)通過全局K-Medoids算法的全局思想，實現(xiàn)數(shù)據(jù)的二次聚類，相比于K-Medoids算法，精度平均提升13.6%，相比于全局K-Medoids算法，精度平均提升2.8%，有效避免了算法陷入局部最優(yōu)。

(3)通過定義文本序列數(shù)據(jù)的描述方式，使得神經網(wǎng)絡算法能夠處理該類數(shù)據(jù)的聚類問題。

實驗證明，基于競爭神經網(wǎng)絡的全局 K-Medoids算法融合了神經網(wǎng)絡并行計算的優(yōu)點和全局K-Medoids算法的全局思想，彌補了各自的缺點。此外，以某機加工企業(yè)工藝數(shù)據(jù)庫中的工藝路線數(shù)據(jù)聚類分析為例，證明了本文提出的算法在面對文本序列數(shù)據(jù)的聚類問題時的有效性，同時為通過聚類技術提取典型工藝路線的問題，提供了一種新的解決思路。