熊偉超　蔣瑜

摘 要：針對(duì)LF蟻群聚類算法沒有區(qū)分?jǐn)?shù)據(jù)集屬性重要度、算法效率低和聚類效果不穩(wěn)定的問題，提出一種基于熵權(quán)的全局記憶LF算法（weighted global ant colony optimization，WGACO）。該算法首先通過熵權(quán)法計(jì)算各屬性熵權(quán)，修改歐氏距離計(jì)算公式，以提升聚類精度；使用權(quán)重最大的屬性值對(duì)數(shù)據(jù)對(duì)象進(jìn)行初始化，增強(qiáng)聚類效果的穩(wěn)定性；引入全局記憶矩陣減少螞蟻的無效移動(dòng)，提升算法效率；加入算法的收斂條件，提升算法實(shí)用性。選取UCI數(shù)據(jù)庫中的7個(gè)真實(shí)數(shù)據(jù)集和3個(gè)人工生成的數(shù)據(jù)集進(jìn)行數(shù)值實(shí)驗(yàn)，并與GMACO、SMACC、ILFACC三種改進(jìn)LF的算法進(jìn)行比較，實(shí)驗(yàn)結(jié)果表明，所提算法在精度、算法效率和穩(wěn)定性上都有比較好的提升，在處理高維數(shù)據(jù)上也有較好的表現(xiàn)。最后，WGACO在商場(chǎng)會(huì)員用戶細(xì)分上表現(xiàn)良好，體現(xiàn)了其實(shí)用價(jià)值。

關(guān)鍵詞：LF蟻群聚類；信息熵；屬性權(quán)重；全局記憶

中圖分類號(hào)：TP18 文獻(xiàn)標(biāo)志碼：A 文章編號(hào)：1001-3695（2023）10-026-3053-06

doi：10.19734/j.issn.1001-3695.2023.02.0046

Global memory LF ant colony clustering algorithm based on entropy weight

Xiong Weichao，Jiang Yu

（College of Software Engineering，Chengdu University of Information Technology，Chengdu 610200，China）

Abstract：Aiming at the problem that LF ant colony clustering algorithm does not distinguish the importance of data set attri-butes，the algorithm efficiency is low and the clustering effect is unstable，this paper proposed a weighted global memory ant colony optimization （WGACO） based on entropy weight.Firstly，it calculated the entropy weight of each attribute by entropy weight method，and modified the Euclidean distance calculation formula to improve the clustering accuracy.It initialized the data object with the value of the largest weight attribute to enhance the stability of the clustering effect，and introduced the glo-bal memory matrix to reduce the invalid movement of ants and improve the efficiency of the algorithm.It added the convergence conditions of the algorithm to improve the practicability of the algorithm.Selecting seven real data sets and three artificially generated data sets in UCI database for numerical experiments，and compared WGACO with GMACO，SMACC and ILFACC three improved LF algorithms.The experimental results show that WGACO has a relatively good improvement in accuracy，algorithm efficiency and stability，and also has a good performance in processing high-dimensional data.Finally，WGACO has performed well in the segmentation of mall member users，reflecting its practical value.

Key words：LF ant colony clustering;information entropy;attribute weight;global memory

0 引言

聚類技術(shù)能夠根據(jù)數(shù)據(jù)本身發(fā)現(xiàn)其內(nèi)在規(guī)律，經(jīng)常作為數(shù)據(jù)挖掘中重要的預(yù)處理步驟。為了應(yīng)對(duì)各種各樣的數(shù)據(jù)，越來越多的聚類算法被提出。蟻群聚類算法通過模擬自然界中工蟻堆積螞蟻尸體的行為實(shí)現(xiàn)聚類，相比于傳統(tǒng)聚類LF算法無須指定聚類個(gè)數(shù)、算法魯棒性更強(qiáng)、更易實(shí)現(xiàn)并發(fā)分布式計(jì)算，并具有抗噪聲數(shù)據(jù)的特點(diǎn)。但是，蟻群聚類算法也存在算法效率較低和算法參數(shù)較多的缺點(diǎn)。Deneubourg等人［1］通過研究自然界螞蟻堆積尸體的行為，提出了解釋蟻群聚類現(xiàn)象的BM（basic model）模型。Lumer等人［2］在BM模型的基礎(chǔ)上提出了LF算法。隨后，眾多學(xué)者的改進(jìn)主要圍繞著提升算法效率和降低算法參數(shù)影響。

在提升算法效率上，劉艷等人［3］加入了信息素來控制螞蟻移動(dòng)的隨機(jī)性，并通過減少數(shù)據(jù)集屬性維度有效地提高了算法聚類效率。牛永潔［4］利用全局記憶矩陣代替之前螞蟻的局部記憶，螞蟻在全局信息下向最優(yōu)位置移動(dòng)而不是直接跳轉(zhuǎn)到該位置，減少了螞蟻的無效移動(dòng)并避免陷入局部最優(yōu)。高陽［5］通過Spark平臺(tái)實(shí)現(xiàn)了算法的并行處理，增加了算法對(duì)大量數(shù)據(jù)的處理能力。王昕宇等人［6］在文獻(xiàn)［4］的基礎(chǔ)上加入了首次找準(zhǔn)原則和相異原則，加快了螞蟻找到數(shù)據(jù)的速度，提升了算法效率。沈興鑫等人［7］設(shè)計(jì)了相似度矩陣，將螞蟻隨機(jī)移動(dòng)方式優(yōu)化為按照相似度系數(shù)規(guī)則實(shí)施目的性的關(guān)聯(lián)，加速了數(shù)據(jù)聚集。Chen等人［8］賦予螞蟻更快的搬運(yùn)速度，減少算法迭代時(shí)間。

