陳俊杰，候宏旭，高 靜

(1.內(nèi)蒙古大學(xué)計(jì)算機(jī)學(xué)院，內(nèi)蒙古呼和浩特010021;2.內(nèi)蒙古農(nóng)業(yè)大學(xué)計(jì)算機(jī)與信息工程學(xué)院，內(nèi)蒙古呼和浩特010018)

0 引言

文本機(jī)會發(fā)現(xiàn)算法KeyGraph是日本學(xué)者Y.Oshawa于1998年在文獻(xiàn)［1］中首先提出的，旨在獲取文中的頻率不高但是對主題有意義的詞.該算法近年來被廣泛關(guān)注并應(yīng)用到各種領(lǐng)域.例如:事件檢測［2］、熱點(diǎn)話題追蹤［3］、金融市場分析［4］、醫(yī)療記錄分析［5］、可視化微博評論［6］、地震檢測［7］、電子商務(wù)［8］等.近年來，很多學(xué)者將其拓寬到了數(shù)據(jù)挖掘領(lǐng)域，如張振亞［9-10］提出的機(jī)會發(fā)現(xiàn)與數(shù)據(jù)挖掘的關(guān)聯(lián)，李林［11］提出的機(jī)會發(fā)現(xiàn)在情報(bào)中的挖掘方法等.然而，由于KeyGraph算法涉及到多個(gè)閾值，需要多次試探求得最優(yōu)解，反復(fù)對數(shù)據(jù)集進(jìn)行掃描，因此有效的KeyGraph建模方法成為人們近年來開始研究的熱點(diǎn).

R.C.Pan［12］提出了一遍掃描 KeyGraph 執(zhí)行模型，該模型利用樹結(jié)構(gòu)來存儲詞語、句子及其對應(yīng)的關(guān)系，但是在執(zhí)行過程中需要多次遍歷樹結(jié)構(gòu)，算法的執(zhí)行效果并不理想.孫曉華等［13］提出了多遍掃描的KeyGraph模型，該模型利用矩陣存儲的相關(guān)性，并利用矩陣運(yùn)算及其分解來實(shí)現(xiàn)KeyGraph算法，有效地提高了原有算法的執(zhí)行效率，但是當(dāng)數(shù)據(jù)集增大的時(shí)候，由于要對所有詞進(jìn)行關(guān)鍵度計(jì)算，計(jì)算的過程要遍歷所有句子，因此執(zhí)行效率顯著降低.孫曉華等［14］提出算法需要解決的主要問題之一就是在處理大數(shù)據(jù)集時(shí)如何有效地提高算法的執(zhí)行效率.本文提出了一種新的KeyGraph建模方法，通過倒排索引的方式存儲詞與句子的信息，并對KeyGraph算法的關(guān)鍵度計(jì)算方法做了改進(jìn).經(jīng)實(shí)驗(yàn)驗(yàn)證該方法能有效地提高算法的執(zhí)行效率.

1 KeyGraph算法的思想

KeyGraph算法是一種借助共現(xiàn)關(guān)系提取表達(dá)文檔主題關(guān)鍵詞的算法.它不僅能夠提取文檔中的高頻關(guān)鍵詞，還可以提取出能夠表達(dá)主題意義的低頻詞.

該算法首先提取文檔中頻繁出現(xiàn)的項(xiàng)作為實(shí)心頂點(diǎn)，計(jì)算頻繁項(xiàng)之間的共現(xiàn)度，在共現(xiàn)度超過指定閾值的實(shí)心頂點(diǎn)之間建立一條實(shí)邊;其次找出圖中的所有連通子圖，每個(gè)連通圖視為一個(gè)島群.島群是由頻繁項(xiàng)組成的，是公眾知識;然后在圖中添加能夠?qū)u群連接起來的新項(xiàng)，該項(xiàng)必須滿足與島群之間共現(xiàn)度的要求.這樣的項(xiàng)標(biāo)識為虛心頂點(diǎn)，虛心頂點(diǎn)和島群之間的連接被稱之為橋.由于虛心頂點(diǎn)不是頻繁項(xiàng)，是不被人們所熟知的內(nèi)容，是隱藏在公眾知識背后的知識，因此被稱為機(jī)會.

2 建模方法及形式化描述

算法執(zhí)行的流程框圖如圖1所示.

圖1 算法執(zhí)行流程框圖Fig.1 Algorithm execution flow diagram

該算法針對的是單篇文檔，由于文檔中的詞和句子的數(shù)量是有限的，因此該算法一定收斂.

2.1 文檔預(yù)處理

