搜索引擎个性化查询服务研究

1搜索引擎个性化查询服务研究北京大学计算机科学技术系冯是聪Jun20022目录•引言•相关研究•自动中文网页分类•用户访问模式•个性化查询服务•进度安排•演示3引言•研究背景•问题的提出•技术路线•系统的体系结构•系统的数据源及特征4研究背景-1•的发展–1989年3月,首次提出WorldWideWeb的概念–1990年9月，基于文本的第一个原型开始运行–1993年2月，发展的高峰–1995年4月，成为Internet上的第一大应用服务–1997年12月，网上大约有3亿2000万网页–2000年2月，不重复网页超过10亿–2002年6月，Google索引超过20亿网页5研究背景-2•国内的发展–1994年，开始登陆中国–2002年1月，上网计算机1,254万台，专线上网计算机数为234万台，拨号上网计算机数为1,020万台。个。上网人数3,370万–“天网”估计目前网页数已经超过5000万•导航系统的分类–Spider式：数量大，准确性低–目录式：数量受限，准确性高6问题的提出•不能提供目录式导航服务。用户希望Spider式搜索引擎同时能够提供目录导航服务。•检索结果中无关或无用的网页过多。大约有一半的结果是无关的。80%用户仅对前2页的查询结果感兴趣。•没有考虑用户的特性。如果输入相同的查询条件，搜索引擎就会返回相同的结果。用户希望能够提供个性化服务。7技术路线图1技术路线•三个方面的问题–网页自动分类–用户访问模式–个性化查询服务匹配网页类别用户类别用户特性网页分类分类8系统的体系结构图2系统的体系结构浏览器天网搜索引擎用户访问模式41网页23用户日志分析器分类器请求响应Web日志文件网页抓取器网页类别类别综合器个性化检索9系统提供的服务•目录式导航服务•重品级（Re-Ranking）及过滤（Filtering）服务。重品级：根据不同用户的访问模式，调整检索返回的URL的权重。使用户感兴趣的URL被排列在查询结果的顶端。•投递（Delivering）或推荐（Recommendation）服务10系统的数据源及特征•数据源–搜索引擎收集的网页–用户静态信息：用户注册信息–用户动态信息：用户访问日志和用户访问网页时的反馈信息等•特征–海量–动态性–不规则性11相关研究•搜索引擎–搜索引擎发展历史–搜索引擎分类–搜索引擎研究动态•自动文本分类–文档模型–训练集与测试集–分类算法–特征选取算法–阈值策略–分类器的性能评价•Web个性化–Web个性化系统的分类–创建基于Web的个性化服务系统的一般步骤–典型的Web个性化系统12搜索引擎•搜索引擎发展历史•搜索引擎分类•搜索引擎研究动态13搜索引擎发展历史•第0代搜索引擎：1994年春天–Lycos:100万网页,10秒以上,“查全率”•第1代搜索引擎：1996年–AltaVista,Inktomi:5000万网页,1000万次检索•第2代搜索引擎：1998年–Google,Inktomi:试图收集整个Web,“查准率”,超文本链的分析和用户反馈•第3代搜索引擎：目前14搜索引擎分类•基于机器人（Robot）的搜索引擎–国外：Google、AltaVista、NorthernLight、Excite、Infoseek、Inktomi、FAST、Lycos等–国内：天网、百度、悠游等•目录式（Directory，或Catalog）搜索引擎–Yahoo!、AOL、Lycos、Google•元（Meta）搜索引擎–ByteSearch、Mamma、MetaCrawler、Profusion15搜索引擎研究动态•多媒体搜索引擎–Google图像搜索工具，•个性化搜索引擎–Google、MSN开展了这个方面的研究•智能化搜索引擎–Askjeeves和尤里卡()•面向主题的搜索引擎–FocusedCrawler•动态网页—“活的老鼠”不好抓–自动文本分类•文档模型•训练集与测试集•分类算法•特征选取算法•阈值策略•分类器的性能评价17文档模型•统计模型–向量空间模型（VSM，VectorSpaceModel）：1969年GerardSalton和McGill提出–Wij=tfij/dfj•潜在语义索引(LSI,LatentSemanticIndexing)–也用向量表示特征项，但是每一个向量代表一个“概念”。由Dumais,Furnas,Landaver和Harshman于1990年提出•概率模型–使用概率构架来表示特征项。由Belkin和Croft于1992年提出18训练集与测试集•TREC会议网站（）•路透社的新闻稿（最新为Reuters21578）•全美医学文献（MEDILINE）•第5次TREC会议出现了以新华社新闻稿件为训练文档的中文数据集•其他语种的文集，如西班牙语、德语、意大利语和法语等•目前还没有出现中文版的Web标准文集19分类算法•简单词匹配法:根据文档和类名中共同出现的词决定文档属于哪些类。•基于同义词的词匹配法：先定义一张同义词表然后根据文档和类名以及类的描述中共同出现的词（含同义词）决定文档属于哪些类。同义词词典WordNet.•经验学习法–IndependentBinary分类系统–m-ary分类系统20分类算法分类自动文档分类算法关键词匹配法同义词匹配法经验学习法M-aryIndependencyBinaryWORDNNLLSFDTreeBayesNNetKNNDNFRocchio21IndependentBinary分类算法•DecisionTree（决策树，Dtree）•简单Bayes算法•神经网络(NNet,NeuralNetwork)•DNF(DisjunctiveNormalForm)归纳算法•Rocchio算法22M-ary分类算法•WORD算法•LLSF(LinearLeastSquaresFit)算法•最近邻居（NN）算法•KNN(k-NearestNeighbor)算法•分类算法的比较–SVM,kNN,LLSFNnet,NB23特征选取算法•文档频率（DF，DocumentFrequency）•信息获取（IG，InformationGain）•互信息（MI，MutualInformation）•开方拟合检验（CHI，χ2-test）•术语强度（TS，TermStrength）•CHI,MIDFTSMI24阈值策略•位置截尾法(RCut)•比例截尾法(PCut)•最优截尾法（SCut）•改进型截尾法(RTCut)•RTCutScutPCutRCut25分类器的性能评价•类别透视法（CategoryPerspectiveMetric）:BinaryClassification–查准率（p，precision）–查全率（r，recall）•文档透视法（DocumentPerspectiveMetric）:m-ary–10point或11point•决策透视法（DecisionPerspectiveMetric)baap26Web个性化•Web挖掘分类•Web个性化系统的分类•创建基于Web的个性化服务系统的一般步骤•典型的Web个性化系统27Web挖掘分类Web挖掘内容挖掘结构挖掘使用挖掘基于代理的方法数据库方法智能查询代理个性化Web代理多层数据库Web查询系统服务器日志分析单个用户使用分析信息过滤/分类28Web个性化系统的分类•Web内容生产者（Web站点经营者）–适应性Web站点–面向所有Web用户•和Web内容消费者（Web用户）–个性化Web站点–面向单个Web用户29创建基于Web的个性化服务系统的一般步骤-1•收集信息–客户端数据–中间代理–服务器端数据•组织并存贮信息–超媒体数据库或面向对象的数据库•分析信息–预处理–模式分析(结构,内容,使用挖掘)–模式发现30创建基于Web的个性化服务系统的一般步骤-2•提供个性化服务–个性化导航服务–信息过滤•个性化查询过滤•协作过滤–信息转换•服务器产生的文档内容进行变换31典型的Web个性化系统系统名称信息收集方式挖掘类型服务客户端代理服务器使用内容结构过滤导航转换WBI√√√√√ParaSite√√√WebTagger√√√√PowerBookmarks√√√√√DeNews√√√√√WebVCR√√√NetPerceptions√√√√√WEBMINIER√√√√SiteHelper√√√√√Letizia√√√√√WebWatcher√√√√√32自动中文网页分类•分类器体系结构•分类目录•训练集与测试集•特征选取算法•分类算法•阈值策略•分类器性能评价•展望33分类器体系结构待分类中文网页向量表示中文切词训练集实例中文切词特征选取算法分类算法校验集测试每个类的阈值训练结果类别表阈值策略候选类列表特征项向量表示34分类目录•国外具有代表性的分类标准–杜威十进分类法》、《美国科研系统常用分类法》、《联合国教科文组织大学学科分类法》•国内具有代表性的分类标准–《中国图书馆分类法》（2000年第四版）；国家标准GB/T13745-92《学科分类与代码》•借鉴的分类体系–《学科分类与代码》–Yahoo!中文网站分类目录–Google使用的OpenDirectory分类目录35分类体系非学术性学术性人文与艺术新闻与媒体商业与经济社会与文化区域娱乐与休闲政府与政治教育自然科学社会科学计算机与因特网医疗与健康视觉艺术摄影三层…………36类别分布类别分布图3.5%2.2%7.6%13.3%2.5%6.4%11.1%2.5%13.6%13.9%8.1%15.4%人文与艺术新闻与媒体商业与经济娱乐与休闲教育区域与组织社会与文化政府与政治自然科学社会科学计算机与因特网医疗与健康37分类目录极其代码表38训练集与测试集•实例网页选取原则–数量:共20；15训练集；5测试集；Thumb–质量–避免重复–分布–层次模型•网页实例集及分类目录收集整理工具•训练集中各个类别训练实例数量的分布39网页实例集收集整理小工具40训练集中各类训练实例数量的分布类别名类别数实例数人文与艺术24419新闻与媒体13294商业与经济481343娱乐与休闲881814计算机与因特网581041教育18301区域531070自然科学1132082政府与政治18352社会科学1042069医疗与健康1362295社会与文化661329共计7391187641特征选取算法定义（1）t表示一个特征项；c表示一个类别；N为训练集中所有实例网页数；A为t和c同时出现的次数；B为t出现而c没有出现的次数；C为c出现而t没有出现的次数；D为t和c都没有出现的次数。)()()()()(22),(DCBADBCACBADNct42定性分析-1•属性1–如果A-0，B-N，那么χ2算法不能够过滤掉不合适的候选特征项。换句话说，它保留了本该过滤掉的噪音。•证明1–引入两个变量Df和Tr–A+B=Df(2);A+C=Tr;(3)–结合(1),(2),(3)和A-0,B-N,我们可以得到公式(4)(4)DfNTrDfct),(243定性分析-2•属性2–如果A-0，B-0，那么χ2算法对低频词不公平。换句话说，它删除了本该保留的特征项•证明2–结合（1），（2），（3）和A-0,B-0,我们可以得到公式（5）(5)TrNTrDfct),(244中文网页的特征•使用中文设计–区别术语•词•关键词•特征项•包含丰富的HTML标签–影响权重–不影响权重•包含各种广告信息、网页设计人员的注释、版权申明等无关或无用信息45一个新的特征选取算法•第1步噪音清除–分析中文网页的结构的三类特殊规则•TABLE标签的大小和位置•TABLE标签的数量及其包含超链的数量•最