在降低參數(shù)影響上，朱峰等人［9］通過螞蟻放下數(shù)據(jù)對(duì)象失敗的次數(shù)與迭代次數(shù)的比值設(shè)計(jì)了聚類精細(xì)程度參數(shù)alpha的數(shù)值變化公式，實(shí)現(xiàn)了alpha參數(shù)的自適應(yīng)。劉陽陽等人［10］根據(jù)先粗分再細(xì)分的思想，階段性地遞減螞蟻可視范圍R，實(shí)現(xiàn)了R參數(shù)的自適應(yīng)，并且設(shè)計(jì)了算法結(jié)束條件，使算法能夠自主完成收斂，提高了算法的實(shí)用性。甘泉等人［11］利用區(qū)域數(shù)據(jù)的信息熵變化代替了螞蟻“拾起”“放下”的判斷條件，減少了算法參數(shù)個(gè)數(shù)。同時(shí)，不少學(xué)者對(duì)蟻群聚類算法的其他方面也進(jìn)行了改進(jìn)。徐曉華等人［12］在BM模型基礎(chǔ)上提出AM（ant movement）模型，把數(shù)據(jù)對(duì)象本身當(dāng)做螞蟻，用睡眠態(tài)、激活態(tài)代替數(shù)據(jù)的撿起和放下，有效避免螞蟻的無效移動(dòng)，提高了聚類的速度和質(zhì)量。Wei［13］加入數(shù)據(jù)組合機(jī)制，采用抽象的蟻群聚類算法對(duì)基準(zhǔn)問題進(jìn)行了聚類，能夠有效地用于多變量聚類。此外，蟻群聚類算法還被應(yīng)用在了復(fù)合物挖掘［14，15］、用戶細(xì)分［16］等領(lǐng)域。通過對(duì)上述的算法改進(jìn)和算法本身分析發(fā)現(xiàn)，LF的算法效率還可以進(jìn)一步提升，獨(dú)立重復(fù)運(yùn)行時(shí)，算法效率和性能波動(dòng)較大的問題沒有被解決。

因此，本文提出一種基于熵權(quán)的全局LF蟻群聚類算法WGACO。該算法首先使用熵權(quán)法，通過信息熵計(jì)算數(shù)據(jù)集各屬性權(quán)重，并修改歐氏距離的計(jì)算公式，使用權(quán)重最大的兩個(gè)屬性值對(duì)數(shù)據(jù)對(duì)象進(jìn)行坐標(biāo)初始化；同時(shí)，引入一個(gè)全局記憶矩陣和算法收斂條件。與其他改進(jìn)的算法相比，本文算法聚類精度更高、聚類速度更快、算法穩(wěn)定性更強(qiáng)。

1 LF蟻群聚類算法

LF算法將待處理的數(shù)據(jù)對(duì)象和螞蟻都隨機(jī)投影到一個(gè)指定大小的二維網(wǎng)格中，并限制一個(gè)網(wǎng)格中只能有一個(gè)數(shù)據(jù)對(duì)象。螞蟻在網(wǎng)格中碰到一個(gè)數(shù)據(jù)對(duì)象Oi后，用式（1）計(jì)算Oi在當(dāng)前區(qū)域中的局部密度f（Oi）。

其中：d2表示數(shù)據(jù)Oi領(lǐng)域的大??；d（i，j）表示Oi與其領(lǐng)域中其他數(shù)據(jù)對(duì)象之間的歐氏距離；α為聚類的精細(xì)度，α過大，不同類數(shù)據(jù)對(duì)象之間的區(qū)分不明顯，聚類的效果變差，α過小，同類數(shù)據(jù)對(duì)象間差異被放大，聚類后簇的個(gè)數(shù)會(huì)多于實(shí)際的簇?cái)?shù)，算法運(yùn)行時(shí)間也會(huì)變長(zhǎng)。

用式（2）將f（Oi）轉(zhuǎn)換為螞蟻撿起Oi的概率。

其中：Kp是螞蟻撿起Oi的難度系數(shù)。如果Ppick大于一個(gè)隨機(jī)數(shù)，螞蟻撿起Oi，在自己的記憶中找到與Oi最匹配的位置后，螞蟻攜帶Oi向該位置隨機(jī)移動(dòng)。攜帶Oi的螞蟻移動(dòng)到新位置后，如果該位置沒有被占用，首先用式（1）計(jì)算f（Oi），之后用式（3）將f（Oi）轉(zhuǎn)換為螞蟻在該位置放下Oi的概率Pdrop。

其中：Kd是螞蟻放下Oi的難度系數(shù)。如果Pdrop大于一個(gè)隨機(jī)數(shù)，螞蟻在該位置放下Oi，并在自己的記憶中記錄該位置，之后重復(fù)之前的動(dòng)作，蟻群經(jīng)過若干次迭代后就能夠?qū)崿F(xiàn)對(duì)所有數(shù)據(jù)對(duì)象的聚類。

2 基于熵權(quán)的全局LF蟻群聚類算法

2.1 熵權(quán)法

在數(shù)據(jù)集中每個(gè)屬性對(duì)聚類的貢獻(xiàn)程度不同，區(qū)分不同屬性的重要度能提高聚類的準(zhǔn)確度、加速聚類。在統(tǒng)計(jì)學(xué)中，某個(gè)數(shù)據(jù)屬性信息熵越小，數(shù)值離散程度越大，則認(rèn)為該數(shù)據(jù)屬性包含的信息越多，對(duì)應(yīng)的權(quán)重越大。熵權(quán)法是一種通過各數(shù)據(jù)屬性本身的信息熵計(jì)算對(duì)應(yīng)權(quán)重的方法，并會(huì)對(duì)得到的結(jié)果進(jìn)行一定的修正，使得到的屬性權(quán)重較為客觀。對(duì)第j個(gè)數(shù)據(jù)屬性，用式（4）計(jì)算其信息熵。

2.2 穩(wěn)定的數(shù)據(jù)初始化策略

