知識聚類(lèi)技術(shù)

2008年10月沈陽(yáng)航空工業(yè)學(xué)院學(xué)報Oet. 2008第25卷第5期Joumal of Shenyang Institute of Aeronautical EngineeringVol. 25 No.5文章編號:1007 - 1385(2008)05 -0058 -05知識聚類(lèi)技術(shù)，季鋒苗霄霄(沈陽(yáng)航空工業(yè)學(xué)院知識工程中心,遼寧沈陽(yáng)100)4摘要:隨著(zhù)知識管理的不斷深人,知識庫所 包容的知識內容越來(lái)越多,如何建立知識的分類(lèi)體系,構建合理的知識關(guān)聯(lián)顯得尤為重要。知識豪類(lèi)是- -種 無(wú)指導的自動(dòng)分類(lèi)方法,在知識的組織和管理中發(fā)揮著(zhù)重要作用,不僅可以有效地節約知識庫優(yōu)化的人力資源，而且還可以更有效的反映知識間的本質(zhì)聯(lián)系。為此主要探討了知識豪類(lèi)的基本過(guò)程,包括知識特征的選取、相似度的計算和豪類(lèi)算法最后介紹了作者的- -些相關(guān)工作。關(guān)鍵詞:知識管理;知識豪類(lèi);知識庫中圈分類(lèi)號:TP391.1文獻標識碼:A .隨著(zhù)互聯(lián)網(wǎng)的不斷發(fā)展,信息激增和信息超;的知識聚類(lèi)更具有實(shí)用的研究?jì)r(jià)值。載給用戶(hù)帶來(lái)了巨大的壓力和焦慮。單純的面向1聚類(lèi)分析技術(shù)文獻和網(wǎng)絡(luò )資源的信息組織形式已經(jīng)遠遠不能滿(mǎn)足用戶(hù)對有效知識的獲取和利用。用戶(hù)更多的是聚類(lèi)分析是數據挖掘技術(shù)中的重要組成部分，需要有價(jià)值和意義的情報和知識內容,所以對現它能夠在數據中發(fā)現令人感興趣的分布模式。聚類(lèi)有的信息組織方法的擴充和發(fā)展已經(jīng)上升到知識過(guò)程就是將-群( set)物理的或抽象的對象,根據它組織的層面,通過(guò)挖掘信息內部更深層次的知識們之間的相似程度,分為若干組( group),其中相似內容,為用戶(hù)提供更好的知識管理服務(wù)。的對象構成-組。一個(gè)聚類(lèi)( cluster),又稱(chēng)簇,就是所謂知識組織就是將知識精煉的過(guò)程,是知由彼此相似的一組對象所構成的集合,不同聚類(lèi)中識管理的重要環(huán)節之一。文獻[1]提到了七種組對象通常是不相似的。聚類(lèi)分析就是從給定的數據織方法,包括知識表示、知識重組、知識聚類(lèi)、知識集中搜索數據對象之間所存在的有價(jià)值聯(lián)系。而在存檢、知識編輯、知識布局和知識監控。本文主要許多應用中,一個(gè)聚類(lèi)中所有對象常?？梢员划斪鹘榻B有關(guān)知識對象按其屬性類(lèi)別加以集中整序或-個(gè)對象來(lái)進(jìn)行處理或分析。整合的知識聚類(lèi)過(guò)程。作為統計學(xué)的一個(gè)分支,聚類(lèi)分析已有多年的人工的知識聚類(lèi)方法多種多樣,包括以學(xué)科歷史,這些研究主要集中在基于距離的聚類(lèi)分析方聚類(lèi)、以主題概念聚類(lèi)、以人聚類(lèi)、以用聚類(lèi)和以面。許多統計軟件包,諸如:S - Plus, SPSS和SAS,時(shí)空聚類(lèi)等。人工的知識聚類(lèi)可以保證知識主題都包含基于k -均值、k -中心等諸多聚類(lèi)分析方法。劃分的合理性、準確性,但在互聯(lián)網(wǎng)信息(主要是在機器學(xué)習中,聚類(lèi)分析屬于一種無(wú)指導的學(xué)習方網(wǎng)頁(yè)內容信息)爆炸式增長(cháng)的前提下,需要支付法。與分類(lèi)學(xué)習不同,無(wú)指導學(xué)習不依靠事先確定大量的人力資源,另外知識的分類(lèi)體系的調整是的數據類(lèi)別,以及標有數據類(lèi)別的學(xué)習訓練樣本集一個(gè)不斷迭代的過(guò)程,其間還面臨對知識分類(lèi)體合。正因為如此,聚類(lèi)分析是一種觀(guān)察式學(xué)習法系不斷地進(jìn)行細化和擴充,難以避免人員支出和(eaming by obervation) ,而不是示例式學(xué)習法( tea時(shí)間支出的無(wú)限制增長(cháng)。而知識聚類(lèi)技術(shù)可將采ming by example)。聚類(lèi)分析己被應用到許多領(lǐng)域，集到的知識進(jìn)行無(wú)指導的自動(dòng)分析,有效地將知其中包括:模式識別、數據分析、市場(chǎng)分析等領(lǐng)域,特識按規定的分類(lèi)標準進(jìn)行劃分,保證了劃分的快別是“中國煤化工的一個(gè)重要手段速性和準確率。與人工的知識聚類(lèi)相比,無(wú)指導發(fā)揮TYHCNMHG收稿日期:2008-03-252知識聚類(lèi)作者簡(jiǎn)介:浮鋒( 1981 -),男,遼寧葫蘆島人,助教，主要研究方向:信息檢索,E - mail:jiduo_ 1@ 163. com。知識聚類(lèi)是對采集的原始知識集合進(jìn)行劃分的第5期季鐸等:知識聚類(lèi)技術(shù)59- -種方法將-一個(gè)知識集劃分成不同的小類(lèi)。同類(lèi)方法可以改善性能。目前,特征選取的研究主要知識要盡量“緊密" ,而類(lèi)與類(lèi)之間的知識要盡量“疏是針對文本分類(lèi)的問(wèn)題，利用特征與類(lèi)別間的關(guān)遠”,目的是發(fā)現知識之間最本質(zhì)的“抱團”性質(zhì)。當系進(jìn)行特征的選取,如:互信息、信息增益,X2統對知識進(jìn)行特征描述之后,知識庫中的知識就被投計等()],特征與文本類(lèi)別相關(guān)性高則被保留,不.影為特征空間中的點(diǎn)集，當選定點(diǎn)間的相似性測度相關(guān)則被拋棄。而在知識聚類(lèi)的任務(wù)中沒(méi)有類(lèi)別函數后,知識聚類(lèi)的結果即被確定。因此知識聚類(lèi)信息可以利用,因此就需要采用無(wú)指導方法進(jìn)行可以分為圖1中的幾個(gè)步驟: .特征的選取?；谖臋n頻度的特征選擇方法無(wú)需任何類(lèi)別信息,針對每個(gè)特征計算包含這個(gè)特征的文檔的[特餐表示 ][相似性黃皮 ][類(lèi)][出數目,如果包含某個(gè)特征的文檔數較低,說(shuō)明該特征所含的信息量較低,它對區分不同的文檔作用圈1聚類(lèi)過(guò)程不是很大,可設定給定閾值過(guò)濾此種特征。但該2.1知識的特征選擇假設在現實(shí)生活中卻不- -定成立,因為某個(gè)特征知識的特征選擇- -般事由領(lǐng)域專(zhuān)家決定使用在多個(gè)文檔中都出現,反而表明它對區分并沒(méi)有哪些特征來(lái)深刻地刻畫(huà)知識的本質(zhì)性質(zhì)和結構。太大的幫助。這和文檔頻度方法所基于的假設剛特征選擇的結果是-一個(gè)輸出矩陣,每-行代表一好相反。但即便如此,這個(gè)方法在實(shí)際應用中仍個(gè)知識,每一列代表- 一個(gè)特征指標變量。特征選然取得了良好的性能。取的優(yōu)劣將直接影響以后的知識聚類(lèi)的分析和決2.2知識的相似性計算策。合理的特征選取方案應當使得同類(lèi)知識在特給出知識間的相互關(guān)系,即兩個(gè)知識樣本間征空間中相距較近，異類(lèi)知識則相距較遠。的相似度或距離。相似度-般定義為界于[0,1]特征選取的方法可以定義如下:給定候選特.之間的一個(gè)值,是知識聚類(lèi)的基礎。相似度計算征集合,從中選擇某個(gè)子集,可以使最終的系統性方法是否反映知識本質(zhì)間的相關(guān)性,將直接決定能最好的子集。特征選取方法基于獨立性假設,知識聚類(lèi)性能的好壞。圖2中,不同的知識庫A根據某個(gè)預先定義評價(jià)優(yōu)劣的準則,從候選特征和B上分別采用不同的相似點(diǎn)計算方法,在A(yíng)分集合中選取最有信息量的特征2。特征選取方布中基于幾何距離相似度的方法最好,而在B分法基于獨立性假設,根據給定的評價(jià)準則,對每個(gè)布中基于余弦距離的聚類(lèi)結果要好于幾何距離。特征分別進(jìn)行評價(jià),并根據評價(jià)的分值按由大到因此,在不同的知識庫中需要通過(guò)大量的實(shí)驗找小進(jìn)行排序,去除得分最小的特征。利用這種方到符合當前樣本集合的相似度計算方法”。常法，系統不僅可以對高維的空間進(jìn)行降維,并且在用的計算方法有Minkowski 距離和Cosine距離某些情況之下(降維程度控制得當，剛好把噪音等,以下僅給出相似度計算公式,更詳細內容請參數據去除，而保留所有的有效特征)可以使聚類(lèi)考有關(guān)文獻。性能得到改善,也就是說(shuō),當去除噪音的收益比特(1)Minkowski距離征選取導致的信息損失來(lái)得大的時(shí)候,特征選取Minkowski距離是幾何上的標準度量單位,定.%|?幾何距離弦距離A205中國煤化工J點(diǎn)分布AHYHCNMHG圖2相似度對聚類(lèi)結果的影響6(沈陽(yáng)航空工業(yè)學(xué)院學(xué)報第25卷義如下。當p=2的時(shí),得到的是歐幾里德距離。每一次改進(jìn)之后的分組方案都較前一次更好, 而L,(d.,d) =(2 |4. -4.)”(1)所謂“好”的標準就是同一分組中的記錄越近越好,而不同分組中的記錄越遠越好?；趧澐值?2)Cosine距離聚類(lèi)算法主要有K - Means算法、K - Medians算Cosine距離是兩向量間夾角的余弦,Cosine法CLARANS算法。距離的一個(gè)特性就是它不依賴(lài)于表示向量的長(cháng)(2)層次方法( Hierarchical Method)度。這種特性使得包含有不同特征頻度的知識被這種方法對給定的數據集進(jìn)行層次的分解，等同地看待,其定義如下:直到某種條件滿(mǎn)足為止。具體又可分為“自底向cos(u ,02)上”和“自頂向下”兩種方案。代表算法有:U●U2BIRCH算法引和CURE算法等。(3)基于模型的方法( Model - Based Meth-2 (weight(u,1)●weight(0,1))od)=基于模型的方法給每一個(gè)聚類(lèi)假定-一個(gè)模wigh(n,I".N Seigh(o.r型,然后去尋找能夠很好的滿(mǎn)足這個(gè)模型的數據(2)集[5,9]。這樣一個(gè)模型可能是數據點(diǎn)在空間中的(3) Kullback - Leibler( KL)距離密度分布函數或者其他。它的一個(gè)潛在的假定就KL距離即相對熵,用于比較兩個(gè)分布的不是:目標數據集是由一系列的概率分布所決定的。同。如果把知識的特征向量看成是兩個(gè)分布,則可通常有兩種方法:統計的方法和神經(jīng)網(wǎng)絡(luò )的方法。以用KL距離來(lái)表示兩分布的相似度。當需要計算(4)基于密度的方法( Density - Based Meth-知識相似度時(shí),一般使用對稱(chēng)的KL距離,其定義如下式:基于密度的方法與其他方法的-一個(gè)根本區別是:它不是基于各種各樣的距離的,而是基于密度S(x)(d,dj) =(P(t1d,) -P(r1 d)的,這樣就能克服基于距離的算法只能發(fā)現球型o P(t1d.)聚類(lèi)的缺點(diǎn)。這個(gè)方法的指導思想就是只要-個(gè)(3)logP(tI )區域中的點(diǎn)的密度大過(guò)某個(gè)闕值,就把它加到與2.3聚類(lèi)算法之相近的聚類(lèi)中去。代表算法有:DBSCAN算聚類(lèi)算法是知識聚類(lèi)中的關(guān)鍵環(huán)節。聚類(lèi)算法[")和OPTICS算法等。法的輸出一般是一個(gè)聚類(lèi)譜系圖，由粗到細地反(5)混合方法( Mixture Method)映了知識庫中知識的分類(lèi)情況;或者直接給出具該方法是將不同的方法進(jìn)行融合,以此來(lái)獲體的知識分類(lèi)方案,包括總分類(lèi)數,每類(lèi)具體包含得更優(yōu)的性能。Clustering by Commttee (CBC)$]那些知識等等。因此在很多實(shí)際應用中需要根據主要觀(guān)點(diǎn)就是通過(guò)兩步進(jìn)行聚類(lèi),首先采用復雜所涉及的數據類(lèi)型、聚類(lèi)的目的以及具體應用要度較低的方法生成類(lèi)內緊密相關(guān)的小類(lèi)Commit,求來(lái)選擇合適的聚類(lèi)算法。然后在采用傳統的方法進(jìn)行聚類(lèi)輸出。DEN-聚類(lèi)算法可以分為以下幾類(lèi):劃分法、層次CLUE (Density basted Clustering) 就是結合了劃分法、基于密度的方法、基于模型的方法和混合法方法、層次方法和局部方法的一個(gè)綜合方法。等[4-6,10]。STING方法也結合了基于網(wǎng)格的方法和自上而下(1)劃分方法( Pritoning Method)的方法。給定-一個(gè)有N個(gè)元組或者記錄的數據集,劃2.4知識聚類(lèi)的結果表示分方法將構造K個(gè)分組(K