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

徐國華

(太原大學 計算機中心,山西 太原 030032)

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

徐國華*

(太原大學 計算機中心,山西 太原 030032)

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

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

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

1 LCS算法論述與問題描述

1.1 LCS算法論述

LCS是英文單詞Longest Common Subsequence的縮寫，其意是指最長的公共子序列.舉例而言，對于兩個序列x1x2…xi…xn和y1y2…yj…ym而言，如果存在序列z1z2…zl…zq，使得序列z1z2…zl…zq中的每一個元素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的公共子序列.如果不存在長度超過序列z1z2…zl…zq長度的序列，則稱序列z1z2…zl…zq為序列x1x2…xi…xn和y1y2…yj…ym的最長公共子序列，即我們所說的LCS.

1.2 研究問題描述

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

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

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

2.1 LCS算法的拓展

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

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

x1x2……xn

(1)

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

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

x1x2……xn

(2)

矩陣Cn×n中的各元素的取值方法與前述一致，不再贅述.此時，我們?nèi)绻麑⒕仃嘋n×n進行二維空間的二等分，就得到了四個維數(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算法的實現(xiàn)以及其優(yōu)勢與不足.在此基礎(chǔ)上，我們采用信息學相關(guān)理論對其進行了拓展，使其運算復雜度得到了分擔，具備了并行計算的基本條件.下面，我們就采用該拓展方法對網(wǎng)頁關(guān)鍵詞挖掘進行實證應(yīng)用研究.

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

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

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

c1c2……cn

(5)

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

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

(6)

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

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

3 結(jié) 語

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

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

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

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

[4] 郭建,趙顯.一種基于圖像處理的快速自動聚焦算法[J].湘潭大學自然科學學報,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.

責任編輯：龍順潮

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

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

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

TP393

A

1000-5900(2015)01-0107-04