em演算法java

A. WEB超鏈分析演算法的WEB超鏈分析演算法

搜索引擎Google最初是斯坦福大學的博士研究生Sergey Brin和Lawrence Page實現的一個原型系統[2]，現在已經發展成為WWW上最好的搜索引擎之一。Google的體系結構類似於傳統的搜索引擎，它與傳統的搜索引擎最大的不同處在於對網頁進行了基於權威值的排序處理，使最重要的網頁出現在結果的最前面。Google通過PageRank元演算法計算出網頁的PageRank值，從而決定網頁在結果集中的出現位置，PageRank值越高的網頁，在結果中出現的位置越前。
2.1.1PageRank演算法
PageRank演算法基於下面2個前提：
前提1：一個網頁被多次引用，則它可能是很重要的；一個網頁雖然沒有被多次引用，但是被重要的網頁引用，則它也可能是很重要的；一個網頁的重要性被平均的傳遞到它所引用的網頁。這種重要的網頁稱為權威（Authoritive）網頁。
前提2：假定用戶一開始隨機的訪問網頁集合中的一個網頁，以後跟隨網頁的向外鏈接向前瀏覽網頁，不回退瀏覽，瀏覽下一個網頁的概率就是被瀏覽網頁的PageRank值。
簡單PageRank演算法描述如下：u是一個網頁，是u指向的網頁集合，是指向u的網頁集合，是u指向外的鏈接數，顯然=| | ，c是一個用於規范化的因子（Google通常取0.85），（這種表示法也適用於以後介紹的演算法）則u的Rank值計算如下：
這就是演算法的形式化描述，也可以用矩陣來描述此演算法，設A為一個方陣，行和列對應網頁集的網頁。如果網頁i有指向網頁j的一個鏈接，則，否則=0。設V是對應網頁集的一個向量，有V=cAV，V為A的特徵根為c的特徵向量。實際上，只需要求出最大特徵根的特徵向量，就是網頁集對應的最終PageRank值，這可以用迭代方法計算。
如果有2個相互指向的網頁a，b,他們不指向其它任何網頁，另外有某個網頁c，指向a，b中的某一個，比如a，那麼在迭代計算中，a，b的rank值不分布出去而不斷的累計。如下圖：
為了解決這個問題，Sergey Brin和Lawrence Page改進了演算法，引入了衰退因子E(u)，E(U)是對應網頁集的某一向量，對應rank的初始值，演算法改進如下：
其中，=1，對應的矩陣形式為V』=c(AV』+E)。
另外還有一些特殊的鏈接，指向的網頁沒有向外的鏈接。PageRank計算時，把這種鏈接首先除去，等計算完以後再加入，這對原來計算出的網頁的rank值影響是很小的。
Pagerank演算法除了對搜索結果進行排序外，還可以應用到其它方面，如估算網路流量，向後鏈接的預測器，為用戶導航等[2]。
2.1.2演算法的一些問題
Google是結合文本的方法來實現PageRank演算法的[2]，所以只返回包含查詢項的網頁，然後根據網頁的rank值對搜索到的結果進行排序，把rank值最高的網頁放置到最前面，但是如果最重要的網頁不在結果網頁集中，PageRank演算法就無能為力了，比如在 Google中查詢search engines，像Google，Yahoo，Altivisa等都是很重要的，但是Google返回的結果中這些網頁並沒有出現。 同樣的查詢例子也可以說明另外一個問題，Google，Yahoo是WWW上最受歡迎的網頁，如果出現在查詢項car的結果集中，一定會有很多網頁指向它們，就會得到較高的rank值， 事實上他們與car不太相關。
在PageRank演算法的基礎上，其它的研究者提出了改進的PageRank演算法。華盛頓大學計算機科學與工程系的Matthew Richardson和Pedro Dominggos提出了結合鏈接和內容信息的PageRank演算法，去除了PageRank演算法需要的前提2，增加考慮了用戶從一個網頁直接跳轉到非直接相鄰的但是內容相關的另外一個網頁的情況[3]。斯坦大學計算機科學系Taher Haveliwala提出了主題敏感（Topic-sensitive）PageRank演算法[4]。斯坦福大學計算機科學系Arvind Arasu等經過試驗表明，PageRank演算法計算效率還可以得到很大的提高[22]。 PageRank演算法中對於向外鏈接的權值貢獻是平均的，也就是不考慮不同鏈接的重要性。而WEB的鏈接具有以下特徵：
1.有些鏈接具有注釋性，也有些鏈接是起導航或廣告作用。有注釋性的鏈接才用於權威判斷。
2.基於商業或競爭因素考慮，很少有WEB網頁指向其競爭領域的權威網頁。
3.權威網頁很少具有顯式的描述，比如Google主頁不會明確給出WEB搜索引擎之類的描述信息。
可見平均的分布權值不符合鏈接的實際情況[17]。J. Kleinberg[5]提出的HITS演算法中引入了另外一種網頁，稱為Hub網頁，Hub網頁是提供指向權威網頁鏈接集合的WEB網頁，它本身可能並不重要，或者說沒有幾個網頁指向它，但是Hub網頁確提供了指向就某個主題而言最為重要的站點的鏈接集合，比一個課程主頁上的推薦參考文獻列表。一般來說，好的Hub網頁指向許多好的權威網頁；好的權威網頁是有許多好的Hub網頁指向的WEB網頁。這種Hub與Authoritive網頁之間的相互加強關系，可用於權威網頁的發現和WEB結構和資源的自動發現，這就是Hub/Authority方法的基本思想。
2.2.1HITS演算法
HITS（Hyperlink－Inced Topic Search）演算法是利用Hub/Authority方法的搜索方法，演算法如下：將查詢q提交給傳統的基於關鍵字匹配的搜索引擎．搜索引擎返回很多網頁，從中取前n個網頁作為根集(root set)，用S表示。S滿足如下3個條件：
1．S中網頁數量相對較小
2．S中網頁大多數是與查詢q相關的網頁
3．S中網頁包含較多的權威網頁。
通過向S中加入被S引用的網頁和引用S的網頁將S擴展成一個更大的集合T．
以T中的Hub網頁為頂點集Vl，以權威網頁為頂點集V2，Vl中的網頁到V2中的網頁的超鏈接為邊集E，形成一個二分有向圖SG=(V1，V2，E)。對V1中的任一個頂點v，用h(v)表示網頁v的Hub值，對V2中的頂點u，用a(u)表示網頁的Authority值。開始時h(v)=a(u)=1，對u執行I操作修改它的a(u)，對v執行O操作修改它的h(v)，然後規范化a（u），h（v），如此不斷的重復計算下面的操作I，O，直到a（u），h（v）收斂。（證明此演算法收斂可見）
I 操作： （1） O操作： （2）
每次迭代後需要對a(u),h(v)進行規范化處理：
式(1)反映了若一個網頁由很多好的Hub指向，則其權威值會相應增加(即權威值增加為所有指向它的網頁的現有Hub值之和)。式(2)反映了若一個網頁指向許多好的權威頁，則Hub值也會相應增加(即Hub值增加為該網頁鏈接的所有網頁的權威值之和)。
和PageRank演算法一樣，可以用矩陣形式來描述演算法，這里省略不寫。
HITS演算法輸出一組具有較大Hub值的網頁和具有較大權威值的網頁。
2.2.2HITS的問題
HITS演算法有以下幾個問題：
1．實際應用中，由S生成T的時間開銷是很昂貴的，需要下載和分析S中每個網頁包含的所有鏈接，並且排除重復的鏈接。一般T比S大很多，由T生成有向圖也很耗時。需要分別計算網頁的A/H值，計算量比PageRank演算法大。
2．有些時候，一主機A上的很多文檔可能指向另外一台主機B上的某個文檔，這就增加了A上文檔的Hub值和B上文檔的Authority，相反的情況也如此。HITS是假定某一文檔的權威值是由不同的單個組織或者個人決定的，上述情況影響了A和B上文檔的Hub和Authority值[7]。
3．網頁中一些無關的鏈接影響A，H值的計算。在製作網頁的時候，有些開發工具會自動的在網頁上加入一些鏈接，這些鏈接大多是與查詢主題無關的。同一個站點內的鏈接目的是為用戶提供導航幫助，也與查詢主題不甚無關，還有一些商業廣告，贊助商和用於友情交換的鏈接，也會降低HITS演算法的精度[8]。
4．HITS演算法只計算主特徵向量，也就是只能發現T集合中的主社區（Community），忽略了其它重要的社區[12]。事實上，其它社區可能也非常重要。
5．HITS演算法最大的弱點是處理不好主題漂移問題（topic drift）[7,8]，也就是緊密鏈接TKC（Tightly-Knit Community Effect）現象[8]。如果在集合T中有少數與查詢主題無關的網頁，但是他們是緊密鏈接的，HITS演算法的結果可能就是這些網頁，因為HITS只能發現主社區，從而偏離了原來的查詢主題。下面討論的SALSA演算法中解決了TKC問題。
6．用HITS進行窄主題查詢時，可能產生主題泛化問題[5,9]，即擴展以後引入了比原來主題更重要的新的主題，新的主題可能與原始查詢無關。泛化的原因是因為網頁中包含不同主題的向外鏈接，而且新主題的鏈接具有更加的重要性。
2.2.3HITS的變種
HITS演算法遇到的問題，大多是因為HITS是純粹的基於鏈接分析的演算法，沒有考慮文本內容，繼J. Kleinberg提出HITS演算法以後，很多研究者對HITS進行了改進，提出了許多HITS的變種演算法，主要有：
2.2.3.1Monika R. Henzinger和Krishna Bharat對HITS的改進
對於上述提到的HITS遇到的第2個問題，Monika R. Henzinger和Krishna Bharat在[7]中進行了改進。假定主機A上有k個網頁指向主機B上的某個文檔d，則A上的k個文檔對B的Authority貢獻值總共為1,每個文檔貢獻1/k，而不是HITS中的每個文檔貢獻1，總共貢獻k。類似的，對於Hub值，假定主機A上某個文檔t指向主機B上的m個文檔，則B上m個文檔對t的Hub值總共貢獻1，每個文檔貢獻1/m。I，O操作改為如下
I 操作：
O操作：
調整後的演算法有效的解決了問題2，稱之為imp演算法。
在這基礎上，Monika R. Henzinger和Krishna Bharat還引入了傳統信息檢索的內容分析技術來解決4和5，實際上也同時解決了問題3。具體方法如下，提取根集S中的每個文檔的前1000個詞語，串連起來作為查詢主題Q，文檔Dj和主題Q的相似度按如下公式計算：
，，=項i在查詢Q中的出現次數，
=項i在文檔Dj中的出現次數，IDFi是WWW上包含項i的文檔數目的估計值。
在S擴展到T後，計算每個文檔的主題相似度，根據不同的閾值（threshold）進行刷選，可以選擇所有文檔相似度的中值，根集文檔相似度的中值，最大文檔相似度的分數，如1/10，作為閾值。根據不同閾值進行處理，刪除不滿足條件的文檔，再運行imp演算法計算文檔的A/H值，這些演算法分別稱為med，startmed，maxby10。
在此改進的演算法中，計算文檔的相似度時間開銷會很大。
2.2.3.2ARC演算法
IBM Almaden研究中心的Clever工程組提出了ARC（Automatic Resource Compilation）演算法，對原始的HITS做了改進，賦予網頁集對應的連結矩陣初值時結合了鏈接的錨（anchor）文本，適應了不同的鏈接具有不同的權值的情況。
ARC演算法與HITS的不同主要有以下3點：
1．由根集S擴展為T時，HITS只擴展與根集中網頁鏈接路徑長度為1的網頁，也就是只擴展直接與S相鄰的網頁，而ARC中把擴展的鏈接長度增加到2，擴展後的網頁集稱為增集（Augment Set）。
2．HITS演算法中，每個鏈接對應的矩陣值設為1，實際上每個鏈接的重要性是不同的，ARC演算法考慮了鏈接周圍的文本來確定鏈接的重要性。考慮鏈接p－>q，p中有若干鏈接標記，文本1<a href=」q」>錨文本</a>文本2，設查詢項t在文本1，錨文本，文本2，出現的次數為n（t），則w（p，q）=1+n（t）。文本1和文本2的長度經過試驗設為50位元組[10]。構造矩陣W，如果有網頁i－>j ，Wi,j=w（i，j），否則Wi,j=0，H值設為1，Z為W的轉置矩陣，迭代執行下面3個的操作：
（1）A=WH （2）H=ZA （3）規范化A，H
3．ARC演算法的目標是找到前15個最重要的網頁，只需要A/H的前15個值相對大小保持穩定即可，不需要A/H整個收斂，這樣2中迭代次數很小就能滿足，[10]中指出迭代5次就可以，所以ARC演算法有很高的計算效率，開銷主要是在擴展根集上。
2.2.3.3Hub平均（ Hub－Averaging－Kleinberg）演算法
Allan Borodin等在[11]指出了一種現象，設有M+1個Hub網頁，M+1個權威網頁，前M個Hub指向第一個權威網頁，第M+1個Hub網頁指向了所有M+1個權威網頁。顯然根據HITS演算法，第一個權威網頁最重要，有最高的Authority值，這是我們希望的。但是，根據HITS，第M+1個Hub網頁有最高的Hub值，事實上，第M+1個Hub網頁既指向了權威值很高的第一個權威網頁，同時也指向了其它權威值不高的網頁，它的Hub值不應該比前M個網頁的Hub值高。因此，Allan Borodin修改了HITS的O操作：
O操作： ，n是(v,u)的個數
調整以後，僅指向權威值高的網頁的Hub值比既指向權威值高又指向權威值低的網頁的Hub值高，此演算法稱為Hub平均（Hub－Averaging－Kleinberg）演算法。
2.2.3.4閾值（Threshhold—Kleinberg）演算法
Allan Borodin等在[11]中同時提出了3種閾值控制的演算法，分別是Hub閾值演算法，Authority閾值演算法，以及結合2者的全閾值演算法。
計算網頁p的Authority時候，不考慮指向它的所有網頁Hub值對它的貢獻，只考慮Hub值超過平均值的網頁的貢獻，這就是Hub閾值方法。
Authority閾值演算法和Hub閾值方法類似，不考慮所有p指向的網頁的Authority對p的Hub值貢獻，只計算前K個權威網頁對它Hub值的貢獻，這是基於演算法的目標是查找最重要的K個權威網頁的前提。
同時使用Authority閾值演算法和Hub閾值方法的演算法，就是全閾值演算法 PageRank演算法是基於用戶隨機的向前瀏覽網頁的直覺知識，HITS演算法考慮的是Authoritive網頁和Hub網頁之間的加強關系。實際應用中，用戶大多數情況下是向前瀏覽網頁，但是很多時候也會回退瀏覽網頁。基於上述直覺知識，R. Lempel和S. Moran提出了SALSA（Stochastic Approach for Link-Structure Analysis）演算法[8]，考慮了用戶回退瀏覽網頁的情況，保留了PageRank的隨機漫遊和HITS中把網頁分為Authoritive和Hub的思想，取消了Authoritive和Hub之間的相互加強關系。
具體演算法如下：
1．和HITS演算法的第一步一樣，得到根集並且擴展為網頁集合T，並除去孤立節點。
2．從集合T構造無向圖G』=（Vh，Va，E）
Vh = { sh | s∈C and out-degree(s) > 0 } ( G』的Hub邊).
Va = { sa | s∈C and in-degree(s) > 0 } (G』的Authority邊).
E= { (sh , ra) |s－>r in T}
這就定義了2條鏈，Authority鏈和Hub鏈。
3．定義2條馬爾可夫鏈的變化矩陣，也是隨機矩陣，分別是Hub矩陣H，Authority矩陣A。
4．求出矩陣H，A的主特徵向量，就是對應的馬爾可夫鏈的靜態分布。
5．A中值大的對應的網頁就是所要找的重要網頁。
SALSA演算法沒有HITS中相互加強的迭代過程，計算量遠小於HITS。SALSA演算法只考慮直接相鄰的網頁對自身A/H的影響，而HITS是計算整個網頁集合T對自身AH的影響。
實際應用中，SALSA在擴展根集時忽略了很多無關的鏈接，比如
1．同一站點內的鏈接，因為這些鏈接大多隻起導航作用。
2．CGI 腳本鏈接。
3．廣告和贊助商鏈接。
試驗結果表明，對於單主題查詢java，SALSA有比HITS更精確的結果，對於多主題查詢abortion，HITS的結果集中於主題的某個方面，而SALSA演算法的結果覆蓋了多個方面，也就是說，對於TKC現象，SALSA演算法比HITS演算法有更高的健壯性。
2.3.1BFS（Backword Forward Step）演算法
SALSA演算法計算網頁的Authority值時，只考慮網頁在直接相鄰網頁集中的受歡迎程度，忽略其它網頁對它的影響。HITS演算法考慮的是整個圖的結構，特別的，經過n步以後，網頁i的Authority的權重是，為離開網頁i的的路徑的數目，也就是說網頁j<>i，對i的權值貢獻等於從i到j的路徑的數量。如果從i到j包含有一個迴路，那麼j對i的貢獻將會呈指數級增加，這並不是演算法所希望的，因為迴路可能不是與查詢相關的。
因此，Allan Borodin等[11]提出了BFS（Backward Forward Step）演算法，既是SALSA的擴展情況，也是HITS的限制情況。基本思想是，SALSA只考慮直接相鄰網頁的影響，BFS擴展到考慮路徑長度為n的相鄰網頁的影響。在BFS中，被指定表示能通過路徑到達i的結點的集合，這樣j對i的貢獻依賴就與j到i的距離。BFS採用指數級降低權值的方式，結點i的權值計算公式如下：
=|B(i)|+ |BF(i)| +|BFB(i)|+……+||
演算法從結點i開始，第一步向後訪問，然後繼續向前或者向後訪問鄰居，每一步遇到新的結點加入權值計算，結點只有在第一次被訪問時加入進去計算。 D.Cohn and H.Chang提出了計算Hub和Authority的統計演算法PHITS（Probabilistic analogue of the HITS）[12]。他們提出了一個概率模型，在這個模型裡面一個潛在的因子或者主題z影響了文檔d到文檔c的一個鏈接，他們進一步假定，給定因子z，文檔c的條件分布P(c|z)存在，並且給定文檔d，因子z的條件分布P（z|d）也存在。
P(d) P(z|d) P(c|z) ，其中
根據這些條件分布，提出了一個可能性函數（likelihood function）L,
，M是對應的連結矩陣
然後，PHITS演算法使用Dempster等提出的EM演算法[20]分配未知的條件概率使得L最大化，也就是最好的解釋了網頁之間的鏈接關系。演算法要求因子z的數目事先給定。Allan Borodin指出，PHITS中使用的EM演算法可能會收斂於局部的最大化，而不是真正的全局最大化[11]。D. Cohn和T. Hofmann還提出了結合文檔內容和超鏈接的概率模型[13]。 Allan Borodin等提出了完全的貝葉斯統計方法來確定Hub和Authoritive網頁[11]。假定有M個Hub網頁和N個Authority網頁，可以是相同的集合。每個Hub網頁有一個未知的實數參數，表示擁有超鏈的一般趨勢，一個未知的非負參數，表示擁有指向Authority網頁的鏈接的趨勢。每個Authoritive網頁j，有一個未知的非負參數，表示j的Authority的級別。
統計模型如下，Hub網頁i到Authority網頁j的鏈接的先驗概率如下給定：
P（i，j）=Exp（+）/（1+Exp（+））
Hub網頁i到Authority網頁j沒有鏈接時，P（i，j）=1/（1+Exp（+））
從以上公式可以看出，如果很大（表示Hub網頁i有很高的趨勢指向任何一個網頁），或者和都很大（表示i是個高質量Hub，j是個高質量的Authority網頁），那麼i－>j的鏈接的概率就比較大。
為了符合貝葉斯統計模型的規范，要給2M+N個未知參數（，，）指定先驗分布，這些分布應該是一般化的，不提供信息的，不依賴於被觀察數據的，對結果只能產生很小影響的。Allan Borodin等在中指定滿足正太分布N（μ，）,均值μ=0，標准方差δ=10，指定和滿足Exp（1）分布，即x>=0，P(>=x)=P(>=x)=Exp（－x）。
接下來就是標準的貝葉斯方法處理和HITS中求矩陣特徵根的運算。
2.5.1簡化的貝葉斯演算法
Allan Borodin同時提出了簡化的上述貝葉斯演算法，完全除去了參數，也就不再需要正太分布的參數μ，δ了。計算公式變為：P（i，j）=/（1+），Hub網頁到Authority網頁j沒有鏈接時，P（i，j）=1/(1+)。
Allan Borodin 指出簡化的貝葉斯產生的效果與SALSA演算法的結果非常類似。 上面的所有演算法，都是從查詢項或者主題出發，經過演算法處理，得到結果網頁。多倫多大學計算機系Alberto Mendelzon, Davood Rafiei提出了一種反向的演算法，輸入為某個網頁的URL地址，輸出為一組主題，網頁在這些主題上有聲望（repution）[16]。比如輸入，www.gamelan.com，可能的輸出結果是「java」，具體的系統可以訪問htpp://www.cs.toronto.e/db/topic。
給定一個網頁p，計算在主題t上的聲望，首先定義2個參數，滲透率和聚焦率，簡單起見，網頁p包含主題項t，就認為p在主題t上。
是指向p而且包含t的網頁數目，是指向p的網頁數目，是包含t的網頁數目。結合非條件概率，引入，，是WEB上網頁的數目。P在t上的聲望計算如下：
指定是既指向p有包含t的概率，即，顯然有
我們可以從搜索引擎（如Altavista）的結果得到，, ,WEB上網頁的總數估計值某些組織會經常公布，在計算中是個常量不影響RM的排序，RM最後如此計算：
給定網頁p和主題t，RM可以如上計算，但是多數的情況的只給定網頁p，需要提取主題後計算。演算法的目標是找到一組t，使得RM（p，t）有較大的值。TOPIC系統中是抽取指向p的網頁中的錨文本的單詞作為主題（上面已經討論過錨文本能很好描述目標網頁，精度很高），避免了下載所有指向p的網頁，而且RM（p，t）的計算很簡單，演算法的效率較高。主題抽取時，還忽略了用於導航、重復的鏈接的文本，同時也過濾了停止字（stop word），如「a」，「the」，「for」，「in」等。
Reputation演算法也是基於隨機漫遊模型的（random walk），可以說是PageRank和SALSA演算法的結合體。
3.鏈接演算法的分類及其評價
鏈接分析演算法可以用來提高搜索引擎的查詢效果，可以發現WWW上的重要的社區，可以分析某個網站的拓撲結構，聲望，分類等，可以用來實現文檔的自動分類等。歸根結底，能夠幫助用戶在WWW海量的信息裡面准確找到需要的信息。這是一個正在迅速發展的研究領域。
上面我們從歷史的角度總結了鏈接分析演算法的發展歷程，較為詳細的介紹了演算法的基本思想和具體實現，對演算法的存在的問題也做了討論。這些演算法有的處於研究階段，有的已經在具體的系統實現了。這些演算法大體可以分為3類，基於隨機漫遊模型的，比如PageRank，Repution演算法，基於Hub和Authority相互加強模型的，如HITS及其變種，基於概率模型的，如SALSA，PHITS，基於貝葉斯模型的，如貝葉斯演算法及其簡化版本。所有的演算法在實際應用中都結合傳統的內容分析技術進行了優化。一些實際的系統實現了某些演算法，並且獲得了很好的效果，Google實現了PageRank演算法，IBM Almaden Research Center 的Clever Project實現了ARC演算法，多倫多大學計算機系實現了一個原型系統TOPIC，來計算指定網頁有聲望的主題。
AT&T香農實驗室的Brian Amento在指出，用權威性來評價網頁的質量和人類專家評價的結果是一致的，並且各種鏈接分析演算法的結果在大多數的情況下差別很小[15]。但是，Allan Borodin也指出沒有一種演算法是完美的，在某些查詢下，結果可能很好，在另外的查詢下，結果可能很差[11]。所以應該根據不同查詢的情況，選擇不同的合適的演算法。
基於鏈接分析的演算法，提供了一種衡量網頁質量的客觀方法，獨立於語言，獨立於內容，不需人工干預就能自動發現WEB上重要的資源，挖掘出WEB上重要的社區，自動實現文檔分類。但是也有一些共同的問題影響著演算法的精度。
1．根集的質量。根集質量應該是很高的，否則，擴展後的網頁集會增加很多無關的網頁，產生主題漂移，主題泛化等一系列的問題，計算量也增加很多。演算法再好，也無法在低質量網頁集找出很多高質量的網頁。
2．噪音鏈接。WEB上不是每個鏈接都包含了有用的信息，比如廣告，站點導航，贊助商，用於友情交換的鏈接，對於鏈接分析不僅沒有幫助，而且還影響結果。如何有效的去除這些無關鏈接，也是演算法的一個關鍵點。
3．錨文本的利用。錨文本有很高的精度，對鏈接和目標網頁的描述比較精確。上述演算法在具體的實現中利用了錨文本來優化演算法。如何准確充分的利用錨文本，對演算法的精度影響很大。
4．查詢的分類。每種演算法都有自身的適用情況，對於不同的查詢，應該採用不同的演算法，以求獲得最好的結果。因此，對於查詢的分類也顯得非常重要。
結束語：當然，這些問題帶有很大的主觀性，比如，質量不能精確的定義，鏈接是否包含重要的信息也沒有有效的方法能准確的判定，分析錨文本又涉及到語義問題，查詢的分類也沒有明確界限。如果演算法要取得更好的效果，在這幾個方面需要繼續做深入的研究，相信在不久的將來會有更多的有趣和有用的成果出現。

