基于猶豫模糊集的凝聚式層次聚類算法

李文全，毛伊敏，彭新東

基于猶豫模糊集的凝聚式層次聚類算法

李文全*，毛伊敏，彭新東

（韶關(guān)學(xué)院 信息工程學(xué)院，廣東 韶關(guān) 512005）（?通信作者電子郵箱78192128@qq.com）

針對猶豫模糊聚類分析存在信息失真、屬性權(quán)重客觀性差、時間復(fù)雜度高的問題，提出一種基于猶豫模糊集的凝聚式層次聚類算法（AHCHF）。首先，采用猶豫模糊元的平均值擴(kuò)充猶豫度小的數(shù)據(jù)對象；其次，利用原始信息熵和內(nèi)部最大差異計算數(shù)據(jù)對象擴(kuò)充前后的權(quán)重，并根據(jù)兩個權(quán)重向量之間的最小鑒別信息確定屬性的綜合權(quán)重；最后，以加權(quán)距離和更小為目標(biāo)，給出猶豫度恒定的中心點構(gòu)造方法。在具體實例和人造數(shù)據(jù)集上進(jìn)行的實驗結(jié)果表明，相較于經(jīng)典的猶豫模糊層次聚類算法（HFHC）和較新的模糊層次聚類算法（FHCA），AHCHF的輪廓系數(shù)（SC）均值分別提高了23.99%和9.28%，運行時間分別平均減少了27.18%和6.40%。以上結(jié)果驗證了所提算法可以有效解決信息失真、屬性權(quán)重客觀性差的問題，并較好地提升聚類效果和聚類性能。

猶豫模糊集；聚類分析；猶豫度；數(shù)據(jù)挖掘；模糊熵

0 引言

聚類分析［1］按照一定規(guī)則將數(shù)據(jù)對象集劃分為若干個不同類簇，使同一類簇的數(shù)據(jù)對象間的相似性盡量大、不同類簇對象間的相似性盡量小，以挖掘隱藏在其中有價值的信息和知識。典型的聚類算法有基于劃分的均值聚類算法［2］、基于層次的變色龍算法［3］、基于網(wǎng)格的空間聚類算法［4］和基于密度的噪聲應(yīng)用空間聚類算法［5］等，這些算法被廣泛應(yīng)用于管理和醫(yī)療等領(lǐng)域。

Chen等［19］依據(jù)Pearson系數(shù)原理定義了猶豫模糊集的相關(guān)系數(shù)，并利用等價矩陣和傳遞閉包，提出了猶豫模糊集的層次聚類算法；Zhang等［20］提出了基于最小加權(quán)漢明距離的猶豫模糊凝聚層次聚類算法；王志飛等［21］設(shè)計了數(shù)據(jù)集的權(quán)重公式和構(gòu)造了簇中心的計算公式，提出了一種凝聚中心猶豫度恒定的模糊聚類算法，但它的權(quán)重沒有考慮猶豫度擴(kuò)充后信息量的變化；張煜等［22］給出了猶豫模糊元素集的補齊方法和距離函數(shù)權(quán)重計算公式，利用密度峰值選取簇中心，提出了基于密度峰值的加權(quán)猶豫模糊聚類算法；孫爽爽等［23］設(shè)計了可擴(kuò)展的猶豫模糊集的加權(quán)相似度計算公式，提出了猶豫模糊數(shù)據(jù)對象集的譜聚類算法；鄧小燕［24］運用核函數(shù)將數(shù)據(jù)映射到高維特征空間，保證原始樣本結(jié)構(gòu)不變的情況下擴(kuò)大樣本間的差異性，提出了猶豫模糊核C-均值聚類算法。

盡管上述算法都取得了較好的聚類效果，也在多個領(lǐng)域得到了應(yīng)用，但仍存在多方面不足，主要體現(xiàn)在如下幾點：

1）猶豫度擴(kuò)充導(dǎo)致信息失真。在猶豫模糊元運算時，需要取最大元或最小元擴(kuò)充猶豫度小的數(shù)據(jù)對象，擴(kuò)充后會使原有信息量發(fā)生改變，導(dǎo)致信息失真。

2）人為主觀給定屬性權(quán)重。既沒有考慮猶豫度擴(kuò)充前的原始信息，也沒有考慮擴(kuò)充后對猶豫度和模糊性的影響，屬性權(quán)重的客觀性較差。