在LF算法中，數(shù)據(jù)對(duì)象的初始位置是隨機(jī)的。由于數(shù)據(jù)集中的數(shù)據(jù)對(duì)象S可以與多個(gè)類的數(shù)據(jù)對(duì)象聚集，算法獨(dú)立重復(fù)運(yùn)行時(shí)，每次隨機(jī)得到的初始化結(jié)果不同，S周圍數(shù)據(jù)對(duì)象的分布情況都不一樣，導(dǎo)致S有時(shí)候先碰到同類對(duì)象被正確聚集，有時(shí)候先碰到異類對(duì)象被錯(cuò)誤聚集，S對(duì)象數(shù)量越多，算法聚類效果波動(dòng)越大，下文給出了數(shù)據(jù)對(duì)象S的定義。每次隨機(jī)初始化后，同類對(duì)象之間的距離也不同，距離短算法迭代快，距離長(zhǎng)算法迭代慢，算法運(yùn)行時(shí)間也有較大波動(dòng)。圖1是LF在UCI數(shù)據(jù)集iris、wine、seed上獨(dú)立重復(fù)運(yùn)行10次的運(yùn)行時(shí)間和ARI［17］數(shù)值，從圖中可以觀察到，LF算法的聚類效率和聚類精度波動(dòng)較大，驗(yàn)證了上述分析，隨機(jī)初始化的方式的確會(huì)影響LF的穩(wěn)定性。

為了增強(qiáng)算法效率的穩(wěn)定性，需要一個(gè)穩(wěn)定的初始化結(jié)果，同一個(gè)對(duì)象初始化位置固定，為了解決算法精度不穩(wěn)定的問題，使S能夠被正確聚集，需要使S周圍有更多的同類對(duì)象，增加其在被搬運(yùn)過程中先碰到同類對(duì)象的概率?？紤]數(shù)據(jù)對(duì)象本身的屬性值是不變的，并且同類對(duì)象在同一屬性上的值相近。因此，使用數(shù)據(jù)對(duì)象自身屬性值對(duì)其進(jìn)行坐標(biāo)初始化可以得到穩(wěn)定的初始化結(jié)果，并且同類對(duì)象在網(wǎng)格上的位置接近，S周圍也會(huì)有更多的同類對(duì)象。由于同類對(duì)象在權(quán)重最大的屬性上值最接近，異類對(duì)象在該屬性上值最不同。所以，在數(shù)據(jù)集所有的屬性中，使用權(quán)重最大屬性值對(duì)數(shù)據(jù)對(duì)象進(jìn)行初始化可以使同類對(duì)象在網(wǎng)格上的位置最接近，并且不同類別的對(duì)象所處的區(qū)域有明顯的間隔，更容易執(zhí)行聚類操作。具體定義如下：

定義1 數(shù)據(jù)對(duì)象S。與同類對(duì)象和異類對(duì)象在歐氏距離度量上區(qū)分不明顯，容易被錯(cuò)誤劃分的對(duì)象。

定義2 權(quán)重最大屬性。數(shù)據(jù)集中，在數(shù)據(jù)對(duì)象分類中貢獻(xiàn)度最大的屬性。

聚類數(shù)據(jù)集根據(jù)自身特點(diǎn)可以劃分為數(shù)據(jù)內(nèi)聚度較高數(shù)據(jù)集、數(shù)據(jù)內(nèi)聚度較低數(shù)據(jù)集和高維數(shù)據(jù)集。圖2是不同類型數(shù)據(jù)集的初始化效果，圖（a）～（c）是使用權(quán)重最大屬性值初始化的理想效果，圖（d）是隨機(jī)初始化效果。接下來結(jié)合圖2分析使用權(quán)重最大屬性值初始化在不同類型數(shù)據(jù)集上的普適性：

a）數(shù)據(jù)內(nèi)聚度較高的數(shù)據(jù)集。該類數(shù)據(jù)集是比較理想的聚類數(shù)據(jù)集，圖（a）是這類數(shù)據(jù)集使用權(quán)重最大屬性值初始化的效果。因?yàn)閿?shù)據(jù)內(nèi)聚度高，所以，這類數(shù)據(jù)集一般沒有S對(duì)象，初始化后不會(huì)提升聚類精度及其穩(wěn)定性。但是從圖中可以看出，同類對(duì)象初始位置非常接近，甚至能夠達(dá)到初步聚類的效果，算法效率會(huì)得到顯著的提升。

b）數(shù)據(jù)內(nèi)聚度較低的數(shù)據(jù)集。大多數(shù)真實(shí)數(shù)據(jù)集屬于該類。圖（b）是這類數(shù)據(jù)集使用權(quán)重最大屬性值初始化的結(jié)果，由于數(shù)據(jù)內(nèi)聚度低，類之間的邊界不明顯，有可能出現(xiàn)S對(duì)象。在LF算法中，為了避免局部最優(yōu)，螞蟻搬運(yùn)對(duì)象的方向有隨機(jī)因素的影響。如果圖中的a1、b1為數(shù)據(jù)對(duì)象S，從a1、b1周圍對(duì)象的分布情況來看，其在被搬運(yùn)的過程中先碰到同類對(duì)象的概率與先碰到異類對(duì)象的概率幾乎相同。如果圖中的其他對(duì)象為數(shù)據(jù)對(duì)象S，其先碰到同類對(duì)象的概率遠(yuǎn)大于先碰到異類對(duì)象的概率。因此，使用權(quán)重最大屬性值對(duì)該類數(shù)據(jù)集初始化不僅能夠提升算法效率，還能夠提升算法聚類精度。

c）維度高，不同類別對(duì)象在權(quán)重最大屬性上差異較大的數(shù)據(jù)集。其初始化效果類似圖（b）。高維屬性往往會(huì)使各對(duì)象在歐氏距離上難以區(qū)分，所有對(duì)象之間都能夠相互聚集，算法的初始化策略不會(huì)對(duì)算法效率及其穩(wěn)定性產(chǎn)生影響。在這類數(shù)據(jù)集中，S對(duì)象的個(gè)數(shù)較多，使用權(quán)重最大屬性值初始化對(duì)聚類精度的提升比較明顯。

