張龍，李鳳蓮，張雪英，史凱岳

（太原理工大學(xué)信息與計算機(jī)學(xué)院，山西榆次 030600）

K-means 算法是一種簡單高效易于實(shí)現(xiàn)的基于劃分的聚類算法，該算法的計算復(fù)雜度接近線性，但初始聚類中心的選擇和樣本的劃分方式均會對聚類性能產(chǎn)生較大的影響[1]，因此，一些改進(jìn)算法相繼被提出。K-means++算法使用最大最小距離法選取初始聚類中心，盡可能選取相對距離較遠(yuǎn)的樣本作為初始聚類中心，一定程度上減小了隨機(jī)選取初始聚類中心對聚類性能的影響[2]。文獻(xiàn)[3]將K-means 與關(guān)系對稱矩陣和社會網(wǎng)絡(luò)分析中的度中心性相結(jié)合，并對K-means 算法初始聚類中心的選擇進(jìn)行了優(yōu)化，提高了聚類算法的性能。文獻(xiàn)[4]提出基于特征關(guān)聯(lián)度的K-means 初始聚類中心優(yōu)化算法，可得到更優(yōu)的聚類結(jié)果。上述改進(jìn)主要是針對初始聚類中心選取開展的研究，對聚類算法樣本劃分方式未進(jìn)行改進(jìn)。

模糊聚類[5](Fuzzy C-Means，F(xiàn)CM)算法將樣本的硬劃分轉(zhuǎn)化為一種柔性的模糊劃分，以此更科學(xué)地度量樣本相似度。文獻(xiàn)[6]在FCM基礎(chǔ)上，提出了一種密度加權(quán)FCM 算法，文獻(xiàn)[7]提出了基于迭代信息熵權(quán)的改進(jìn)LFCM 聚類算法。上述FCM 及其改進(jìn)算法主要以樣本的劃分方式為切入點(diǎn)進(jìn)行改進(jìn)，提高了聚類性能，但處理中規(guī)模和大規(guī)模數(shù)據(jù)時的復(fù)雜度較高。

近年來，隨著強(qiáng)化學(xué)習(xí)在AlphaGo上的成功應(yīng)用，將強(qiáng)化學(xué)習(xí)和聚類算法相結(jié)合也成為一個新的研究方向。學(xué)習(xí)自動機(jī)[8]作為一種強(qiáng)化學(xué)習(xí)算法，使用該算法對聚類算法進(jìn)行改進(jìn)是近年來的一個熱點(diǎn)。文獻(xiàn)[9]提出了學(xué)習(xí)自動機(jī)聚類算法(Learning Automata Clustering，LAC)。受該文獻(xiàn)啟發(fā)，文中提出了一種基于DPRI(Discretized Pursuit Reward Inaction)的單行為強(qiáng)化聚類算法，在聚類過程中引入DPRI算法中的離散更新技術(shù)，去除了算法中智能體(Agent)行為概率之和必須為1 的約束，把行為概率轉(zhuǎn)換為累積獎勵，并引入ε貪婪策略，提升了Agent 選擇行為的速度，有效降低了時間復(fù)雜度。

1 基礎(chǔ)理論

1.1 強(qiáng)化學(xué)習(xí)

強(qiáng)化學(xué)習(xí)[10](Reinforcement Learning，RL)又稱增強(qiáng)學(xué)習(xí)，通過模擬人類學(xué)習(xí)過程中的“探索”和“利用”機(jī)制，把待分析問題抽象為馬爾科夫決策過程[11](Markov Decision Process，MDP)。該過程中，如果Agent 的某個行為得到系統(tǒng)的正向反饋，那么Agent選擇該行為的趨勢就會增大；如果Agent 所選行為得到系統(tǒng)的負(fù)向反饋，那么Agent 選擇該行為的趨勢就會下降。強(qiáng)化學(xué)習(xí)的目的就是在學(xué)習(xí)過程中使得到的獎勵最大化。

1.2 馬爾科夫決策過程

