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