1、第22卷第6期吉林大學(xué)學(xué)報(信息科學(xué)版V ol.22No.6 2004年11月Journal of Jilin University(Information Science EditionNov.2004文章編號:1671-5896(200406-0643-05基于模糊聚類和信息熵的綜合評價算法張運凱1,王方偉1,戴敬書2,黃文艷3,陳艷紅4(1.河北師范大學(xué)網(wǎng)絡(luò)中心,河北石家莊050016;2.河北電視臺新聞中心,河北石家莊050031;3.河北師范大學(xué)數(shù)學(xué)與信息學(xué)院,河北石家莊050016;4.秦皇島外國語職業(yè)學(xué)院,河北秦皇島066311摘要:針對目前綜合評價技術(shù)存在的主旨不相協(xié)調(diào)、忽略了

2、簡潔性與有效性問題,在分析已有算法的基礎(chǔ)上,提出了一種基于模糊聚類和信息熵的綜合評價算法,該算法有針對性地克服了原有評價算法的缺陷,具有較好的實用性,最后通過實際數(shù)據(jù)對該算法的有效性進行了驗證。關(guān)鍵詞:模糊聚類;信息熵;綜合評價中圖分類號:TP312文獻標(biāo)識碼:ANew comprehensive evaluation algorithm based on fuzzyclustering and information entropyZH ANG Yun-kai1,W ANG Fang-wei1,DAI Jing-shu2,HUANG Wen-yan3,CHEN Yan-hong4(1.Net

3、work Center Hebei Normal Univers ity,Shijiazhuang050016,China;2.News Center,Hebei Television Station,Shijiaz huang050031,China;3.College of Mathe matics and Infor mation Science,Hebei Normal Univers ity,Shijiazhuang050016,China;4.QingHuangDao Foreign Language Professional Coll ege,Qinghuangdao066311

4、,ChinaA bstract:Aims at inc onsistent leitmotiv in current comprehensive evaluation technology,neglects the pr oblem of suc-cinctness and validity,analyzes the ago algorithms in the foundation,propases a comprehensive evaluation algovithm based on fuzzy dustering and information entropy.This algorit

5、hm hurdles flaws of original algorithms,has a good prac-ticabitity.The validity of this algorithm has been validated through the actual data.Keywords:fuzzy clustering;information entropy;comprehensive evaluatio引言評價是隨著人類社會活動的發(fā)展而產(chǎn)生的。為了進行管理,就要進行一系列的評價。評價活動廣泛存在于社會生活的各個領(lǐng)域。如教師授課績效考核、員工工作能力的考核等。長期以來,評價主要是依

6、靠人的經(jīng)驗,屬于經(jīng)驗評價范疇。單憑個人的知識、經(jīng)驗、智慧和膽略來做評價難免出現(xiàn)重大失誤,這主要由于同一事物具有多種屬性,受到多種因素的影響。其次,隨著科學(xué)技術(shù)的不斷深化,研究的對象越來越復(fù)雜,而復(fù)雜的東西難以精確表示。為了能客觀公正地對事物進行評價,出現(xiàn)了模糊綜合評價方法。很多學(xué)者對此進行了深入研究,提出了一些方法13。但是現(xiàn)在綜合評價技術(shù)還存在下面主要問題:存在一種與綜合評價主旨不相協(xié)調(diào)的傾向,人們似乎比較關(guān)心評價方法的復(fù)雜性而忽略了簡潔性與有效性,盲目追求數(shù)學(xué)方法形式的復(fù)雜性,有意無意的將評價方法的復(fù)雜性和評價方法的有效性混為一談。為此,筆者提出一個基于模糊聚類和信息熵的綜合評價算法,該算

7、法具有操作簡單、易于實現(xiàn)和良好實用性的特點。收稿日期:2004-02-12作者簡介:張運凱(1965,男,河北望都人,河北師范大學(xué)副教授,主要從事計算機網(wǎng)絡(luò)研究,Tel:86-311-6268469,E-mail: zhyk。1改進后的綜合評價算法1.1模糊聚類和信息熵傳統(tǒng)的聚類分析是一種硬劃分,它把每個待辨識的對象嚴格地劃分到某個類中,具有非此即彼的性質(zhì),因此這種分類的類別界限是分明的。而實際上大多數(shù)對象并沒有嚴格區(qū)分的屬性,它們在形態(tài)和類屬方面存在著中介性,適合進行軟劃分。Zadeh 4提出的模糊集理論為這種軟劃分提供了有力的分析工具,人們開始用模糊的方法來處理聚類問題,并稱之為模糊聚類分

8、析。由于模糊聚類能表示樣本類屬的中介性,即建立起了樣本對于類別不確定性的描述,從而能更客觀地反映現(xiàn)實世界,從而成為聚類分析研究的主流。模糊劃分的概念最早由Ruspini 5提出,利用這一概念人們提出了多種聚類方法,比較典型的有:基于相似性關(guān)系和模糊關(guān)系的方法6、基于模糊等價關(guān)系的傳遞閉包方法7、基于模糊圖論最大樹方法8等。然而由于上述方法不適用于大數(shù)據(jù)量情況,難以滿足實時性要求高的場合,因此其實際的應(yīng)用領(lǐng)域狹小。文獻9用模糊集來劃分邊界,并提出數(shù)量型屬性模糊關(guān)聯(lián)規(guī)則的概念,但沒有給出相應(yīng)的算法。實際中受到普遍歡迎的是基于目標(biāo)函數(shù)的方法,該方法設(shè)計簡單、解決問題的范圍廣,最終還可以轉(zhuǎn)化為優(yōu)化問題

9、而借助經(jīng)典數(shù)學(xué)的非線性規(guī)劃理論求解,并易于計算機實現(xiàn)。因此,該類方法成為聚類研究的熱點。在模糊聚類的具體應(yīng)用過程中,認為被分類對象集合X 中的樣本x i ,i =1,2,n ,以一定的隸屬度隸屬于某一類,也就是說,所有的樣本都分別以不同的隸屬度隸屬于某一類。因此,每一類認為是樣本集合X 上的一個模糊子集,每種這樣的分類結(jié)果所對應(yīng)的分類矩陣R ,就是一個模糊矩陣。該分類矩陣滿足下列3個條件:1r ij 0,1,即分類矩陣元素在0和1之間取值;2ci =1r i j =1,即每列中分別屬于各類的隸屬度之和為1,對一個樣本而言,它對各類的隸屬度之和為1;3nj =1r i j >0,即每行的元

10、素之和大于0,這保證了每類都必須有樣本。模糊聚類的主要算法有模糊等價矩陣法、模糊I SODATA 聚類分析法等。按照人們的常識:小概率事件所蘊含的信息量較大;就隨機性而言,基本事件個數(shù)相同者,以等概率分布場平均信息量大。上面的表述只是從定性的角度對信息進行了描述,在處理相關(guān)信息時沒有任何信息的損失,但該方法不能提供基于對象的各因素的重要性大小,所以還需要提供先驗的權(quán)重分配,必須借助于熵的概念,才能定量表達,熵是描述信息不確定性的度量。設(shè)X 是取有限個值的隨機變量,p i =P X =x i ,i =1,2,n ,則X 的熵定義為H (X =ni =1p i log a1p i其中,底數(shù)a 為任

11、何正數(shù),并規(guī)定當(dāng)p i =0時,p i log a1p i=0。上述表達式即為Shannon 信息熵表達式。由此可見,信息熵是由事物內(nèi)部屬性客觀決定的,如果能夠用信息熵來確定權(quán)重,則能夠保證權(quán)重的客觀性。關(guān)于信息熵對確定權(quán)重的意義詳見文獻10,11。1.2算法的具體實現(xiàn)1.2.1經(jīng)典模糊聚類的改進對目標(biāo)函數(shù)的改進主要是在目標(biāo)函數(shù)中引入權(quán)重,使目標(biāo)函數(shù)能反映事物屬性之間的輕重關(guān)系J (R ,V =n j =1ci =1r qi j d 2ij 其中 =(w 1,w 2,w m 644吉林大學(xué)學(xué)報(信息科學(xué)版第22卷1.2.2算法的具體步驟1據(jù)標(biāo)準化處理,這里采用極大值標(biāo)準化處理方法。2確定評價因

12、素的權(quán)重系數(shù),形成權(quán)重向量。3對待評價對象的集合進行聚類。a 用閾值矩陣法對所有樣本進行大致的分類:固定c 值,將所有樣本進行初始化,c 即為評價結(jié)果論域中元素的個數(shù);構(gòu)造相似矩陣R =(r i j H H ,i =1,2,H ,j =1,2,H ,表示樣本i 與樣本j 的相似程度。樣本之間相似程度可以用相似系數(shù)法、距離法和貼近度法來表示,這里選取貼近度法r i j =mk =1(x i k x jk /mk =1(x ik x jk 求出等價關(guān)系R *。通過平方計算法可以快速求得R *。依次求得R 2,R 4,R 8,R 2k,直到R 2k=R2k -1,則有R *=R 2k。采用截集矩陣法

13、進行分類。是R *中的隸屬度,選擇不同的隸屬度使樣本分為不同的c 類。b 在大致分類基礎(chǔ)上,進行精確分類:對求得的分類采用平均值法計算出初始的聚類中心(V 01,V 02,V 0c ;根據(jù)公式對聚類中心進行修正;若滿足結(jié)束條件,則迭代結(jié)束,否則回到。2算法的分析與驗證該算法以綜合評價工作的本質(zhì)要求為突破點,根據(jù)綜合評價工作的具體特點,采用了改進后的模糊聚類方法;針對模糊聚類與綜合評價工作的不同,在算法中引入了由信息熵得到的權(quán)重向量,從而保證了算法的有效。筆者以1997年中國經(jīng)濟統(tǒng)計年鑒提供的統(tǒng)計數(shù)據(jù)為基礎(chǔ),采用基于模糊聚類和信息熵的綜合評價算法對6個城市的經(jīng)濟指標(biāo)進行綜合評測。已知決策對象集A

14、 =a 1,a 2,a 3,a 4,a 5,a 6,分別為石家莊、蘇州、武漢、烏魯木齊、蘭州、呼和浩特;指標(biāo)集Z =z 1,z 2,z 3,z 10,其中,z -1表示土地面積,z 2表示年末總?cè)丝?z 10,表示職工平均工資,具體數(shù)據(jù)詳見表1。表11997年全國6市主要經(jīng)濟指標(biāo)Tab .1The main economic targets of six cities in 1997城市名稱土地面積/km2年末總?cè)丝?萬人國民生產(chǎn)總值/萬元人均生產(chǎn)總值/元實現(xiàn)利稅總額/萬元固定資產(chǎn)投資完成額/萬元出口總值/萬美元實際利用外資/萬美元財政總收入/萬元職工均工資/元石家莊15848860.1978

15、1399891146529942981487125998291933842116256蘭州13086280.462436800875716247410364863500087862319576578烏魯木齊12000151.942169045144681115288992543699024654002767702武漢8467723.90912325612673640502408179794109453338541986406呼和浩特17224200.371287130647282713265964387930301539275195蘇州8488574.991132594119713116756

16、5405176050439024472376538484431專家調(diào)查法得到的權(quán)重向量為0.2,0.1,0.05,0.05,0.2,0.05,0.15,0.15,0.05,0.05,由此6城市經(jīng)濟發(fā)展水平排行為:蘇州、石家莊、武漢、蘭州、烏魯木齊、呼和浩特;2由比較矩陣法得到的權(quán)重向量為0.15,0.05,0.1,0.05,0.15,0.1,0.1,0.2,0.05,0.05,由此6個城市經(jīng)濟發(fā)展水平排行為:蘇州、武漢、石家莊、蘭州、烏魯木齊、呼和浩特;3由Delphi 方法得到的權(quán)重向量為0.17,0.05,0.1,0.03,0.15,0.1,0.1,0.2,0.05,0.05,由此6個城市

17、經(jīng)濟發(fā)展水平排行為:蘇州、武漢、石家莊、蘭州、烏魯木齊、呼和浩特;4由信息熵理論得到的權(quán)重向量為0.017,0.05,0.06,0.03,0.17,0.18,0.23,0.21,0.043,0.01。1997年中國縣域經(jīng)濟基本競爭力評價中心對這6個城市的經(jīng)濟發(fā)展水平的排行為:蘇州、武漢、石家莊、烏魯木齊、蘭州、呼和浩特。通過和上面幾種方法的計算結(jié)果比較,可以看出,多少都存在一645第6期張運凱,等:基于模糊聚類和信息熵的綜合評價算法定出入:專家調(diào)查法得到的6個城市的排行中,發(fā)生了兩對錯誤,即武漢和石家莊以及烏魯木齊和蘭州,可見該方法的實用性具有一定的局限性;比較矩陣法和Delphi 法由于對專

18、家的調(diào)查信息作了一定的數(shù)學(xué)處理,在對6個城市的排行中只發(fā)生了一對錯誤,即蘭州和烏魯木齊。而本算法將城市的經(jīng)濟發(fā)展水平分為3類:高、中、低,求得聚類的中心;根據(jù)上述6個城市與聚類中心的距離計算各個城市所屬的類別,可以求得蘇州的經(jīng)濟發(fā)展水平為“高”;武漢和石家莊的經(jīng)濟發(fā)展水平為:“中”;而烏魯木齊、蘭州和呼和浩特的經(jīng)濟發(fā)展水平為“低”;為了進一步區(qū)分,將武漢和石家莊到經(jīng)濟發(fā)展水平“中”的距離歸一化,分別為:1和0.9166。烏魯木齊、蘭州和呼和浩特相應(yīng)距離歸一化為:1,0.9421和0.74444;綜上所述,6個城市的排行為:蘇州、武漢、石家莊、烏魯木齊、蘭州、呼和浩特。這個結(jié)果與“中國縣域經(jīng)濟網(wǎng)

19、”(www .china -county .or g 的評價結(jié)果一致。3應(yīng)用實例教師素質(zhì)評測系統(tǒng)對學(xué)校而言,教師對學(xué)校教學(xué)水平的提高起了極其重要的作用。如何公正、科學(xué)的評價一個教師的圖1教師素質(zhì)評價的因素Fig .1The factors of the teach ability evaluating system綜合素質(zhì),調(diào)動他們工作的積極性,對提高學(xué)校的教學(xué)水平乃至整個國家的教育水平都十分重要。該系統(tǒng)是模糊綜合評價系統(tǒng)平臺的一個實例,主要側(cè)重于定量指標(biāo)。教師綜合素質(zhì)評測的評測體系包括以下4個模塊:信息采集、信息管理、系統(tǒng)維護、系統(tǒng)幫助。其中信息管理包括信息查詢、信息統(tǒng)計、信息評價,信息評價

20、是本系統(tǒng)的核心部分。由于教師職業(yè)的基本特點是勞動者與勞動工具二者的統(tǒng)一,所以教師素質(zhì)有以下幾個特點:全面性、示范性、穩(wěn)定性、再創(chuàng)性。鑒于此,該系統(tǒng)主要考慮的因素如圖1所示。3.1新算法的應(yīng)用3.1.1數(shù)據(jù)規(guī)格化度量單位的選取對于評價結(jié)果有很大影響。例如將身高的單位從米變?yōu)槌?將體重的單位從公斤變?yōu)榘鯇⒅苯佑绊懹嬎愕慕Y(jié)果。為了避免出現(xiàn)這種情況,必須將數(shù)據(jù)標(biāo)準化,將數(shù)據(jù)中的單位“去掉”,為此采用平均數(shù)規(guī)格化。3.1.2確定評價要素及其權(quán)重根據(jù)實際要求確定:課堂教學(xué)、教學(xué)實踐、獲獎專利等11項為評價要素,其權(quán)重均為1/11。3.1.3對待評價對象的集合進行聚類1用閾值矩陣法對所有樣本進行大致的分類:

21、c =5,將所有樣本進行初始化,c 即為評價結(jié)果論域(優(yōu)、良、中、及格、不及格中元素的個數(shù);構(gòu)造相似矩陣R =(r ij H H ,r i j ,i =1,2,H ;j =1,2,H ,表示樣本與樣本的相似程度,樣本之間相似程度用貼近度法表示;求出等價關(guān)系R *;采用截集矩陣法進行分類。2在大致分類基礎(chǔ)上,進行精確分類:對求得的分類采用平均值法計算出初始的聚類中心,(V 01,V 02,V 05;根據(jù)公式對聚類中心進行修正;若滿足結(jié)束條件,則迭代結(jié)束,否則回到。3.2系統(tǒng)主要運行界面該系統(tǒng)主要側(cè)重于對定量指標(biāo)進行評價,通過綜合評價模塊的處理,將評價結(jié)果直觀地反映出來,如圖2,3所示。646吉林

22、大學(xué)學(xué)報(信息科學(xué)版第22卷 從圖3可以直觀地看出某個教師的綜合素質(zhì)評價結(jié)果,還可以知道所有教師的綜合排名,方便教師了解自己的不足之處,以便及時改正,有助于整個教師隊伍綜合素質(zhì)的提高。4結(jié)論綜合評價方法在很多領(lǐng)域(如網(wǎng)絡(luò)優(yōu)化、教學(xué)、施工的決策研究、質(zhì)量分析等方面都有廣泛的應(yīng)用。筆者提出了一個基于模糊聚類和信息熵的綜合評價算法,具有操作簡單,易于實現(xiàn)等優(yōu)點,通過實驗分析,該算法的評價結(jié)果更符合實際情況,具有良好的實用性,當(dāng)評價指標(biāo)很多時,該算法更具優(yōu)越性。參考文獻:1黃淑琴(HU ANG Shu -qin .公路路線方案的多級綜合模糊評價(Fu zzy model for transp ort

23、pro ject app rais al J .中國公路學(xué)報(China Journal of Highway and Trans port ,1997,10(3:3744.2沈敏德,朱建公(SHEN M in -de ,ZH U Jian -gong .對機械傳動設(shè)計方案模糊評價中幾個問題的探討(An appr och toso me pro blems of fu zzy evaluation for mechnaical transm iss ion concept J .西南工學(xué)院學(xué)報(Jou rnal of Southwest Ins titute of Technolog y ,1

24、998,13(4:4043.3張邦禮,尹朝東,曹龍漢(ZH ANG Bang -li ,YIN Chao -dong ,CA O Long -han .柴油機故障診斷中的遺傳與模糊C -均值混合聚類分析算法(Clus tering by hybird genetic /C -means algor ithm in fault diagno sis for dies el engines J .計算機工程與應(yīng)用(Co mputer Engineering and A pplicatio ns ,2002,38(3:254256.4ZA DEH L A .Fu zzy s ets J .Info rmation an d Control ,1965,8(3:338353.5R USPINI E H .Numerical metho ds fo r fu zzy clustering J .Information Science ,1970,2(3:319350.6TAM U RA S ,HIG UCHI S ,TANA KAK .Pattern clas sification based on fu zzy relations J .IEEE SM C ,1971,1(1:217242.7ZKIM LE .Fu zzy relation c