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

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

0 引言

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

本文擬將競(jìng)爭(zhēng)神經(jīng)網(wǎng)絡(luò)和全局K-Medoids算法結(jié)合起來(lái)用于樣本聚類分析。將Aristidis L提出的全局思想應(yīng)用于K-Medoids算法，避免算法陷入局部最優(yōu)的情況。此外，利用神經(jīng)網(wǎng)絡(luò)快速并行計(jì)算的優(yōu)點(diǎn)來(lái)解決全局K-Medoids算法串行迭代的缺點(diǎn)，加快算法的全局搜索速度。基于上述原因，本文提出基于競(jìng)爭(zhēng)神經(jīng)網(wǎng)絡(luò)的全局K-Medoids聚類算法。

1 算法介紹

1.1 競(jìng)爭(zhēng)神經(jīng)網(wǎng)絡(luò)算法

競(jìng)爭(zhēng)神經(jīng)網(wǎng)絡(luò)是一種無(wú)監(jiān)督學(xué)習(xí)方法的神經(jīng)網(wǎng)絡(luò)，其主要思想是基于競(jìng)爭(zhēng)學(xué)習(xí)，通過(guò)網(wǎng)絡(luò)輸出層中各個(gè)神經(jīng)元之間相互競(jìng)爭(zhēng)來(lái)獲得對(duì)輸入模式的響應(yīng)機(jī)會(huì)，且只有一個(gè)神經(jīng)元成為勝利者[8]。整個(gè)網(wǎng)絡(luò)由m個(gè)神經(jīng)元構(gòu)成的輸入層和n個(gè)神經(jīng)元構(gòu)成的輸出層組成，其網(wǎng)絡(luò)的連接權(quán)重為：

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

(1)

其中，wij為第i個(gè)輸入神經(jīng)元與第j個(gè)輸出神經(jīng)元之間的權(quán)重。

對(duì)于N個(gè)樣本，其輸入模式為：

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

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

(2)

其中，bj為第j個(gè)輸出神經(jīng)元的閾值。

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

(3)

對(duì)于獲勝的神經(jīng)元而言，根據(jù)Kohonen學(xué)習(xí)規(guī)則更新與其相關(guān)的連接權(quán)重，假設(shè)學(xué)習(xí)速率為η，則根據(jù)下式調(diào)整權(quán)重Δwij：

(4)

競(jìng)爭(zhēng)神經(jīng)網(wǎng)絡(luò)算法流程如圖1所示。

圖1 競(jìng)爭(zhēng)神經(jīng)網(wǎng)絡(luò)算法流程圖

1.2 全局K-Medoids聚類算法

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

(5)

Sim=1/dXi,Xj

(6)

對(duì)于N個(gè)樣本{X1,X2,...,XN}>的聚類問(wèn)題，其相異度矩陣如下：

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

聚類數(shù)為K的聚類問(wèn)題，其目標(biāo)函數(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 競(jìng)爭(zhēng)神經(jīng)網(wǎng)絡(luò)全局K-Medoids聚類算法

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

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

對(duì)于兩個(gè)文本序列Xm=(x1,x2,...,xm)與Xn=(x1,x2,...,xn)，它們之間最長(zhǎng)公共子文本序列為：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個(gè)元素，則文本序列Xm與Xn之間的相似度為：

(7)

dX1,Xi=1/Sim

(8)

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

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

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

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

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

2.2 算法總體流程

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

圖3 本文算法流程圖

3 實(shí)例驗(yàn)證

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

3.1 實(shí)例1

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

(9)

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

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

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

3.2 實(shí)例2

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

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

(10)

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

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

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

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

表1 3種算法聚類分析結(jié)果

表2 零件工藝路線和編碼

4 結(jié)論

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

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

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

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