d）維度高，不同類別對(duì)象在權(quán)重最大屬性上差異較小的數(shù)據(jù)集。圖（c）是這類數(shù)據(jù)集初始化的效果，所有對(duì)象混雜在一起，不能實(shí)現(xiàn)聚類操作，初始化策略的改變無法影響其聚類效率和精度。

式（8）為按照屬性值的具體初始化公式。

其中：X為數(shù)據(jù)對(duì)象在網(wǎng)格上的坐標(biāo)；N為網(wǎng)格長(zhǎng)度；i為數(shù)據(jù)對(duì)象權(quán)重最大的屬性值；max為當(dāng)前數(shù)據(jù)集中該屬性的最大值；min為當(dāng)前數(shù)據(jù)集中該屬性的最小值。

2.3 全局記憶矩陣

LF算法中各螞蟻獨(dú)立執(zhí)行聚類動(dòng)作，螞蟻之間沒有信息交流。當(dāng)一只螞蟻將數(shù)據(jù)對(duì)象搬運(yùn)到目的數(shù)據(jù)對(duì)象附近時(shí)，該數(shù)據(jù)對(duì)象可能已經(jīng)被其他螞蟻搬走，導(dǎo)致螞蟻無效移動(dòng)。為了實(shí)現(xiàn)螞蟻之間的信息共享，引入一個(gè)三列的全局記憶矩陣，分別記錄數(shù)據(jù)對(duì)象索引、數(shù)據(jù)對(duì)象在當(dāng)前位置的Pdrop以及數(shù)據(jù)對(duì)象失效標(biāo)志，數(shù)據(jù)對(duì)象坐標(biāo)信息通過索引從對(duì)象位置矩陣中獲取。加入全局記憶矩陣后，螞蟻拾起、移動(dòng)、放下的處理步驟發(fā)生變化，具體如下：

a）螞蟻成功拾起數(shù)據(jù)對(duì)象后，如果全局記憶中存在該對(duì)象，將該對(duì)象設(shè)為失效點(diǎn)。

b）螞蟻在全局記憶中找到與當(dāng)前數(shù)據(jù)對(duì)象最相似的數(shù)據(jù)對(duì)象后，向目標(biāo)對(duì)象隨機(jī)移動(dòng)。

c）螞蟻成功放下數(shù)據(jù)對(duì)象后，在全局記憶中用當(dāng)前數(shù)據(jù)對(duì)象信息替換失效對(duì)象信息，如果沒有失效對(duì)象，將當(dāng)前數(shù)據(jù)對(duì)象的Pdrop與全局記憶中最小的Pdrop進(jìn)行比較，如果當(dāng)前數(shù)據(jù)對(duì)象的Pdrop大于該P(yáng)drop，用當(dāng)前數(shù)據(jù)對(duì)象信息替換對(duì)應(yīng)數(shù)據(jù)對(duì)象信息，否則全局記憶保持不變。

全局記憶矩陣的加入能夠?qū)崿F(xiàn)蟻群中的信息共享，每只螞蟻都能作出當(dāng)前最合適的選擇。移動(dòng)的隨機(jī)性是LF算法不易陷入局部最優(yōu)的關(guān)鍵，而移動(dòng)的有向性能夠加速聚類，全局記憶中螞蟻向目標(biāo)對(duì)象隨機(jī)移動(dòng)兼顧了移動(dòng)的隨機(jī)性和有向性，避免陷入局部最優(yōu)的同時(shí)提升算法效率。矩陣中的失效標(biāo)志列能夠快速找到替換項(xiàng)，減少更新矩陣時(shí)的時(shí)間。

2.4 算法自主收斂

LF中算法迭代次數(shù)是固定的，次數(shù)過低聚類效果不理想，次數(shù)過高會(huì)影響算法效率。從式（1）（2）可以發(fā)現(xiàn)，越是到聚類后期，數(shù)據(jù)對(duì)象周圍同類數(shù)據(jù)的數(shù)量越多，該對(duì)象與其領(lǐng)域?qū)ο笾g的歐氏距離d（i，j）變得越小，區(qū)域密度f（Oi）變得越大，該對(duì)象被拾起的概率Ppick變得越小，該對(duì)象很難被螞蟻拾起，對(duì)應(yīng)螞蟻仍保持為空載狀態(tài)。類似的對(duì)象越多，網(wǎng)格上處于空載狀態(tài)的螞蟻就越多。因此通過算法每次迭代結(jié)束后空載螞蟻的數(shù)量可以判斷算法的聚類進(jìn)度，當(dāng)算法中空載螞蟻的數(shù)量連續(xù)多次超出預(yù)設(shè)范圍后，可以認(rèn)為聚類基本完成。具體的收斂條件為：當(dāng)算法在連續(xù)20次迭代中空載螞蟻的數(shù)量超過總數(shù)量的90%時(shí)，算法結(jié)束。真實(shí)的數(shù)據(jù)集中難免會(huì)存在異常對(duì)象，這類對(duì)象不能與其他對(duì)象發(fā)生聚集行為，導(dǎo)致拾起這些對(duì)象的螞蟻一直處于負(fù)載狀態(tài)，影響算法收斂。為了避免這些數(shù)據(jù)的影響，為每只螞蟻增加一個(gè)計(jì)數(shù)器，記錄螞蟻連續(xù)放下數(shù)據(jù)對(duì)象失敗的次數(shù)，當(dāng)計(jì)數(shù)器數(shù)值達(dá)到指定的次數(shù)后將當(dāng)前負(fù)載的數(shù)據(jù)對(duì)象強(qiáng)行放下，轉(zhuǎn)而去處理其他數(shù)據(jù)對(duì)象。組合以上的改進(jìn)，WGACO偽代碼如下。

算法1 WGACO算法

輸入：數(shù)據(jù)集D。

輸出：聚類結(jié)果C。