B. mahout topic模型怎麼使用

利用sqoop將數據從MySQL導入到HDFS中,利用mahout的LDA的cvb實現對輸入數據進行聚類,並將結果更新到資料庫中。數據流向圖如下

mahout演算法分析

輸入數據格式
為<IntegerWritable, VectorWritable>的matrix矩陣,key為待聚類文本的數字編號，value為待聚類文本的單詞向量Vector, Vector的index為單詞在字典中的編號, value為TFIDF值。

演算法相關參數詳解(不包含hadoop運行參數)
項目中所有參數設置均與mahout-0.9目錄下的examples/bin/cluster-reuters.sh的147-172行設置一樣，即
$SCOUT cvb -i ${WORK_DIR}/${ROWID_MATRIX_DIR}/matrix -o ${WORK_DIR}/${LDA_DIR} -k 20 -ow -x 20 -dict ${WORK_DIR}/${DICTIONARY_FILES} -dt ${WORK_DIR}/${LDA_TOPICS_DIR} -mt ${WORK_DIR}/${LDA_MODEL_DIR}

input -- 輸入數據的hdfs路徑,這里是/home/hadoop-user/scout_workspace/scout/dataset/reuters-out-matrix-debug/matrix
dt -- 文檔主題輸出路徑,保存了每個文檔的相應topic的概率,這里是/home/hadoop-user/scout_workspace/scout/dataset/reuters-lda-topics
mt -- model的路徑,這里是/home/hadoop-user/scout_workspace/scout/dataset/reuters-lda-debug
k -- number of topics to learn,這里設置成20
x -- 模型迭代次數,也就是需要多少次迭代來生成最後的Model,默認值20
seed -- Random seed,生成初始readModel時的種子,默認值System.nanoTime() % 10000
dict -- 字典路徑,這里是/home/hadoop-user/scout_workspace/scout/dataset/reuters-out-seqdir-sparse-lda/dictionary.file-*
a -- Smoothing for document/topic distribution, document/topic分布的平滑系數,默認為1.0E-4
e -- Smoothing for topic/term distribution, topic/term分布的平滑系數,默認為1.0E-4
關於a和e,根據描述,a和e的合適取值為k/50(k為topic數量),但是這個網頁還保留著mahout ldatopics的命令介紹,而mahout 0.8,0.9均沒有該命令,推測應該是比較陳舊的內容,因此還是根據cluster-reuters.sh中的設置來，也就是採取默認值。
mipd -- 這個參數非常重要，對於每個文檔程序是先用RandomSeed來生成一個初始的readModel然後進行mipd次迭代，算出最終的model進行更新，這里選默認值10次

