基于半直覺模糊圖的兩種聚類分析算法

魚先鋒，萬世昌

（商洛學院數學與計算機應用學院，陜西商洛726000）

基于半直覺模糊圖的兩種聚類分析算法

魚先鋒，萬世昌

（商洛學院數學與計算機應用學院，陜西商洛726000）

給出了半直覺模糊圖傳遞閉包和最大生成樹的概念；提出了基于半直覺模糊圖傳遞閉包和最大相關樹的兩種聚類分析算法。討論了算法的合理性，分析了算法的復雜度。結合實例，用這兩種聚類分析算法做了基于半直覺模糊圖聚類分析。結果顯示算法合理高效。

半直覺模糊圖；傳遞閉包；最大生成樹；聚類分析

圖論將對象及對象間的聯系抽象成圖形，是分析解決實際問題的一種很有效的方法。如今圖論作為重要的數學工具已廣泛應用在計算機科學、信息論、控制論、系統科學等眾多領域。經典圖論只能用于刻畫對象間的確定關系；而現實世界中對象間很多關系都是不確定的。Zadeh提出了模糊集[1]用以表示對象間不確定的隸屬關系。Atanassov提出了直覺模糊集[2]，是對Zadeh模糊集最有影響的一種擴充和發展。Rosenfeid第一次提出了模糊圖的概念。在提出了若干模糊圖的相關概念及性質后，Rosenfeid初步建立了模糊圖論系統。然后Mordeson等[3-7]結合已有的模糊圖理論，給出了模糊圖之間的關系、模糊圖的補、模糊圖的最優路、強樹等相關的連通性質，以及其它性質及運算的研究；提出了完全模糊圖和正則模糊圖，及相應的運算性質。還有許多文獻也研究了模糊圖的相關性質與應用[8-10]。在文獻[11]建立了半直覺模糊圖模型，用頂點表示對象，用具有直覺模糊測度的邊刻畫對象之間的聯系。給出了半直覺模糊圖的生成子圖、度、路徑、相關截圖、無猶豫半直覺模糊圖及其序等概念。本文擬在文獻[11]基礎上給出半直覺模糊圖傳遞閉包和最大相關樹的概念，并在此基礎上給出通過先求半直覺模糊圖傳遞閉包和最大相關樹再求其相關截圖的方法來做聚類分析的兩種聚類算法，并對算法的復雜度作以分析。最后將結合經典實例作基于半直覺模糊圖的聚類分析。

1 半直覺模糊圖的相關理論

定義1～定義3是在文獻[11]中建立的半直覺模糊圖模型及在本文中將要用到的相關概念。

定義1半直覺模糊圖：半直覺模糊圖為直覺模糊關系集其中，

1）V={v1，v2，…，vn}為頂點之集，表示有限個對象；

半直覺模糊圖的邊集是直覺模糊關系，可以表示成n×n(n=|V|)的一個直覺模糊矩陣，。這樣以來半直覺模糊圖就可以用來表示了。

定義2半直覺模糊圖子圖：設，為半直覺模糊圖，

2）V1′，V2′?V，且V1′∩V2′=φ，稱是的連通分量；

定義3半直覺模糊圖的截圖：設為一個半直覺模糊圖，對?p，q，0≤p，q≤1且p+q≤1，

定義4半直覺模糊圖的性質：在半直覺模糊圖中

一般對象間的相關性是相互的，即eij=(vi，vj)=eji所以半直覺模糊圖的邊集一般是一個對稱關系，?vi，vj∈V只定義無向邊eij即可。另外?vi∈V被認為每個對象與自身是完全相關的即eii=(vi，vi)=(1，0)。可見，一般的直覺模糊關系就是一個滿足自反性和對稱性的直覺模糊關系。就是直覺模糊相似矩陣[12]。

定義6直覺模糊關系的冪：為直覺模糊矩陣，定義的冪，其中m∈N+，并規定為n元直覺模糊單位陣。

定義7半直覺模糊圖的傳遞閉包：設為半直覺模糊圖，為直覺模糊關系的傳遞閉包，則稱半直覺模糊圖為的傳遞閉包。

定義8半直覺模糊圖的序：為一個半直覺模糊圖，，，若μ1=μ2且λ1=λ2，則稱e1等于e2記作e1=e2；否則，

1）若d＞0則稱e1相關大于或不相關小于e2記作e1?e2。

2）若d＜0則稱e1相關小于或不相關大于e2記作e1?e2。

定義半直覺模糊圖的序是為了求最大相關樹時任意兩條邊可以排序。

定義9半直覺模糊圖最大相關樹：設為半直覺模糊圖，若滿足，

定義9是將經典圖論中圖的最小生成樹的定義擴展到半直覺模糊圖中。

2 基于半直覺模糊圖的聚類分析

