放牧代码和思想
专注自然语言处理、机器学习算法
    Why join the Navy if you can be a pirate?

《智能Web算法》2.4 根据用户点击改进搜索结果

搜索引擎通过分析每个用户的每次搜索与用户的每次点击,从中学习到哪个结果才是用户最需要的,最终可以针对每个用户改进搜索结果。这是机器学习一个实例。

在《智能Web算法》的2.4章,给出了简单的实现,利用用户点击数据来训练搜索引擎,得出每个结果的用户点击分值,然后综合索引分值和PageRank,改进了最终的结果:

package com.hankcs;

import iweb2.ch2.clicks.UserClick;
import iweb2.ch2.clicks.UserQuery;
import iweb2.ch2.shell.FetchAndProcessCrawler;
import iweb2.ch2.shell.LuceneIndexer;
import iweb2.ch2.shell.MySearcher;
import iweb2.ch2.shell.PageRank;
import iweb2.ch5.classification.bayes.NaiveBayes;
import iweb2.ch5.classification.core.TrainingSet;

/**
 * @author hankcs
 */
public class ch2_4_UserClicks
{
    public static void main(String[] args) throws Exception
    {
        //===========================================================================================
//
// -- Data (Business news URLs and 3 spam pages)
//
        FetchAndProcessCrawler crawler = new FetchAndProcessCrawler("C:/iWeb2/data/ch02",5,200);

        crawler.setUrls("biz");
        crawler.addUrl("file:///c:/iWeb2/data/ch02/spam-biz-01.html");
        crawler.addUrl("file:///c:/iWeb2/data/ch02/spam-biz-02.html");
        crawler.addUrl("file:///c:/iWeb2/data/ch02/spam-biz-03.html");

// or use ALL the pages
// crawler.setAllUrls();

        crawler.run();

//
// -- Lucene
//
        LuceneIndexer luceneIndexer = new LuceneIndexer(crawler.getRootDir());
        luceneIndexer.run();
        MySearcher oracle = new MySearcher(luceneIndexer.getLuceneDir());

//
// -- PageRank
//
        PageRank pageRank = new PageRank(crawler.getCrawlData());
        pageRank.setAlpha(0.9);
        pageRank.setEpsilon(0.00000001);
        pageRank.build();

//
// -- Load the user clicks
//
        // 捕获用户点击
        UserClick aux = new UserClick();
        // 载入训练实例
        UserClick[] clicks = (UserClick[]) aux.load("C:/iWeb2/data/ch02/user-clicks.csv");
        // 创建训练集
        TrainingSet tSet = new TrainingSet(clicks);

//
// -- Create the classifier and train it
//
        // 定义分类器
        NaiveBayes naiveBayes = new NaiveBayes("Naive Bayes", tSet);
        naiveBayes.trainOnAttribute("UserName");
        naiveBayes.trainOnAttribute("QueryTerm_1");
        naiveBayes.trainOnAttribute("QueryTerm_2");
        naiveBayes.train();

        oracle.setUserLearner(naiveBayes);

//
// -- Combined ranking
//
        UserQuery dmitryQuery = new UserQuery("dmitry","google ads");
        oracle.search(dmitryQuery,5,pageRank);

        UserQuery babisQuery = new UserQuery("babis","google ads");
        oracle.search(babisQuery,5,pageRank);

    }
}

顺带一提,从Google Code检出的配书源码有一处错误,贝叶斯分类器的关注属性设置有误,会导致训练无效。

我调试了很久才发现不对劲,希望读者朋友不要重蹈覆辙。

贝叶斯分类器读取了用户点击数据,并且统计了每次点击的相关属性。

假如用户"dmitry"搜索"google ads",那么这次搜索被分类器分为三个属性:

dmitry
google
ads

用户的一次搜索被称为一次实例,每个实例I被分解出为若干个属性A,比如上面分解出了三个属性,分别是用户id、搜索词第一部分、搜索词第二部分(这是分词器的功劳)。两个实例只要任意属性不同,则被视为不同的实例。现在有一个备选的搜索结果C,怎么知道C就是用户想要的结果的概率有多大呢?这是一个后验概率的绝佳应用场景,记所求概率为P(C|I),即实例I发生了并且实例I属于概念C的概率。由贝叶斯公式可以知道P(C|I)=P(I|C)*P(C)/P(I)。