LDA演算法程序分析

演算法的大致流程如下

1.解析參數與Configuration設置

2.讀取Model(第一次運行時沒有這個過程)
如果hfds上面已經有部分model，那麼程序將讀取最後一個model，並以這個model作為初始readModel來繼續進行演算法迭代，也就是說有類似於斷電-重啟的機制

3.運行演算法迭代(Mapper過程)生成LDA模型
這個過程是最為復雜的階段，許多地方我也不是很明白，我將盡最大努力進行解釋
首先分析Mapper,即CachingCVB0Mapper,顧名思義就是能夠緩存的Mapper，表現在其readModel的選取上面，如果目錄裡面不存在任何model則用RandomSeed初始化一個readModel，否則讀取最近的一個model。程序將model劃分為readModel和writeModel，這兩個都是TopicModel類，並由ModelTrainer來進行調度和管理

CachingCVB0Mapper整個過程如下圖所示(清晰大圖見附件)

在上面這個整體框架下,mahout程序應用了CVB0 Algorithm來計算LDA模型, 在map過程中通過對向量docTopic和矩陣docTopicModel的反復迭代求解，算出每個document的docTopicModel並且在update writeModel階段將docTopicModel矩陣進行向量的相加操作，經歷完所有的map過程後得到整個corpus的docTopicModel矩陣，最終在cleanup過程中將topic的index作為key，矩陣docTopicModel作為value寫入rece。該過程涉及到的演算法如下所示

