over 2 years ago

輸入中文搜尋後,我們預期這個搜尋引擎能為我們找到關聯性最高的網頁,並按照得分順序作排序。這裡所謂的得分,可能使用幾種方式來計算,這篇討論的重點在此。

正規化

分數的高低不希望隨著樣本增大而變大,或者因為選擇不同的元素(字頻、字距…)作處理,而無法比較其間的權重關係。所以我們先將數據作正規化。簡單的作法是取出樣本的最大值,分別除上此值。

my_search_engine.py
def normalizescores(self,scores,smallIsBetter=False):
    ## input:scores --> dictionary of scores: {1:5,2:3,...}

    
    vsmall =0.00001 # avoid division by 0

    if smallIsBetter:
        minscore=min(scores.values())
        return dict([(u,float(minscore)/max(vsmall,l)) for (u,l) in scores.items()])
    else:
        maxscore = max(scores.values())
        if maxscore==0: 
            maxscore =vsmall
        return dict([(u,float(c)/maxscore) for (u,c) in scores.items()])

以網頁內容為基礎


一種直觀的分析方法是,利用網頁的內容作為評分。可能的元素有字頻,字距

  • 字頻(frequency):

網頁中出現搜尋的關鍵字數愈多,代表網頁關聯性愈高,排序得分也應該愈高。舉例來說一個網頁(urlid:1)中找到香蕉芭樂的位置分別為(1,9)(12,20)那按照上篇-搜尋引擎(二)的結構,輸出為(1,1,12),(1,1,20),(1,9,12),(1,9,20)四種。

my_search_engine.py
    def frequencyscore(self,rows):
        # 1.scored by counting word frequency in a page,

        # 

        # input:

        # -- rows:[(url1,wordloc1,wordloc2,..),(url2,wordloc1,wordloc2),..]        

        # output: 

        # -- counts[urlid], word frequency in urlid

        counts=defaultdict(int)

        for row in rows:
            counts[row[0]]+=1
        return self.normalizescores(counts)
  • 字距(locationscore):
    如果香蕉芭樂出現在標題,或者距離標題近一點的副標題,那關鍵字的得分也應該愈高。選擇所在的關鍵字最小的位置,而愈小的得分愈高。
my_search_engine.py
def locationscore(self,rows):
    # 2.scored by catching location of word in a page,

    locations=dict([(row[0],100000) for row in rows])
    for row in rows:
        loc=sum(row[1:])
        if loc<locations[row[0]]:
            locations[row[0]] = loc
    return self.normalizescores(locations,smallIsBetter=True)

以網頁間的連結性為基礎


利用網頁的連結性來作得分判斷,

  • 網頁連結度(inboundlinkscore):

假設某一網頁被大部分的網頁連結(如google/yahoo這種入口網站),那這種網站排序也會在前面一點(得分高)。

my_searche_engine.py
def inboundlinkscore(self,rows):
    # 3. score by in-bound-link

    uniqueurls=set([row[0] for row in rows])
    inboundcount=dict([(u,self.con.execute(\
        'select count(*) from link where toid=%d'%u).fetchone()[0]
    )
    for u in uniqueurls])

    return self.normalizescores(inboundcount)

  • 網頁排名(PageRank):

這是google的共同創辦人LarryPage提出的演算法,不只是目前當代搜尋引擎的基礎,也幫google公司取得空前的成功。概念如下,

如果已經知道,那麼

觀察到D雖然排名較小可是她只有一個對外連結(到A),所以D的貢獻比起B,C都來的大。問題是剛開始,我們並不知道B,C,D的排名(PageRank)。實際作法是先猜測每個網頁的排名,每個網頁重新計算排序,迭代數次後,此值會趨於收斂。

note:此函數必須放在爬蟲Crawler的類別下,不然每搜尋一次就要計算一次pagerank會哭哭的…

my_search_engine.py
def calculatepagerank(self,iterations=20):
    # caluculate page-rangk by iterations(default=20), 

    
    # clear out the current PageRank tables

    self.con.execute('drop table if exists pagerank')
    self.con.execute('create table pagerank(urlid primary key,score)')

    # initialize every url with a PageRank of 1

    self.con.execute('insert into pagerank select rowid, 1.0 from urllist')
    self.con.commit()

    # loop through every urlid,and iterate several times(numbers is iterations)

    for i in range(iterations):
        print 'iterations no: %d'%(i)
        # loop through every urlid

        for (urlid,) in self.con.execute("select rowid from urllist"):
            pr=0.15

            # loop through all pages which link to this one

            for (linker,) in self.con.execute(
                "select distinct fromid from link where toid=%d"%urlid):
                # get page rank

                linkingpr=self.con.execute(
                    'select score from pagerank where urlid=%d' %linker).fetchone()[0]

                # get the total number links from this linker

                linkingcounts = self.con.execute(
                    "select count(*) from link where fromid=%d"%linker).fetchone()[0]
                pr+=0.85*(linkingpr/linkingcounts)

            self.con.execute(
                "update pagerank set score=%f where urlid=%d"%(pr,urlid))
        self.con.commit()
  • 連結內文資訊(linktextscore):

內文的連結文字通常隱含有很大的資訊量,例如雅虎拍賣我們能很輕易的猜到,連結的地方就是y拍首頁。所以透過連結內文資訊,我們也能取得排序資訊。

my_search_engine.py
def linktextscore(self,rows,wordids):
        # 5. score by link-text 


        linkscores=dict([(row[0],0) for row in rows])
        # print linkscores

        for wordid in wordids:
            cur=self.con.execute(
                "select link.fromid,link.toid from linkword,link \

                where wordid=%d and linkword.linkid=link.rowid"%wordid
                )
            for (fromid,toid) in cur:                
                if toid in linkscores:
                    # print "toid:%d"%toid                    

                    pr=self.con.execute(
                        "select score from pagerank where urlid=%d"%fromid
                        ).fetchone()[0]
                    linkscores[toid]+=pr
        return self.normalizescores(linkscores)

完整的程式碼請參考這裡


參考資料

← 搜尋引擎(二)中文搜尋 關鍵字提取-TextRank算法 →
 
comments powered by Disqus