基于模糊聚類和信息熵的綜合評(píng)價(jià)算法-

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

2、簡(jiǎn)潔性與有效性問題,在分析已有算法的基礎(chǔ)上,提出了一種基于模糊聚類和信息熵的綜合評(píng)價(jià)算法,該算法有針對(duì)性地克服了原有評(píng)價(jià)算法的缺陷,具有較好的實(shí)用性,最后通過實(shí)際數(shù)據(jù)對(duì)該算法的有效性進(jìn)行了驗(yàn)證。關(guān)鍵詞:模糊聚類;信息熵;綜合評(píng)價(jià)中圖分類號(hào):TP312文獻(xiàn)標(biāo)識(shí)碼: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引言評(píng)價(jià)是隨著人類社會(huì)活動(dòng)的發(fā)展而產(chǎn)生的。為了進(jìn)行管理,就要進(jìn)行一系列的評(píng)價(jià)。評(píng)價(jià)活動(dòng)廣泛存在于社會(huì)生活的各個(gè)領(lǐng)域。如教師授課績(jī)效考核、員工工作能力的考核等。長(zhǎng)期以來,評(píng)價(jià)主要是依

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

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

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

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

10、素之和大于0,這保證了每類都必須有樣本。模糊聚類的主要算法有模糊等價(jià)矩陣法、模糊I SODATA 聚類分析法等。按照人們的常識(shí):小概率事件所蘊(yùn)含的信息量較大;就隨機(jī)性而言,基本事件個(gè)數(shù)相同者,以等概率分布場(chǎng)平均信息量大。上面的表述只是從定性的角度對(duì)信息進(jìn)行了描述,在處理相關(guān)信息時(shí)沒有任何信息的損失,但該方法不能提供基于對(duì)象的各因素的重要性大小,所以還需要提供先驗(yàn)的權(quán)重分配,必須借助于熵的概念,才能定量表達(dá),熵是描述信息不確定性的度量。設(shè)X 是取有限個(gè)值的隨機(jī)變量,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時(shí),p i log a1p i=0。上述表達(dá)式即為Shannon 信息熵表達(dá)式。由此可見,信息熵是由事物內(nèi)部屬性客觀決定的,如果能夠用信息熵來確定權(quán)重,則能夠保證權(quán)重的客觀性。關(guān)于信息熵對(duì)確定權(quán)重的意義詳見文獻(xiàn)10,11。1.2算法的具體實(shí)現(xiàn)1.2.1經(jīng)典模糊聚類的改進(jìn)對(duì)目標(biāo)函數(shù)的改進(jìn)主要是在目標(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é)報(bào)(信息科學(xué)版第22卷1.2.2算法的具體步驟1據(jù)標(biāo)準(zhǔn)化處理,這里采用極大值標(biāo)準(zhǔn)化處理方法。2確定評(píng)價(jià)因

12、素的權(quán)重系數(shù),形成權(quán)重向量。3對(duì)待評(píng)價(jià)對(duì)象的集合進(jìn)行聚類。a 用閾值矩陣法對(duì)所有樣本進(jìn)行大致的分類:固定c 值,將所有樣本進(jìn)行初始化,c 即為評(píng)價(jià)結(jié)果論域中元素的個(gè)數(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 求出等價(jià)關(guān)系R *。通過平方計(jì)算法可以快速求得R *。依次求得R 2,R 4,R 8,R 2k,直到R 2k=R2k -1,則有R *=R 2k。采用截集矩陣法

13、進(jìn)行分類。是R *中的隸屬度,選擇不同的隸屬度使樣本分為不同的c 類。b 在大致分類基礎(chǔ)上,進(jìn)行精確分類:對(duì)求得的分類采用平均值法計(jì)算出初始的聚類中心(V 01,V 02,V 0c ;根據(jù)公式對(duì)聚類中心進(jìn)行修正;若滿足結(jié)束條件,則迭代結(jié)束,否則回到。2算法的分析與驗(yàn)證該算法以綜合評(píng)價(jià)工作的本質(zhì)要求為突破點(diǎn),根據(jù)綜合評(píng)價(jià)工作的具體特點(diǎn),采用了改進(jìn)后的模糊聚類方法;針對(duì)模糊聚類與綜合評(píng)價(jià)工作的不同,在算法中引入了由信息熵得到的權(quán)重向量,從而保證了算法的有效。筆者以1997年中國(guó)經(jīng)濟(jì)統(tǒng)計(jì)年鑒提供的統(tǒng)計(jì)數(shù)據(jù)為基礎(chǔ),采用基于模糊聚類和信息熵的綜合評(píng)價(jià)算法對(duì)6個(gè)城市的經(jīng)濟(jì)指標(biāo)進(jìn)行綜合評(píng)測(cè)。已知決策對(duì)象集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年全國(guó)6市主要經(jīng)濟(jì)指標(biāo)Tab .1The main economic targets of six cities in 1997城市名稱土地面積/km2年末總?cè)丝?萬人國(guó)民生產(chǎn)總值/萬元人均生產(chǎn)總值/元實(shí)現(xiàn)利稅總額/萬元固定資產(chǎn)投資完成額/萬元出口總值/萬美元實(shí)際利用外資/萬美元財(cái)政總收入/萬元職工均工資/元石家莊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)濟(jì)發(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個(gè)城市經(jīng)濟(jì)發(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個(gè)城市

17、經(jīng)濟(jì)發(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年中國(guó)縣域經(jīng)濟(jì)基本競(jìng)爭(zhēng)力評(píng)價(jià)中心對(duì)這6個(gè)城市的經(jīng)濟(jì)發(fā)展水平的排行為:蘇州、武漢、石家莊、烏魯木齊、蘭州、呼和浩特。通過和上面幾種方法的計(jì)算結(jié)果比較,可以看出,多少都存在一645第6期張運(yùn)凱,等:基于模糊聚類和信息熵的綜合評(píng)價(jià)算法定出入:專家調(diào)查法得到的6個(gè)城市的排行中,發(fā)生了兩對(duì)錯(cuò)誤,即武漢和石家莊以及烏魯木齊和蘭州,可見該方法的實(shí)用性具有一定的局限性;比較矩陣法和Delphi 法由于對(duì)專

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

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

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

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

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

23、pro ject app rais al J .中國(guó)公路學(xué)報(bào)(China Journal of Highway and Trans port ,1997,10(3:3744.2沈敏德,朱建公(SHEN M in -de ,ZH U Jian -gong .對(duì)機(jī)械傳動(dòng)設(shè)計(jì)方案模糊評(píng)價(jià)中幾個(gè)問題的探討(An appr och toso me pro blems of fu zzy evaluation for mechnaical transm iss ion concept J .西南工學(xué)院學(xué)報(bào)(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 .柴油機(jī)故障診斷中的遺傳與模糊C -均值混合聚類分析算法(Clus tering by hybird genetic /C -means algor ithm in fault diagno sis for dies el engines J .計(jì)算機(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