馬爾科夫決策過程(MDP)是一個四元組＜S,A,T,R＞。其中，S={s1,s2,…,sn}表示包含該過程中所有狀態(tài)的有限集合；A={a1,a2,…,aK}表示一個有限的行為集合，其中K≥2；T=p{si+1|si,ai}是一組狀態(tài)轉(zhuǎn)移函數(shù)，表征了Agent 在狀態(tài)si下，選擇行為ai后轉(zhuǎn)換到狀態(tài)si+1的過程；R={r1,r2,…,rT}，ri=r(si,ai,si+1)表示關(guān)于當(dāng)前狀態(tài)、行為和下一個狀態(tài)的標(biāo)量函數(shù)，即Agent 在狀態(tài)si下選擇行為ai轉(zhuǎn)移到狀態(tài)si+1后環(huán)境給予的獎勵。MDP 狀態(tài)轉(zhuǎn)移過程如圖1 所示。

圖1 MDP狀態(tài)轉(zhuǎn)移過程

1.3 離散學(xué)習(xí)自動機(jī)DPRI算法

DPRI算法是強(qiáng)化學(xué)習(xí)中的一種經(jīng)典離散學(xué)習(xí)自動機(jī)算法，算法將估計器技術(shù)和離散化技術(shù)進(jìn)行了結(jié)合[12]。該算法的整體特點(diǎn)是行為選擇概率向量的更新取決于環(huán)境的反饋和歷史經(jīng)驗(yàn)。算法引入了行為被選擇的次數(shù)Zi和被獎勵的次數(shù)Wi，通過求解獎勵概率的估計值，追溯獎勵概率值最大的行為；行為的累積獎勵在區(qū)間[0,1]上是跳步更新的，變化量用表示，其中r表示行為的個數(shù)，N表示行為概率的更新分辨率。若概率更新后大于1 則強(qiáng)制為1，若更新后的概率值小于0，則強(qiáng)制為0。文中結(jié)合強(qiáng)化學(xué)習(xí)算法的特點(diǎn)，并融合DPRI算法中離散化獎勵更新技術(shù)，提出了一種基于DPRI的單行為強(qiáng)化聚類算法(Single Behaviour Reinforcement Clustering algorithm based on DPRI，SBRC)。

1.4 ε 貪婪策略

貪婪策略[13]是強(qiáng)化學(xué)習(xí)中對貪心算法的別稱，使用貪婪策略求解問題時，每個階段達(dá)到局部最優(yōu)解，以實(shí)現(xiàn)最終全局最優(yōu)的目的[14]。文中使用貪婪策略選擇行為具體是指，當(dāng)Agent 選擇行為時，選取Q表中累積獎勵值最大的行為。ε貪婪策略(0 ≤ε≤1)是基于概率對強(qiáng)化學(xué)習(xí)任務(wù)中的“探索”和“利用”相結(jié)合的方法，Agent 每次選擇行為時，以ε的概率對Q表進(jìn)行“利用”，即選擇累積獎勵值最大的行為，以1-ε的概率進(jìn)行“探索”，即在行為集中隨機(jī)選擇一個行為。依據(jù)3.2 節(jié)的實(shí)驗(yàn)結(jié)果，SBRC 算法中ε取值為0.9。

2 算法實(shí)現(xiàn)

文中提出的SBRC算法將ε貪婪策略和DPRI算法的離散化獎勵更新技術(shù)與聚類算法相結(jié)合，把聚類任務(wù)轉(zhuǎn)化為強(qiáng)化學(xué)習(xí)任務(wù)。算法初始化時，建立一個大小為N×K的Q表，其中N表示輸入樣本的數(shù)量，對應(yīng)N個Agent，K表示Agent 可選擇的行為數(shù)量，對應(yīng)聚類任務(wù)中的聚類數(shù)目，Q表中的每一行數(shù)據(jù)與一個Agent 相關(guān)聯(lián)，算法在迭代過程中不斷更新Q表直至趨于穩(wěn)定。停止迭代時，每個Agent 最大累積獎勵所對應(yīng)的類簇即為該樣本的所屬類簇。

2.1 強(qiáng)化信號的構(gòu)建