對于中文文檔而言需要先進(jìn)行分詞、分句、去除停用詞的預(yù)處理工作.預(yù)處理后的文檔記作D={s1，s2，…si，..sn}，其中 si為句子.對文檔 D進(jìn)行掃描，獲取文檔中出現(xiàn)的詞并記錄每個(gè)詞的詞頻.對詞按詞頻排序并將排序后的詞w標(biāo)記為w(id，content，freq，key)，其中 id 為詞的標(biāo)識序號，id越小頻次越高;content為詞的內(nèi)容;freq為詞在文檔中出現(xiàn)的總次數(shù);key為詞的關(guān)鍵度.建立詞的列表 W，其中 W［k］為第 k個(gè)詞.為每個(gè)句子按其出現(xiàn)的次序建立編號，句子標(biāo)記為 S〈w1，w2，…，wk〉，句子中可能存在重復(fù)的詞，即可能存在如下的句子:si=〈w1，w2，w1〉.文檔句子的個(gè)數(shù)記為 Ns.

按照得到的詞集合 W={w1，w2，..wi，wk}為其建立句子集的倒排索引，倒排索引用矩陣表示，記為A.集合W的元素個(gè)數(shù)記為Nw，即文檔中詞的個(gè)數(shù).

2.2 模型及其形式化描述

2.2.1 提取高頻詞及其關(guān)聯(lián)度

高頻詞集合記作

式中:Hf為高頻詞閾值，集合V中的元素個(gè)數(shù)記為Nf，即高頻詞的個(gè)數(shù).掃描矩陣A，得到高頻詞共現(xiàn)節(jié)點(diǎn)索引.單詞間的關(guān)聯(lián)度為

式中:wi，wj∈W，|wj|s表示單詞 wj在句子 s中的頻率.

式中:CoNode(wi)為高頻詞wi共現(xiàn)的關(guān)聯(lián)節(jié)點(diǎn)集合;wj為共現(xiàn)詞;assoc(wi，wj)為共現(xiàn)詞 wj與 wi的關(guān)聯(lián)度.

高頻詞與其他高頻詞之間的關(guān)聯(lián)節(jié)點(diǎn)集為

高頻詞與高頻詞之間的關(guān)聯(lián)度為

以高頻詞為節(jié)點(diǎn)建立圖 G.設(shè)定關(guān)聯(lián)度閾值A(chǔ)f，掃描 CoNodeHf索引，若 CoNodeHf val(wi，wj)＞Af，則為 wi與 wj之間建立一條實(shí)心邊.

2.2.2 建立連通子圖

在圖G中尋找最大連通子圖，若最大連通子圖不能包含所有的節(jié)點(diǎn)，則G必為非連通圖，則將G劃分成若干個(gè)連通子圖.圖中連通子圖的個(gè)數(shù)記為Ng，每個(gè)連通圖中的節(jié)點(diǎn)構(gòu)成一個(gè)群組g.群組 g中的節(jié)點(diǎn) g Nodes記作 g Nodes(g)，群組 g的個(gè)數(shù)記作NG.為每個(gè)群組g創(chuàng)建群組節(jié)點(diǎn)句子索引，掃描高頻詞的關(guān)聯(lián)節(jié)點(diǎn)倒排索引，獲得群組g的相關(guān)節(jié)點(diǎn)索引.

即g AssocNodes(g)是與群組g關(guān)聯(lián)度大于0的詞，也就是與群組 g中的詞共現(xiàn)過的詞，將g AssocNodes(g)的元素個(gè)數(shù)記為Nwa，求出群組g中的節(jié)點(diǎn)，出現(xiàn)過的句子編號記作

式中:k為句子編號;g AssocNodes(g)的元素個(gè)數(shù)記為 Nsa.

2.2.3 計(jì)算詞的關(guān)鍵度并獲取關(guān)鍵詞

計(jì)算單詞的關(guān)鍵度key(w)需要借助兩個(gè)輔助公式［1］

其中:

關(guān)鍵度key(w)的計(jì)算方式為

根據(jù)KeyGraph算法定義，若詞w在句子s中出現(xiàn)，而群組g中的節(jié)點(diǎn)并未在 s中出現(xiàn)，則based(w，g)=0，即based(w，g)值不為0的節(jié)點(diǎn)一定是和群組g中的節(jié)點(diǎn)共現(xiàn)過的節(jié)點(diǎn)，未和群組g共現(xiàn)的節(jié)點(diǎn)其值一定是0.

將公式(9)變?yōu)?/p>

進(jìn)一步分析KeyGraph算法再計(jì)算based(w，g)的值，掃描文檔時(shí)并不需要掃描所有句子，只需要考慮群組g節(jié)點(diǎn)出現(xiàn)過的句子的集合.將其進(jìn)一步變形為