3）新類中心點的構(gòu)造性能不理想。采用平均算子構(gòu)造中心點，時間復(fù)雜度高且空間復(fù)雜度呈指數(shù)級增長，嚴(yán)重影響算法性能。

為解決上述問題，本文提出一種基于猶豫模糊集的凝聚式層次聚類算法（Agglomerative Hierarchical Clustering algorithm based on Hesitant Fuzzy set， AHCHF）。

本文的主要工作如下：

1）提出保持信息熵不發(fā)生改變的猶豫度擴(kuò)充方法。采用猶豫模糊元的平均值擴(kuò)充猶豫度小的數(shù)據(jù)對象，避免猶豫度擴(kuò)充導(dǎo)致信息失真。

2）提出基于最小鑒別信息的綜合權(quán)重計算方法，利用原始信息熵和內(nèi)部最大差異計算猶豫度擴(kuò)充前后的權(quán)重，并根據(jù)權(quán)重向量之間的最小鑒別信息確定綜合權(quán)重，以解決人為主觀權(quán)重存在客觀性差的問題。

3）提出猶豫度恒定的中心點構(gòu)造方法。在保持猶豫度不增加的情況下，利用平均算子計算中心點的最小元和最大元，并根據(jù)分箱原則，確定中心點的其他元素，以此構(gòu)造加權(quán)距離之和更小的中心點，解決以往算法存在時間復(fù)雜度高、空間復(fù)雜度呈指數(shù)級增長的問題。

最后，在具體實例和人造數(shù)據(jù)上驗證了所提算法的有效性。實驗結(jié)果表明，與經(jīng)典的猶豫模糊層次聚類算法（Hesitant Fuzzy Hierarchical Clustering algorithm， HFHC）［17］和最新的模糊層次聚類算法（Fuzzy Hierarchical Clustering Algorithm， FHCA）［21］相比，AHCHF在有效解決信息失真、屬性權(quán)重客觀性差問題的基礎(chǔ)上，提升了聚類效果，減少了聚類時間。

1 相關(guān)工作

2 AHCHF

2.1　算法思想

AHCHF首先對數(shù)據(jù)預(yù)處理，通過擴(kuò)充猶豫度，使同一屬性下的特征值具有相同猶豫度；其次，把每個數(shù)據(jù)對象看成一個類，計算類間的加權(quán)距離，找出最小距離并合并成新的類；最后構(gòu)造新類的中心點和計算新類與其他類之間的加權(quán)距離，不斷合并最小距離的類，直到所有的數(shù)據(jù)對象聚成一類。根據(jù)算法思路可知，它主要包含猶豫度的擴(kuò)充、屬性權(quán)重的確定和聚類中心點的構(gòu)造這3個階段。各階段的主要任務(wù)有：1）猶豫度的擴(kuò)充。針對猶豫度不相等的情況，采用猶豫模糊元平均值填充的方法，擴(kuò)充猶豫度小的數(shù)據(jù)對象，解決猶豫度擴(kuò)充導(dǎo)致信息失真的問題。2）屬性權(quán)重的確定。利用信息熵確定猶豫模糊元擴(kuò)充前的原始權(quán)重，利用猶豫模糊元的最大離差確定擴(kuò)充后的權(quán)重，并根據(jù)兩者之間的最小鑒別信息確定綜合權(quán)重，解決人為主觀給定屬性權(quán)重問題。3）聚類中心的構(gòu)造。以加權(quán)距離和更小為目標(biāo)，在猶豫度不增加的情況下，構(gòu)造新類的中心點，解決算法性能較低下的問題。

2.2　猶豫度的擴(kuò)充

另外，根據(jù)得分函數(shù)與平均值的定義可知，它們的值都是猶豫模糊元的平均值，故有：

綜上，由于得分函數(shù)與離差度都沒有發(fā)生改變，則有：

依據(jù)定理1，猶豫度擴(kuò)充的主要步驟如下：

算法1 猶豫度擴(kuò)充算法。

1） 初始化數(shù)據(jù)：

for=1 todo

找出當(dāng)前屬性下的最大猶豫度

end for

2） 元素排序：

repeat

for=todo

分別找出最大值和最小值下標(biāo)

end for

將最大值放在最后，最小值放在最前

until（<）

for=1 todo

大于平均值的元素向后移動

end for

2.3　屬性權(quán)重的確定