a）初始化參數(shù)如網(wǎng)格大小GridNum，螞蟻數(shù)量AntNum，數(shù)據(jù)數(shù)量N，聚類精細(xì)度α，鄰域半徑R，拾起難度K1，放下難度K2，全局記憶容量MemorySize。

b）計(jì)算數(shù)據(jù)集各屬性權(quán)重。

c）將得到的權(quán)重按照式（7）加入到歐氏距離的計(jì)算當(dāng)中。

d）通過式（8）完成數(shù)據(jù)對(duì)象在網(wǎng)格上的初始化。

e）隨機(jī)選擇螞蟻，若螞蟻為空載執(zhí)行步驟f），為負(fù)載執(zhí)行步驟g）。

f）螞蟻隨機(jī)跳轉(zhuǎn)到一個(gè)數(shù)據(jù)對(duì)象上，通過式（1）（2）判斷能否撿起該對(duì)象。

g）螞蟻通過式（1）（3）判斷能否在當(dāng)前位置放下負(fù)載的數(shù)據(jù)對(duì)象，若不能，則根據(jù)全局記憶矩陣?yán)^續(xù)移動(dòng)。

h）判斷算法是否收斂，收斂執(zhí)行步驟i），否則繼續(xù)執(zhí)行步驟e）。

i）輸出聚類結(jié)果。

3 算法復(fù)雜度分析

LF作為迭代的算法，其時(shí)間復(fù)雜度為O（MNK），M為迭代次數(shù)，N為螞蟻個(gè)數(shù)，K為每次迭代中每只螞蟻的計(jì)算量。由于N為事先指定的常數(shù)，所以LF算法的時(shí)間復(fù)雜度屬于O（n2）。使用新的歐氏距離，改變數(shù)據(jù)初始化策略只是使用了不同的計(jì)算公式，在時(shí)間復(fù)雜度上沒有變化。因此，WGACO的整體時(shí)間復(fù)雜度為O（MNK+T），依舊屬于O（n2），T為計(jì)算屬性權(quán)重的時(shí)間開銷。使用權(quán)重最大屬性值對(duì)數(shù)據(jù)對(duì)象進(jìn)行初始化后，螞蟻搬運(yùn)數(shù)據(jù)對(duì)象的距離變短，使用全局記憶矩陣后，減少了無效迭代的次數(shù)，WGACO中的M值會(huì)明顯小于LF中的M值。因此，雖然WGACO的時(shí)間復(fù)雜度與LF相同，運(yùn)行效率卻會(huì)明顯提升。LF的空間復(fù)雜度為O（1），每只螞蟻都擁有常數(shù)個(gè)記憶空間。WGACO引入了全局記憶矩陣，并為每只螞蟻增加了一個(gè)計(jì)數(shù)器，依然只使用了常數(shù)個(gè)存儲(chǔ)空間，空間復(fù)雜度依然為O（1）。

4 仿真實(shí)驗(yàn)及分析

4.1 實(shí)驗(yàn)環(huán)境與實(shí)驗(yàn)數(shù)據(jù)集

對(duì)比實(shí)驗(yàn)在Anaconda4 jupyterlab中完成。實(shí)驗(yàn)所用操作系統(tǒng)為Windows 10，處理器為Intel Core i5-8250U@1.60 GHz四核，內(nèi)存為8 GB。表1為7個(gè)UCI數(shù)據(jù)集的說明，表2為三個(gè)由sklearn內(nèi)置的make_blobs函數(shù)生成的數(shù)據(jù)集，其中cluster_std參數(shù)表示生成的數(shù)據(jù)集中同一類數(shù)據(jù)的方差大小。設(shè)置與GMACO［6］、SMACC［7］和ILFACC［8］三種改進(jìn)LF的算法對(duì)比。

4.2 實(shí)驗(yàn)參數(shù)

參數(shù)設(shè)置為：Kpick=0.1，Kdrop=0.15，鄰域r=2，二維網(wǎng)格的大小是100×100，螞蟻個(gè)數(shù)為30，全局記憶的長(zhǎng)度為50［4］，螞蟻計(jì)數(shù)器的閾值為20。

從式（1）發(fā)現(xiàn)，適合每個(gè)數(shù)據(jù)集的α值不相同。因此，在實(shí)驗(yàn)前需要先多次運(yùn)行算法找到適合不同數(shù)據(jù)集的α值。合適的α值應(yīng)該滿足以下要求：在該α值下算法能夠完成收斂；同時(shí)，為了充分驗(yàn)證改進(jìn)后算法的有效性，每個(gè)數(shù)據(jù)集取三個(gè)不同的α值進(jìn)行對(duì)比實(shí)驗(yàn)，三個(gè)α值依次增大。表3是各個(gè)數(shù)據(jù)集在實(shí)驗(yàn)中的α值，第一列為在多次調(diào)試中找到的能使該數(shù)據(jù)集完成收斂的最小α值。從式（7）發(fā)現(xiàn)，修改后的歐氏距離計(jì)算公式縮小了屬性之間的差值，導(dǎo)致α的取值范圍發(fā)生變化。為了維持對(duì)比實(shí)驗(yàn)的公平，其余三種對(duì)比算法也使用式（7）計(jì)算歐氏距離，將各屬性權(quán)重全部設(shè)為1/n，n為數(shù)據(jù)的屬性個(gè)數(shù)。

聚類結(jié)果的評(píng)價(jià)指標(biāo)使用調(diào)整蘭德系數(shù)ARI（adjustable Rand index）［17］和F指標(biāo)（F1-measure）［18］，ARI為［-1，1］，F(xiàn)1為［0，1］，值越大代表聚類效果越好。同時(shí)，記錄四種算法的運(yùn)行時(shí)間來評(píng)估算法效率，運(yùn)行時(shí)間包含數(shù)據(jù)預(yù)處理、屬性權(quán)重計(jì)算、數(shù)據(jù)集初始化、算法迭代。實(shí)驗(yàn)結(jié)果中的數(shù)值都為每個(gè)算法獨(dú)立重復(fù)運(yùn)行20次后的均值。