CVB0演算法分析圖解(清晰大圖見附件)

4.利用生成的LDA模型推導出topic的概率分布

演算法總結
可以看出演算法本質上面就是bayes公式和EM演算法的結合
E過程就是首先假定一個均勻分布且歸一化的topic概率分布向量docTopics，利用該值通過貝葉斯公式算出單詞 - 主題的概率分布矩陣 docTopicModel(見CVB0演算法分析圖解中的第一步)

M過程就是根據生成的docTopicModel進行CVB0演算法分析圖解中的2,3,4,5步重新計算得到新的docTopics

然後反復重復 E - M 過程n次，得到收斂後的docTopics和docTopicModel，其中docTopicModel可以用於lda模型的更新，而docTopics就是我們聚類需要的topic概率分布向量

演算法後記
幾點問題還沒有得到解決
1.在mahout中是按照下面的式子計算docTopicModel的
double termTopicLikelihood =
(topicTermRow.get(termIndex) + eta) * (topicWeight + alpha)/ (topicSum + eta * numTerms);
疑問就是該式子比貝葉斯公式添加了幾個平滑系數項，這樣寫的理論依據在哪裡，來源於哪篇著作或者論文，平滑系數eta和alpha分別是代表什麼含義，如何選取這兩個系數。
2.CVB0演算法分析圖解中第2步進行歸一化的理論依據，即為什麼要進行歸一化
3.update writeModel過程中對於topicTermCounts的計算
即為什麼要在每次map時候對p(topic | term)進行累加，還沒有完全想明白

