【文章內(nèi)容簡介】 問題二的建模與求解 模型 II 的分析 對于問題（ 2），通過對于通用中文搜索引擎的了解 [8]，發(fā)現(xiàn)按照信息搜集方法和服務提供方式的不同 ,大致可分為基于 Robot 的搜索引擎和基于 Director 的搜索引擎。但兩者都具有較大的片面性，前者查全率高但查準率較低，后者查準率高但查全率較低。因此 ,本文希望開發(fā)一種新型的搜索引擎即具有 Robot 更新及時、無須人工干預的特點 ,又具有 Dieroctr 信息準確的特點 ,這就是面向主題的、 基于多維數(shù)據(jù)的 中文人名搜索引擎。 模型 II 的建立與求解 模型 II 的具體建立過程如下： 構(gòu)建姓氏網(wǎng)頁數(shù)據(jù)集 （一）搜集并抓取所有與輸入姓氏相關(guān)的網(wǎng)頁 構(gòu)建中文人名數(shù)據(jù)庫（附錄 ） ,從而在搜索引擎中將所有與所輸入姓氏相關(guān)的網(wǎng)頁搜集并抓取下來 ,為組建多維數(shù)據(jù)方體奠定內(nèi)容基礎(chǔ)。 （二）去除與主題無關(guān)的噪聲數(shù)據(jù) 網(wǎng)頁中除了與所查找內(nèi)容相符的信息外，通常還包含很多“噪音”內(nèi)容，如與主題內(nèi)容無關(guān)的導航條、 廣告信息、版權(quán)信息以及調(diào)查問卷等內(nèi)容。因此，下一步操作為去除網(wǎng)頁中與主題無關(guān)的噪聲數(shù)據(jù)。 網(wǎng)頁是由若干內(nèi)容塊組成的 ,而內(nèi)容塊是由特定的標簽規(guī)劃出的 (稱之為容器標簽 ), 9 常用的容器標簽有 table、 tr、 p等。本文首先對網(wǎng)頁 HTML 規(guī)范中的標簽按照功能進行分類 ,進而提出更加適合網(wǎng)頁凈化的標簽樹的構(gòu)造方法 [10]。 由于網(wǎng)頁凈化是以內(nèi)容塊為單位進行保留和刪除 ,因此 ,依據(jù)容器標簽構(gòu)造標簽樹中的結(jié)點是較為合理的。而其它類型的標簽信息可以作為它所在 的內(nèi)容塊的屬性而存在。標簽樹構(gòu)造完成后 ,網(wǎng)頁凈化過程就變?yōu)閷撕灅渲薪Y(jié)點的剪裁。 （ 1）算法相關(guān)公式 根據(jù)以上分析 ,網(wǎng)頁凈化過程是在網(wǎng)頁內(nèi)部以內(nèi)容塊為單位進行重要性和相關(guān)性評價 ,而不是網(wǎng)頁間的比較。因此我們使用如下的特征項權(quán)值計算公式。 （ 1） 其中 ,BWeight 表示網(wǎng)頁中內(nèi)容塊的權(quán)值 ,它的值由一個內(nèi)容塊中的重要標簽來決定； BN 表示網(wǎng)頁中內(nèi)容塊的總數(shù)； BTfji 表示關(guān)鍵詞 j 出現(xiàn)在內(nèi)容塊 i 中的詞頻。 另外 ,我們采用的相似性計算公式是較為常用的計算對應向量的 inecos 距離。給定向量， ? ? ? ?xxxXxxx nnX ,2,1,21 ,, ?? ?? （ 2） 分析姓氏網(wǎng)頁數(shù)據(jù)集 網(wǎng)頁數(shù)據(jù)集的分析包括信息提取、姓氏文檔切分詞處理、補償式信息提取的主題文本分類、相似文檔的聚類和姓氏網(wǎng)頁多維數(shù)據(jù)集的構(gòu)建等。 （一）信息提取 由于我們所設計的中文人名搜索引擎的最終目標是實現(xiàn)人物職業(yè)、居住地址、工作單位的層次樹狀結(jié)果的顯示，因此 ,在對文檔進行了預處理也就是消除文檔噪音之后 ,首要任務就是在所處理的網(wǎng)頁文檔中將人物的職業(yè)、居住地址、工作單位三個屬性從文檔 10 中分離出來 ,為后續(xù)的工作奠定基礎(chǔ)。 定義 l:知識庫 D:由各個知 識表構(gòu)成。知識表是信息提取所需要的涉及到特定領(lǐng)域的詞典以及提取模式庫。 定義 2:姓氏網(wǎng)頁數(shù)據(jù)集 M:姓氏網(wǎng)頁數(shù)據(jù)集合是從 Inter上抓取包含姓氏的網(wǎng)頁構(gòu)建而來。 （ 1）建立知識庫 D； （ 2）根據(jù)搜索的中文人名 ,在上一步中抓取到的姓氏數(shù)據(jù)集合 M 中搜索 ,得到所有相關(guān)網(wǎng)頁內(nèi)容 ,定義網(wǎng)頁內(nèi)容集合為 },{ 21 nW ?? ； （ 3）對每一個 wj 進 行網(wǎng)頁去噪處理 ,得到凈化后的文本集合 },{ 21 ttt nT ?? ； （ 4）對每一個 Tj 進行分句 ,得到句子集合 },{ 21 sisisi nS ?? ； （ 5）根據(jù)文本分類標識庫 ,將文本集合 T 分為兩類 :個人介紹類 C1和個人活動類 C2。對句子集合 S進行文本分類判定 ,確定 S屬于 CX 類； （ 6）對句子 Sjj 進行分詞標注 ,根據(jù)標注詞性和相關(guān)知識庫從句子集合 S 中過濾掉不相關(guān)的句子 ,提取相關(guān)的句子集合為 },{ 21 csicsicsi mCS ?? ，其中 mn 或者 mn； （ 7）根據(jù)針對 CS 類的信息提取方法 ,對 CSj 進行信息提取 ,提取出關(guān)于人的屬性元組? ?CKAKJKBj , ,存入數(shù)據(jù)庫中。 （二）補償式信息提取的主題文本分類算法 定義 1：假設 TH是某個主題 , },{ 21 MMMM n?? 是主題 D的屬性集合 ,M為主題TH 的知識庫；主題可以按照某一屬性劃分 ,記做 )( MTHK MM jj ?? ； 劃分 ),}(,{ 21 n u l lMP MMMMMM ijjm ???? ?，構(gòu)成了 TH 的一個特定劃分 ,記為 PTH ,P 將主題 TH 劃分的等價類稱為知識 P的基本概念。 定義 2：關(guān)于人物主題的姓氏網(wǎng)頁文檔集 Q來自 WWW的搜索結(jié)果 ,M={職業(yè) ,居住地點 ,工作單位 ,身高 ,體重 ,膚色 ,頭發(fā) ,年齡 ,政治面貌 ......},構(gòu)成了主題人物的知識庫。通過信息 嫡對知 識簡化 ,針 對網(wǎng)絡 文檔的 特點 ,得到 了關(guān)于 人物 主題的 核知 11 識 : ? ??pcore {職業(yè)，居住地址，工作單位 }，這意味著通過 P 可以將關(guān)于人的主題的文檔進行分類。 定義 3 對于主題 文檔 D, ? ?A AAAA nD ,3,2,1 ?? 是文檔 D 擁有的屬性集 ,如果ADPcore ?)( ，則稱文檔 D 是可區(qū)分的，否則為不可區(qū)分的。 假設所有姓氏網(wǎng)頁文檔 U以 ? ??pcore {職業(yè)，居住地址，工作單位 }進行信息提取。將所有文檔分為可分辨文檔 UIND 和不可分辨文檔 UND ? ?UU NDINDU ?? 。對 U 標識其屬性號 ,對可分辨文檔 UIND 進行劃分 ,得到： ? ? },{ 21 cccU mIN D pc or e ??，即 m個等價類。 然后，用最鄰近學習算法計算。其具體計算方法為： （ 3） 其中， k 表示類 Cj 中文檔的個數(shù) ,VCj 表示文檔的特征失量 ,CCj 表示類 cj 的特征矢量。文本特征矢量采用 TF*ITF 計算 : VVVVtnttt?321 s ims ims ims ims ims ims ims ims imPPPnmnnmmcmcc????????21222211121121 ?? （ 4） 其中， ? 的運算法則為 VVVVsimckcktjtjjk ?? , )1,1( mknj ???? ，在矩陣中求出每行的最小值 ? ?simsim jkmkm in11m in ?? ，記取最小值的下標為 i ，也就是文本 tj 與 ci 最相似。 12 設定閾值 M1 ,若 Msim 11min ? ,則將其歸于 Ci 文檔類中 .并更改其 tj 的屬性標識為Ci 的屬性標識 ,補償一部分分類 。 （三）語句 詞條矩陣聚簇式動態(tài)增長聚類算法 通過補償式信息提取的主題文本分類算法得到了職業(yè)、居住地址、工作單位三個人物屬性的不同分類 ,然而還會存在部分人物屬性不完全的網(wǎng)頁無法被歸類到相應的劃分當中去。因此，我們就需要應用語句 詞條矩陣聚類算法 ,按照內(nèi)容聚類 ,將剩余的網(wǎng)頁聚集到相應的分類當中。下面 ,我們對這一算法做比較詳細的分析說明。 定義 1：假定有 d 篇文檔 ,由 n 個單詞構(gòu)成 ,aji 是矩陣的元素點 ,tji 是第 i 個單詞在文檔 j 中出現(xiàn)的次數(shù) ,即 TF。 di 是出現(xiàn)第 i 個單詞的文檔數(shù)目。那么 ,則有 : （ 5） 其中 ,我們用詞頻 TF和反向詞頻 IDF 的乘積 ,來描述單詞的權(quán)值 。 定義 2： 假定 d(x)