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