相似度和相異度是現實世界中對象間最主要的關聯屬性之一。將對象作為頂點集，將對象間的相似度作為相關度，相異度作為不相關度，就可以很自然的用半直覺模糊圖刻畫對象間的相似度和相異度。相似度和相異度主要應用是聚類分析、目標識別[12-17]。對象分類是研究對象屬性和性質的最基本的一種方法。聚類分析的基本原理是定義對象間的相似度或相異度，然后將對象按相似度由大到小，或按相異度由小到大不斷聚合到不同類型中。下面給出基于基于半直覺模糊圖的兩種聚類分析算法。

2.1 基于半直覺模糊圖傳遞閉包的聚類分析算法

定理1在半直覺模糊圖的傳遞閉包中，邊集是一個等價直覺模糊關系。

定理1的證明見文獻[15]。

定理2聚類分析結果一般包含多個連通分量，連通分量的個數為對象集V={v1，v2，…，vn}中所有對象在相關水平(p，q)下的分類類型數；在的同一連通分量中的頂點屬于同一種類型。

定理3基于半直覺模糊圖傳遞閉包圖的聚類分析算法的空間復雜度為o(n3)，時間復雜度為o(n4)。

證明：算法的主要空間和時間開銷來自于求半直覺模糊圖傳遞閉包圖。存儲需要開辟n個規模為n×n的二維數組空間，故空間復雜度為o(n3)。根據定義5一次直覺模糊關系合成需要求n×n個直覺模糊數。求一個直覺模糊數要計算，需要做2n次max-min運算，所以一次直覺模糊關系合成的時間復雜度為o(n3)。而通常求直覺模糊傳遞閉包圖要做n次直覺模糊關系合成求得，。

所以基于半直覺模糊圖傳遞閉包圖的聚類分析算法的時間復雜度為o(n4)。

2.2 基于半直覺模糊圖最大相關樹的聚類分析算法

定理4基于半直覺模糊圖最大生成樹的聚類分析算法第2）步計算結果是的最大相關生成樹。

基于半直覺模糊圖最大生成樹的聚類分析算法第2）步計算過程實際上是在Kruskal算法（經典圖的最小生成樹算法）基礎上，稍加改動。區別一是對邊排序是按定義3中給出的序關系比較大小的；二是最大生成樹的邊是按由大到小的順序添加的。其他步驟算法基本原理是一樣的。

定理5基于半直覺模糊圖最大生成樹的聚類分析結果一般包含多個連通分量，連通分量的個數為對象集V={v1，v2，…，vn}中所有對象在相關水平(p，q)下的分類類型數；在的同一連通分量中的頂點屬于同一種類型。

定理6基于半直覺模糊圖最大生成樹的聚類分析算法的空間復雜度為o(n2)，時間復雜度為o(n2log2n)。

證明：算法的輸入為半直覺模糊圖；其頂點集和直覺模糊相似矩陣空間復雜度為o(n)和o(n2)。中間計算結果和算法最后輸出結果都為初始半直覺模糊圖的子圖，空間復雜度不超過o(n2)；所以整個計算過程的空間復雜度為o(n2)。

用冒泡、選擇、交換、插入排序法復雜度為o((n2)2)=o(n4)。其他計算的時間復雜度都與的規模相同為o(n2)。所以整個計算過程的時間復雜度為o(n2log2n)。

2.3 應用實例

某手機市場欲對5種不同的手機v1，v2，v3，v4，v5進行分類，每部手機有6個可供評價的因素：硬件功能(G1)，待機時間(G2)，價格(G3)，運行速度(G4)，設計外觀(G5)，安全性(G6)．每部手機在各評價因素（屬性）下的特征信息用直覺模糊數表示，見表1。

表1 手機的直覺模糊屬性特征值

用文獻[16]中給出的計算相似度的公式，

和文獻[17]中給出的計算相異度的公式，

分別計算相似度和相異度作為手機Ai與Aj間的相關度(μij，γij)。為計算方便取p=1，用式(1)和式(2)求得手機間的直覺模糊相關矩陣為，

將手機之集做頂點集V={v1，v2，…，vn}，直覺模糊相似矩陣做邊集，可得到半直覺模糊圖。分別用基于求半直覺模糊圖傳遞閉包圖和最大生成樹的兩種聚類分析算法對進行分類。

如法炮制，取置信水平(0.45，0.45)會將手機分作2類{v1，v3，v4，v5}，{v2}；取置信水平(0.57，0)會將手機分作4類{v1，v5}，{v2}，{v3}，{v4}；取置信水平(p，q)＞(0.57，0)會將手機分作5類{v1}，{v2}，{v3}，{v4}，{v5}。再求的最大生成樹得到，所示。當取置信水平，(0.45，0.47)會將手機分作1類{v1，v2，v3，v4，v5},如圖2所示；取置信水平(0.45，0.45)會將手機分作2類{v1，v3，v4，v5}，{v2}如圖2所示；取置信水平(0.47，0.44)會將手機分作3類{v1，v5}，{v3，v4}，{v2}。如圖3所示；取置信水平(0.57，0.33)會將手機分作4類{v1，v5}，{v2}，{v3}，{v4}如圖4所示；取置信水平(p，q)＞(0.57，0.33)會將手機分作5類，{v1}，{v2}，{v3}，{v4}，{v5}。