屬性權(quán)重在聚類分析中起著舉足輕重的作用，權(quán)重的微小變化都可能產(chǎn)生不同的聚類結(jié)果。以往的屬性權(quán)重是人為設(shè)定的，主觀因素影響大，沒有考慮數(shù)據(jù)擴(kuò)充前后信息量的變化，客觀性和科學(xué)性不足。本文提出基于最小鑒別信息的綜合權(quán)重的方法，它先使用熵權(quán)法確定猶豫模糊元素擴(kuò)充前的原始權(quán)重，其次用最大離差法確定猶豫度擴(kuò)充后的權(quán)重，再次利用最小鑒別信息構(gòu)造猶豫模糊元素的綜合權(quán)重，以此解決人為主觀給定屬性權(quán)重問題。該方法需要分別計算數(shù)據(jù)對象的原始權(quán)重、擴(kuò)充后權(quán)重和綜合權(quán)重。

1）原始權(quán)重。

2）擴(kuò)充后權(quán)重。

擴(kuò)充后權(quán)重是利用最大離差法計算數(shù)據(jù)對象擴(kuò)充后的屬性權(quán)重。最大離差法利用猶豫模糊元的邊界和內(nèi)部之間的差異計算屬性權(quán)重的方法。猶豫模糊元素的差異越大，說明屬性對聚類結(jié)果影響較大，應(yīng)該賦予較大的權(quán)重；猶豫元素差異越小，說明屬性對聚類結(jié)果影響較小，應(yīng)該賦予較小的權(quán)重。由此可知，屬性權(quán)重的選擇應(yīng)該盡可能地使屬性對所有對象的總偏差最大。根據(jù)此原則，構(gòu)造猶豫模糊環(huán)境中屬性權(quán)重的計算模型［26］，具體為：

構(gòu)建式（7）的拉格朗日函數(shù)，并求解得到：

3）綜合權(quán)重。

求解式（10），得到第個屬性的綜合權(quán)重：

則最小權(quán)重鑒別信息分布滿足

證明 取先驗權(quán)重分布與目標(biāo)權(quán)重分布之間的鑒別信息為目標(biāo)函數(shù)，以最小鑒別信息為準(zhǔn)則，則：

則有：

通過定理2可知，利用最小鑒別信息構(gòu)造的綜合權(quán)重，既能較好地反映擴(kuò)充前的信息量，又能客觀地反映擴(kuò)充后對信息量的影響。具體實現(xiàn)過程如算法2所示。

算法2 確定綜合權(quán)重算法。

for=1 todo

根據(jù)式（5）計算猶豫模糊熵

end for

for=1 todo

end for

for=1 todo

end for

2.4　聚類中心的構(gòu)造

根據(jù)平均算子原理，由多個數(shù)據(jù)對象形成簇心時，中心點的計算需要取遍所有集合的所有元素，是集合元素的全排列。中心點的猶豫度是所有集合猶豫度的乘積。隨著聚合對象的增多，計算簇心的時間復(fù)雜度將迅速增加，同時空間復(fù)雜度呈指數(shù)級增長，運算性能將大幅下降，極大程度上限制了算法的應(yīng)用。針對此問題，本文提出了猶豫度恒定的中心點構(gòu)造方法，主要步驟有：

構(gòu)造中心點的具體實現(xiàn)過程如算法3所示。

算法3 聚類中心的構(gòu)造算法。

4） 根據(jù)式（14）計算中間元素

5） 中間元素排序

repeat

for=todo

分別找出最大值和最小值對應(yīng)的下標(biāo)

end for

將最大值放在最后，最小值放在最前

until （<）

end for

2.5　AHCHF流程

算法4 AHCHF。

3） 聚類

repeat

根據(jù)式（4）計算各簇中心之間的加權(quán)距離

end for

=-1

3 實驗與結(jié)果分析

表1猶豫模糊對象集

Tab.1　Hesitant fuzzy object sets

為了計算猶豫模糊對象的加權(quán)距離，需要擴(kuò)充猶豫度小的數(shù)據(jù)對象。取猶豫模糊元素的平均值對它補充，擴(kuò)充后的猶豫模糊集如表2所示。

表2擴(kuò)充后的猶豫模糊對象集

Tab.2　Expanded hesitant fuzzy object sets

表3不同方法計算的屬性權(quán)重

Tab.3　Attribute weights calculated by different methods

表4猶豫模糊對象之間距離

Tab.4　Distance among hesitation fuzzy objects

