小男孩‘自慰网亚洲一区二区,亚洲一级在线播放毛片,亚洲中文字幕av每天更新,黄aⅴ永久免费无码,91成人午夜在线精品,色网站免费在线观看,亚洲欧洲wwwww在线观看

搜索
分享

MapReduce在搜索引擎中一些應(yīng)用

 IT技術(shù)武館 2014-07-17

word-doc矩陣

在進(jìn)行文件分類或文檔檢索的時(shí)候，我們通常需要建立一個(gè)word-doc矩陣，來記錄每個(gè)詞在每篇文檔中出現(xiàn)的次數(shù)。

class Mapper
    method map(docid id,doc d)
        foreach term in d
            Emit(pair(term,id),1)

一種更高效的方法是在mapper側(cè)進(jìn)行聚合。

class Mapper
    method map(docid id,doc d)
        H := new AssociativeArray
        foreach term in d
            H{term} := H{term}+1
        foreach term in H
            Emit(pair(term,id),H{term})

圖的寬度優(yōu)先遍歷

現(xiàn)代的爬蟲一般采用寬度優(yōu)先的規(guī)則來遍歷網(wǎng)絡(luò)。還有在Dijkstra算法中也是一種寬度優(yōu)先的規(guī)則--每發(fā)再一個(gè)新的最近點(diǎn)，就更新與之相鄰的節(jié)點(diǎn)的dist。我們可以用MapReduce迭代的方式來實(shí)現(xiàn)Dijkstra算法。每輪迭代運(yùn)行一次Map-Reduce，最多迭代N次，N是圖中節(jié)點(diǎn)的個(gè)數(shù)。用鄰接鏈表來存儲(chǔ)圖。算法開始時(shí)，起始節(jié)點(diǎn)的dist賦0，其余的節(jié)點(diǎn)dist賦無窮大。先考慮簡(jiǎn)單的情形--每條邊的權(quán)值都是1。

class Mapper
    method map(nid n,node N)
        d := N.distance
        Emit(nid n,N)           //pass along graph structure
        foreach nodeid m in N.AdjacencyList
            Emit(nid m,d+1)     //Emit distances to reachable nodes
             
class Reducer
    method reduce(nid m,[d1,d2,...])
        minDist := infinite
        M := NULL
        foreach d in [d1,d2,...]
            if IsNode(d)
                M := d          //recover graph structure
            else if d<minDist    //lookup for shortest distance
                minDist := d
        M.distance := minDist   //update shortest distance
        Emit(nid m,node M)

在迭代式的Map-Reduce程序設(shè)計(jì)中，需要有一個(gè)driver來控制迭代的進(jìn)行，檢查終止條件是否滿足。在reducer中如果所有node的minDist都沒有更新，更迭代終止。

上面的代碼只算出了源節(jié)點(diǎn)到其他節(jié)點(diǎn)的最短路程，并沒有記錄下最短路徑，所以我們需要在更新minDist的同時(shí)記錄下它的上一個(gè)節(jié)點(diǎn)，mapper在輸出(nid,dist)時(shí)也應(yīng)該輸出與dist對(duì)應(yīng)的是哪個(gè)節(jié)點(diǎn)。

上面假設(shè)任意節(jié)點(diǎn)間的距離都是1，當(dāng)是任意值r時(shí)，只需要在mapper中輸出(nid m,d+r)就可以了。

跟單進(jìn)程的Dijkstra算法比起來，這種Map-Reduce版的算法顯然計(jì)算量大了許多，因?yàn)樗看蔚家z查每一個(gè)節(jié)點(diǎn)的鄰居的dist是否需要更新；而單進(jìn)程的Dijkstra算法通過維持一個(gè)優(yōu)先隊(duì)列，它每次迭代只需要檢查隊(duì)首元素的鄰居的dist是否需要更新。在Hadoop中，mapper和reducer通信方式非常受限，我們無法維持一個(gè)像優(yōu)先隊(duì)列這樣一種全局的數(shù)據(jù)結(jié)構(gòu)。正因如此，Map-Reduce不適合于處理大規(guī)則，稠密圖。

Page Rank

