徐國華

(太原大學(xué) 計(jì)算機(jī)中心,山西 太原 030032)

拓展的LCS算法展開的網(wǎng)頁關(guān)鍵詞挖掘研究*

徐國華*

(太原大學(xué) 計(jì)算機(jī)中心,山西 太原 030032)

以經(jīng)典的LCS算法為基礎(chǔ)，通過對(duì)其進(jìn)行分析，確定其不足之處，從而對(duì)其進(jìn)行適度拓展，使其協(xié)同運(yùn)算能力得到提升.在此基礎(chǔ)上，利用拓展的LCS算法對(duì)網(wǎng)頁關(guān)鍵詞快速挖掘展開分析，通過具體實(shí)例確定其有效性.

LCS；拓展；網(wǎng)頁；關(guān)鍵詞;挖掘

網(wǎng)頁信息的挖掘在互聯(lián)網(wǎng)時(shí)代的重要性越來越重要，實(shí)現(xiàn)網(wǎng)頁信息挖掘的快速、高效仍然是目前需要很好解決的一大問題[1～4].本文利用LCS算法，嘗試進(jìn)行網(wǎng)頁關(guān)鍵詞的挖掘研究.對(duì)LCS算法進(jìn)行了拓展，以此對(duì)網(wǎng)頁關(guān)鍵詞快速挖掘展開具體分析，通過具體實(shí)例確定其有效性.

1 LCS算法論述與問題描述

1.1 LCS算法論述

LCS是英文單詞Longest Common Subsequence的縮寫，其意是指最長(zhǎng)的公共子序列.舉例而言，對(duì)于兩個(gè)序列x1x2…xi…xn和y1y2…yj…ym而言，如果存在序列z1z2…zl…zq，使得序列z1z2…zl…zq中的每一個(gè)元素zl不僅包含在序列x1x2…xi…xn中，而且還包含在序列y1y2…yj…ym中.另外，不僅有z1=xi1，z2=xi2，…，zl=xi,l，…，zq=xi,q成立，還有z1=yj1，z2=yj2，…，zl=yj,l，…，zq=yj,q成立(其中，xis∈x1x2…xi…xn，yjt∈y1y2…yj…ym),則稱序列z1z2…zl…zq為序列x1x2…xi…xn和y1y2…yj…ym的公共子序列.如果不存在長(zhǎng)度超過序列z1z2…zl…zq長(zhǎng)度的序列，則稱序列z1z2…zl…zq為序列x1x2…xi…xn和y1y2…yj…ym的最長(zhǎng)公共子序列，即我們所說的LCS.

1.2 研究問題描述

本文的主要問題是如何利用LCS的特性進(jìn)行網(wǎng)頁關(guān)鍵詞的挖掘.具體說來，就是在不同的網(wǎng)頁內(nèi)容中尋找到最適合其特色的關(guān)鍵詞.對(duì)于該問題，我們可以將其轉(zhuǎn)換為兩個(gè)字符序列的最長(zhǎng)公共子序列問題，即LCS問題.以字符序列w1w2…wi…wn代表長(zhǎng)度為n的網(wǎng)頁內(nèi)容，以字符序列k1k2…kl…kv代表長(zhǎng)度為n的備選關(guān)鍵詞.如果字符序列k1k2…kl…kv為字符序列w1w2…wi…wn的真正關(guān)鍵詞，那么字符序列k1k2…kl…kv必為字符序列w1w2…wi…wn的LCS.同時(shí)，字符序列k1k2…kl…kv在字符序列w1w2…wi…wn中重復(fù)的次數(shù)必須達(dá)到閥值要求.通過此方法就可將一個(gè)備選關(guān)鍵詞最終確定為真正的關(guān)鍵詞.

下面，我們就采用LCS相關(guān)原理來進(jìn)行網(wǎng)頁關(guān)鍵詞的挖掘工作.

2 LCS算法的拓展及其在網(wǎng)頁關(guān)鍵詞挖掘中的具體應(yīng)用

2.1 LCS算法的拓展

在1.1中我們對(duì)LCS算法進(jìn)行了論述，對(duì)于該算法的具體實(shí)現(xiàn)以及對(duì)應(yīng)的優(yōu)缺點(diǎn)還缺乏認(rèn)識(shí)，現(xiàn)在我們就此問題進(jìn)行研究，并針對(duì)其不足給予改進(jìn)或者說是拓展.

LCS算法的傳統(tǒng)實(shí)現(xiàn)方法是采用矩陣分析[5,6]的方法實(shí)現(xiàn)，以序列x1x2…xi…xn和y1y2…yj…ym為例.我們將其對(duì)應(yīng)到一個(gè)n×m矩陣An×m，每一列按照自左至右的順序依次對(duì)應(yīng)字符x1,…,xi，…，xn，每一行按照自上向下的順序依次對(duì)應(yīng)字符y1，…，yj，…，ym.其具體對(duì)應(yīng)形式如下：

x1x2……xn

(1)