表5不同算法的聚類結(jié)果對比

Tab.5　Comparison of clustering results by different algorithms

3.1　聚類結(jié)果分析

為了說明AHCHF的聚類效果，引入輪廓系數(shù)（Silhouette Coefficient， SC）評價指標(biāo)。SC值越大，聚類效果越好。

1）不同算法之間對比。

將本文提出的AHCHF與經(jīng)典的HFHC［17］和較新的層次聚類算法FHCA［21］進(jìn)行對比。當(dāng)猶豫度不相同時，HFHC和FHCA采用悲觀方法擴(kuò)充。結(jié)果如表5所示，對應(yīng)的輪廓系數(shù)如表6所示。

由表5可知，3種算法的聚類效果相似，僅有細(xì)小差異。當(dāng)聚成4類和5類時，AHCHF的聚類結(jié)果與FHCA的結(jié)果相同，與HFHC略有不同；當(dāng)聚成3類時，AHCHF聚類結(jié)果與HFHC的結(jié)果相同，與FHCA稍有不同。

由表6可知，AHCHF的輪廓系數(shù)均值最大，說明聚類效果整體最優(yōu)，相較于HFHC和FHCA，分別提升了23.99%和9.28%。導(dǎo)致聚類效果提升的原因有兩個：一是猶豫度采用不同的擴(kuò)充方式，HFHC和FHCA采用悲觀擴(kuò)充，而AHCHF采用平均值擴(kuò)充；二是采用的權(quán)重不同，HFHC取平均主觀權(quán)重，F(xiàn)HCA使用客觀權(quán)重，但它沒有考慮猶豫度擴(kuò)充后信息量的改變，而AHCHF采用綜合權(quán)重，結(jié)果更客觀合理。

2）不同擴(kuò)充方法之間對比。

表6不同算法的輪廓系數(shù)均值

Tab.6　Mean silhouette coefficients of different algorithms

表7本文算法在不同擴(kuò)充方法下的聚類結(jié)果對比

Tab.7　Comparison of clustering results by proposed algorithm under different expansion methods

表8本文算法在不同擴(kuò)充方法下的輪廓系數(shù)均值

Tab.8　Mean silhouette coefficients of proposed algorithm under different expansion methods

由表8可知，平均值擴(kuò)充下的輪廓系數(shù)均值最大，悲觀擴(kuò)充下的輪廓系數(shù)均值最小。3種擴(kuò)充方法的聚類效果不相同，導(dǎo)致不相同的原因是不同擴(kuò)充方法使猶豫模糊集的信息熵發(fā)生了不同程度信息失真：采用悲觀擴(kuò)充，擴(kuò)充前后的信息熵變化較大，信息失真較嚴(yán)重；采用樂觀擴(kuò)充，擴(kuò)充前后的信息熵變化較小，信息失真較輕；而采用平均值擴(kuò)充，擴(kuò)充前后的信息熵保持不變，信息未失真?？梢?，采用平均值擴(kuò)充得到的聚類結(jié)果更合理。

3.2　簇中心點的比較

表9不同算法的中心距離對比

Tab.9　Comparison of center distance of different algorithms

3.3　屬性權(quán)重分析

由表10可知，綜合權(quán)重與主觀權(quán)重2的結(jié)果完全相同，與主觀權(quán)重1和主觀權(quán)重3的結(jié)果有差異。在簇數(shù)為4時，綜合權(quán)重的結(jié)果與主觀權(quán)重3的結(jié)果不同。在簇數(shù)為3時，綜合權(quán)重的結(jié)果與主觀權(quán)重1和主觀權(quán)重3的結(jié)果均不同。

由表11可知，主觀權(quán)重2的輪廓系數(shù)均值最大，其次是綜合權(quán)重，說明兩種權(quán)重的聚類效果較好。主觀權(quán)重1和主觀權(quán)重3的輪廓系數(shù)均值較小，說明聚類效果也較差。導(dǎo)致聚類效果不同的原因是主觀權(quán)重1認(rèn)為每個屬性同等重要，每個屬性權(quán)重相等；事實上屬性之間存在差別，重要性必然各不相同。主觀權(quán)重3的第1個屬性的權(quán)重值過小，對加權(quán)距離產(chǎn)生較大影響，使得聚類結(jié)果發(fā)生了變化；而綜合權(quán)重既考慮了屬性之間的重要程度，又考慮了數(shù)據(jù)擴(kuò)充前后的變化情況，客觀性更強(qiáng)，聚類結(jié)果更合理。