4.3 實(shí)驗(yàn)結(jié)果與分析

圖3為所有數(shù)據(jù)集使用權(quán)重最大屬性值初始化的效果。初始化效果符合圖2中的預(yù)期，可以看出，data1、iris、seed屬于內(nèi)聚度較高的數(shù)據(jù)集，data2、wine、Wdbc、wave屬于內(nèi)聚度較低數(shù)據(jù)集，move、cover屬于在個(gè)別屬性值上有明顯區(qū)別的高維數(shù)據(jù)集，data3屬于不能聚類的數(shù)據(jù)集。圖3的實(shí)驗(yàn)結(jié)果證實(shí)了使用權(quán)重最大屬性值初始化策略的普適性。

表4為四種算法的對(duì)比實(shí)驗(yàn)結(jié)果。在算法效率上，WGACO在低維數(shù)據(jù)集iris、wine、seed、Wdbc、wave上表現(xiàn)最好，比GMACO平均快3.43倍，比SMACC平均快2.21倍，比ILFACC快1.76倍，一方面是因?yàn)閃GACO在初始化后，數(shù)據(jù)集中同類對(duì)象就能基本處于網(wǎng)格上的同一區(qū)域，極大地縮短了算法迭代時(shí)間。初始化效果越好，WGACO的聚類效率提升效果越明顯，WGACO在初始化效果好的iris、seed、Wdbc上比其余三種算法平均快3.4倍，而在初始化效果一般的wine和wave上平均只快了1倍。因此，在數(shù)據(jù)量較小的wine數(shù)據(jù)集中，SMACC和ILFACC算法的聚類效率與WGACO相近，甚至有時(shí)能夠更快。另一方面是因?yàn)閃GACO中引入了全局記憶矩陣，全局記憶相比于ILFACC中的局部記憶更具時(shí)效性，屬性熵權(quán)的加入使全局記憶信息更準(zhǔn)確，避免了算法因過時(shí)、錯(cuò)誤信息而出現(xiàn)的無效迭代，能夠有效地提升聚類效率。在高維數(shù)據(jù)集move、cover中，WGACO相比于其余三種算法沒有明顯優(yōu)勢(shì)，這是因?yàn)檩^高的維度使不同簇之間的對(duì)象在距離度量上出現(xiàn)同質(zhì)現(xiàn)象，所有對(duì)象互相都能產(chǎn)生聚集行為，數(shù)據(jù)集被聚集的速度受算法的影響變小，表4中可以發(fā)現(xiàn)，在最高維度的cover數(shù)據(jù)集上四種算法的聚類效率幾乎沒有差別。表4中黑體數(shù)據(jù)為同組中的最優(yōu)值。

在聚類精度上，WGACO和ILFACC在五個(gè)低維數(shù)據(jù)集上的聚類精度整體高于GMACO和SMACC，因?yàn)檫@兩種算法都在計(jì)算歐氏距離中加入了屬性權(quán)重的調(diào)節(jié)。其中，在iris、seed、Wdbc數(shù)據(jù)集上WGACO和ILFACC的F值和ARI幾乎持平，在wine和wave數(shù)據(jù)集上，WGACO的F值和ARI高于ILFACC，平均高出9%，這是因?yàn)檫@兩種數(shù)據(jù)集數(shù)據(jù)內(nèi)聚程度較低，數(shù)據(jù)對(duì)象S的個(gè)數(shù)較多。而在高維數(shù)據(jù)集move和cover中，WGACO的聚類精度明顯高于其他三種算法，F(xiàn)值和ARI平均比GMACO高18%和25%，比SMACC高17%和24%，比ILFACC高15%和23%，因?yàn)殡S著數(shù)據(jù)維度的增加，在距離度量計(jì)算中無效屬性對(duì)有效屬性的干擾越來越大，單純地加入屬性權(quán)重的影響變小，ILFACC在兩個(gè)高維數(shù)據(jù)集上的聚類精度相比于GMACO和SMACC并沒有明顯提升，對(duì)象是否被正確聚類更多地取決于其周圍對(duì)象的分布情況。WGACO單獨(dú)使用權(quán)重最大的兩個(gè)屬性對(duì)數(shù)據(jù)集進(jìn)行初始化，能夠避免其他屬性的干擾，相比于ILFACC算法，能夠更有效地發(fā)揮屬性權(quán)重的作用。同時(shí)，全局記憶矩陣能夠使螞蟻向當(dāng)前全局最優(yōu)位置隨機(jī)移動(dòng)，避免了陷入了局部最優(yōu)，而SMACC通過尋找聚類對(duì)象領(lǐng)域中的相似對(duì)象來決定該對(duì)象被搬運(yùn)的方向，缺乏全局信息的指導(dǎo)，雖然其聚類速度快，但容易陷入局部最優(yōu)，聚類精度不高。

在表4中觀察到，隨著α值的增大，四種算法都出現(xiàn)了聚類精度下降、運(yùn)行時(shí)間減小的趨勢(shì)，從α的最小值到最大值，GMACO的F值和ARI分別下降14%和22%，SMACC分別下降11%和12%，ILFACC分別下降15%和12%，WGACO分別下降4%和6%。α為聚類的精細(xì)度系數(shù)，α變大代表所有對(duì)象在螞蟻眼中開始變得相似，此時(shí)，低維數(shù)據(jù)集中不同類別的對(duì)象開始出現(xiàn)不可區(qū)分的現(xiàn)象，其被正確聚類的概率也開始受到周圍對(duì)象分布情況的影響，與上述高維數(shù)據(jù)集的情況類似。因此，使用權(quán)重最大屬性初始化策略后，WGACO對(duì)α有一定的容錯(cuò)能力，聚類精度的下降程度要比其余三種算法小。