圖1 最大生成樹

圖2 置信水平(0.45，0.45)下分類結果

圖3 置信水平(0.47，0.44)下分類結果

圖4 置信水平(0.57，0.33)下分類結果

兩種聚類分析算法分類結果一致；也與預設之手機類型結果一致。基于半直覺模糊圖傳遞閉包和最大生成樹的兩種聚類分析算法都是合理有效的。

3 結語

討論了半直覺模糊圖的自反性、對稱性和傳遞性。定義了半直覺模糊圖的合成運算和冪運算。進而給出了半直覺模糊圖傳遞閉包的定義。定義了半直覺模糊圖相關邊的序關系將經典圖論中圖的最小生成樹的定義擴展到半直覺模糊圖中給出了半直覺模糊圖最大生成樹的概念。提出了基于半直覺模糊圖傳遞閉包和最大相關樹的兩種聚類分析算法。討論了算法的合理性；分析了算法的復雜度。結合實例用這兩種聚類分析算法做了基于半直覺模糊圖聚類分析。結果顯示此兩種聚類分析算法聚類結果一致，并與預設分類結果一致，算法合理高效。

[1]ATANASSOV K．Intujtionistic Fuzzy sets[J].Fuzzy Sets And System,1986(1)：87-96．

[2]ZADEH L A.Fuzzy Sets[J].Information and Control,1965,8：338-353．

[3]CERRUTI U.Graphs and fuzzy graphs[C].New York：Fuzzy Inform ation and Decision Processes,1982：123-l31．

[4]TALAL AL H.Complete fuzzy graphs[J].International Journal of Mathematical Combinatonics,2011,4：26-34．

[5]MORDESON J N,NAIR P S.Cycles and cocycles of fuzzy graphs[J].Inform Sci,1996(90)：39-49．

[6]MORDESON J N，NAIR P S．Fuzzy graphs and fuzzy hypergraphs[M].New York：Physica Verlag,2000．

[7]E1GHOUL M.Folding of fuzzy graphs and fuzzy spheres[J].Fuzzy Sets and Systems,1993(58)：355-363．

[8]趙學靖,蘇錦霞,楊鳳翔.模糊圖在生物群落聚類中的應用[J].蘭州大學學報(自然科學版),2001,37(1)：14-18.

[9]廖麗平,胡仁杰.基于模糊圖的模糊社會網絡定義及其性質分析[J]．廣西工業大學學報,2012,12(3)：14-18.

[10]楊文華,李生剛.區間值模糊圖的運算性質[J].模糊系統與數學,2013,27(2)：127-135．

[11]魚先鋒.半直覺模糊圖與應用[J].計算機工程與應用,2016,52(18)：88-91.

[12]張洪美,徐澤水,陳琦.直覺模糊集的聚類方法研究[J].控制與決策,2007,22(8)：882-888．

[13]賀正洪,雷英杰,王剛.基于直覺模糊聚類的目標識別[J].系統工程與電子技術,2011,33(6)：1283-1288.

[14]劉鎖蘭,王江濤,王建國,等.一種新的基于圖論聚類的分割算[J].計算機科學,2008,25(9)：245-247.

[15]ZHAO F X，MA Z M，YAN L．Fuzzy clustering based on vague relations[C]∥Proc．of the Fuzzy Systems and Knowledge Discovery,2006：79-88．

[16]LIU W．New similarity measures between intuitionistic fuzzy sets and between elements[J].Mathematical and Computer Modelling,2005,42(1-2)：61-70．

[17]LID F．Some measures of dissimilarity in intuitionistic fuzzy structures[J].Journal of Computerand System Sciences,2004,68(1)：115-122．

（責任編輯：李堆淑）

Two Kinds of Clustering Analysis Algorithm Based on Half Intuitionistic Fuzzy Graph

YU Xian-feng,WAN Shi-chang
(School of Mathematics and Computer Application，Shangluo University，Shangluo 726000,Shaanxi)

The definition of transitive closure and maximum spanning tree of a half intuitionistic fuzzy graph is given.And then two kinds of clustering analysis algorithm are proposed based on transitive closure and maximum spanning tree of a half intuitionistic fuzzy graph.The rationality of the algorithms are discussed,and their complexity are analyzed.Combining with an example,we use the two clustering analysis algorithms for clustering analysis based on half intuitionistic fuzzy graph.The clustering analysis results show that the algorithm is reasonable and efficient.

half intuitionistic fuzzy graph;transitive closure;maximum spanning tree;clustering analysis

TP301.2

：A

：1674-0033（2017）04-0001-06

10.13440/j.slxy.1674-0033.2017.04.001

2017-05-12

陜西省教育廳專項科研計劃項目（16JK1236）

魚先鋒，男，陜西商州人，碩士，講師