當(dāng)字符y1與字符x1一致時(shí)，對(duì)應(yīng)的矩陣元素a(1,1)取值為1；同理，由于字符y2與字符x2一致，對(duì)應(yīng)的矩陣元素a(2,2)取值為1，由于字符y2與字符x1不一致，對(duì)應(yīng)的矩陣元素a(2,1)取值為0.這樣我們只需判斷矩陣對(duì)角線上全部為1的序列，其就為L(zhǎng)CS的備選序列.對(duì)于n×n矩陣Bn×n而言，要將其轉(zhuǎn)換為僅僅包含數(shù)值0與數(shù)值1的矩陣，一共需要n×n次運(yùn)算；隨后在每一條對(duì)角線上進(jìn)行備選LCS挑選，最多需要進(jìn)行2×n×(n+1)/2次判斷，即可確定整個(gè)對(duì)角線上的備選LCS是否為真正的LCS.總體而言，需要O(2n2)次運(yùn)算，就可得到每一個(gè)備選LCS的重復(fù)次數(shù).該方法的最大優(yōu)點(diǎn)在于將LCS變?yōu)榭蓪?shí)現(xiàn)，缺點(diǎn)在于隨著字符數(shù)量的激增，運(yùn)算復(fù)雜度急速上升.如何有效地降低該算法的運(yùn)算復(fù)雜度，或者說是否存在并行運(yùn)算的方法來降低該算法的復(fù)雜度，就成為互聯(lián)網(wǎng)信息急速增長(zhǎng)的大環(huán)境下的迫切問題.針對(duì)該問題，我們嘗試對(duì)其進(jìn)行拓展，具體思路如下.

對(duì)于序列x1x2…xi…xn和y1y2…yj…yn而言，我們將其對(duì)應(yīng)到一個(gè)n×n矩陣Cn×n，每一列按照自左至右的順序依次對(duì)應(yīng)字符x1，…，xi，…xn，每一行按照自上向下的順序依次對(duì)應(yīng)字符y1，…，yj，…，yn.其具體對(duì)應(yīng)形式如下：

x1x2……xn

(2)

矩陣Cn×n中的各元素的取值方法與前述一致，不再贅述.此時(shí)，我們?nèi)绻麑⒕仃嘋n×n進(jìn)行二維空間的二等分，就得到了四個(gè)維數(shù)相同的子矩陣，其構(gòu)成如下：

(3)

其中C1,1、C1,2、C2,1、C2,2均為(n/2)×(n/2)矩陣.

(4)

其中D1,1、D1,2、D1,3、D2,1、D2,2、D2,3、D3,1、D3,2、D3,3均為(n/3)×(n/3)矩陣.

通過上述論證分析，我們明確了LCS算法的實(shí)現(xiàn)以及其優(yōu)勢(shì)與不足.在此基礎(chǔ)上，我們采用信息學(xué)相關(guān)理論對(duì)其進(jìn)行了拓展，使其運(yùn)算復(fù)雜度得到了分擔(dān)，具備了并行計(jì)算的基本條件.下面，我們就采用該拓展方法對(duì)網(wǎng)頁關(guān)鍵詞挖掘進(jìn)行實(shí)證應(yīng)用研究.

2.2 拓展的LCS算法在網(wǎng)頁關(guān)鍵詞挖掘中的具體應(yīng)用

隨著互聯(lián)網(wǎng)規(guī)模的急速膨脹，以文字形式出現(xiàn)的互聯(lián)網(wǎng)信息量也急速增加.如何針對(duì)這些網(wǎng)頁信息進(jìn)行有效的關(guān)鍵詞確定，從而提高對(duì)網(wǎng)頁信息的快速歸類與檢索就成為當(dāng)務(wù)之急.下面我們就以一個(gè)具體實(shí)例展開分析.

在現(xiàn)有的互聯(lián)網(wǎng)搜索引擎中，已經(jīng)有基本能夠覆蓋所有信息的關(guān)鍵詞信息，以序列{Keyi}p代表之.其中第i個(gè)關(guān)鍵詞用Keyi表示，一共有p個(gè)關(guān)鍵詞.當(dāng)前需要確定關(guān)鍵詞的網(wǎng)頁的文本信息內(nèi)容用序列c1c2…ci…ct表示，依照前面的方法進(jìn)行矩陣轉(zhuǎn)換.但是在轉(zhuǎn)換之前，我們需要將離散的關(guān)鍵詞序列轉(zhuǎn)化為連續(xù)的關(guān)鍵詞序列.具體的方法是在每一個(gè)關(guān)鍵詞之后用特殊字符“#”作為拼接詞將其連接.比如關(guān)鍵詞“Econometric”和關(guān)鍵詞“Math”用特殊字符“#” 拼接后就轉(zhuǎn)變?yōu)殛P(guān)鍵詞序列“Econometric#Math”.由此我們就可完成離散關(guān)鍵詞的連續(xù)化操作.隨后進(jìn)行矩陣轉(zhuǎn)換，得到下式：

c1c2……cn

(5)

其中變量ki代表通過關(guān)鍵詞拼接后得到的第i個(gè)關(guān)鍵詞；變量cj代表第i個(gè)網(wǎng)頁內(nèi)容信息.