強(qiáng)化學(xué)習(xí)中強(qiáng)化信號是環(huán)境給與Agent 的反饋信號[15]。傳統(tǒng)的K-means 等聚類算法根據(jù)聚類中心的變化是否小于給定的閾值作為算法停止迭代的條件，但聚類中心只能反映該類簇在樣本空間的位置，無法對類簇中樣本的聚集程度進(jìn)行描述。平均類內(nèi)距離反映了類簇中樣本的聚集程度，若一次迭代結(jié)束后平均類內(nèi)距離增大，則說明該類簇中的樣本更加分散，反之則更加緊密。因此，SBRC 算法使用平均類內(nèi)距離變化趨勢作為發(fā)送強(qiáng)化信號的依據(jù)，平均類內(nèi)距離的計算方法如式（1）所示：

式（1）中，Adis(cj)表示第j個類簇的平均類內(nèi)距離，|cj|表示第j個類簇中樣本的數(shù)量，M表示樣本的屬性個數(shù)，xim表示第i個樣本的第m個屬性，cjm表示第j個聚類中心的第m個屬性，其中1≤m≤M。

2.2 Q表的構(gòu)建

SBRC 算法運(yùn)行前建立大小為N×K的Q表，如表1 所示，其中rik表示第i個Agent 行為k的累計獎勵。該算法無需滿足條件,1 ≤i≤N，即去除了Agent 累積獎勵和為1 的約束。Q表在算法迭代過程中不斷更新，最終達(dá)到穩(wěn)定狀態(tài)。

表1 輸入樣本所對應(yīng)的Q表

2.3 Q表的更新過程

SBRC 算法運(yùn)行過程中，Agent 根據(jù)ε貪婪策略選擇行為。每次迭代結(jié)束后，計算各類簇的平均類內(nèi)距離，并與該類簇上一次得到的平均類內(nèi)距離比較。如果距離減小，則表明此次迭代選擇該行為的所有Agent 組成的類簇更加緊密，該類簇中所有Agent 會得到一個獎勵信號，使得該行為的累積獎勵值增大，反之使得該行為的累積獎勵值減小，Q表的更新過程如圖2 所示。算法迭代過程中，每個Agent有ε的概率去選擇最大累積獎勵值所對應(yīng)的行為，有1-ε的概率在行為集中隨機(jī)選擇一個行為，圖2中假設(shè)了聚類數(shù)K=3 的情況。該更新過程是針對一個Agent 而言的，圖中與聚類數(shù)對應(yīng)的行為數(shù)為3，分別代表3 個類簇。狀態(tài)Siter表示該Agent 正處于第iter次迭代，Q1、Q2、Q3分別表示3 種行為的累積獎勵，Adis(iter)表示該Agent 所在類簇第iter次迭代結(jié)束后的平均類內(nèi)距離。Q1↑表示行為1 的累積獎勵增大，Q1↓表示行為1 的累積獎勵值減小，Q1_ 表示行為1 的累積獎勵值不變。算法中設(shè)置累積獎勵上下限分別為1 和-1，如果更新后的累積獎勵值大于1或者小于-1，則將其強(qiáng)制為1 或-1。累積獎勵的更新方法如式（2）和式（3）所示：

圖2 SBRC算法Q表更新過程

式（2）表示Agent 選擇了行為k后，相較于上次迭代，平均類內(nèi)距離減小時累積獎勵的更新方式。行為k的累積獎勵增大，其余行為的累積獎勵不變。

式（3）表示Agent 選擇了行為k后，相較于上次迭代，平均類內(nèi)距離增大時的累積獎勵的更新方式。此時行為k的累積獎勵減小，其余行為的累積獎勵不變。

2.4 算法初始化及偽代碼

算法運(yùn)行前需要輸入?yún)?shù)，并對相關(guān)變量進(jìn)行初始化：輸入聚類數(shù)K，最大迭代數(shù)為maxiter，平均類內(nèi)距離變化閾值為stop；創(chuàng)建大小為N×1 的行為向量，用于存儲Agent 選擇的行為，初值設(shè)置為0；創(chuàng)建大小為N×K的Q表，用于存儲累積獎勵，初始值設(shè)為0；創(chuàng)建大小為N×1 的強(qiáng)化信號向量，用于存儲環(huán)境反饋的信號，初始值設(shè)為0；創(chuàng)建大小為2×K的向量，用于存放平均類內(nèi)距離，初始值為0。SBRC 算法的偽代碼如下：