項目運行環境
hadoop-1.2.1
sqoop-1.4.4
mahout-0.9
關於環境的安裝部署請參考相關文章，這里不多加贅述。上面三個軟體在我本機的都是部署在/home/hadoop-user/mahout_workspace/目錄下。另外自己寫的scout項目部署在/home/hadoop-user/scout_workspace/目錄下

項目代碼
項目代碼已經放到Github上有興趣的同學可以下載下來看下，重點查看bin目錄下的腳本文件以及driver,export,analyzer等幾個包下的java文件

整個項目架構分析
該項目的初始數據保存在MySQL中, 演算法分析需要map/rece過程以及hdfs文件系統的參與, 最後將結果更新至MySQL,整個過程如圖所示

C. 誰做過 EM演算法 java實現

在基本配置(Basic Configuration)界面中，我們可以給以下選項設置參數：

默認的語言(Default Language)給安裝過程和操作系統指定默認的語言。

鍵盤(Keyboard) 設置默認的鍵盤，通常要與語言相對應。

時區(Time Zone)把計算機的硬體時鍾設置為utc的原子時間，後者即為格林威治標准時間。

超級系統管理員密碼(root Password)指定超級系統管理員的密碼，可能需要加密。

D. 誰做過 EM演算法 java實現

參考：