求P(I|C)对应于贝叶斯分类器/iweb2/ch5/classification/bayes/NaiveBayes.java的如下方法

/**
     * 已知用户想要的的是c,用户查询i的概率
     * @param i
     * @param c
     * @return
     */
    public double getProbability(Instance i, Concept c)
    {

        double cP = 1;

        // 遍历实例的每个属性
        for (Attribute a : i.getAtrributes())
        {

            // 如果是训练集要用到这个属性
            if (a != null && attributeList.contains(a.getName()))
            {
                Map<Attribute, AttributeValue> aMap = p.get(c);
                AttributeValue aV = aMap.get(a);
                if (aV == null)
                {
                    // the specific attribute value is not present for the current concept.
                    // Can you justify the following estimate?
                    // Can you think of a better choice?
                    // 从来没有观察到的概念
                    cP *= ((double) 1 / (tSet.getSize() + 1));
                }
                else
                {
                    // 实例i的似然率等于观测到各个属性的概率的乘积
                    // 一个属性的概率=属性出现的次数/训练集中概念的实例数量
                    cP *= (aV.getCount() / conceptPriors.get(c));
                }
            }
        }

        return (cP == 1) ? (double) 1 / tSet.getNumberOfConcepts() : cP;
    }

在这个方法里统计了对于实例I的所有受关注的属性,在所有属于概念C的实例中的出现概率,并且将其累乘起来作为结果返回。

求P(C)则简单得多,对应于贝叶斯分类器/iweb2/ch5/classification/bayes/NaiveBayes.java的如下方法

/**
     * 获取c的先验概率,根据训练集中该概念出现的次数取得
     * @param c
     * @return
     */
    public double getProbability(Concept c)
    {
        Double trInstanceCount = conceptPriors.get(c);
        if (trInstanceCount == null)
        {
            trInstanceCount = 0.0;
        }
        return trInstanceCount / tSet.getSize();
    }

P(I)对应于贝叶斯分类器/iweb2/ch5/classification/bayes/NaiveBayes.java的如下方法

/**
     * 获取观察到实例i的概率 This method calculates the denumerator of Bayes theorem
     * @param i
     * @return the probability of observing <CODE>Instance</CODE> i
     */
    public double getProbability(Instance i)
    {
        double cP = 0;

        for (Concept c : getTset().getConceptSet())
        {

            cP += getProbability(i, c) * getProbability(c);
        }
        return (cP == 0) ? (double) 1 / tSet.getSize() : cP;
    }

这里稍微转了个弯,统计了全部“用户实际需要概念小c,最终搜索I,小c是训练集中任意的概念”的概率之和,并将其作为结果返回。

搜索结果就是将三个分数统计起来:

double indexScore = docResults[i].getScore();

                double pageRankScore = pR.getPageRank(url);

                BaseConcept bC = new BaseConcept(url); // 创建一个实例,对应着文件名

                double userClickScore = learner.getProbability(bC, uClick);
                // 打印出来看看
                System.out.println(uQuery.getUid() + " click " + url + " -> " + userClickScore);

                // Create the final score
                double hScore;

                if (userClickScore == 0)    // 计算最终(混合)分数
                {

                    hScore = indexScore * pageRankScore * EPSILON;

                }
                else
                {

                    hScore = indexScore * pageRankScore * userClickScore;
                }

                // Update the score of the results
                docResults[i].setScore(hScore);

知识共享许可协议 知识共享署名-非商业性使用-相同方式共享码农场 » 《智能Web算法》2.4 根据用户点击改进搜索结果

分享到:更多 ()

评论 2

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址
  1. #1

    所以您修正過的部分是哪邊呢? 在下才疏學淺,能否明示一二?

    ffmm2年前 (2015-08-04)回复
    • 两份代码对比一下就知道了

      hankcs2年前 (2015-08-04)回复

我的开源项目

HanLP自然语言处理包基于DoubleArrayTrie的Aho Corasick自动机