在網(wǎng)頁排序算法中Page Rank可謂鼎鼎有名--雖然它只是Google對(duì)網(wǎng)頁進(jìn)行排序的上千種因素中的一個(gè)。該算法認(rèn)為一個(gè)網(wǎng)頁的重要度，由它鏈接到它的的網(wǎng)頁的重要度來決定。網(wǎng)頁重要度公式為：

|G|中整個(gè)網(wǎng)絡(luò)當(dāng)中節(jié)點(diǎn)的總個(gè)數(shù)，α是隨機(jī)跳轉(zhuǎn)因子，L(n)是所有鉸接到網(wǎng)頁n的網(wǎng)頁的集合，C(m)是網(wǎng)頁m的出度。在網(wǎng)頁m上的一個(gè)沖浪者它以1/C(m)的概率進(jìn)入網(wǎng)頁n。如何理解加式的第1項(xiàng)呢？一個(gè)沖浪者在瀏覽網(wǎng)頁時(shí)并不總是點(diǎn)擊超鏈接進(jìn)行下去的，他也有可能在地址欄隨機(jī)地輸入了一個(gè)網(wǎng)址，一下子跳轉(zhuǎn)到了一個(gè)完全不相關(guān)的網(wǎng)頁。

Page Rank算法迭代地計(jì)算每個(gè)網(wǎng)頁的重要度，實(shí)際上就是一種寬度優(yōu)先遍歷的方法。一個(gè)網(wǎng)頁從它的所有incoming網(wǎng)頁中“收集”重要度，很自然地用reducer來完成。開始時(shí)給網(wǎng)絡(luò)圖上的每個(gè)節(jié)點(diǎn)賦一個(gè)服從[0,1]的均勻分布的隨機(jī)值作為其重要度。Map-Reduce不斷地迭代，直到每個(gè)網(wǎng)頁的重要度都不再變化為止。

下面的代碼簡(jiǎn)化起見，沒有考慮公式中的第一項(xiàng)。

class Mapper
    method map(nid n,node N)
        p := N.PageRank/|N.AdjacencyList|
        Emit(nid n,N)           //pass along graph structure
        foreach nodeid m in N.AdjacencyList
            Emit(nid m,p)
             
class Reducer
    method reduce(nid m,[p1,p2,...])
        M := NULL
        s := 0
        foreach p in [p1,p2,...]
            if IsNode(p)
                M := p
                s := M.PageRank
            else
                s := s+p
        M.PageRank := s
        Emit(nid m,node M)

Graph Structure被mapper拋出，又被reducer寫入磁盤，這樣它從上一次迭代又傳遞一了下一次迭代。

 

HMM算法

當(dāng)年李開復(fù)搞語音識(shí)別用的就是隱馬爾可夫算法，HMM在中文分詞和詞性標(biāo)注中也大顯威力。

EM算法也是Machine Learning中的重要算法之一，比如HMM模型參數(shù)的確立、高斯混合模型參數(shù)的確立都要用到它。

 

K-means算法

K-means是一種古老且經(jīng)典的聚類算法，至今仍廣泛使用。

class Mapper
    method setup()
        Centers[K] := ReadFromFile
    method map(docid id,doc d)
        H := new AssociativeArray
        foreach data in d
            Centers[index] := NearestCenterToData
            c := H{index}.left
            s := H{index}.right
            H{index} := Pair(c+1,s+data)
        foreach integer i in H
            Emit(i,H{i})
             
class Reducer
    method reduce(integer i,pairs [p1,p2,...])
        s := 0
        c := 0
        foreach pair in [p1,p2,...]
            s := s+pair.right
            c := c+pair.left
        Emit(i,s/c)

    本站是提供個(gè)人知識(shí)管理的網(wǎng)絡(luò)存儲(chǔ)空間，所有內(nèi)容均由用戶發(fā)布，不代表本站觀點(diǎn)。請(qǐng)注意甄別內(nèi)容中的聯(lián)系方式、誘導(dǎo)購買等信息，謹(jǐn)防詐騙。如發(fā)現(xiàn)有害或侵權(quán)內(nèi)容，請(qǐng)點(diǎn)擊一鍵舉報(bào)。
    轉(zhuǎn)藏 分享 獻(xiàn)花（0）

    0條評(píng)論

    發(fā)表

    請(qǐng)遵守用戶 評(píng)論公約

    類似文章 更多