上述分析可以得出結(jié)論，WGACO在數(shù)據(jù)內(nèi)聚程度較高的低維數(shù)據(jù)集上主要為提升聚類速度，在數(shù)據(jù)內(nèi)聚程度較低的低維數(shù)據(jù)集和高維數(shù)據(jù)集上主要為提升聚類精度，符合2.2節(jié)中的分析。

圖4為GMACO、SMACC、ILFACC、WGACO在各數(shù)據(jù)集上獨(dú)立運(yùn)行20次后運(yùn)行時(shí)間和ARI標(biāo)準(zhǔn)差的折線圖表示。從折線圖上可以直觀地觀察到，WGACO在低維數(shù)據(jù)集上運(yùn)行時(shí)間的穩(wěn)定性比其余三種算法強(qiáng)，在高維數(shù)據(jù)集上聚類精度的穩(wěn)定性比其余三種算法強(qiáng)，符合2.2節(jié)中的分析。

4.4 算法統(tǒng)計(jì)測(cè)試

為了更直觀地對(duì)比不同算法之間的性能，對(duì)GMACO、SMACC、ILFACC、WGACO的運(yùn)行時(shí)間和ARI使用Friedman和Nemenyi后續(xù)檢驗(yàn)，α設(shè)置為0.05。Friedman檢驗(yàn)是利用秩實(shí)現(xiàn)對(duì)多個(gè)總體分布是否存在顯著差異的非參數(shù)檢驗(yàn)方法。圖5為各算法用Friedman檢驗(yàn)圖表示的檢測(cè)結(jié)果，圖中橫軸為算法排序值，縱軸為算法，橫線的中點(diǎn)為算法平均序值，若兩條橫線有交叉，說明對(duì)應(yīng)的算法之間沒有明顯性能差異。從測(cè)試結(jié)果可以直觀地發(fā)現(xiàn)，WGACO的聚類效果和算法效率都明顯優(yōu)于GMACO，比SMACC、ILFACC表現(xiàn)更好。

4.5 算法應(yīng)用

為了驗(yàn)證WGACO的實(shí)用性，將其用于商場(chǎng)用戶細(xì)分，用于給營(yíng)銷團(tuán)隊(duì)的決策提供依據(jù)。mall customer segmentation data數(shù)據(jù)集是Kaggle中的商場(chǎng)會(huì)員信息，數(shù)據(jù)集中有200個(gè)會(huì)員信息，會(huì)員信息分別為顧客ID、性別、年齡、年收入和消費(fèi)得分。由于真實(shí)的數(shù)據(jù)沒有標(biāo)簽，所以用輪廓系數(shù)作為用戶細(xì)分結(jié)果的評(píng)價(jià)指標(biāo)，輪廓系數(shù)為［-1，1］，值越大代表聚類效果越好。輪廓系數(shù)通過同一簇內(nèi)數(shù)據(jù)的內(nèi)聚程度和不同簇內(nèi)數(shù)據(jù)的離散程度對(duì)聚類結(jié)果進(jìn)行評(píng)價(jià)。

圖6分別是WGACO對(duì)該數(shù)據(jù)集的初始化效果和聚類結(jié)果，聚類結(jié)果的輪廓系數(shù)為0.62。表5中根據(jù)每一類會(huì)員的均值收入和消費(fèi)水平將會(huì)員分為了五類，如表5所示。其中：A類會(huì)員為高收入低消費(fèi)客戶；B類會(huì)員為平均收入和平均消費(fèi)的客戶；C類會(huì)員為高收入高消費(fèi)客戶；D類會(huì)員為低收入高消費(fèi)客戶；E類會(huì)員為低收入低消費(fèi)客戶。不同類型的會(huì)員之間的平均收入和平均消費(fèi)得分有明顯的區(qū)別，聚類結(jié)果的輪廓系數(shù)較高，都體現(xiàn)了WGACO聚類結(jié)果的合理性，證明了WGACO的應(yīng)用價(jià)值。

5 結(jié)束語

本文從LF算法運(yùn)行時(shí)間過長(zhǎng)、聚類效果不穩(wěn)定的問題出發(fā)，提出了一種基于熵權(quán)的全局LF蟻群聚類算法（WGACO）。WGACO通過信息熵計(jì)算數(shù)據(jù)集各屬性權(quán)重，并將其加入到歐氏距離的計(jì)算當(dāng)中，隨后使用兩個(gè)權(quán)重最大的屬性值作為數(shù)據(jù)對(duì)象的初始坐標(biāo)，同時(shí)加入了全局記憶矩陣和算法結(jié)束條件。通過在七個(gè)UCI數(shù)據(jù)集和三個(gè)人工生成的數(shù)據(jù)集上的實(shí)驗(yàn)，驗(yàn)證了WGACO在聚類精度、算法效率、算法穩(wěn)定性上都有較好的提升，面對(duì)高維數(shù)據(jù)也有較好的表現(xiàn)。通過在Kaggle用戶數(shù)據(jù)集上的應(yīng)用，證明了WGACO的應(yīng)用價(jià)值。

但本文算法依賴屬性權(quán)重，在實(shí)驗(yàn)中發(fā)現(xiàn)，單一的權(quán)重計(jì)算方式在面對(duì)某些數(shù)據(jù)集時(shí)得出的效果不理想，不過改進(jìn)后算法的效率有較大的提升，在屬性權(quán)重確定上多一些時(shí)間開銷是值得的。因此，后續(xù)工作中可以結(jié)合多種權(quán)重計(jì)算方法來保證權(quán)重的正確。同時(shí)，蟻群算法由于算法參數(shù)過多導(dǎo)致實(shí)用性較低，減少算法參數(shù)也是下一步的研究?jī)?nèi)容。

參考文獻(xiàn)：

［1］Deneubourg J L，Goss S，F(xiàn)ranks N，et al.The dynamics of collective sorting robot-like ants and ant-like robots［C］//Proc of the 1st International Conference on Simulation of Adaptive Behavior.1991：356-365.

