搜索与排名

爬虫 #

书中的爬虫代码非常的老了，并且网站也无法访问了，大家可以忽略

建立索引 #

urllist: 索引过的 URL
wordlist: 单词列表
wordlocation: 单词在文档中的位置
linktable: 不同链接之间的关系
linkwords: 单词和链接之间的关系

因为网站也无不工作了，这里采用网上已经生成的 DB 直接下载即可。

关于其他的基础查询部分，这里都不涉及。

准备好环境我们可以体验下

>>> e = searchengine.searcher("searchindex.db")
>>> e.getmatchrows('function')
select w0.urlid,w0.location from wordlocation w0 where w0.wordid=1111
([(1, 3226), (186, 340), (186, 546), (58, 2488), (123, 430), (123, 866), (123, 1268), (123, 1294), (123, 1345), (123, 1385), (123, 1821), (123, 1847), (123, 1897), (123, 1929), (82, 1673), (327, 2431), (327, 2465), (327, 3571), (327, 3586), (327, 3606), (139, 460), (139, 611), (139, 1250), (139, 1328), (171, 1284), (171, 3363), (171, 4774), (96, 1141), (96, 1412), (372, 828), (372, 872), (372, 923), (372, 946), (372, 973), (372, 990), (372, 1000), (372, 1013), (372, 1032), (372, 1058), (372, 1069), (372, 1135), (372, 1159), (372, 1188), (372, 1211), (372, 1278), (255, 417), (255, 706), (156, 914), (208, 584), (226, 352), (226, 388), (226, 424), (226, 433), (226,

返回的2个值是 urlid wordlocation,多个值就是 urlid wordlocation wordlocation

Content-Based Ranking 基于内容的排名 #

根据几个模式来进行排名

单词频次: 查询文档中如果频次出现的越多，相关度
文档位置: 文档的主体比较靠近开始的地方
单词距离: 多个单词，靠近的应该就更有相关度

  def getscoredlist(self,rows,wordids):
    totalscores=dict([(row[0],0) for row in rows])

    # 后面来填充
    weights=[]
    for (weight,scores) in weights:
      for url in totalscores:
        totalscores[url]+=weight*scores[url]

    return totalscores

  def geturlname(self,id):
    return self.con.execute(
    "select url from urllist where rowid=%d" % id).fetchone()[0]

  def query(self,q):
    # 查询所有的 row 和 word id
    rows,wordids=self.getmatchrows(q)
    # 给其打分
    scores=self.getscoredlist(rows,wordids)
    rankedscores=[(score,url) for (url,score) in scores.items()]
    rankedscores.sort()
    rankedscores.reverse()
    # 返回排序的结果
    for (score,urlid) in rankedscores[0:10]:
      print '%f\t%s' % (score,self.geturlname(urlid))
    return wordids,[r[1] for r in rankedscores[0:10]]

归一化函数 #

将那些可能越大越好和越小越好的分数进行归一化，返回 0 - 1，0最不匹配，1最为匹配

  def normalizescores(self,scores,smallIsBetter=0):
    vsmall=0.00001 # Avoid division by zero errors
    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()])

单词频度 #

就是使用单词出现的频次来记录得分。

def frequencyscore(self,rows):
    counts=dict([(row[0],0) for row in rows])
    for row in rows: counts[row[0]]+=1
    return self.normalizescores(counts)

文档位置 #

def locationscore(self,rows):
    # 给每一个 url 分配了一个 100000 的预留长度
    locations=dict([(row[0],1000000) for row in rows])
    for row in rows:
      # 计算 row 查询出来的所有的位置的 SUM，越大就越远
      loc=sum(row[1:])
      # 如果这次算出来的位置比之前的要小，就更新，取最好成绩
      if loc<locations[row[0]]: locations[row[0]]=loc
    
    return self.normalizescores(locations,smallIsBetter=1)

单词距离 #

def distancescore(self,rows):
    # 如果只有 1 个单词，就不存在距离了
    if len(rows[0])<=2: return dict([(row[0],1.0) for row in rows])

    # 初始话，给每个 URL 分配了一个 100000 的预留长度
    mindistance=dict([(row[0],1000000) for row in rows])

    for row in rows:
      # 这里计算了每个单词之间的距离，取最小的，作为最终的成绩
      dist=sum([abs(row[i]-row[i-1]) for i in range(2,len(row))])
      if dist<mindistance[row[0]]: mindistance[row[0]]=dist
    return self.normalizescores(mindistance,smallIsBetter=1)

Using Inbound Links 外部链接回指 #

一般认为谁被链接的多，说明这个网站的质量越高。

计数器 #

我们直接去系统中查询出现的频次就可以，但是缺点就是相关度会变得很低。因为比如那种综合性的网页会指向所有的页面。因此有个 google 的 pagerank 算法

PageRank #

比如这里要计算的话，公式如下

PR(A) = 0.15 + 0.85 * ( PR(B)/links(B) + PR(C)/links(C) + PR(D)/links(D) )      
      = 0.15 + 0.85 * ( 0.5/4 + 0.7/5 + 0.2/1 )      
      = 0.15 + 0.85 * ( 0.125 + 0.14 + 0.2)      
      = 0.15 + 0.85 * 0.465      
      = 0.54525

但是我们计算 A 的时候需要 B 已经包含了，那么我们需要初始化，方法如下

  def calculatepagerank(self,iterations=20):
    #  清单当前的 pagerank 标
    self.con.execute('drop table if exists pagerank')
    self.con.execute('create table pagerank(urlid primary key,score)')
    
    #  初始化每个都 1.0
    for (urlid,) in self.con.execute('select rowid from urllist'):
      self.con.execute('insert into pagerank(urlid,score) values (%d,1.0)' % urlid)
    self.dbcommit()
    
    for i in range(iterations):
      print "Iteration %d" % (i)
      for (urlid,) in self.con.execute('select rowid from urllist'):
        pr=0.15
        
        # 循环遍历指向当前网页的所有页面
        for (linker,) in self.con.execute(
        'select distinct fromid from link where toid=%d' % urlid):
          # 得到链接源的 pagerank 值
          linkingpr=self.con.execute(
          'select score from pagerank where urlid=%d' % linker).fetchone()[0]

          # 计算新 pagerank 然后更新
          linkingcount=self.con.execute(
          'select count(*) from link where fromid=%d' % linker).fetchone()[0]
          pr+=0.85*(linkingpr/linkingcount)
        self.con.execute(
        'update pagerank set score=%f where urlid=%d' % (pr,urlid))
      self.dbcommit()

使用这个算法就很简单了

  def pagerankscore(self,rows):
    # 查询所有的 pagerank
    pageranks=dict([(row[0],self.con.execute('select score from pagerank where urlid=%d' % row[0]).fetchone()[0]) for row in rows])
    maxrank=max(pageranks.values())
    # 用最大作为基数，算个百分比就好
    normalizedscores=dict([(u,float(l)/maxrank) for (u,l) in pageranks.items()])
    return normalizedscores

使用链接文本 #

就是如果 A 链接到 B，那么 A 在链接 B 的时候，往往会在超链接里面编写一些说明，这些说明非常的有价值

  def linktextscore(self,rows,wordids):
    linkscores=dict([(row[0],0) for row in rows])
    for wordid in wordids:
      cur=self.con.execute('select link.fromid,link.toid from linkwords,link where wordid=%d and linkwords.linkid=link.rowid' % wordid)
      # 如果包含这个关键字的链接中包含了 toid，那说明这个链接价值很高，把 from 的 pr 加上去
      for (fromid,toid) in cur:
        if toid in linkscores:
          pr=self.con.execute('select score from pagerank where urlid=%d' % fromid).fetchone()[0]
          linkscores[toid]+=pr
    maxscore=max(linkscores.values())
    normalizedscores=dict([(u,float(l)/maxscore) for (u,l) in linkscores.items()])
    return normalizedscores

Learning from Clicks 从点击中学习 #

使用神经网络来完成这个事情，从左边的 输入层 到最后的 输出层 中间都是 隐藏层

设置数据库 #

HiddenNode: 代表隐藏层节点

create table hiddennode(create_key)

Wordhidden: 单词层到隐藏层

create table wordhidden(fromid,toid,strength)

HiddenURL: 隐藏层到输出层

create table hiddenurl(fromid,toid,strength)

Feeding Forward 前馈法 #

是用一个函数，用节点输入得出响应强度，X 轴代表了节点的输入，输入为 0 的时候快速爬高，2 就几乎不动了，作为一种 S 型函数，上图就是一个 tanh 函数

构建网络 #

def setupnetwork(self, wordids, urlids):
    # 单词列表
    self.wordids = wordids
    # 查询到所有的 hidden id
    self.hiddenids = self.getallhiddenids(wordids, urlids)
    self.urlids = urlids

    # 输出值
    self.ai = [1.0] * len(self.wordids)
    self.ah = [1.0] * len(self.hiddenids)
    self.ao = [1.0] * len(self.urlids)

    # 根据链接的强度，构建权重矩阵
    ## word -> hidden
    self.wi = [[self.getstrength(wordid, hiddenid, 0)
                for hiddenid in self.hiddenids]
                for wordid in self.wordids]
    ## hidden -> url
    self.wo = [[self.getstrength(hiddenid, urlid, 1)
                for urlid in self.urlids]
                for hiddenid in self.hiddenids]

前馈算法 #

def feedforward(self):
    # 将输入的 word 的 下标置为 1
    for i in range(len(self.wordids)):
        self.ai[i] = 1.0

    # 隐藏层激活
    for j in range(len(self.hiddenids)):
        sum = 0.0
        # 单词层到隐藏层的权重累加
        for i in range(len(self.wordids)):
            sum = sum + self.ai[i] * self.wi[i][j]
        # tanh 一下，转为 0 - 1
        self.ah[j] = tanh(sum)

    # 输出层激活
    for k in range(len(self.urlids)):
        sum = 0.0
        # 隐藏到输出层权重累加
        for j in range(len(self.hiddenids)):
            sum = sum + self.ah[j] * self.wo[j][k]
        # tanh 一下，转为 0 - 1
        self.ao[k] = tanh(sum)

    return self.ao[:]

这样整个流程就跑通了，不过整个网络并没有训练，现在得到的结果都是一样的

if __name__ == '__main__':
    mynet = searchnet("nn.db")
    wWorld, wRiver, wBank = 101, 102, 103
    uWorldBank, uRiver, uEarth = 201, 202, 203
    print mynet.getresult([wWorld, wBank], [uWorldBank, uRiver, uEarth])
    [0.07601250837541616, 0.07601250837541616, 0.07601250837541616]

Training with Backpropagation 反向传播算法训练 #

为什么叫反向传播算法，因为这个算法是从输出层到隐层的过程，也就是说，从最后一个神经元到第一个神经元的过程。这样的话，就可以用后向传播算法来训练了。

对于输出层调整顺序如下

计算节点当前输出结果和期望之间的差距
利用 dtanh 函数确定节点总输入需要如何变化
改变买个外部回指链接的强度值，按照学习比例调整

对于隐层调整顺序如下

将每个输出链接的强度值乘以其目标节点所需的该变量，累加求和
利用 dtanh 函数确定节点总输入需要如何变化
改变每个输入的强度值，按照学习比例调整

def backPropagate(self, targets, N=0.5):
    # 计算输出层的误差
    output_deltas = [0.0] * len(self.urlids)
    for k in range(len(self.urlids)):
        # 偏差量
        error = targets[k] - self.ao[k]
        # 如何变化
        output_deltas[k] = dtanh(self.ao[k]) * error

    # 计算隐藏层的误差
    # 这里就体现了反向传播，输出层的变化要向上游所有的隐藏层进行变化
    hidden_deltas = [0.0] * len(self.hiddenids)
    for j in range(len(self.hiddenids)):
        error = 0.0
        # 遍历输出层的每个链接的误差值和 w->h 的权重比例计算，求和
        for k in range(len(self.urlids)):
            error = error + output_deltas[k] * self.wo[j][k]
        hidden_deltas[j] = dtanh(self.ah[j]) * error

    # 更换输出层
    for j in range(len(self.hiddenids)):
        for k in range(len(self.urlids)):
            change = output_deltas[k] * self.ah[j]
            self.wo[j][k] = self.wo[j][k] + N * change

    # 更新隐藏层
    for i in range(len(self.wordids)):
        for j in range(len(self.hiddenids)):
            change = hidden_deltas[j] * self.ai[i]
            self.wi[i][j] = self.wi[i][j] + N * change


# 训练查询
def trainquery(self, wordids, urlids, selectedurl):
    # 生成一个隐藏层
    self.generatehiddennode(wordids, urlids)

    # 初始化神经网络
    self.setupnetwork(wordids, urlids)
    self.feedforward()
    targets = [0.0] * len(urlids)
    targets[urlids.index(selectedurl)] = 1.0
    # 训练网络
    error = self.backPropagate(targets)
    # 更新到数据库里面
    self.updatedatabase()

训练 #

勘误参考 #

集体智慧编程–勘误表(1-4章)