即在計(jì)算詞語w關(guān)鍵度時(shí)首先掃描群組g的節(jié)點(diǎn)索引，檢查該節(jié)點(diǎn)是否屬于gAssocNodes(g)，如果不存在根本不需要計(jì)算，其值一定為0;若在該群組的關(guān)聯(lián)節(jié)點(diǎn)中，則不需要掃描文檔中的所有句子，只需要掃描g Sentences(g)中的句子.

將詞語按照關(guān)鍵度值排序，將大于設(shè)定閾值Kf的節(jié)點(diǎn)記作KeyNodes，抽取為候選關(guān)鍵詞加入到G中.掃描高頻詞的關(guān)聯(lián)節(jié)點(diǎn)倒排索引，并將關(guān)聯(lián)度超過設(shè)定閾值A(chǔ)f的候選關(guān)鍵詞抽取為關(guān)鍵詞.

2.3 算法復(fù)雜度比較

本文的計(jì)算關(guān)鍵度算法的復(fù)雜度從原來的O((Nw－Nf)NgNs)變?yōu)?O(NwaNgNsa)，顯然 Nwa≤Nw－Nf，Nsa≤Ns，而通常情況文檔都不只一個(gè)連通圖，即便是只有一個(gè)連通圖，也不會所有的單詞都和該連通圖中的詞都共現(xiàn).由于Nwa?Nw－Nf，Nsa?Ns，因此本文的算法大大地提高了算法的執(zhí)行效率.

3 實(shí)驗(yàn)及分析

本文的實(shí)驗(yàn)文檔為搜狐網(wǎng)站中的新聞和小說，分詞工具采用中科院的ICTCLAS，模型實(shí)現(xiàn)采用Java語言，開發(fā)版本JDK6.實(shí)驗(yàn)運(yùn)行環(huán)境為Windowns 7 32位操作系統(tǒng)，主頻 3.06 GHz，內(nèi)存 4 G.

采用本文的建模方法實(shí)現(xiàn)的該算法以搜狐新聞標(biāo)題為“專家解讀:大部制改革要防止權(quán)力擴(kuò)張”為例進(jìn)行說明，其詞與詞頻的對照表如表1所示.

表1 詞頻表Tab.1 Word frequency table

實(shí)驗(yàn)設(shè)置各閾值:Hf=2，Af=1，Kf=0.05，Cf=1.獲得的連通圖頂點(diǎn)集合如表2所示，得到的文本機(jī)會及其Key值如表3所示.

表2 連通圖頂點(diǎn)單詞集合表Tab.2 Set of vertex words in connective graph

表3 文本機(jī)會及其Key值對照表Tab.3 Text chances and key values table

該新聞主要闡述了大部制改革即合并部門是符合發(fā)展需求的，但同時(shí)也存在權(quán)利擴(kuò)張、膨脹的負(fù)面影響.從實(shí)驗(yàn)結(jié)果可以看出，得到的文本機(jī)會反映了隱藏在公眾知識后的隱含知識.

為驗(yàn)證本文建模方法的正確性和效率，實(shí)驗(yàn)中將文檔按句數(shù)分成5種類型，對每種類型的文檔各取150篇進(jìn)行實(shí)驗(yàn)，并將實(shí)驗(yàn)結(jié)果與文獻(xiàn)［13］的執(zhí)行模型實(shí)現(xiàn)結(jié)果進(jìn)行了比較，結(jié)果發(fā)現(xiàn)在取相同閾值的情況下，兩種建模方法的執(zhí)行結(jié)果完全相同，且按照本文建模方法實(shí)現(xiàn)的過程執(zhí)行效率明顯高于文獻(xiàn)［13］的方法.不同執(zhí)行算法執(zhí)行的運(yùn)行時(shí)間對照表如表4所示.

從實(shí)驗(yàn)結(jié)果可以看出，本文的建模方法執(zhí)行效率明顯高于文獻(xiàn)［13］的方法，尤其是當(dāng)文檔的句子數(shù)超過400句之后，其執(zhí)行速度提高了7 s左右，算法的執(zhí)行效率平均提高了32.5%.

表4 不同算法執(zhí)行效果比較表Tab.4 Efficiency compare of different methods

4 結(jié)論