表10不同權(quán)重下的聚類結(jié)果對比

Tab.10　Comparison of clustering results under different weights

表11不同權(quán)重下的輪廓系數(shù)均值

Tab.11　Mean silhouette coefficients under different weights

3.4　復(fù)雜度分析

為驗證AHCHF的實用性，從時間復(fù)雜度和空間復(fù)雜度進(jìn)行了分析。算法的測試環(huán)境為64位Windows 7操作系統(tǒng)，Intel core i7-6500 2.5 GHz，內(nèi)存為8 GB，測試平臺為C# 4.0開發(fā)平臺。

1）時間復(fù)雜度分析。

表12不同算法的聚類時間對比

Tab.12　Comparison of clustering time among different algorithms

由表12可知，在樣本數(shù)為10時，AHCHF相較于HFHC和FHCA，運行時間縮短了22.04%和4.17%；樣本數(shù)的增加到50時，運行時間縮短了34.59%和8.50%；平均縮短了27.18%和6.40%。隨著樣本數(shù)的增加，HFHC和FHCA的運行時間均高于AHCHF，主要原因是HFHC在合并對象后，新中心點的猶豫度呈指數(shù)級增長，計算中心點與其他對象的距離時需要擴(kuò)充猶豫度，導(dǎo)致程序頻繁申請和釋放空間，增加了時間消耗；同樣地，F(xiàn)HCA在計算中心點過程更繁瑣，在總體運行時間多于AHCHF。

2）空間復(fù)雜度分析。

由表13可知，在最好情況下，3種算法的空間復(fù)雜度相同；當(dāng)數(shù)據(jù)對象的猶豫度大于1時，F(xiàn)HCA與AHCHF呈線性增長，而HFHC呈指數(shù)級增長。

表13不同算法的空間復(fù)雜度對比

Tab.13　Comparison of spatial complexity among different algorithms

從上述時間復(fù)雜度和空間復(fù)雜度分析可知，AHCHF減少了聚類時間，并將空間的復(fù)雜度從指數(shù)級降低至線性級，較好地提升了聚類性能。

4 結(jié)語

猶豫模糊集能體現(xiàn)信息的模糊性和決策者的猶豫不決，使得它的層次聚類分析更適應(yīng)于現(xiàn)實場景。本文針對猶豫模糊聚類過程中存在的問題，提出了基于猶豫模糊集的凝聚式層次聚類算法（AHCHF）。該算法在保持信息熵不發(fā)生改變的情況下，采用猶豫模糊元的平均值擴(kuò)充猶豫度，并利用猶豫模糊元的熵和最大離差確定綜合客觀權(quán)重，既反映擴(kuò)充前的原始信息，又體現(xiàn)擴(kuò)充后數(shù)據(jù)狀態(tài)，然后優(yōu)化了聚類中心點的構(gòu)造方法。通過聚類效果、屬性權(quán)重、中心距離和聚類時間這4個指標(biāo)的對比實驗，結(jié)果表明，AHCHF可以有效解決信息失真、屬性權(quán)重客觀性差的問題，并提升聚類效果和聚類性能。

雖然AHCHF提升了猶豫模糊集的聚類性能，但仍存在以下不足：1）綜合權(quán)重過于客觀，沒有結(jié)合主觀權(quán)重，靈敏性不強(qiáng)；2）中心點構(gòu)造算法在處理大規(guī)模數(shù)據(jù)時的性能仍較低。以上不足是下一步工作重點；同時，進(jìn)一步降低復(fù)雜度、拓展算法的應(yīng)用領(lǐng)域也是今后努力的方向。

[1] 徐曉，丁世飛，丁玲.密度峰值聚類算法研究進(jìn)展［J］.軟件學(xué)報， 2022，33（5）：1800-1816.（XU X， DING S F， DING L. Survey on density peaks clustering Algorithm ［J］. Journal of Software， 2022， 33（5）： 1800-1816.）

[2] BALAKUMAR J， VIJAYARANI S. Text document clustering using artificial bee colony with bisecting-means algorithm［J］.International Journal of Advanced Research in Computer Science，2018，9（1）： 619-623.

[3] KARYPIS G， HAN E-H， KUMA R V. Chameleon： hierarchical clustering using dynamic modeling［J］. Computer， 1999， 32（8）： 68-75.

