最好的搜索引擎開發交流社區 http://www.zhuayu.net
也可以加入qq群： 38707929
找不到數據挖掘的版塊, 而這個課題的建立是基于STUCTS的,所以發在這里也未嘗不可^_^.
好久沒寫blog了,由于之前對畢業設計的要求理解錯誤,導致研究方向發生了偏移. 在3月7號的時候導師開了一個會才知道要做的系統是一個聚類系統, 之前研究的使用訓練集產生分類器的方法是針對"自動歸類"的.
香港回來后(3月9~3月16), 開始了這個課題的研究, 這個過程中碰到種種困難. 比如vsm(向量空間模型), STC(后綴樹表示法)等等要涉及一些矩陣分解(對web網頁表示的降維), 基向量,特征值... 以前一直覺得學數學對軟件開發毫無用處, 現在得洗洗腦子了,因為以前接觸的多是web應用型項目,框架建好了,填填代碼而已.
很感謝陳黎飛博士, soulmachine, 在我學習的過程中,給予的指導.
過幾天就要交開題報告了, 所以我就先在這里總結一下我這幾天的學習心得. 一開始我看了幾篇陳博士給我的幾篇論文, 大概對web網頁聚類過程有了大概的了解.后來研究Carrot2(一個開源的聚類程序,讀者可以上網查詢相關信息,網址是project.carrot2.org),看的全是英文資料,比較的累,呵呵, 不夠Carrot2設計的真的很好,很容易看懂, 不過對幾個聚類算法(lingo, Fuzzyant...)還是要花一些功夫的
下面我分要點進行總結.
一. web網頁聚類基本流程和框架
這里引用的是Carrot2的一個框架, 這跟我研究的web網頁自動分類是一致的.
通過各種大型搜索引擎API獲得源數據(一般至少包括一個唯一的URL地址,網頁標題), 通過網頁清洗,分詞,提取特征項(降維作用),建立VSM, 構造STC進行聚類(如果你采用STC作為聚類算法), 聚類后就到了怎樣把聚類結果展現給用戶了, 這里有個很關鍵的問題是,如果讓用戶一看分類目錄的標題,就知道這個類里包含那方面的內容.
這里要補充說一下的是, Carrot2并沒有中文分詞功能,其默認的分詞功能往往不能盡如人意.本人打算以后用中科院的ICTCLAS分詞組件進行分詞.
二. 基本概念解釋
1. TF：（term frequency）用關鍵詞的次數除以網頁的總字數（在一篇特定網頁中）-------詞權值, 用于建立VSM
2. IDF（Inverse document frequency）：它的公式為ｌｏｇ（Ｄ／Ｄｗ）其中Ｄ是全部網頁數（假定一個關鍵詞 ｗ 在 Ｄｗ 個網頁中出現過）
-------詞權值, 用于建立VSM
3. TF/IDF(可以有改進,見論文TFRDF---詞頻相對文本頻率): 在 VSM中文檔被映射成由一組規范化特征項權值矢量 ,其中特征項權值常見的量化加權模型有:布爾模型、詞頻模型、TF IDF模型 ,我們使用效果較好的 TF IDF 模型。這種模型認為特征詞條在某文檔中的重要性與其在該文檔中出現的頻率成正比 ,與其在其他文檔中出現的頻率成反比。因此它主
要考慮兩個因素: ①詞語頻率 TF TermFrequency ,即詞語在(文檔中出現次數; ②詞語倒排文檔頻率 IDF InverseDocumentFrequency ,即詞語在文檔集合中分布的一種量化。.
4. 頻度：指一個詞（或其它語義單位）在文本中出現的次數越多，則所帶 的 信息量越大。
集中度：指在多類別的大量文本中，一個詞只在一類或少數幾類文本里出現，而在其它文本里不出現，則它所帶的信息量就大，對所在文本的類別的表示能力就強。
分散度：指在某一類文本中，一個詞在越多的文本中出現，即越分散，說明它信息量越大，對類別表示能力越強。
5.. 文檔頻率 DF、互信息 MI、信息增益 IG、期望交叉熵 CE、CHI 統計、文本證據權和優勢率、特征強度------一系列特征提取的方法(目的:降維)
6.歸一化(實際應用中各類別文本的長度很難一致，各類文本包含的字數、詞數可能差別會很大，這對詞頻會造成直接影響，因此通常對詞頻作歸一化處理。) 你在所有的數據中找出最大的那個數max 可以用matlab的max函數 在所有的數據中找出最小的那個數min 可以用matlab的min函數 然后把所有的數據這樣計算 (x-min)/(max-min) 這樣所有的數據都歸一化為0到1之間的數了
這對于模式識別是很重要的一環 無論你是用BP網、多層感知器、SVM
7 .Stopwords：詞“的”站了總詞頻的 80% 以上，而它對確定網頁的主題幾乎沒有用。我們稱這種詞叫“應刪除詞”（Stopwords)，也就是說在度量相關性是不應考慮它們的頻率。
8負熵:sdg (在google的數學之美系列里能找到)
熵：是表征熱力學系統的混亂度或者是無序度大小的物理量，主要描述的是
系統的穩定狀態的一個表征值。
熵包括高熵和低熵，其中“高熵”對系統是高混亂的或者是無序的狀態，“低熵”對系統是低混亂的或者是有序的狀態。
其中大多數書中主要講到的是“負熵流”，關于負熵流的概念我的理解是：外界向系統輸入能量，使系統降低的熵值超過系統內部產生的熵值的那部分熵值就是負熵流。負熵值使系統趨于平衡，穩定。
9.n元語法短語
一般來說，N-Gram模型就是假設當前詞的出現概率只同它前面的N-1個詞有關，或者說它是用前N-1個詞的出現概率去預測當前詞的出現概率(Markov Chain)。常用的N-Gram模型有uni-Gram (N=1、一元組)、bi-Gram(N=2、二元組)和tri-Gram (N=3、三元組)。
1. 傳統檢索系統以詞庫比對法斷出索引詞，則可稱為「以詞彙為主」
(word-based)的索引詞模式。
2. 中文系統中亦有「以字元為主」(character-based)的索引詞模式。
3. 「N-gram索引法」，N-gram為文件中任意N個連續字元，
如「中國社會」此一字串，
當N為２時將可產生
「中國」、「國社」、「社會」三個索引詞。如此可排除或降低
「字元法」中類似
「中國」與「國中」的字串順序問題，也可省去「詞彙法」中維護詞庫的煩惱。
10.一個矩陣被因式分解成兩個矩陣, 左矩陣U中所有列向量(稱為基向量).
一直沒搞懂基向量(那個紅坐標是怎么弄出來的)----該圖的背景可以看附件Clustering SearchResults with Carrot2 的第47頁
11. KNN(K-Nearest Neighbor)
KNN法即K最近鄰法，最初由Cover和Hart于1968年提出的，是一個理論上比較成熟的方法。該方法的思路非常簡單直觀：如果一個樣本在特征空間中的k個最相似(即特征空間中最鄰近)的樣本中的大多數屬于某一個類別，則該樣本也屬于這個類別。該方法在定類決策上只依據最鄰近的一個或者幾個樣本的類別來決定待分樣本所屬的類別。
KNN方法雖然從原理上也依賴于極限定理，但在類別決策時，只與極少量的相鄰樣本有關。因此，采用這種方法可以較好地避免樣本的不平衡問題。另外，由于KNN方法主要靠周圍有限的鄰近的樣本，而不是靠判別類域的方法來確定所屬類別的，因此對于類域的交叉或重疊較多的待分樣本集來說，KNN方法較其他方法更為適合。
該方法的不足之處是計算量較大，因為對每一個待分類的文本都要計算它到全體已知樣本的距離，才能求得它的K個最近鄰點。目前常用的解決方法是事先對已知樣本點進行剪輯，事先去除對分類作用不大的樣本。另外還有一種Reverse KNN法，能降低KNN算法的計算復雜度，提高分類的效率。
該算法比較適用于樣本容量比較大的類域的自動分類，而那些樣本容量較小的類域采用這種算法比較容易產生誤分。
12. SVM法
SVM法即支持向量機(Support Vector Machine)法，由Vapnik等人于1995年提出，具有相對優良的性能指標。該方法是建立在統計學習理論基礎上的機器學習方法。通過學習算法，SVM可以自動尋找出那些對分類有較好區分能力的支持向量，由此構造出的分類器可以最大化類與類的間隔，因而有較好的適應能力和較高的分準率。該方法只需要由各類域的邊界樣本的類別來決定最后的分類結果。
支持向量機算法的目的在于尋找一個超平面H(d),該超平面可以將訓練集中的數據分開，且與類域邊界的沿垂直于該超平面方向的距離最大，故SVM法亦被稱為最大邊緣(maximum margin)算法。待分樣本集中的大部分樣本不是支持向量，移去或者減少這些樣本對分類結果沒有影響，SVM法對小樣本情況下的自動分類有著較好的分類結果。
12. K-NN和SVM是基于向量空間模型(VSM)的最好的分類器,
14. 聚類的方法: 1. 基于圖論的方法,形成一個樣本間相似性矩陣, 根據閥值類確定類別; 二是基于種子的方法,先指定一個初識的類中心,其他的樣本的類別與最近的類中心相同; 3.聚類分裂法,將新的信息樣本作為一個查詢,與已經存在的類進行比較,尋求最佳匹配類作為其所屬的類別. 當然,還可以將聚類方法分為平面方法和層次方法,只是考慮的角度不同而已.
(以上12點,是我學習過程中摘記下來的,雖然已經過整理,但還是有些亂^_!!)
三. 畢業設計的目標
1. 一個可以運行的基于WEB的網頁自動分類系統(無監督): 其可以根據用戶輸入的查詢, 直接從goolge搜索引擎中查詢并獲得查詢結果,對查詢結果清洗后, 進行分詞,特征提取后,建立VSM模型,并用STC聚類算法進行聚類,并通過分類目錄的形式顯示給用戶.
2. 數據來源只針對搜索引擎返回的snippet, 并不獲取整個網頁
3. 處理文件格式為: a.純文本(無超鏈接,無格式)---plain text
b. 網頁(html, xml): 暫不考慮各種顏色信息,各種格式等的影響
暫不考慮DOC. PDF的文件格式
4. 擬適用中英文網頁
四. 設計難點
1. 中文分詞
2. 高維度的降維
3. 適用中英文查詢
4. 結果顯示的標簽提取問題
5. 分布式查詢的性能問題
五. 實現方法
1. 軟件平臺: myeclipse + tomcat + stucts + cvs
2. 測試工具: junit + jmeter
Ps:
1. 學習Carrot2可以到project.carrot2.org,有豐富的例子和介紹
2. 如果有些文件格式發不上來,我會發在我的論壇里 www.zhuayu.net
3. 本人也初次接觸這種帶些研究性質的項目,還望各位多多指教!
|