packagenlp;
/**
*@authorOrisun
*date2011-10-22
*/
importjava.util.ArrayList;

publicclassBaumWelch{

intM;//隱藏狀態的種數
intN;//輸出活動的種數
double[]PI;//初始狀態概率矩陣
double[][]A;//狀態轉移矩陣
double[][]B;//混淆矩陣

ArrayList<Integer>observation=newArrayList<Integer>();//觀察到的集合
ArrayList<Integer>state=newArrayList<Integer>();//中間狀態集合
int[]out_seq={2,1,1,1,2,2,2,2,2,1,1,1,1,2,2,2,2,1,1,
1,1,1,2,2,2,1,1,1,1,1,2,1};//測試用的觀察序列
int[]hidden_seq={1,1,1,1,2,2,2,2,2,2,2,2,2,2,2,2,2,1,
1,1,1,1,2,2,2,1,1,1,1,1,1,1};//測試用的隱藏狀態序列
intT=32;//序列長度為32

double[][]alpha=newdouble[T][];//向前變數
doublePO;
double[][]beta=newdouble[T][];//向後變數
double[][]gamma=newdouble[T][];
double[][][]xi=newdouble[T-1][][];

//初始化參數。Baum-Welch得到的是局部最優解，所以初始參數直接影響解的好壞
publicvoidinitParameters(){
M=2;
N=2;
PI=newdouble[M];
PI[0]=0.5;
PI[1]=0.5;
A=newdouble[M][];
B=newdouble[M][];
for(inti=0;i<M;i++){
A[i]=newdouble[M];
B[i]=newdouble[N];
}
A[0][0]=0.8125;
A[0][1]=0.1875;
A[1][0]=0.2;
A[1][1]=0.8;
B[0][0]=0.875;
B[0][1]=0.125;
B[1][0]=0.25;
B[1][1]=0.75;

observation.add(1);
observation.add(2);
state.add(1);
state.add(2);

for(intt=0;t<T;t++){
alpha[t]=newdouble[M];
beta[t]=newdouble[M];
gamma[t]=newdouble[M];
}
for(intt=0;t<T-1;t++){
xi[t]=newdouble[M][];
for(inti=0;i<M;i++)
xi[t][i]=newdouble[M];
}
}

//更新向前變數
publicvoipdateAlpha(){
for(inti=0;i<M;i++){
alpha[0][i]=PI[i]*B[i][observation.indexOf(out_seq[0])];
}
for(intt=1;t<T;t++){
for(inti=0;i<M;i++){
alpha[t][i]=0;
for(intj=0;j<M;j++){
alpha[t][i]+=alpha[t-1][j]*A[j][i];
}
alpha[t][i]*=B[i][observation.indexOf(out_seq[t])];
}
}
}

//更新觀察序列出現的概率，它在一些公式中當分母
publicvoipdatePO(){
for(inti=0;i<M;i++)
PO+=alpha[T-1][i];
}

//更新向後變數
publicvoipdateBeta(){
for(inti=0;i<M;i++){
beta[T-1][i]=1;
}
for(intt=T-2;t>=0;t--){
for(inti=0;i<M;i++){
for(intj=0;j<M;j++){
beta[t][i]+=A[i][j]
*B[j][observation.indexOf(out_seq[t+1])]
*beta[t+1][j];
}
}
}
}

//更新xi
publicvoipdateXi(){
for(intt=0;t<T-1;t++){
doublefrac=0.0;
for(inti=0;i<M;i++){
for(intj=0;j<M;j++){
frac+=alpha[t][i]*A[i][j]
*B[j][observation.indexOf(out_seq[t+1])]
*beta[t+1][j];
}
}
for(inti=0;i<M;i++){
for(intj=0;j<M;j++){
xi[t][i][j]=alpha[t][i]*A[i][j]
*B[j][observation.indexOf(out_seq[t+1])]
*beta[t+1][j]/frac;
}
}
}
}

//更新gamma
publicvoipdateGamma(){
for(intt=0;t<T-1;t++){
doublefrac=0.0;
for(inti=0;i<M;i++){
frac+=alpha[t][i]*beta[t][i];
}
//doublefrac=PO;
for(inti=0;i<M;i++){
gamma[t][i]=alpha[t][i]*beta[t][i]/frac;
}
//for(inti=0;i<M;i++){
//gamma[t][i]=0;
//for(intj=0;j<M;j++)
//gamma[t][i]+=xi[t][i][j];
//}
}
}

//更新狀態概率矩陣
publicvoipdatePI(){
for(inti=0;i<M;i++)
PI[i]=gamma[0][i];
}

//更新狀態轉移矩陣
publicvoipdateA(){
for(inti=0;i<M;i++){
doublefrac=0.0;
for(intt=0;t<T-1;t++){
frac+=gamma[t][i];
}
for(intj=0;j<M;j++){
doubledem=0.0;
//for(intt=0;t<T-1;t++){
//dem+=xi[t][i][j];
//for(intk=0;k<M;k++)
//frac+=xi[t][i][k];
//}
for(intt=0;t<T-1;t++){
dem+=xi[t][i][j];
}
A[i][j]=dem/frac;
}
}
}

//更新混淆矩陣
publicvoipdateB(){
for(inti=0;i<M;i++){
doublefrac=0.0;
for(intt=0;t<T;t++)
frac+=gamma[t][i];
for(intj=0;j<N;j++){
doubledem=0.0;
for(intt=0;t<T;t++){
if(out_seq[t]==observation.get(j))
dem+=gamma[t][i];
}
B[i][j]=dem/frac;
}
}
}

//運行Baum-Welch演算法
publicvoidrun(){
initParameters();
intiter=22;//迭代次數
while(iter-->0){
//E-Step
updateAlpha();
//updatePO();
updateBeta();
updateGamma();
updatePI();
updateXi();
//M-Step
updateA();
updateB();
}
}

publicstaticvoidmain(String[]args){
BaumWelchbw=newBaumWelch();
bw.run();
System.out.println("訓練後的初始狀態概率矩陣：");
for(inti=0;i<bw.M;i++)
System.out.print(bw.PI[i]+"	");
System.out.println();
System.out.println("訓練後的狀態轉移矩陣：");
for(inti=0;i<bw.M;i++){
for(intj=0;j<bw.M;j++){
System.out.print(bw.A[i][j]+"	");
}
System.out.println();
}
System.out.println("訓練後的混淆矩陣：");
for(inti=0;i<bw.M;i++){
for(intj=0;j<bw.N;j++){
System.out.print(bw.B[i][j]+"	");
}
System.out.println();
}
}
}