本文提出了一種KeyGraph建模方法，并對其進(jìn)行了形式化描述.該方法采用倒排索引的方式進(jìn)行存儲并改進(jìn)了KeyGraph的Key值計(jì)算方法，結(jié)果證明本文的建模方法是有效的，當(dāng)文檔規(guī)模增大時(shí)能有效地提高算法的執(zhí)行效率.在實(shí)驗(yàn)的過程中，我們也同時(shí)發(fā)現(xiàn)，由于KeyGraph算法在執(zhí)行的過程中需要設(shè)定4個(gè)閾值，而隨著文檔規(guī)模的變化閾值是不能一成不變的，也就是說閾值的設(shè)定嚴(yán)重地影響了關(guān)鍵詞提取的結(jié)果.通常人們都根據(jù)經(jīng)驗(yàn)設(shè)定閾值，這樣使得KeyGraph算法的執(zhí)行結(jié)果過多地依賴于人的經(jīng)驗(yàn)，當(dāng)經(jīng)驗(yàn)不足的時(shí)候，KeyGraph算法的執(zhí)行結(jié)果將嚴(yán)重受限，同時(shí)對于中文關(guān)鍵詞抽取而言需要先進(jìn)行分詞，這樣分詞的效果嚴(yán)重影響關(guān)鍵詞的抽取效果，尤其是受新詞、未登錄詞、專有名詞的影響.因此，根據(jù)文檔的規(guī)模如何設(shè)定閾值，如何提取更為有效的關(guān)鍵詞是下一步需要研究的問題.

［1］Ohsawa Y，Benson N E，Yachida M.KeyGraph:Automatic indexing by co-occurrence graph based on building construction metaphor［C］.Research and Technology Advances in Digital Libraries，IEEE International Forum on，1998:12-18.

［2］Sayyadi H，Hurst M，Maykov A.Event detection and tracking in social streams［C］.Proceedings of International Conference on Weblogs and Social Media(ICWSM)，2009:45-52.

［3］Ohsawa Y.Chance discoveries for making decisions in complex real world［J］.New Generation Computing，2002，20(2):143-163.

［4］Izumi K，Goto T，Matsui T.Analysis of financial markets＇fluctuation by textual information［J］.Transactions of the Japanese Society for Artificial Intelligence，2010，25:383-387.

［5］Kushima M，Araki K，Suzuki M，et al.Analysis and visualization of In-patients＇nursing record using text mining technique［C］.Proceedings of the International MultiConference of Engineers and Computer Scientists，2011:11-18.

［6］Tsuda K，Thawonmas R.KeyGraph for visualization of discussions in comments of a blog entry with comment scores［J］.WESE Trans.Computers，2005，12(4):1794-801.

［7］Ohsawa Y.KeyGraph as risk explorer in earthquake sequence［J］.Journal of contingencies and crisis management，2002，10(3):119-128.

［8］Chen L C，Yu T J，Hsieh C J.Key Graph-based chance discovery for exploring the development of e-commerce topics［J］.Scientometrics，2013，95(1):1-19.

［9］張振亞，程紅梅，王煦法.從數(shù)據(jù)挖掘到機(jī)會/征兆發(fā)現(xiàn)［J］.計(jì)算機(jī)科學(xué)與技術(shù)，2007，34(10):188-191.Zhang Zhenya，Cheng Hongmei，Wang Xufa.From data minning to chance/sign discovery［J］.Computer Science，2007，34(10):188-191.(in Chinese).

［10］張振亞，程紅梅，張曙光.機(jī)會發(fā)現(xiàn)中簡單場景構(gòu)造方法研究［J］.計(jì)算機(jī)工程，2011，37(8):192-196.Zhang Zhenya，Cheng Hongmei，Zhang Shuguang.Research on approach of simple scenario map construction in chance discovery［J］.Computer Engineering，2011，37(8):192-196.(in Chinese).

［11］李琳.機(jī)會發(fā)現(xiàn)及其在情報(bào)學(xué)方面的應(yīng)用［J］.情報(bào)科學(xué)，2011，29(2):172-176.Li Lin.Chance discovery and application in information science［J］.Information Science，2011，29(2):172-176.(in Chinese).

［12］Pan R C，Hong C F，Huang C J，et al.One-scan key-Graph implementation［C］.The Third Conference on Evolutionary Computation Applications and International Workshop on Chance Discovery，2005:77-84.

［13］孫曉華，劉大昕，徐悅竹，等.多遍掃描的KeyGraph執(zhí)行模［J］.系統(tǒng)工程與電子技術(shù)，2009，31(10):2516-2519.Sun Xiaohua，Liu Daxin，Xu Yuezhu，et al.Multi-scan KeyGraph implement model［J］.Systems Engineering and Electronics，2009，31(10):2516-2519.(in Chinese).

［14］孫曉華，劉大昕，徐悅竹，等.文本機(jī)會發(fā)現(xiàn)研究綜述［J］.計(jì)算機(jī)工程，2010，36(20):43-45.Sun Xiaohua，Liu Daxin，Xue Yuezhu，et al.Survey of text chance discovery research［J］.Computer Engineering，2010，36(20):43-45.(in Chinese).

［15］中科院計(jì)算所.ICTCLAS 2010版［EB/OL］.2013，http://www.ictclas.org.