基于聚類算法的本體層次關(guān)系獲取研究

基于聚類算法的本體層次關(guān)系獲取研究

1引言本體是一種有效的知識組織方式，被納入語義網(wǎng)體系，因其具有明確性、形式性和共享性三大特征，可以在網(wǎng)絡(luò)資源上融入計(jì)算機(jī)可以理解的信息，達(dá)到資源的語義理解，是語義層面上網(wǎng)絡(luò)信息的交換與共享的基礎(chǔ)[1]。它將Web資源通過語義的方式組織起來，使得互聯(lián)網(wǎng)的資源獲取更加便捷，是在互聯(lián)網(wǎng)上提供高效服務(wù)的先決條件。目前，本體在人工智能、信息檢索、知識工程、數(shù)據(jù)挖掘等學(xué)科領(lǐng)域中被廣泛研究和應(yīng)用[2]。在本體構(gòu)建過程中，術(shù)語間層次關(guān)系的建立，影響到本體的最終質(zhì)量。本文嘗試以聚類方法為基礎(chǔ)，得到測試術(shù)語集的層次關(guān)系，并抽取每個類中的標(biāo)簽，最終完成本體層次關(guān)系的獲取。2相關(guān)研究工作目前，構(gòu)建本體層次關(guān)系的方法常用的有基于詞典的方法、基于詞匯—句法模式的方法、基于Harris假設(shè)的方法、基于關(guān)聯(lián)規(guī)則的方法和基于語言學(xué)的方法。聚類方法是基于Harris假設(shè)方法的一種，Harris假設(shè)又稱為分布式假設(shè)，最早由Harris[3]提出，表述為如果兩個詞的上下文語境相似，那么這兩個詞也是相似的。基于Harris假設(shè)，衍生出基于層次聚類的方法[4,5]和基于形式概念分析的方法[6]兩種主要聚類方法，而國內(nèi)外的學(xué)者也不斷嘗試?yán)蒙鲜龇椒▽垲愃惴ㄟM(jìn)行調(diào)整和改進(jìn)，以滿足實(shí)際應(yīng)用的需要。馬輝民等[7]討論了文本表示方法中最常用到的向量空間模型，分析了其優(yōu)勢和不足，并基于一個文本處理實(shí)驗(yàn)，對VSM模型從可實(shí)現(xiàn)角度給出改進(jìn)建議。樂兵等[8]提出了基于遺傳算法的動態(tài)文本聚類方法，采用二進(jìn)制編碼方式對聚類中心進(jìn)行編碼，類內(nèi)中的點(diǎn)與其類中心的歐氏距離作為適應(yīng)度函數(shù)，通過遺傳算子的操作對類中心進(jìn)行逐步迭代，直至適應(yīng)度函數(shù)收斂，得到使聚類劃分效果最好的聚類中心。龔靜等[9]提出了K－means聚類算法中選取初始聚類中心及處理孤立點(diǎn)的新方法，改進(jìn)了K－means算法對初始聚類中心和孤立點(diǎn)文本很敏感的不足之處，并將改進(jìn)后的算法應(yīng)用于中文文本聚類中。王剛等[10]針對文本聚類缺少涉及概念的內(nèi)涵及概念間的聯(lián)系，提出了一種基于本體相似度計(jì)算的文本聚類算法TCBO(TextClusteringBasedonOntology)。該算法把文檔用本體來刻畫，以便描述概念的內(nèi)涵及概念間的聯(lián)系。同時(shí)，他們還設(shè)計(jì)和改進(jìn)了文本相似度計(jì)算算法，應(yīng)用本體的語義相似度來度量文檔間相近程度，設(shè)計(jì)了具體的根據(jù)相似度進(jìn)行文本聚類的算法。溫春等[11]通過分析已有的中文本體概念層次獲取方法的特點(diǎn)和不足，提出了一種利用度屬性獲取概念層次的方法。季培培等[12]針對如何獲取術(shù)語語義層次內(nèi)部結(jié)構(gòu)的關(guān)鍵問題，構(gòu)建術(shù)語語義層次獲取流程，采用多重聚類方法獲取層次關(guān)系，結(jié)合綜合相似度計(jì)算方法提取層次內(nèi)部的聚類標(biāo)簽。余永紅等[13]應(yīng)用遺傳算法進(jìn)行全局和快速的文本特征項(xiàng)選擇以實(shí)現(xiàn)降維處理，引入概率匿名思想，根據(jù)文本中不同特征項(xiàng)權(quán)重的組合，基于動態(tài)規(guī)劃設(shè)計(jì)一個優(yōu)化的多項(xiàng)式時(shí)間聚類算法。在聚類方法中，K－means聚類算法較為成熟，運(yùn)用也非常廣泛，但是由于其初始類中心點(diǎn)是隨機(jī)確定的，最終往往導(dǎo)致局部最優(yōu)的聚類結(jié)果，而不是全局最優(yōu)。因此本文嘗試對K－means算法進(jìn)行改進(jìn)，利用蟻群算法對術(shù)語集合進(jìn)行初步聚類，對每個劃分出來的簇進(jìn)行局部K－means聚類，并利用術(shù)語綜合相似度計(jì)算的方法得到每個簇的標(biāo)簽，從而完成本體層次關(guān)系的構(gòu)建。3方法描述在先前的工作中[14]，筆者對專利文獻(xiàn)中的術(shù)語進(jìn)行了抽取，方法為在ICTCLAS詞典分詞的基礎(chǔ)上，利用串頻最大匹配算法從中文專利文本中抽取候選概念，再利用TFIDF算法得到相關(guān)特征項(xiàng)的權(quán)重，經(jīng)過篩選后得到最終概念術(shù)語。針對上述術(shù)語，首先為術(shù)語建立向量空間模型，計(jì)算術(shù)語間的語義相似度，再利用蟻群算法，對術(shù)語集合進(jìn)行第一次聚類計(jì)算，利用蟻群算法的強(qiáng)魯棒性和優(yōu)良的分布式計(jì)算能力獲取若干個初始類，確定術(shù)語集合的聚類中心點(diǎn)，最后采用自上而下的多重K－means聚類算法得到術(shù)語層次關(guān)系。在獲取聚類標(biāo)簽時(shí)，使用術(shù)語間綜合語義相似度的方法進(jìn)行類標(biāo)簽的標(biāo)記，即綜合相似度最大的術(shù)語被提取出來作為當(dāng)前類的類標(biāo)簽，并將剩余的術(shù)語提取出來進(jìn)行下一層聚類，直到滿足聚類的層次要求時(shí)停止。獲取流程如圖1所示。3.1數(shù)據(jù)預(yù)處理在進(jìn)行聚類算法之前，需要對領(lǐng)域數(shù)據(jù)集合進(jìn)行預(yù)處理，包括術(shù)語向量空間模型的建立和術(shù)語間語義相似度的計(jì)算，具體轉(zhuǎn)換步驟如下：(1)使用TFIDF方法為術(shù)語集合構(gòu)建VSM模型。3.2改進(jìn)的蟻群聚類蟻群算法(AntColonyAlgorithm,ACA)是一種通過模擬自然界螞蟻搜索路徑的行為而形成的新型模擬算法，最早由Dorigo等[17]提出。相對于傳統(tǒng)的K－means聚類，蟻群聚類具有分布式和強(qiáng)魯棒性等特點(diǎn)。蟻群算法在聚類開始時(shí)不必設(shè)置聚類的數(shù)量，可以自己完成聚類；具有群集算法的優(yōu)勢——并行性、健壯性，不會因?yàn)槟承┪浵伒耐蛘咤e誤行為而影響整體聚類效果；可以把聚類過程投射到一個二維平面上進(jìn)行，增加了聚類結(jié)果表示的可視性。蟻群算法主要通過平均相似性和概率轉(zhuǎn)換函數(shù)來輔助實(shí)現(xiàn)。(1)平均相似性[18]螞蟻在某個坐標(biāo)中“拾起”、“移動”或者“放下”物體的概率是由該對象與周圍對象的平均相似性決定的。術(shù)語平均相似性的定義如下[19]：(2)概率轉(zhuǎn)換函數(shù)概率轉(zhuǎn)換函數(shù)由平均相似性f()得到，如果數(shù)據(jù)對象與周圍對象的平均相似性較小，那么螞蟻“拾起”的概率就越大；反之則“放下”的概率就越大。本文選擇了Sigmoid函數(shù)作為概率轉(zhuǎn)換函數(shù)，相對于其他函數(shù)，該函數(shù)具有更快的收斂性[20]。由此，得到無負(fù)載螞蟻“拾起”對象的概率和有負(fù)載螞蟻“放下”對象的概率分別如下[19,20]：(3)算法改進(jìn)在傳統(tǒng)的蟻群聚類算法中：①螞蟻路徑的選擇是隨機(jī)的，有可能出現(xiàn)同一只螞蟻多次訪問某個坐標(biāo)的情況，導(dǎo)致程序運(yùn)算時(shí)間延長；②可能會出現(xiàn)某個坐標(biāo)的術(shù)語與當(dāng)前術(shù)語集中的其他任何術(shù)語都不相關(guān)或者與周圍位置對象的平均相似性始終達(dá)不到指定閾值的情況，一旦螞蟻“拾起”了此類術(shù)語，在迭代結(jié)束時(shí)都無法“放下”該術(shù)語，造成了螞蟻資源的浪費(fèi)。為此，本文對算法進(jìn)行了相應(yīng)改進(jìn)：①增加螞蟻記憶體存儲螞蟻已經(jīng)爬行過的路徑；②設(shè)定負(fù)載螞蟻的最大“放下”次數(shù)，如果超過指定次數(shù)的螞蟻依然沒有“放下”術(shù)語，則表示該術(shù)語為孤立的，標(biāo)記為孤立點(diǎn)；③記錄所有螞蟻的已爬行路線，螞蟻在隨機(jī)選擇路線時(shí)繞過其他螞蟻和自身已經(jīng)爬行過的路線。算法過程如下：①將術(shù)語集對象投射到一個平面，給每個術(shù)語隨機(jī)分配一個坐標(biāo)值；②將所有螞蟻初始化為無負(fù)載，隨機(jī)選擇一個對象；③定義最大迭代次數(shù)M，若i不大于M，轉(zhuǎn)向步驟④，否則轉(zhuǎn)向步驟⑨；④定義螞蟻數(shù)量ant_n，如果j不大于n，轉(zhuǎn)向步驟⑤，否則轉(zhuǎn)向步驟③；⑤記錄螞蟻爬行的路線，如果當(dāng)前螞蟻或者其他螞蟻已經(jīng)爬行過該坐標(biāo)，則轉(zhuǎn)向步驟④，否則轉(zhuǎn)向步驟⑥；⑥根據(jù)式(3)計(jì)算螞蟻所在坐標(biāo)對象與鄰近對象的平均相似性，如果螞蟻無負(fù)載，依據(jù)式(4)計(jì)算螞蟻的拾起概率，若大于某一隨機(jī)概率P，則螞蟻“拾起”該對象，同時(shí)將自己標(biāo)記為“已負(fù)載”，隨機(jī)移往別處；否則拒絕“拾起”該對象；⑦如果螞蟻無負(fù)載，則依據(jù)式(5)計(jì)算放下概率，如果大于某一隨機(jī)概率，則螞蟻“放下”該對象，并標(biāo)記自己為“無負(fù)載”，隨機(jī)移往別處；否則，轉(zhuǎn)向步驟⑧；⑧定義螞蟻?zhàn)畲蟆胺畔隆贝螖?shù)T，如果t不大于T，則轉(zhuǎn)向步驟⑦，否則轉(zhuǎn)向步驟④；⑨若i不大于文檔集合數(shù)量C，則轉(zhuǎn)向步驟⑩，否則轉(zhuǎn)向步驟(12)；⑩在二維平面上隨機(jī)分配一個點(diǎn)，取得該點(diǎn)的對象，如果對象不為空，則將該對象賦值給變量Tmp，再按照3*3的區(qū)域，遞歸取出該區(qū)域其他坐標(biāo)的對象以及擴(kuò)展區(qū)域的其他對象，直到坐標(biāo)上對象值為空時(shí)停止；(11)為Tmp分配一個聚類序號，轉(zhuǎn)向步驟⑨；(12)完成聚類。表1顯示了蟻群聚類的結(jié)果：以類簇1為例，“連續(xù)燒燉式”、“鋼坯退火”、“退火溫度”、“脫磷率”、“鋼退火”等術(shù)語都屬于鋼板和線材軋制后的退火工藝范疇，而“分體式真空槽室”、“預(yù)熱箱體”、“支撐對流板”、“線材連續(xù)退火機(jī)”等術(shù)語則為退火用設(shè)備，因此，基于蟻群算法的聚類效果總體較好。但也會存在一些錯誤，例如類簇3中的“平均值”，類簇4中的“傷”、“積”等詞匯，這可能與術(shù)語抽取方法的準(zhǔn)確率和測試數(shù)據(jù)的規(guī)模有關(guān)。3.3K－means多重聚類在經(jīng)過蟻群聚類后，原始術(shù)語集合被聚集為若干個大類，得益于蟻群聚類算法的特點(diǎn)，每個簇的術(shù)語分布較為平均，降低了局部最優(yōu)情況的出現(xiàn)幾率。但是蟻群算法需要滿足一定的迭代次數(shù)才能完成最終聚類，往往比較費(fèi)時(shí)，而K－means算法則具有簡潔、快速的特點(diǎn)。因此，在已經(jīng)完成初步聚類的情況下，對于每個大類中的術(shù)語集可以再利用K－means算法進(jìn)行多重聚類，從而在不耗費(fèi)太多時(shí)間的情況下，得到術(shù)語的層次關(guān)系。此外，對于每次的聚類結(jié)果，本文采用了術(shù)語綜合相似度[12]來獲取當(dāng)前類的標(biāo)簽。術(shù)語綜合相似度是指聚類結(jié)果中每個術(shù)語與其他術(shù)語的相似度之和(見式(7))，若某個術(shù)語的綜合相似度大于其他術(shù)語，則表示該術(shù)語在當(dāng)前類中代表了最寬泛的語義內(nèi)容，可以作為類標(biāo)簽使用。由此，K－means多重聚類的過程可以描述為：利用術(shù)語綜合相似度計(jì)算每個簇中術(shù)語的綜合相似度，提取綜合相似度最大的術(shù)語作為頂層類標(biāo)簽；再利用K－means算法對剩余的術(shù)語進(jìn)行聚類；對于每次的聚類結(jié)果，分別利用術(shù)語綜合相似度進(jìn)行類標(biāo)簽的提取，并將剩下的術(shù)語放入下一層進(jìn)行聚類，直到達(dá)到L層后停止。具體算法步驟如下：(1)定義蟻群聚類的類目數(shù)量M，若i不大于M，轉(zhuǎn)向步驟(2)，否則轉(zhuǎn)向步驟(9)；(2)如果類目中的術(shù)語數(shù)量少于規(guī)定的T，使用式(7)得到綜合相似度最大的術(shù)語，將其提取出來作為當(dāng)前類的標(biāo)簽，并將剩余術(shù)語賦值給當(dāng)前類，轉(zhuǎn)向步驟(1)，否則轉(zhuǎn)向步驟(3)；(3)使用式(2)獲得當(dāng)前蟻堆的相似矩陣，用式(7)提取類標(biāo)簽，將作為類標(biāo)簽的術(shù)語剔除；(4)對于已剔除類標(biāo)簽的類術(shù)語集合，設(shè)定子類的聚類數(shù)量為當(dāng)前類術(shù)語總數(shù)的平方根[21]，再利用K－means算法進(jìn)行聚類，得到n個子類；(5)若j不大于子類總數(shù)n，轉(zhuǎn)向步驟(6)，否則轉(zhuǎn)向步驟(1)；(6)對于每個子類，利用式(7)計(jì)算術(shù)語綜合相似度，并提取類標(biāo)簽；(7)如果提取類標(biāo)簽后術(shù)語總數(shù)少于規(guī)定的T，將剩余的術(shù)語進(jìn)行合并，賦值給當(dāng)前類，并轉(zhuǎn)向步驟(5)，否則轉(zhuǎn)向步驟(8)；(8)遞歸對子類進(jìn)行下一層聚類，如果聚類層次達(dá)到給定的L，則轉(zhuǎn)向步驟(5)，否則轉(zhuǎn)向步驟(6)；(9)對聚類結(jié)果進(jìn)行整理，完成聚類。4實(shí)驗(yàn)結(jié)果及分析本文的實(shí)驗(yàn)語料采用文獻(xiàn)[14]的術(shù)語抽取結(jié)果，共計(jì)25497個術(shù)語。這些術(shù)語主要從國際專利分類號為C21的中文專利名稱和摘要中獲取，因此筆者從國家知識產(chǎn)權(quán)局下載了截至2010年12月國際專利分類號(IPC)為C21(鐵的冶金)的共計(jì)6435條專利數(shù)據(jù)作為實(shí)驗(yàn)對象。預(yù)先設(shè)定最大聚類層次為4層，每層可聚類術(shù)語總數(shù)不少于5個，經(jīng)計(jì)算，共計(jì)得到237個一級類、786個二級類、1196個三級類和1088個四級類，結(jié)果如圖2所示。圖2本體層次關(guān)系獲取結(jié)果片段由于目前并沒有統(tǒng)一的驗(yàn)證標(biāo)準(zhǔn)對聚類結(jié)果進(jìn)行評價(jià)，因此只能通過由專家人工評價(jià)的方式對聚類結(jié)果進(jìn)行評估。本文從聚類結(jié)果中隨機(jī)抽取了10個一級類，由領(lǐng)域?qū)＜曳謩e對其分層歸類和類標(biāo)簽抽取的準(zhǔn)確性進(jìn)行評測，結(jié)果如表2所示。表2從分層歸類是否合理和類標(biāo)簽抽取是否準(zhǔn)確兩個角度對聚類結(jié)果進(jìn)行了評價(jià)：(1)歸類是否合理。此次實(shí)驗(yàn)歸類的準(zhǔn)確率均值達(dá)到了80.47％，結(jié)合圖3可以看出，對于二級類目“淬火”來說，“合金工件”、“冷軋輥”、“涌泉式”、“期望”等術(shù)語明顯不屬于該類，而將“等離子淬火”、“激光淬火機(jī)床”等術(shù)語歸于該類較為合理。(2)類標(biāo)簽抽取結(jié)果是否準(zhǔn)確。從“淬火”的子類看，第二層將“淬火”設(shè)置為該類的標(biāo)簽比較合理，“等離子淬火”、“激光淬火機(jī)床”、“導(dǎo)感應(yīng)器”等類標(biāo)簽的設(shè)置也比較符合要求。但是“期望”作為第三層的類標(biāo)簽則不可取?？傮w看來，歸類準(zhǔn)確率和類標(biāo)簽抽取準(zhǔn)確率分別達(dá)到80.47％和78.78％，層次關(guān)系和類標(biāo)簽抽取基本合理，但是并不完善，其原因主要有：(1)用于測試的文檔集數(shù)量較少。本文只選用了國際專利分類號為C21的發(fā)明專利作為測試文檔集，該分類雖然標(biāo)記為“鐵的冶金”，但是并不能完全涵蓋煉鐵的所有領(lǐng)域。導(dǎo)致部分聚類結(jié)果的層次關(guān)系和歸類準(zhǔn)確性達(dá)不到領(lǐng)域?qū)＜艺J(rèn)知的水平，需要擴(kuò)大測試文檔的規(guī)模，增加“C22”、“C23”、“B21”、“B22”等其他分類的內(nèi)容，以提高聚類準(zhǔn)確性。(2)高頻詞的影響。在綜合相似度計(jì)算過程中，高頻詞往往會因?yàn)槠湓谖墨I(xiàn)中與其他術(shù)語同時(shí)存在的幾率較大，從而在計(jì)算時(shí)可能得到較高的分值，容易被抽取出來作為類標(biāo)簽，而排名稍后的術(shù)語有可能代表了該類的主要含義，因排名靠后而被剔除。如果在實(shí)驗(yàn)中考慮了高頻詞的因素，通過合理的手段降低高頻詞的綜合相似度權(quán)重，則可以有效提高類標(biāo)簽抽取的準(zhǔn)確性。(3)測試用的術(shù)語集合本身并不完備。本次測試使用了文獻(xiàn)[14]的術(shù)語抽取結(jié)果，該結(jié)果隨機(jī)樣本的測試準(zhǔn)確率達(dá)到了86.73％，并不是完全準(zhǔn)確，從而導(dǎo)致在聚類過程中，一些沒有意義的術(shù)語也參與了聚類計(jì)算，從而影響了整體的聚類效果。5結(jié)語術(shù)語層次關(guān)系的構(gòu)建是本體學(xué)習(xí)中的重要步驟，影響整個本體的質(zhì)量，文本聚類則是本體層次關(guān)系構(gòu)建的基本方法。本