［2］Lumer E D，F(xiàn)aieta B.Diversity and adaptation in populations of clustering ants［C］//Proc of International Conference on Simulation of Adaptive Behavior.1994：501-508.

［3］劉艷，周斌.增量文本軟聚類速度改善算法設(shè)計(jì)及仿真［J］.計(jì)算機(jī)仿真，2022，39（8）：524-528.（Liu Yan，Zhou Bin.Design and simulation of incremental text soft clustering speed improvement algorithm［J］.Computer Simulation，2022，39（8）：524-528.）

［4］牛永潔.具有全局指導(dǎo)的啟發(fā)式蟻群聚類新算法［J］.計(jì)算機(jī)技術(shù)與發(fā)展，2013，23（9）：74-77.（Niu Yongjie.A new heuristic ant colony clustering algorithm with global guidance［J］.Computer Technology and Development，2013，23（9）：74-77.）

［5］高陽.一種改進(jìn)的不平衡數(shù)據(jù)集過采樣方法及其并行算法研究［D］.煙臺(tái)：煙臺(tái)大學(xué)，2021.（Gao Yang.Research on an improved oversampling method for unbalanced datasets and its parallel algorithm［D］.Yantai：Yantai University，2021.）

［6］王昕宇，羅可.具有全局記憶的LF蟻群聚類算法［J］.計(jì)算機(jī)工程與應(yīng)用，2019，55（20）：52-57，113.（Wang Xinyu，Luo Ke.Ant colony clustering algorithm with global memory［J］.Computer Engineering and Application，2019，55（20）：52-57，113.）

［7］沈興鑫，楊余旺，肖高權(quán)，等.基于相似度的蟻群聚類算法［J］.計(jì)算機(jī)與數(shù)字工程，2021，49（6）：1052-1057.（Shen Xingxin，Yang Yuwang，Xiao Gaoquan，et al.Ant colony clustering algorithm based on similarity［J］.Computer and Digital Engineering，2021，49（6）：1052-1057.）

［8］Chen Lianyong，Song Jinyu.Abnormal data detection method based on ant colony clustering［C］//Proc of the 6th International Conference on Electronic Information Technology and Computer Engineering.2022：66-72.

［9］朱峰，陳莉.一種改進(jìn)的蟻群聚類算法［J］.計(jì)算機(jī)工程與應(yīng)用，2010，46（6）：133-135.（Zhu Feng，Chen Li.An improved ant colony clustering algorithm［J］.Computer Engineering and Application，2010，46（6）：133-135.）

［10］劉陽陽，呂偉明，霍萌萌，等.基于LF算法改進(jìn)的動(dòng)態(tài)蟻群聚類算法［EB/OL］.（2012-04-06）［2023-04-06］.http：//www.paper.edu.cn/releasepaper/content/201204-60.（Liu Yangyang，Lyu Weiming，Huo Mengmeng，et al.Dynamic ant colony clusteralgorithm based on improved LF algorithm［EB/OL］.（2012-04-06）［2023-04-06］.http：//www.paper.edu.cn/releasepaper/content/201204-60.）

［11］甘泉，王慧.一種改進(jìn)的蟻群聚類分析算法［J］.系統(tǒng)仿真技術(shù)，2015，11（3）：219-223，206.（Gan Quan，Wang Hui.An improved ant colony clustering analysis algorithm［J］.System Simulation Technology，2015，11（3）：219-223，206.）

［12］徐曉華，陳崚.一種自適應(yīng)的螞蟻聚類算法［J］.軟件學(xué)報(bào)，2006，17（9）：1884-1889.（Xu Xiaohua，Chen Ling.An adaptive ant clustering algorithm［J］.Journal of Software，2006，17（9）：1884-1889.）

［13］Wei Gao.Improved ant colony clustering algorithm and its performance study［M］//Computational Intelligence and Neuroscience.2016：19.

［14］胡健，朱海灣，毛伊敏.基于蟻群聚類的動(dòng)態(tài)加權(quán)PPI網(wǎng)絡(luò)復(fù)合物挖掘［J］.計(jì)算機(jī)應(yīng)用研究，2020，37（2）：390-397，420.（Hu Jian，Zhu Haiwan，Mao Yimin.Dynamic weighted PPI network complex mining based on ant colony clustering［J］.Application Research of Computers，2020，37（2）：390-397，420.）

［15］胡嘉偉，吳云志，樂毅，等.基于改進(jìn)LF算法的PPI網(wǎng)絡(luò)聚類方法［J］.湖南工程學(xué)院學(xué)報(bào)：自然科學(xué)版，2016，26（3）：56-59.（Hu Jiawei，Wu Yunzhi，Le Yi， et al. PPI network clustering method based on improved LF algorithm［J］.Journal of Hunan University of Engineering：Natural Science Edition，2016，26（3）：56-59.）

［16］Chniter M，Abid A，Kallel I，et al.Computational complexity analysis of ant colony clustering algorithms：application to students grouping problem［C］//Proc of IEEE International Conference on Systems，Man，and Cybernetics.Piscataway，NJ：IEEE Press，2022：736-741.

［17］Vinh N X，Epps J，Bailey J.Information theoretic measures for cluste-rings comparison：variants，properties，normalization and correction for chance［J］.The Journal of Machine Learning Research，2010，11：2837-2854.

［18］Powers D M W.Evaluation：from precision，recall and F-measure toROC，informed ness，marked ness and correlation［J］.Journal of Machine Learning Technologies，2020（2）：37-63.

收稿日期：2023-02-21；修回日期：2023-04-13

作者簡(jiǎn)介：熊偉超（2002-），男，四川南充人，碩士研究生，主要研究方向?yàn)閿?shù)據(jù)挖掘、智能計(jì)算；蔣瑜（1980-），男（通信作者），四川鄰水人，副教授，碩士，主要研究方向?yàn)閿?shù)據(jù)挖掘、粗糙集與智能計(jì)算（jiangyu@cuit.edu.cn）．