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

李文全，毛伊敏，彭新東

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

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

（韶關學院 信息工程學院，廣東 韶關 512005）（?通信作者電子郵箱78192128@qq.com）

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

猶豫模糊集；聚類分析；猶豫度；數據挖掘；模糊熵

0 引言

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

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

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

1）猶豫度擴充導致信息失真。在猶豫模糊元運算時，需要取最大元或最小元擴充猶豫度小的數據對象，擴充后會使原有信息量發生改變，導致信息失真。

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

3）新類中心點的構造性能不理想。采用平均算子構造中心點，時間復雜度高且空間復雜度呈指數級增長，嚴重影響算法性能。

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

本文的主要工作如下：

1）提出保持信息熵不發生改變的猶豫度擴充方法。采用猶豫模糊元的平均值擴充猶豫度小的數據對象，避免猶豫度擴充導致信息失真。

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

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

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

1 相關工作

2 AHCHF

2.1　算法思想

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

2.2　猶豫度的擴充

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

綜上，由于得分函數與離差度都沒有發生改變，則有：

依據定理1，猶豫度擴充的主要步驟如下：

算法1 猶豫度擴充算法。

1） 初始化數據：

for=1 todo

找出當前屬性下的最大猶豫度

end for

2） 元素排序：

repeat

for=todo

分別找出最大值和最小值下標

end for

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

until（<）

for=1 todo

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

end for

2.3　屬性權重的確定

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

1）原始權重。

2）擴充后權重。

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

構建式（7）的拉格朗日函數，并求解得到：

3）綜合權重。

求解式（10），得到第個屬性的綜合權重：

則最小權重鑒別信息分布滿足

證明 取先驗權重分布與目標權重分布之間的鑒別信息為目標函數，以最小鑒別信息為準則，則：

則有：

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

算法2 確定綜合權重算法。

for=1 todo

根據式（5）計算猶豫模糊熵

end for

for=1 todo

end for

for=1 todo

end for

2.4　聚類中心的構造

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

構造中心點的具體實現過程如算法3所示。

算法3 聚類中心的構造算法。

4） 根據式（14）計算中間元素

5） 中間元素排序

repeat

for=todo

分別找出最大值和最小值對應的下標

end for

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

until （<）

end for

2.5　AHCHF流程

算法4 AHCHF。

3） 聚類

repeat

根據式（4）計算各簇中心之間的加權距離

end for

=-1

3 實驗與結果分析

表1猶豫模糊對象集

Tab.1　Hesitant fuzzy object sets

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

表2擴充后的猶豫模糊對象集

Tab.2　Expanded hesitant fuzzy object sets

表3不同方法計算的屬性權重

Tab.3　Attribute weights calculated by different methods

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

Tab.4　Distance among hesitation fuzzy objects

表5不同算法的聚類結果對比

Tab.5　Comparison of clustering results by different algorithms

3.1　聚類結果分析

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

1）不同算法之間對比。

將本文提出的AHCHF與經典的HFHC［17］和較新的層次聚類算法FHCA［21］進行對比。當猶豫度不相同時，HFHC和FHCA采用悲觀方法擴充。結果如表5所示，對應的輪廓系數如表6所示。

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

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

2）不同擴充方法之間對比。

表6不同算法的輪廓系數均值

Tab.6　Mean silhouette coefficients of different algorithms

表7本文算法在不同擴充方法下的聚類結果對比

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

表8本文算法在不同擴充方法下的輪廓系數均值

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

由表8可知，平均值擴充下的輪廓系數均值最大，悲觀擴充下的輪廓系數均值最小。3種擴充方法的聚類效果不相同，導致不相同的原因是不同擴充方法使猶豫模糊集的信息熵發生了不同程度信息失真：采用悲觀擴充，擴充前后的信息熵變化較大，信息失真較嚴重；采用樂觀擴充，擴充前后的信息熵變化較小，信息失真較輕；而采用平均值擴充，擴充前后的信息熵保持不變，信息未失真。可見，采用平均值擴充得到的聚類結果更合理。

3.2　簇中心點的比較

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

Tab.9　Comparison of center distance of different algorithms

3.3　屬性權重分析

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

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

表10不同權重下的聚類結果對比

Tab.10　Comparison of clustering results under different weights

表11不同權重下的輪廓系數均值

Tab.11　Mean silhouette coefficients under different weights

3.4　復雜度分析

為驗證AHCHF的實用性，從時間復雜度和空間復雜度進行了分析。算法的測試環境為64位Windows 7操作系統，Intel core i7-6500 2.5 GHz，內存為8 GB，測試平臺為C# 4.0開發平臺。

1）時間復雜度分析。

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

Tab.12　Comparison of clustering time among different algorithms

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

2）空間復雜度分析。

由表13可知，在最好情況下，3種算法的空間復雜度相同；當數據對象的猶豫度大于1時，FHCA與AHCHF呈線性增長，而HFHC呈指數級增長。

表13不同算法的空間復雜度對比

Tab.13　Comparison of spatial complexity among different algorithms

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

4 結語

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

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

[1] 徐曉，丁世飛，丁玲.密度峰值聚類算法研究進展［J］.軟件學報， 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］.計算機應用研究，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］.南京理工大學學報（自然科學版），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] 徐曉，丁世飛，孫統風，等.基于網格篩選的大規模密度峰值聚類算法［J］.計算機研究與發展，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］.小型微型計算機系統，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] 張煜，陸億紅，黃德才.基于密度峰值的加權猶豫模糊聚類算法［J］.計算機科學，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] 孫爽爽，黃德才，陸億紅.猶豫模糊數據對象集的譜聚類算法［J］.小型微型計算機系統，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-均值聚類用于數據庫系統選擇［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］.數學的實踐與認識， 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。

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

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