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

魚先鋒，萬世昌

（商洛學(xué)院數(shù)學(xué)與計算機應(yīng)用學(xué)院，陜西商洛726000）

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

魚先鋒，萬世昌

（商洛學(xué)院數(shù)學(xué)與計算機應(yīng)用學(xué)院，陜西商洛726000）

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

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

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

1 半直覺模糊圖的相關(guān)理論

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

定義1半直覺模糊圖：半直覺模糊圖為直覺模糊關(guān)系集其中，

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

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

定義2半直覺模糊圖子圖：設(shè)，為半直覺模糊圖，

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

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

定義4半直覺模糊圖的性質(zhì)：在半直覺模糊圖中

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

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

定義7半直覺模糊圖的傳遞閉包：設(shè)為半直覺模糊圖，為直覺模糊關(guān)系的傳遞閉包，則稱半直覺模糊圖為的傳遞閉包。

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

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

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

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

定義9半直覺模糊圖最大相關(guān)樹：設(shè)為半直覺模糊圖，若滿足，

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.3 應(yīng)用實例

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

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

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

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

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

將手機之集做頂點集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}。再求的最大生成樹得到，所示。當(dāng)取置信水平，(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)下分類結(jié)果

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

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

兩種聚類分析算法分類結(jié)果一致；也與預(yù)設(shè)之手機類型結(jié)果一致?；诎胫庇X模糊圖傳遞閉包和最大生成樹的兩種聚類分析算法都是合理有效的。

3 結(jié)語

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

[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]趙學(xué)靖,蘇錦霞,楊鳳翔.模糊圖在生物群落聚類中的應(yīng)用[J].蘭州大學(xué)學(xué)報(自然科學(xué)版),2001,37(1)：14-18.

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

[10]楊文華,李生剛.區(qū)間值模糊圖的運算性質(zhì)[J].模糊系統(tǒng)與數(shù)學(xué),2013,27(2)：127-135．

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

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

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

[14]劉鎖蘭,王江濤,王建國,等.一種新的基于圖論聚類的分割算[J].計算機科學(xué),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．

（責(zé)任編輯：李堆淑）

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）

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