SBRC 算法第一次迭代時，所有Agent 隨機(jī)選擇一個行為，計算各個類簇的平均類內(nèi)距離。從第二次迭代開始，每個Agent 依據(jù)ε貪婪策略選擇行為，并計算新的平均類內(nèi)距離，與上一次迭代得到的平均類內(nèi)距離作比較。若距離減小，則給予該類簇中所有Agent 獎勵信號，否則給予懲罰信號，每個Agent根據(jù)收到的信號類型更新Q表，當(dāng)平均類內(nèi)距離的變化小于閾值stop或達(dá)到最大迭代次數(shù)maxiter，則停止迭代并輸出聚類結(jié)果。

3 實(shí)驗(yàn)及結(jié)果分析

3.1 實(shí)驗(yàn)數(shù)據(jù)及評價指標(biāo)

實(shí)驗(yàn)采用準(zhǔn)確率、DB 指數(shù)以及輪廓系數(shù)對聚類性能進(jìn)行評價。準(zhǔn)確率的計算方法如式（4）所示：

式（4）中，n表示樣本的數(shù)量，ck表示Q表中樣本標(biāo)簽為k的所有樣本集合，rj表示真實(shí)標(biāo)簽為j的樣本集合。表示兩者交集中樣本的數(shù)量。

Davies-Bouldin(DB)指數(shù)[16]是聚類算法的一種內(nèi)部評價指標(biāo)，該值越小表明聚類效果越好，計算方法如式（5）所示：

式（5）中，K為聚類數(shù)目，Adisi為類簇Ci的平均類內(nèi)距離，Cij為類簇Ci和類簇Cj聚類中心之間的距離。

輪廓系數(shù)結(jié)合了內(nèi)聚度和分散度兩種因素[17]，可以對同一數(shù)據(jù)集在不同算法中的聚類結(jié)果進(jìn)行評價。輪廓系數(shù)的計算方法如式（6）所示：

式（6）中，a(i)為第i個樣本與它所屬類簇中其他樣本的距離均值，b(i)為第i個樣本到與之距離最近的另一個類簇中所有樣本的距離均值。輪廓系數(shù)介于-1 和1 之間，且越接近1，該點(diǎn)的內(nèi)聚度與分散度越好。

實(shí)驗(yàn)數(shù)據(jù)及Q表初始化值如表2 所示。其中D1～D7 為小規(guī)模數(shù)據(jù)集，D8～D10 為中規(guī)模和大規(guī)模數(shù)據(jù)集。

表2 數(shù)據(jù)集信息及Q表初始化值

3.2 貪婪系數(shù)的選取

文中以iris 數(shù)據(jù)集為例說明貪婪系數(shù)的選取過程。使用不同的貪婪系數(shù)進(jìn)行SBRC 聚類，分別取值0.5、0.6、0.7、0.8 和0.9，選取同一樣本觀察不同貪婪系數(shù)下最大累積獎勵的收斂情況，實(shí)驗(yàn)結(jié)果如圖3 所示。由圖3 可知，貪婪系數(shù)為0.5 時Q值的收斂速度最慢，為0.9 時收斂速度最快，對其他數(shù)據(jù)集進(jìn)行分析可得到相同結(jié)論，因此，將貪婪系數(shù)設(shè)置為0.9。

圖3 貪婪系數(shù)對算法收斂性能的影響

3.3 實(shí)驗(yàn)結(jié)果及分析

為說明SBRC 算法的有效性，文中選用經(jīng)典聚類算法K-means（簡稱KM）、K-means++（簡稱KM++）、FCM 以及文獻(xiàn)[9]提出的LAC 算法作對比，進(jìn)行聚類性能分析。

圖4給出了5種算法平均準(zhǔn)確率的對比情況。由圖4 可知，相比于其他3 種聚類算法，LAC 和SBRC 算法結(jié)果整體最優(yōu)。10個數(shù)據(jù)集中有6個數(shù)據(jù)集SBRC算法的準(zhǔn)確率最高，其中D3、D6、D8 數(shù)據(jù)集的準(zhǔn)確率相比于LAC 算法分別提高了1.8%、3.8%和2.6%。

圖4 SBRC算法準(zhǔn)確率對比結(jié)果