[4] SEGUNDO P S， RODRIGUEZ-LOSADA D. Robust global feature based data association with a sparse bit optimized maximum clique algorithm［J］. IEEE Transaction on Robotics， 2013， 29（5）： 1332-1339.

[5] ESTER M， KRIEGEL H P， SANDER， et al. A density-based algorithm for discovering clusters in large spatial databases with noise［C］// Proceeding of the 2nd International Conference on Knowledge Discovery and Data Mining. Portland： AAAI Press， 1996： 226-231.

[6] ZADEH L A. Fuzzy sets［J］. Information and Control， 1965， 8（3）： 338-353.

[7] ATANASSOV K T. Intuitionistic fuzzy sets［J］. Fuzzy Sets and Systems， 1986， 20（1）： 87-96.

[8] ZADEH L A. The concept of a linguistic variable and its application to approximate reasoning-Ⅱ ［J］. Information Sciences， 1975， 8（4）： 301-357.

[9] MENDEL J M. Uncertain Rule-based Fuzzy Logic System： Introduction and New Directions［M］. Upper Saddle River： Prentice-Hall， 2001： 56-57.

[10] DuBOIS D， PRADE H. Fuzzy Sets and Systems： Theory and Applications ［M］. Orlando： Academic Press， 1980： 35-37.

[11] DUNN J C. A fuzzy relative of the ISODATA process and its use in detecting compact well-separated clusters ［J］. Journal of Cybernetics， 1973， 3（3）： 32-57.

[12] 賀正洪，雷英杰.直覺模糊C-均值聚類算法研究［J］.控制與決策，2011，26（6）：847-850，856.（HE Z H， LEI Y J. Research on intuitionistic fuzzy C-means clustering algorithm［J］. Control and Decision， 2011， 26（6）： 847-850，856.）

[13] XIANG T， GONG S. Spectral clustering with eigenvector selection［J］. Pattern Recognition， 2008， 41（3）： 1012-1029.

[14] 劉怡俊，龍錦濤，楊曉君.基于多層二部圖的高光譜模糊聚類算法［J］.計算機(jī)應(yīng)用研究，2023，40（4）：1246-1249.（LIU Y J， LONG J T， YANG X J. Fuzzy clustering based on hierarchical bipartite graph for large scale hyperspectral image［J］. Application Research of Computers， 2022， 40（4）： 1246-1249.）

[15] 耿新青，王正歐.基于增量式模糊聚類算法的文本挖掘［J］.南京理工大學(xué)學(xué)報（自然科學(xué)版），2022，46（5）：579-585，593.（GENG X Q， WANG Z O. Text mining based on incremental fuzzy clustering algorithm［J］. Journal of Nanjing University of Science and Technology， 2022， 46（5）： 579-585， 593.）

[16] 徐曉，丁世飛，孫統(tǒng)風(fēng)，等.基于網(wǎng)格篩選的大規(guī)模密度峰值聚類算法［J］.計算機(jī)研究與發(fā)展，2018，55（11）：2419-2429.（XU X， DING S F， SUN T F， et al. Large-scale density peaks clustering algorithm based on grid screening［J］. Journal of Computer Research and Development， 2018， 55（11）： 2419-2429.）

[17] TORRA V. Hesitant fuzzy sets［J］. International Journal of Intelligent Systems， 2010， 25（6）： 529-539.

[18] XU Z， XIA M. Distance and similarity measures for hesitant fuzzy sets ［J］. Information Sciences， 2011， 18（11）： 2128-2138.

[19] CHEN N， XU Z S， XIA M M. Hierarchical hesitant fuzzy-means clustering algorithm［J］. Applied Mathematics， 2014， 29： 1-17.

[20] ZHANG X L， XU Z S. Hesitant fuzzy agglomerative hierarchical clustering algorithms［J］. International Journal of Systems Science， 2013， 46（3）： 562-576.

[21] 王志飛，陸億紅.凝聚中心猶豫度恒定的模糊層次聚類算法［J］.小型微型計算機(jī)系統(tǒng)，2021，42（1）：20-26.（WANG Z F， LU Y H. Fuzzy hierarchical clustering algorithm with constant hesitation of agglomeration center［J］. Journal of Chinese Computer Systems， 2021， 42（1）： 20-26.）

