页面的中文

Vol.
15,No.
92004JournalofSoftware软件学报1000-9825/2004/15(09)1328基于多示例学习的中文Web目录页面推荐黎铭,薛晓冰,周志华+(南京大学计算机软件新技术国家重点实验室,江苏南京210093)ChineseWebIndexPageRecommendationBasedonMulti-InstanceLearningLIMing,XUEXiao-Bing,ZHOUZhi-Hua+(NationalLaboratoryforNovelSoftwareTechnology,NanjingUniversity,Nanjing210093,China)+Correspondingauthor:Phn:+86-25-83686268,E-mail:zhouzh@nju.
edu.
cn,http://cs.
nju.
edu.
cn/people/zhouzh/Received2004-02-12;Accepted2004-05-09LiM,XueXB,ZhouZH.
ChineseWebindexpagerecommendationbasedonmulti-instancelearning.
JournalofSoftware,2004,15(9):1328~1335.
http://www.
jos.
org.
cn/1000-9825/15/1328.
htmAbstract:Multi-InstancelearningprovidesanewwaytotheminingofChinesewebpages.
Inthispaper,aparticularwebminingtask,i.
e.
Chinesewebindexpagerecommendation,ispresentedandthenaddressedthroughtransformingittoamulti-instancelearningproblem.
ExperimentsontherealworlddatasetshowthattheproposedmethodisaneffectivesolutiontotheChinesewebindexpagerecommendationproblem.
Keywords:multi-instancelearning;Webmining;machinelearning;ChineseWebindexpagerecommendation;prefixtree摘要:多示例学习为中文Web挖掘提供了一种新的思路.
提出中文Web目录页面推荐这种特殊的Web挖掘任务,并且将其转化为多示例学习问题来解决.
在真实世界数据集上的实验结果显示,该方法能够有效地解决该问题.
关键词:多示例学习;Web挖掘;机器学习;中文Web目录页面推荐;前缀树中图法分类号:TP183文献标识码:A互联网技术的不断成熟和发展,使得在全球范围内实现资源共享和信息交换成为可能.
各种资源和信息以不同的格式、不同的存储方式分布在这个庞大分布式系统的各个结点上,并以一些固定的访问方式来提供用户使用.
互联网上这些巨量的、无固定结构的信息,使用户从中有效找出自己感兴趣的部分变得越发困难.
同时,从巨量信息中发掘出个性化信息和知识的要求也越来越大.
因此,Web挖掘技术[1]应运而生.
SupportedbytheNationalNaturalScienceFoundationofChinaunderGrantNo.
60105004(国家自然科学基金);theNationalOutstandingYouthFoundationofChinaunderGrantNo.
60325207(国家杰出青年科学基金);theNationalGrandFundamentalResearch973ProgramofChinaunderGrantNo.
2002CB312002(国家重点基础研究发展规划(973))作者简介:黎铭(1980-),男,湖南长沙人,硕士生,主要研究领域为机器学习,数据挖掘;薛晓冰(1982-),男,硕士生,主要研究领域为机器学习,数据挖掘;周志华(1973-),男,博士,教授,博士生导师,主要研究领域为机器学习,数据挖掘,模式识别,信息检索,神经计算.
黎铭等:基于多示例学习的中文Web目录页面推荐1329Web挖掘技术大体上可以分成3大类[2]:Web内容挖掘,用于发现Web文档数据中的知识;Web结构挖掘,用于发现Web页面之间超链接相互指向的关系;Web用户日志挖掘,用于预测用户在Web上交互式信息查询中的行为.
其中,分析用户对于网上资源使用的偏好,能够更有效地为用户提供其可能感兴趣的信息,还可以帮助优化资源的分配,因此,Web用户日志挖掘非常重要.
本文所要解决的中文Web目录页面推荐问题正是一种特殊的Web用户日志挖掘问题.
通过对用户进行Web目录页面推荐,告诉用户当前浏览的Web目录页面中是否可能包含该用户感兴趣的内容页面,从而可以节省用户随着链接到达自己不感兴趣的Web页面的时间.
此外,该技术还可以用于中间件服务器上,以有效地指导由客户端发起Web页面复本缓存,平衡网络负载.
在进行中文Web页面推荐时,本文把目录页面及其相关联的内容页面看成一个个的包,从而将该问题转化为一个多示例学习(multi-instancelearning)[3]问题.
实验证明,通过多示例学习的方法能够有效地解决中文Web目录页面推荐问题,并且取得比传统方法更好的结果.
本文第1节简单介绍多示例学习以及Web目录页面推荐问题.
第2节介绍对于中文Web页面的特征抽取和包生成方法.
第3节叙述针对目录页面推荐问题提出的Fretcit-kNN算法.
第4节给出实验结果.
最后是结束语.
1多示例学习和Web目录页面推荐1.
1多示例学习20世纪90年代中期,Dietterich等人[3]在对药物活性预测问题的研究中首先提出了多示例学习这个概念.
在多示例学习问题中,训练集不再是由若干示例组成,而是由一组含有概念标记的包(bag)组成,每个包是若干没有概念标记的示例集合.
如果一个包中至少存在一个正例,则该包被标记为正包;如果一个包中不含有任何正例,则该包为反包.
学习系统通过对已经标定类别的包进行学习来建立模型,希望尽可能正确地预测不曾遇到过的包的概念标记.
与监督学习相比,多示例学习中的示例是没有概念标记的,这与监督学习中所有示例都有概念标记不同.
因此,多示例比监督学习更加困难.
Dietterich等人[3]发现,C4.
5决策树、BP神经网络等常用的监督学习算法很难用于解决多示例问题.
然而,由于多示例学习具有独特的性质和广泛的应用前景,属于以往机器学习研究的一个盲区,因此在国际机器学习界引起了广泛的反响,被认为是和监督学习、非监督学习、强化学习并列的一种学习框架[4].
研究者们已经提出了很多多示例学习的算法,例如:APR(axis-parallelrectangle)[3],DiverseDensity[5],Citation-kNN[6],ID3-MI[7],RIPPER-MI[7],BP-MIP[8]等.
Zhou和Zhang[9]将集成学习(ensemblelearning)技术用于多示例学习,在基准测试上取得了迄今最好的结果,他们还指出,将传统的监督学习的着眼点从示例的层次上升至包的层次,就可以将传统的监督学习算法改造为多示例学习算法.
此外,还有一些学者对APR算法的PAC-可学习性进行了研究,并得到了一些有意义的结论[10,11].
1.
2Web目录页面推荐在WorldWideWeb中富含信息的网页通过超链接相连,形成了一个庞大的网状结构.
用户需要沿着超链接去寻找自己感兴趣的信息.
这势必会经常出现用户通过看似相关的超链接而访问到与自己实际信息需求无关的网页.
如果能够在用户访问某个页面时就告诉用户,该页面中是否包含了他可能感兴趣的内容,就可以帮助用户更有效地访问网上的信息资源.
虽然WorldWideWeb上信息组织方式因不同的网站而有所区别,但是大体上都符合一种隐含的二级层次结构,即把详细内容写在一个页面中,而把和该页面内容相关的词语或句子作为指向该页面的超链接放在另一个页面中,作为该页面的入口索引.
本文中那些陈述内容的页面称为内容页面(contentpage),包含了大量指向内容页面的超链接的页面称为目录页面(indexpage).
在目录页面中,一条超链接唯一地代表了与之相关联的内容页面.
对于各大门户网站,例如:www.
sina.
com.
cn,各栏目页面就是一个目录页面.
图1(a)是一个新浪国内新闻的栏目页面,它包含了若干指向具体新闻页面的目录,其中圆圈中的一条目录对应于图1(b)中的内容页面.
1330JournalofSoftware软件学报2004,15(9)(a)Indexpage(a)目录页面(b)Contentpage(b)内容页面Fig.
1Indexpageandcontentpage图1目录页面和内容页面通过分析用户所遇到的目录页面以及用户是否认为该目录页面包含自己感兴趣的内容,可以得到某个特定用户在信息需求上的偏好.
当浏览新的目录页面时,用户能够得到根据自己偏好分析所得出的反馈,它指出当前目录页面是否可能包含用户感兴趣的信息.
本文中称这个过程为Web目录页面推荐(Webindexrecommendation).
在Web目录页面推荐过程中,用户只需指出某个目录页面中是否包含其感兴趣的内容,而无须指出感兴趣的具体链接,这样不仅便于用户使用,还可以简化人机界面的设计.
但这样一来,与请求用户具体指出感兴趣的链接相比,推荐问题变得更加复杂.
幸运的是,如果把每个内容页面看成一个示例,目录页面就是包含若干示例的包,那么Web目录页面推荐问题就映射为一个多示例学习问题,这样就可以利用多示例学习技术来解决这个问题.
2特征抽取2.
1Web页面的特征抽取内容页面是用户感兴趣信息的主要载体,从内容页面中有效抽取最能表征用户感兴趣信息的特征是精确进行Web目录页面推荐的必要前提.
一个内容页面中包含了图像、动画、音频、超链接等丰富的信息表达方式,但最主要的信息传递方式还是正文的文字信息.
为了简单起见,本文只处理正文信息.
通常情况下,一篇文章中出现频率高的词汇都从某一个侧面反映了文章的主题.
当然,对于那些诸如"如果"、"但是"、"而且"等无意义的虚词将不作考察.
这些高频词是传递文章所包含信息的关键性词汇,因此可以用其作为属性值来表示整篇文章.
本文使用内容页面正文中出现频率最高的p个词汇,形成一个p维特征向量W=[w1,w2,…,wp]T来代表内容页面,其中wi(i=1,2,…,p)是W对应的内容页面正文中出现频率第i高的词汇.
一个包含有m个内容页面的目录页面就可以表示成一个含有m个示例的包Bag={[w11,w12,…,w1p]T,[w21,w22,…,w2p]T,…,[wm1,wm2,…,wmp]T}.
这样,对于中文Web页面特征抽取的关键就是如何准确地从中文Web页面中提取出高频词.
2.
2中文高频词提取与英文不同,中文的词汇不像英语中的单词那样是自然分割的,而是词和词之间紧密连接成为句子.
句子中的词汇需要人为地通过语境来切分,同一句话所表达的意思会因不同的切分方式而有所不同.
在中文分词问题上,主要有两大类解决办法,一是基于词典的分词,另一种是无词典的分词.
由于Web页面推荐中所涉及到的词汇内容广泛,并且可能包括相当数量的专用名词,显然,基于词典的分词方法难以满足要求.
同时,这些所需要的词汇必须在出现频率上满足一定的要求.
因此,使用一些基于词汇出现频率统计的无词典的分词技术[12],可以较准确地提取出文本中的高频词.
本文在词频统计基础上引入前缀树结构,在不影响查找时间的同时有效地降低存储开销.
前缀树是根据字黎铭等:基于多示例学习的中文Web目录页面推荐1331串的前缀组织而成的树型结构,如图2所示.
前缀树第i层的每个结点中都包含了一个长度为i的字串以及该字串在文中出现的频率.
父结点中的字串是子结点中字串的最大前缀.
互为兄弟结点的字串仅最后一个汉字不同.
中央政府(2)中央政(2)中华人民(3)中华人(3)中国心(2)中国人(2)中央(2)中华(4)中国(5)中(13)Fig.
2Aninstanceofprefixtree图2前缀树的一个实例对于高频词的抽取可以分成预处理、字串形成和后处理3个阶段.
在预处理阶段,首先利用绝对切分标记、条件切分标记以及特殊字符[12]将征文内容划分为若干字串,然后分别统计每个字的出现频率,对于大于某个阈值fmin的字记录其在文中的位置.
在字串形成阶段,针对每一个字频高于fmin的汉字C,构造一棵以C为根的前缀树,并把文中所有以C为第1个汉字并且C后面每个汉字出现频率都大于fmin的字串加入到前缀树中.
如果有包含该字串的结点,则把该结点的频率加1.
最后从前缀树中导出候选高频词集合.
具体算法如图3所示.
在后处理阶段,为了得到最小的高频词集合,需根据预先设定好的阈值从候选高频字串集合中除去冗余的汉字模式[13].
设字串C1是字串C2的前缀或后缀,w=Freq(C1)/Freq(C2),其中Freq(C)表示字串C在文章中出现的频率.
若w≤0.
3,舍弃C1;若w≥0.
9,舍弃C2,这里0.
3与0.
9均为经验值[13].
Algorithm:Extract_FreqStrExtractingfrequentstringfromgiventextInput:thegiventextT,theminimumfrequencyrequiredfminOutput:thesetoffrequentstringcontainedinthetext,SProcess:InitializeS←ForeachcharactercinTwithFreq(c)≥fminBuildaprefixtreePreTreerootedatcForeachappearanceofcinTSetstartPostothepositionofthecurrentappearanceofcinTtmpPos←(startPos+1)Whilethecharacterc′indexedbytmpPosisnotaseparatorandFreq(c′)≥fminFormtmpStrbeginwithcandendedwithc′AddtmpStrtoPreTreetmpPos←(tmpPos+1)TraversePreTreeaddfrequentwordstoSFig.
3Algorithmforextractinghighfrequencycandidatewords图3候选高频字串抽取算法3Fretcit-kNN算法k近邻(k-nearestneighbor)算法是一种经典的惰性学习(lazylearning)[14]算法.
由于用户在进行浏览时,其Web日志是不断积累的,为了更好地利用这些数据,本文使用k近邻算法来进行学习.
k近邻算法的关键是如何度量两个样本之间的距离,通常采用欧式距离来度量.
在多示例问题中,样本是包含多个示例的包.
为了使k近邻算法能够适用于多示例学习,就必须给出两个包之间距离的度量方法.
Wang和Zucker在他们提出的扩展k近邻算法[6]中引入Hausdorff距离[15]来度量包之间的距离.
通俗地说,两个集合A,B之间的Hausdorff距离小于等于d当且仅当A中的每一个元素到至少一个B中的元素的距离不超过d,同时,B中的每一个元素到至少一个A中的元素的距离不超过d.
由于Hausdorff距离对于噪声比较敏感,他们建议在实际应用中使用最小Hausdorff距离(minimumHausdorffdistance):1332JournalofSoftware软件学报2004,15(9)minH(A,B)=max{h(A,B),h(B,A)}(1)其中,baBAhBbAa=∈∈minmin),(.
然而直接使用最小Hausdorff距离作为距离度量的k近邻算法有时候并不能很有效地解决多示例问题.
概念标记为正的包中可能存在伪正例(falsepositiveinstance)[6],而这些伪正例会吸引反包.
在使用最小Hausdorff距离计算一个含有一定数量伪正例的包的k个最近邻时,可能会因为反包的数量超过正包的数量,从而造成错误分类.
为此,Wang和Zucker[6]提出了鲁棒性更好的Citation-kNN算法.
该方法在使用多数投票对一个未知包x进行分类时,不仅要考虑r个离它最近的包的概念标记,同时还要考虑把x作为c近邻的所有包的概念标记,然后一并统计投票结果.
如果投票相等,则x为反包.
采用上述方法,可以较好地解决典型的多示例学习问题,例如药物活性预测问题[3].
然而对于本文中提出的Web目录页面推荐问题来说,所有示例的属性都是非数值可枚举型的,不能像对待数值型属性那样直接使用欧氏距离进行计算.
如何计算两个示例的特征向量之间的距离成为重要的问题.
本文在第2节提到,每一个内容页面使用一个p维特征向量来表示,第i维的属性值为对应的内容页面中的第i频繁词.
从直观上说,如果两个内容页面所传达的信息内容越相近,它们所对应的特征向量中高频词相同的概率也应该越大,因此,如果两个特征向量包含相同的词汇越多,距离就应该越小.
根据这个启发式原则,本文定义如下距离计算方法.
设两个示例a=[x1,x2,…,xp]T,b=[y1,y2,…,yp]T是p维特征向量,则a和b之间的距离为∑==pjijiyxp1,),(11δba(2)其中,δ(x,y)=1iffx=y.
这样,把式(1)中计算两个示例之间距离的部分用式(2)来代替,就得到了频繁项最小Hausdorff距离(frequenttermminimumHausdorffdistance).
将其作为Citation-kNN的距离度量,便得到了适合于解决Web目录页面推荐问题的方法FREquentTermCITation-kNN,简记为Fretcit-kNN.
在使用Fretcit-kNN对一个未知包x的概念标记进行预测时,首先需要计算x和训练集中其他包之间的频繁项最小Hausdorff距离,从而找出x的r个最近邻以及所有把x作为c近邻的包.
然后根据这些包的多数投票结果来确定x的概念标记.
4实验及结果本文采用来自于真实世界的数据来检验Fretcit-kNN算法在解决中文Web目录页面推荐问题上的有效性.
实验数据由117个目录页面及其所有相关的内容页面产生,这些页面分别来自新浪、搜狐等知名中文门户网站.
整个数据集未经过压缩的大小为854MB,每个目录页面最多包含247个链接,最少包含26个.
8个志愿者分别在浏览了每个目录页面及其相关的内容页面之后,按照如下规则给每一个目录页面添加一个概念标记:对于当前浏览的目录页面,如果能够通过其包含的某条超链接访问到自己所感兴趣的内容页面,则标记由该目录页面所生成的包为正包;如果该目录页面中所有目录所相关的内容页面自己都不感兴趣,则标记由该目录页面所生成的包为反包.
把这8组不同的概念标记分别与从这117个目录页面生成的包相结合,就得到了8个不同的中文Web目录页面推荐问题的数据集,其分别包含的正例数和反例数见表1.
针对上述每一个数据集,随机挑选66%的数据(77个样本)作为训练集,余下的34%的数据(40个样本)用作测试.
其中,训练集和测试集中正例与反例的分布与原数据集相同.
本文使用两种常用的文本分类算法和Fretcit-kNN算法作比较.
一种是TFIDF算法[16],它把每个文本表示成为一个特征向量,并分别导出一个表示正例的特征向量和一个表示反例的特征向量,然后计算待分类文本对应向量和这两个向量夹角的余弦值,待分类文档的概念标记被置成余弦值最大的向量的概念标记.
另一种算法是普通的k近邻算法,它使用式(2)来计算两个示例之间的距离.
本文中称其为Txt-kNN算法.
对于上述两种非多示例学习算法,目录页面及其所有相关内容页面的正文连接成的一段文字就看成一个示例,从中提取高频词作为特征向量.
黎铭等:基于多示例学习的中文Web目录页面推荐1333Table1Distributionofpositiveandnegativeinstancesinthedatasets表1数据集中正例和反例分布情况DatasetPositiveNegativeU14770U24374U39621U48433U55661U63978U77938U83978Table2ExperimentalresultsofTFIDF,Txt-kNNandFrecit-kNNwith5-dimentionfeaturevector表2TFIDF,Txt-kNN和Fretcit-kNN在5维特征向量下的比较结果TFIDFTxt-kNNFretcit-kNNDataAccu.
RecallPreci.
Accu.
RecallPreci.
Accu.
RecallPreci.
U1.
769.
4001.
00.
692.
667.
588.
641.
400.
545U2.
718.
2141.
00.
872.
6431.
00.
795.
714.
714U3.
9741.
00.
970.
9491.
00.
941.
9741.
00.
970U4.
769.
857.
828.
692.
821.
767.
718.
893.
758U5.
821.
947.
750.
872.
842.
889.
846.
895.
810U6.
590.
538.
412.
615.
462.
429.
795.
538.
778U7.
9491.
00.
929.
974.
9621.
001.
001.
001.
00U8.
872.
769.
833.
872.
923.
750.
949.
923.
923Avg.
808.
716.
840.
817.
790.
796.
840.
795.
812Table3ExperimentalresultsofTFIDF,Txt-kNNandFrecit-kNNwith7-dimentionfeaturevector表3TFIDF,Txt-kNN和Fretcit-kNN在7维特征向量下的比较结果TFIDFTxt-kNNFretcit-kNNDataAccu.
RecallPreci.
Accu.
RecallPreci.
Accu.
RecallPreci.
U1.
769.
4001.
00.
615.
533.
500.
718.
533.
667U2.
718.
2141.
00.
769.
500.
778.
795.
714.
714U3.
9741.
00.
970.
949.
969.
969.
9231.
00.
914U4.
692.
750.
808.
641.
821.
719.
744.
821.
821U5.
8211.
00.
731.
872.
895.
850.
846.
947.
783U6.
590.
462.
400.
769.
462.
750.
641.
308.
444U7.
923.
962.
926.
949.
962.
9621.
001.
001.
00U8.
923.
846.
917.
846.
923.
706.
949.
923.
923Avg.
801.
704.
844.
801.
758.
779.
827.
781.
783Table4ExperimentalresultsofTFIDF,Txt-kNNandFrecit-kNNwith10-dimentionfeaturevector表4TFIDF,Txt-kNN和Fretcit-kNN在10维特征向量下的比较结果TFIDFTxt-kNNFretcit-kNNDataAccu.
RecallPreci.
Accu.
RecallPreci.
Accu.
RecallPreci.
U1.
769.
4001.
00.
667.
600.
563.
692.
533.
615U2.
718.
2141.
00.
846.
643.
900.
871.
929.
765U3.
923.
969.
939.
897.
969.
912.
9741.
00.
970U4.
59.
607.
773.
718.
893.
758.
846.
964.
844U5.
8211.
00.
731.
923.
947.
900.
9231.
00.
864U6.
641.
538.
467.
692.
385.
556.
718.
385.
625U7.
9741.
00.
963.
949.
9231.
001.
001.
001.
00U8.
923.
846.
917.
846.
923.
706.
9741.
00.
929Avg.
795.
697.
849.
817.
785.
787.
875.
851.
827在实验中,Fretcit-kNN的参数r和c分别被设置为3和5,Txt-kNN中的k值设置为3.
由于特征向量中的高频词的个数直接影响到特征向量对示例的表征能力,为此,实验需要在高频词个数不同的情况下来比较上述3种算法.
在高频词个数一定的情况下,首先得到TFIDF,Txt-kNN,Fretcit-kNN在每一个数据集上的正确率(accuracy)、查准率(precision)和查全率(recall),然后针对每种算法求出对应的上述3项指标在8个数据集上面的平均值.
表2~表4分别对应于高频词个数为5,7,10时的结果.
正确率、查准率、查全率的计算方式由式(3)~式(5)给出,其中设测试集中包含P个正例和N个反例,正例中包含被分类器正确分类的Pa个样本以及分类错误的Pr个样本,反例中包含被分类器误认为是正例的Na个样本以及正确识别为反例的Nr个样本.
1334JournalofSoftware软件学报2004,15(9)NPNPaccuarcyra++=(3)aaaNPPprecision+=(4)PPrecalla=(5)从表2~表4可以看出,在特征向量中各高频词数量不同的情况下,Fretcit-kNN在所有数据集上的平均正确率都明显优于其他两种非多示例学习算法,如图4所示.
其中Fretcit-kNN在特征向量中包含10个高频词时性能较好,只有12.
5%的错误率,分别是TFIDF和Txt-kNN错误率的61.
0%((10.
875)/(10.
795)=0.
610)和68.
3%((10.
875)/(10.
817)=0.
683).
值得注意的是,当特征向量包含高频词较少的时候(5个高频词),Fretcit-kNN也只有16%的错误率.
由此看出,Fretcit-kNN在只考虑Web页面中少量高频词的时候仍然有效.
TFIDFTxt-kNNFretcit-kNN0.
7750.
8000.
8250.
8500.
8750.
900Accuracy5710ThenumberofattributesFig.
4ComparisonofaccuracyundervariousnumberofattributesbetweenTFIDF,Txt-kNNandFretcit-kNN图4TFIDF,Txt-kNN和Fretcit-kNN不同属性值个数下的正确率对比对于查全率来说,Fretcit-kNN在3种不同的高频词个数的情况下,整体的表现也优于TFIDF和Txt-kNN.
从表2~表4中的数据可以计算出Fretcit-kNN查全率的平均值为80.
9%,而TFIDF和Txt-kNN的3种情况下查全率的平均值分别只有70.
6%和77.
8%.
因此Fretcit-kNN较其他两种算法能够发现更多用户感兴趣的页面.
对于查准率来说,Fretcit-kNN在表2~表4这3种不同情况下的平均值为80.
7%,优于Txt-kNN的78.
7%,但是差于TFIDF的84.
4%.
这说明在进行Web目录页面推荐时,Fretcit-kNN算法可能会向用户推荐比TFIDF更多的不感兴趣的内容.
虽然TFIDF的查准率比Fretcit-kNN高3.
7%,但其查全率比Fretcit-kNN低10.
3%.
因此综合3项指标来看,采用多示例学习的Fretcit-kNN算法明显地优于TFIDF和Txt-kNN这两种非多示例学习算法.
这表明,使用多示例学习能够较好地解决Web目录页面推荐问题.
5结束语本文使用多示例学习技术来解决中文Web目录页面推荐问题.
本文把每个内容页面看成一个示例,包含若干指向内容页面的超链接的目录页面就可以看成包含多个示例的包.
从而将中文Web目录页面推荐问题转化成一个多示例学习问题.
本文中利用基于词频统计的中文分词技术提取高频词作为示例的属性值,并定义了频繁项最小Hausdorff距离,从而得到多示例学习算法Fretcit-kNN.
在真实数据集上的实验证明,以多示例学习方法来解决中文Web目录页面推荐问题是有效的.
在将来的工作中,寻找一种方法来标定目录页面中那些用户真正感兴趣的超链接将更加方便用户迅速找到所需信息.
此外,由于本文使用的基于k近邻的算法需要保存所有的访问记录,如何通过只挑选一部分重要的记录并加以保存以减少存储和计算开销,从而使其具有能够处理更大规模数据的能力也是一个十分值得研究的问题.
References:[1]EtzioniO.
Theworldwideweb:Quagmireorgoldmine.
CommunicationsoftheACM,1996,39(11):65~68.
[2]KosalaR,BlockeelH.
Webminingresearch:Asurvey.
ACMSIGKDDExplorations,2000,2(1):1~15.
黎铭等:基于多示例学习的中文Web目录页面推荐1335[3]DietterichTG,LathropRH,Lozano-PérezT.
Solvingthemultiple-instanceproblemwithaxis-parallelrectangles.
ArtificialIntelligence,1997,89(1-2):31~71.
[4]MaronO.
Learningfromambiguity[Ph.
D.
Thesis].
Cambridge:MassachusettsInstituteofTechnology,1998.
[5]MaronO,Lozano-PérezT.
Aframeworkformultiple-instancelearning.
In:JordanMI,KearnsMJ,SollaSA,eds.
AdvancesinNeuralInformationProcessingSystems10.
Cambridge:MITPress,1998.
570~576.
[6]WangJ,ZuckerJD.
Solvingthemultiple-instanceproblem:Alazylearningapproach.
In:LangleyP,ed.
Proc.
of17thInt'lConf.
onMachineLearning.
SanFrancisco:MorganKaufmannPublishers,2000.
1119~1125.
[7]ChevaleyreY,ZuckerJD.
Solvingmultiple-instanceandmultiple-partlearningproblemswithdecisiontreesanddecisionrules.
Applicationtothemutagenesisproblem.
In:StrouliaE,MatwinS,eds.
LectureNotesinArtificialIntelligence2056,Berlin:Springer-Verlag,2001.
204~214.
[8]ZhouZH,ZhangML.
Solvingthemulti-instanceproblemwithneuralnetworks.
TechnicalReport,Nanjing:AILaboratory,DepartmentofComputerScienceandTechnology,NanjingUniversity,2002.
[9]ZhouZH,ZhangML.
Ensemblesofmulti-instancelearners.
In:LavracN,GambergerD,BlockeelH,TodorovskiL,eds.
LectureNotesinArtificialIntelligence2837,Berlin:Springer-Verlag,2003.
492~502.
[10]LongPM,TanL.
PAClearningaxis-alignedrectangleswithrespecttoproductdistributionsfrommultiple-instanceexamples.
MachineLearning,1998,30(1):7~21.
[11]AuerP,LongPM,SrinivasanA.
Approximatinghyper-rectangles:Learningandpseudo-randomsets.
JournalofComputerandSystemSciences,1998,57(3):376~388.
[12]HanKS,WangYC,ChenGL.
Researchonfasthigh-frequencystringsextractingandstatisticsalgorithmwithnothesaurus.
JournalofChineseInformationProcessing,2001,15(2):23~30(inChinesewithEnglishabstract).
[13]JinXY,SunZX,ZhangFY.
Adomain-independentdictionary-freelexicalacquisitionmodelforChinesedocument.
JournalofChineseInformationProcessing,2001,15(6):33~39(inChinesewithEnglishabstract).
[14]AhaDW.
Lazylearning:Specialissueeditorial.
ArtificialIntelligenceReview,1997,11(1-5):7~10.
[15]EdgarGA.
Measure,Topology,andFractalGeometry.
Berlin:Springer-Verlag,1990.
[16]JoachimsT.
AprobabilisticanalysisoftheRocchioalgorithmwithTFIDFfortextcategorization.
In:FisherD,ed.
Proc.
ofthe14thInt'lConf.
onMachineLearning.
SanFrancisco:MorganKaufmannPublishers,1997.
143~151.
附中文参考文献:[12]韩客松,王永成,陈桂林.
无词典高频字串快速提取和统计算法研究.
中文信息学报,2001,15(2):23~30.
[13]金翔宇,孙正兴,张福炎.
一种非受限中文文档抽词方法.
中文信息学报,2001,15(6):33~39.