圖5 給出了5 種聚類算法DB 指數(shù)的對比情況。由圖5 可知，相對于3 種經(jīng)典聚類算法，LAC 和SBRC算法結(jié)果整體依然較優(yōu)，且SBRC 算法稍優(yōu)于LAC。10 個數(shù)據(jù)集中有6 個數(shù)據(jù)集SBRC 算法的DB 指數(shù)均最優(yōu)，其余數(shù)據(jù)集結(jié)果也接近最優(yōu)，這表明SBRC 聚類算法具有較好的類內(nèi)緊湊度和類間分散度[18]。

圖5 SBRC算法DB指數(shù)對比結(jié)果

圖6 給出了5 種算法輪廓系數(shù)的對比情況。由圖6 可知，10 個數(shù)據(jù)集中有5 個數(shù)據(jù)集SBRC 算法的輪廓系數(shù)最高，其中D5、D6、D8 和D10 數(shù)據(jù)集相比于LAC 算法分別提高了0.018、0.053、0.068 以及0.048。

圖6 SBRC算法輪廓系數(shù)對比結(jié)果

表3 給出了5 種聚類算法運(yùn)行時間的對比情況。由表3 可知，7 個小規(guī)模數(shù)據(jù)集中，4 個數(shù)據(jù)集SBRC算法運(yùn)行時間最短。3 個中規(guī)模和大規(guī)模數(shù)據(jù)集相較于其他幾種對比算法，LAC 和SBRC 算法的運(yùn)行時間至少降低了一個數(shù)量級，SBRC 算法比LAC 算法降低效果顯著。其原因一方面與強(qiáng)化學(xué)習(xí)的行為選擇機(jī)制有關(guān)；另一方面，由于SBRC 算法采用了單行為獎勵方式，其他未選擇行為的累計獎勵不需要更新，所以相對于LAC 算法，SBRC 算法時間復(fù)雜度更低。

表3 SBRC與已有聚類算法運(yùn)行時間對比情況

綜上可知，與3 種經(jīng)典算法相比，LAC 和SBRC算法在準(zhǔn)確率、內(nèi)聚度和分散度方面，皆具有更優(yōu)的聚類性能。在算法運(yùn)行復(fù)雜度方面，SBRC 算法使用的單行為獎勵更新機(jī)制使之具有更低的時間復(fù)雜度；對大規(guī)模數(shù)據(jù)集而言，SBRC 算法則具有更強(qiáng)的時間優(yōu)勢。

3.4 實(shí)驗(yàn)過程分析

為說明SBRC 算法有效性，對算法迭代過程中單個Agent 累積獎勵進(jìn)行跟蹤，說明Q表的更新及收斂情況。圖7 給出了iris 數(shù)據(jù)集中單個樣本Q值的更新及收斂情況。其中，圖7(a)、(b)、(c)分別取自3 個不同標(biāo)簽中的樣本，圖中a1、a2及a3分別表示行為1、行為2 和行為3。通過分析可知，圖7(a)和圖7(c)的收斂速度較快，但是圖7(b)中的Q值在算法運(yùn)行前期經(jīng)歷了一段時間的震蕩，這是由強(qiáng)化學(xué)習(xí)本身“探索”和“利用”的特性以及樣本本身的分布情況造成的。

圖7 iris數(shù)據(jù)集每類中單個樣本Q值更新及收斂情況

4 結(jié)論

針對聚類結(jié)果對初始聚類中較為敏感的缺陷以及樣本的劃分方式對聚類性能的影響，文中提出了一種基于DPRI算法的SBRC 聚類算法。實(shí)驗(yàn)結(jié)果表明，相比3 種經(jīng)典聚類算法，文中提出的SBRC 算法及LAC 算法在大多數(shù)數(shù)據(jù)集上具有更高的準(zhǔn)確率、更優(yōu)的DB 指數(shù)以及更高的輪廓系數(shù)，說明了兩種基于強(qiáng)化學(xué)習(xí)聚類算法的有效性。時間復(fù)雜度方面，相比于LAC 算法，SBRC 算法處理各種規(guī)模的數(shù)據(jù)集時，都具有較大優(yōu)勢，這對下一步繼續(xù)采用SBRC 算法分析大規(guī)模數(shù)據(jù)集，提供了前期研究基礎(chǔ)。但是，SBRC 算法通過建立Q表存儲各行為的累積獎勵，是一種用空間換時間的做法，下一步就如何減小算法的空間復(fù)雜度方面進(jìn)行研究。