E. pattern recognition and machine learning這本書怎麼看

作者：Richardmore
這本書可以說是機器學習的經典學習之作。以前在上機器學習這么課的時候，很多細節還沒聯繫到，結果在讀論文中就顯得捉襟見肘。本文打算理清楚這本書的脈絡，也順便為學習機器學習的人打下一個學習路線圖。

1. 排除兩塊內容

現排除第五章的內容神經網路，之所以把神經網路先單列出來，原因一是一個比較獨立的研究脈絡，二是因為這部分因為深度學習的原因太熱了，所以我認為在學習機器學習中把神經網路單列出來學習，在交大的研究生課程安排中，神經網路是機器學習的後續課程。
對於第6，7章，也不在下面的學習路線中，因為這部分是關於核技巧方面的，主要是就是高斯過程回歸，高斯過程分類以及SVM等內容。
2. 一個概率圖框架為中心視角

排除了上面幾章的內容，PRML書中可以用下面的學習路線圖覆蓋，通過這個圖可以理清楚了各個內容的不同角色。
<img src="https://pic3.mg.com/_b.png" data-rawwidth="1888" data-rawheight="412" class="origin_image zh-lightbox-thumb" width="1888" data-original="https://pic3.mg.com/_r.png">

說明：
（1）一般模型中都會有隱變數因此，，因此對於P（X）的採用MLE學習的另一個技巧,便是第九章 EM演算法。條件是在M步時，Q要可以被analytically computed。
（2）至於為什麼近似，Exact Inference is hard we resort to approximation
3. 隱變數技巧

下面我們看看另外一個視角：隱變數技巧。隱變數不僅可以使得模型的表達能力豐富起來，而且通常對於隱變數往往富有一定的實際意義。

<img src="https://pic1.mg.com/_b.png" data-rawwidth="1764" data-rawheight="422" class="origin_image zh-lightbox-thumb" width="1764" data-original="https://pic1.mg.com/_r.png">

說明：
（1）這里所謂的結合模型中，在PRML中最後一章僅僅提到了以加法的方式進行模型集合，也就是mixture of experts，在論文Hinton G E. Training procts of experts by minimizing contrastive divergence[J]. Neural computation, 2002, 14(8): 1771-1800. 提出了proct of experts 模型，也就是以乘法的方式進行結合，RBM就是一種特殊的proct of experts 模型，而高斯混合模型便是加法模型的代表。
（2）隱變數的技巧是機器學習中一種重要的技巧，隱變數的加入不僅僅增加了模型的表達能力，而且，隱變數還可以被賦予某種特殊的意義，比如RBM模型中隱變數h被當成顯變數v的特徵抽象。這當然歸根結底是因為隱變數模型確實是現實世界真實存在的情況，unobserved but important variables do exist! 當然隱變數的引入也為模型的推斷帶來了新的挑戰，有很多比較好的隱變數模型往往找不到很高效的方法，而被限制著。
4. 例子說明

下面分別從上面兩個視角來分析RBM模型，貝葉斯線性回歸和序列模型。
4.1 RBM模型
RBM模型是一個無向2層對稱的圖模型，從隱變數的視角來看，它是一個以乘法方式結合的distributed models。當然隱變數的引入增加了模型的復雜性和表達能力，但是也為學習，推斷帶來了問題。對於RBM的參數學習，因為是無向圖，所以採用MLE最大化P（X），但是由於此時P（X，Z）難以評估，所以
<img src="https://pic2.mg.com/v2-_b.png" data-rawwidth="834" data-rawheight="94" class="origin_image zh-lightbox-thumb" width="834" data-original="https://pic2.mg.com/v2-_r.png">
很難計算，沒有在RBM的學習中不能像高斯混合模型那樣可以採取EM演算法。因此只能採取最為標準的做法，求取P（X）的梯度，結果梯度公式如下：
<img src="https://pic2.mg.com/v2-_b.png" data-rawwidth="800" data-rawheight="90" class="origin_image zh-lightbox-thumb" width="800" data-original="https://pic2.mg.com/v2-_r.png">