考慮到當(dāng)前網(wǎng)頁內(nèi)容長(zhǎng)度與關(guān)鍵詞序列長(zhǎng)度，我們將矩陣進(jìn)行適當(dāng)?shù)牡确址纸?，分解為q×q個(gè)子矩陣.具體形式如下：

(6)

其中每一個(gè)子矩陣Gl,j,l∈[1,q],j∈[1,q]均為(n/q)×(n/q)矩陣.

對(duì)于上述矩陣(具體是指每一個(gè)子矩陣和母矩陣)進(jìn)行如前所述的數(shù)值賦值和判斷工作，并進(jìn)行銜接工作.從而得到每一個(gè)關(guān)鍵詞在網(wǎng)頁內(nèi)容中出現(xiàn)的次數(shù)，將此次數(shù)與之前設(shè)定的閥值進(jìn)行比對(duì)，當(dāng)次數(shù)超過閥值時(shí)，我們就將此備選關(guān)鍵詞轉(zhuǎn)化為針對(duì)當(dāng)前網(wǎng)頁內(nèi)容的具體關(guān)鍵詞；當(dāng)次數(shù)低于閥值時(shí)，我們就將此備選關(guān)鍵詞去除.通過此法，我們即可對(duì)復(fù)雜網(wǎng)頁內(nèi)容進(jìn)行精確和快速的分類，并以分類結(jié)果對(duì)外搜索時(shí)的關(guān)鍵詞進(jìn)行搜索判定.這一方面提高了對(duì)隨時(shí)產(chǎn)生的網(wǎng)頁內(nèi)容的快速歸類，另一方面，又為網(wǎng)頁信息的對(duì)外展示提供了關(guān)鍵的、準(zhǔn)確的、可靠的決策依據(jù).

3 結(jié) 語

本文首先對(duì)LCS算法進(jìn)行了拓展，確定了其優(yōu)勢(shì)以及不足.并針對(duì)發(fā)現(xiàn)的不足，通過與信息技術(shù)相結(jié)合，確定了對(duì)其進(jìn)行拓展的思路與方法.通過理論證明，不僅拓展了LCS算法，而且驗(yàn)證了拓展算法的有效性與協(xié)同處理性能.隨后，在此基礎(chǔ)上，針對(duì)網(wǎng)頁信息的特征展開實(shí)證分析，確定了復(fù)雜網(wǎng)頁的關(guān)鍵詞挖掘方法與實(shí)現(xiàn)過程.

[1] 岳冬冬.一種測(cè)度數(shù)據(jù)序列同步波動(dòng)強(qiáng)度的方法及應(yīng)用[J].統(tǒng)計(jì)與決策,2012(22):31-35.

[2] 王克富.基于數(shù)據(jù)挖掘技術(shù)的AFH客戶分類應(yīng)用研究[J].技術(shù)經(jīng)濟(jì)與管理研究,2012(11):13-17.

[3] 孫娜,郭延鋒.基于增量式學(xué)習(xí)的數(shù)據(jù)流實(shí)時(shí)分類模型[J].計(jì)算機(jī)工程與設(shè)計(jì),2012(11):17-22.

[4] 郭建,趙顯.一種基于圖像處理的快速自動(dòng)聚焦算法[J].湘潭大學(xué)自然科學(xué)學(xué)報(bào),2012，34(02)：22-25.

[5] EUGENIO C,DOMENICO T.Distributed data mining patterns and services: an architecture and experiments[J].Concurrency and Computation: Practice and Experience, 2012,24(15):1 751-1 774.

[6] ZHU X,MAHULE T, HAIMONTI D, et al.Peer-to-peer distributed text classifier learning in PADMINI[J].Statistical Analysis and Data Mining, 2012,5(5):446-462.

[7] CAO L.Actionable knowledge discovery and delivery[J].Wiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery, 2012(2):149-163.

[8] KANISHKA B, KAMALIKA D, KIRK B,et al.Scalable, asynchronous, distributed eigen monitoring of astronomy data streams[J].Statistical Analysis and Data Mining, 2011,4(3):336-352.

[9] MIRKO B.Contrast and change mining[J].Wiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery, 2011(3):215-230.

責(zé)任編輯：龍順潮

Using the Extended Method of LCS to Solve the Keywords Data Mining for Webpage in Internet

XUGuo-hua*

(The Computer Center of Taiyuan University,Taiyuan 030032 China)

According to the rapid expansion of Internet information under the webpage key words determine the operational efficiency is low problem started the research. In classic LCS algorithm as the research breakthrough, through carries on the thorough analysis, identify its shortcomings, thus carries on the moderate expansion, the collaborative operation capacity upgrade. On this basis, using the extended LCS algorithm Corps webpage key words fast mining expansion concrete research, through the concrete example of the effectiveness of the method, and summarize the research results.

LCS; extended; webpage; keywords; data mining

2014-04-11

山西省教育科學(xué)十二五規(guī)劃課題(GH-11139)

徐國華(1974— ),女，山西 忻州人，副教授.E-mail:bianji006@sina.com

TP393

A

1000-5900(2015)01-0107-04