[22] 張煜，陸億紅，黃德才.基于密度峰值的加權(quán)猶豫模糊聚類算法［J］.計算機(jī)科學(xué)，2021，48（1）：145-151.（ZHANG Y， LU Y H， HUANG D C. Weighted hesitant fuzzy clustering based on density peaks［J］. Computer Science， 2021， 48（1）： 145-151.）

[23] 孫爽爽，黃德才，陸億紅.猶豫模糊數(shù)據(jù)對象集的譜聚類算法［J］.小型微型計算機(jī)系統(tǒng)，2023，44（2）：225-231.（SUN S S， HUANG D C， LU Y H. Spectral clustering algorithm for hesitating fuzzy data object set［J］. Journal of Chinese Computer Systems， 2023， 44（2）： 225-231.）

[24] 鄧小燕.猶豫模糊核C-均值聚類用于數(shù)據(jù)庫系統(tǒng)選擇［J］.控制工程，2020，27（1）：182-187.（DENG X Y. Hesitant fuzzy kernel C-means clustering for database system selection［J］. Control Engineering of China， 2020， 27（1）： 182-187.）

[25] 閆菲菲，魏翠萍，任智亮.猶豫模糊集的熵［J］.數(shù)學(xué)的實踐與認(rèn)識， 2018，48（14）：243-250.（YAN F F， WEI C P， REN Z L. Entropy measure for hesitant fuzzy sets［J］. Mathematics in Practice and Theory， 2018， 48（14）： 243-250.）

[26] XU Z， ZHANG X. Hesitant fuzzy multi-attribute decision making based on TOPSIS with incomplete weight information［J］. Knowledge-Based Systems， 2013， 52： 53-64.

Agglomerative hierarchical clustering algorithm based on hesitant fuzzy set

LI Wenquan*， MAO Yimin， PENG Xindong

（，，512005，）

Aiming at the problems of information distortion， poor objectivity of attribute weights， and high time complexity in hesitant fuzzy clustering analysis， an Agglomerative Hierarchical Clustering algorithm based on Hesitant Fuzzy set （AHCHF） was proposed. Firstly， the average value of hesitancy fuzzy elements was used to expand the data object with small hesitation. Secondly， the weights of data object before and after expansion were calculated by using the original information entropy and internal maximum difference， and the comprehensive attribute weight was determined according to the minimum discrimination information between the two weight vectors. Finally， with the goal of making the sum of weighted distances smaller， a center point construction method with constant hesitation was given. Experimental results on specific examples and synthetic datasets show that compared with the classic Hesitant Fuzzy Hierarchical Clustering algorithm （HFHC） and the recent Fuzzy Hierarchical Clustering Algorithm （FHCA）， the proposed AHCHF increases the mean Silhouette Coefficient （SC） by 23.99% and 9.28% respectively， and shortens the running time by 27.18% and 6.40% averagely and respectively， proving that the proposed algorithm can effectively solve the problems of information distortion and poor objectivity of attribute weights， and improve the clustering effect and performance well.

hesitant fuzzy set; clustering analysis; hesitation; data mining; fuzzy entropy

This work is partially supported by National Natural Science Foundation of China （62006155）， Scientific Research Project of Department of Education of Guangdong Province （2022ZDJS048）， Characteristic Innovation Project in Ordinary Universities in Guangdong Province （2023KTSCX137）.

LI Wenquan， born in 1980， M. S.， associate professor. His research interests include data mining， fuzzy mathematics.

MAO Yimin， born in 1970， Ph. D.， professor. Her research interests include data mining， big data security.

PENG Xindong， born in 1990， Ph. D.， associate professor. His research interests include fuzzy mathematics， artificial intelligence.

TP391.7

A

1001-9081（2023）12-3755-09

10.11772/j.issn.1001-9081.2023010094

2023?02?07；

2023?05?05；

2023?05?08。

國家自然科學(xué)基金資助項目（62006155）；廣東省教育廳科研項目（2022ZDJS048）；廣東省普通高校特色創(chuàng)新類項目（2023KTSCX137）。

李文全（1980—），男，江西龍南人，副教授，碩士，主要研究方向：數(shù)據(jù)挖掘、模糊數(shù)學(xué)；毛伊敏（1970—），女，新疆伊犁人，教授，博士，主要研究方向：數(shù)據(jù)挖掘、大數(shù)據(jù)安全；彭新東（1990—），男，江西九江人，副教授，博士，主要研究方向：模糊數(shù)學(xué)、人工智能。