然而對於計算後面的model部分的積分需要知道模型的概率分布，評估模型的概率分布需要計算一個標准化的分母，難以計算。因此就需要依賴近似，由於p（v｜h），p（h｜v）都是可以分析公式表達，因此採用Gibbs sampler來數值逼近積分。當然後來Hinton G E. Training procts of experts by minimizing contrastive divergence[J].發現對於這一部分，Gibbs sampler 不需要多部的迭代，一次迭代就可以了，從而使的訓練RBM的時間代價大大降低了，後來（A fast learning algorithm for deep belief nets，2006）提出了貪婪式的訓練多層DBN（stacked RBM），每層都是訓練RBM，從而使的深度學習煥發新的活力（Recing the dimensionality of data with neural networks，2006）。

4.2 貝葉斯線性回歸Bayesian Linear Regression BLR

這個模型是最為基礎的，這個模型在PRML中，利用直接推斷，變分法推斷，MCMC采樣都是可以做的；因此便於比較不同演算法得到的結果。之前，本來打算在這里以LDA主題模型來舉例，雖然LDA的EM演算法， 變分法，以及Gibbs sampling 都是可以做的，但是模型太復雜，所以果斷放棄了，以BLR模型作為例子說明。
BLR是一個有向圖模型，是一個典型的貝葉斯網路（雖然簡單一點）。如果以一個貝葉斯的視角來看，其中的隱變數便是線性參數w，以及各種超參數α,β.....，在貝葉斯的處理視角之下，這些都會賦予一個先驗分布。當然，有些模型書中也提到，有不同層次上的貝葉斯網路。有的是僅僅對參數w賦予一個先驗分布，而對於其他的參數（hyperparameter）僅僅是作為模型參數，就是假設是一個渡固定的數值，然後再通過learn evidence function，其實說白了就是MLE，來尋找最佳的超參數α,β....。相比於把線性參數w，以及各種超參數α,β.....全部作為放入到貝葉斯網路中，這樣的做法顯然簡化了模型，降低了貝葉斯網路的復雜性。這個技巧也在多處的論文中出現。
從隱變數的角度來看，由於BLR模型相對簡單，其中並沒有隨機隱變數，僅僅是一些參數w，以及各種超參數α,β..的環境隱變數。
4.3 序列模型：隱馬爾可夫鏈HMM與條件隨機CRF

隱馬爾可夫鏈HMM這個模型是一個有向圖模型，典型的貝葉斯網路，只不過這個網路是一個線性鏈（linear chains），因此可以進行分析上推斷，要知道對於一般網路，並不存在通用的實用的inference演算法。因為HMM是一個有向圖模型。但是（1）在PRML書中，以及李航《統計學習》中並沒有把其當作一個貝葉斯網路來進行處理，對所有的參數比如發射概率，轉移矩陣概率都是模型的參數，而不是通過賦予一個先驗分布，從而納入到貝葉斯網路框架之中。因此對於模型而言，關鍵的便是通過MLE最大化P（X）來學習模型的參數，因為這里的有隱變數，因此在PRML，以及《統計學習》中都是通過EM演算法做的。（2）其實，HMM是一個典型的線性鏈式的貝葉斯網路，因此對於通過對其參數賦予先驗分布，進而從貝葉斯的角度，來對模型進行推斷是一個非常自然的想法。我在論文Sharon Goldwater， Thomas L Griffiths 論文 A Fully Bayesian Approach to Unsupervised Part-of-Speech Tagging，中作者採用了Bayesian HMM 重新做了POS任務。作者在文中還詳細羅列了Bayesian HMM 相比普通的HMM的優點：（a）可以使用先驗知識，例如在POS中語言的認知可以加入到先驗分布之中，而且（b）貝葉斯的推斷，是通過一個後驗分布推斷參數，相比MLE點估計，會更加准確。對於貝葉斯的推斷，作者在文中使用了Gibbs sample抽樣實現了數值采樣推斷模型。最後作者比較了Gibbs sample＋Bayesian HMM和普通的HMM ＋EM，在POS任務效果更加好。另外，對於本論文的作者Thomas L Griffiths，第一次接觸這個學者，是在讀Gibbs sample in LDA這篇文章，作者推導了LDA的各種的條件分布，然後基於Gibbs sample 進行采樣，記得Github上有Java版的實現代碼，其推導十分嚴謹，並且有代碼輔助，是學習LDA的一個捷徑。在近似推斷方面可以看出Thomas L Griffiths是一個堅定的數值采樣學派，而LDA的開山之作《Latent Dirichlet Allocation 》的作者David M. Blei，看了作者部分文章以後，發現這個人是在近似推斷方面是一個變分法的堅定學派，在《Latent Dirichlet Allocation 》之中，便是通過變分法進行推斷了，David M. Blei還寫了一個關於變分法的入門講義pdf，網上可以搜到。所以回看我們概率圖視角，做機器學習推斷是不可避免的，有的是變分法近似，有的是數值采樣近似，也有的是EM演算法試一試。至於選擇哪一種，就看你的問題哪一個比較簡單了。但是好像有的人對這些方面各有偏愛。
再說一下條件隨機場CRF，相比與HMM，這也是一個序列模型，在很多的NLP任務中，CRF都是state of art 的演算法，畢竟人家可以方便的特徵工程嘛。但是這種日子被深度學習取代了，在NLP方面，RNN（遞歸神經網路）要比CRF表現更好，見我之前博文基於RNN做語義理解和詞向量。先不說這么遠，CRF的模型架構上是一個典型的無向的鏈式概率圖模型，因此，（回看我們概率圖的視角），CRF的關鍵問題便是如何進行學習了P（X），好在求其該模型直接求其梯度並沒有太大的困難，具體可以參見李航的《統計學習》。
5 結束語

這篇文章，從概率圖，隱變數兩個視角對PRML中各個章節進行了串聯，並以RBM，BLR，序列模型（HMM&CRF）具體說明這種串聯。