基于距离的决策树学习算法用于Web分类任务的研究

理论计算机科学电子笔记157（2006）35-40www.elsevier.com/locate/entcs使用基于距离的决策树进行Web分类1诉 是真的。 F e rri2J. Hern'ana-Orallo2M.J. Ram 'ırez-Quintana2DSIC，UniversidadPolit'ecnicadeValencia，Caminode Vera s/n，Apdo.22012，46071 Valencia，Spain.摘要在Web分类中，网页主要根据其内容被分配到预定义的类别（内容挖掘）。但是，网站的结构可能会提供有关其类别的额外信息（结构挖掘）。传统上，这两种方法都是单独应用的，或者使用不生成模型的技术（如贝叶斯技术）进行处理。不幸的是，在某些分类背景下，一个可理解的模型变得至关重要。因此，将基于规则的技术（规则学习，决策树学习）应用于Web分类任务将是有趣的。 在本文中，我们概述了我们的通用学习算法，即所谓的基于距离的决策树学习算法（DBDT），可用于Web分类的场景。 该算法与传统算法的不同之处在于， 通过度量条件（“比”更接近）来定义。这一变化允许决策树处理结构化属性（列表、图形、集合等）。以及公知的名义和数字属性。一般来说，这些结构化的属性将被用来表示网站的内容和结构保留字：Web挖掘，分类，结构化数据，决策树，基于距离的方法。1引言Etzioni [4]将Web挖掘定义为使用数据挖掘技术从Web文档和服务中提取信息。由于Web上有大量可用的文档，因此在Web上执行的最常见的任务之一是将文档分类为一个或多个类别。为1这项工作得到了欧盟-印度跨文化传播项目信息和通信技术ALA/95/23/2003/077-054和巴伦西亚省政府GV 04 B/477赠款以及CICYT赠款TIN 2004-7943-C 04 -02的部分支助2电子邮件：{vestruch，cferri，jorallo，mramirez}@ dsic.upv.es1571-0661 © 2006 Elsevier B. V.在CC BY-NC-ND许可下开放访问。doi：10.1016/j.entcs.2005.12.04336诉Estruch等人/理论计算机科学电子笔记157（2006）35例如，这在必须对新闻文章进行分类、对电子邮件进行分类和过滤、推荐电影或音乐或搜索关于某个主题的信息（搜索引擎）的应用程序中是必不可少的。虽然有些作者将分类与分类3区分开来，但为了简单起见，在本文中，我们将两者作为同义词使用，因为一个分类问题可以由几个分类器解决。对Web文档进行分类的最简单方法是只考虑其中的文本部分（文本分类）。其基本思想是将文档分类为c类，如果文档中存在与c定义相关的然而，Web文档不仅仅是纯文本，包含在其他部分（如超链接）中的信息也可能与分类过程相关。例如，如果我们对体育新闻进行分类，如果我们的分类器认为一条体育新闻包含团队，比赛或体育场等词，或包含其他体育新闻的链接，则可以获得更准确的分类。因此，最近的研究解决了这个问题，从Web内容挖掘和Web结构挖掘融合的想法。例如，[7]将链接的文本附加到目标页面的文本。[1]考虑网页的文本及其相邻页面的文本和类别。 其他一些方法能够处理页面中的文本组件以及它们之间的链接，例如[2]，[5]或[6]。在本文中，我们研究了DBDT方法如何适用于Web分类问题。这种方法使我们能够将Web内容和Web结构挖掘集成在一个独特的框架中，通过使用结构化数据类型来表示每个组件或上下文特征（标题，关键字，文本，链接等）。在页面中找到。 然后DBDT使用该证据，其中通过度量条件（“比”更接近”）定义分裂准则，并处理结构化属性。 通过一个简单的Web分类实例说明了本文的组织结构如下。在第2节中，概述了DBDT算法。我们的方法的一个说明性例子在第3节中显示。最后，第4节提出了一些结论。2基于距离的决策树在[3]中，我们定义了一种名为基于距离的决策树的学习方法。这个建议是基于使用原型和距离来定义[3]分类是归纳模型的过程，因为每个文档只被分配一个类，而分类则涉及一个文档可以属于多个类的情况。诉Estruch等人/理论计算机科学电子笔记157（2006）3537决策树的划分。我们的决策树推理策略是中心分裂方法[8]的一种改进，包括计算一组属性原型，而不是考虑所有属性的另一种方法。基本上，对于每个属性和每个类，计算原型（使从它到其他属性的所有距离之和最小化的值），只考虑属于该属性和该类的值。 一旦这个过程完成，就选择一个属性来分割数据集。拆分通过将每个实例关联到其最接近的属性原型来进行。根据一些众所周知的启发式函数（增益比、GINI指数等）来选择分裂属性。为此，度量空间与每个属性相关联。请注意，将所有属性作为一个整体来处理的事实，就像中心分裂一样，将可理解的模型提取变成了一项更困难的任务，即使所涉及的属性是名义上的或数字的。这种中心分裂的结果与经典的决策树（参见下面的算法）没有很大的不同，当属性是名义型和数字型时，但是在我们的情况下，我们能够处理包含结构化属性的数据，例如集合，列表或树。P ROCE DUREDBDT（S，m）;//单属性中心分割。学习基于属性距离的决策INPUT：作为以下形式的示例的集合的训练集合S：（x1，. ..，xn），n≥1，其中每个属性都是标称的，数字化或结构化。度量空间与每个属性相关联。m是每个节点的最大子节点开始C← {Class（e）：e∈S}//C是现有类如果|C|<2 Then RETURN EndIf对于每个属性xj：//使用属性xj为每个类计算两个（或更多）中心如果V值（xj，S）<2则继续结束如果//下一次迭代ProtList←Compute Prototypes（xj，S，m，C）.如果大小（ProtList）≤1则返回结束如果Splitj← n//属性xj的可能拆分的集合Fori←1 tolength（ProtList）//对于所有原型S<$←{e∈S：i=Attracts（e，P rotList，x）}//S<$包含原型i吸引的示例i j iSplitj=SplitjS//我们将一个新的子节点添加到这个拆分中i←i+1End ForEnd ForBestSplit=ArgmaxSplitj（Opt mal it y（Splitj））//GainRatio，MDL，.对于BestSplit中的每个集合SkDBDT（Sk，n）//继续每个子节点端我38诉Estruch等人/理论计算机科学电子笔记157（2006）35端辅助函数Attracts和Compute Prototypes是该方法固有的。简而言之，函数Attracts只是确定哪个原型被分配了一个新的示例，函数ComputePrototypes为每个属性获取一组原型。3说明性示例在运行DBDT算法之前，前一步包括决定将要使用哪种数据类型以及它们的相关度量函数。让我们考虑下面的例子。用户对使用搜索引擎从因特网寻找体育新闻感兴趣。这个搜索引擎必须自动“决定”哪些可用文档符合搜索参数。因此，这个任务可以作为一个两类分类问题来解决。为此目的从HTML文档中提取的信息可以分为以下三类：• 结构：它指的是一个网站的页面是如何通过超链接相互连接的。在形式上，它被表示为一个图。然而，我们将使用一种更简单的方法，但它反过来是图挖掘文献中一个非常常见的提议：我们将图表示为一组有序对其中每对编码两个链接页面。具体地说，有序对中的每个项将存储一组关键字。此外，为了简洁起见，我们使用众所周知的集合之间的对称差异作为度量函数。• 内容：它处理网页中包含的信息。传统上，这些信息被表示为一个袋子或一个单词向量。在我们的例子中，我们只考虑一个属性，一个集合，它反映了整个内容（内容），并且我们使用集合之间的对称差异的适应作为度量函数。• Web用途：我们所说的Web用途信息是指从HTTP连接到Web服务器所获得的信息。所有这些数据都可以通过名义或数字属性进行编码。对于这些类型，我们可以使用离散度量或绝对值差异。在我们的示例中，此属性由Connections引用，它包含每日连接数。下一步是通过从处理过的数据集中训练模型来推断分类器，该数据集包含从某些网页收集的信息，例如表1中所包含的信息。在 Structure 属 性 中 的 集 合 { （ [Olympics ， games] ， [swim] ） ， （ [swim] ，[win]），（[win]，[medal]）}按以下方式解释。列表的第一个组成部分代表诉Estruch等人/理论计算机科学电子笔记157（2006）3539ID.结构内容康涅狄格类1{（[Olympics，games]，[swim]），（[swim]，[win]），（[Olympics，games]，[boxing]），（[win]，[medal]）{（0lympics，30），（held，10）（夏天，40）}10没有2{（[Olympics，games]，[swim]），（[swim]，[win]），（[win]，[medal]）}{（0lympics，15），（summer，20）（Athens，40）}20是的3{（[足球]，[欧洲]），（[欧洲]，[最终]），（[fenal]，[best，player]）}{（football，20），（champion，10）}40没有4{（[fotballl]，[match]），（[match]，[team，playyers]），（[fotballl]，[refer ee es]），（[match]，[results]）}{（足球，20），（欧洲，10），（冠军，12）}40是的5{（[fotballl]，[match]），（[match]，[team，playyers]），（[match]，[scores]）}{（football，20），（Europe，10）}40是的表1来自Web服务器示例存储库的信息。这个页面链接了另一个以“游泳”为唯一关键词的页面。对于集合的第二个和第三个组成部分，推理是相同的如果我们应用DBDT算法（使用基于准确性的启发式算法），我们发现要选择的第一个属性（作为第一个拆分）是Connection，值为40（第四个实例的Conn值）和10（第一个实例的Conn值在迭代过程中，属性Structure和Content分别用于拆分左侧和右侧的第一级节点。最后，新获得的节点是纯节点，过程停止，得到基于距离的决策树（见下图4）。a)b）、数据集康涅狄格更接近于41352Strne内容比纯节点纯节点纯节点纯节点分类：是类别：否类别：否分类：是图1.一、1.第一次分裂后的决策树（2）完成流程后的决策树ID.结构内容康涅狄格类{（[fotballl]，[match]），（[match]，[playyers]），（[match]，[results]）}{（足球，30），（举行，10）（欧洲，7）}36没有表2来自Web服务器示例存储库的信息。现在想象一下，如表2所述的网站与作为要向客户显示的候选网站的其他网站一起存储在列表中。在直接列出它们之前，我们应该对网站存储库进行分类，以便4数字对应于实例id，粗体数字代表特定分区的每个类数据集康涅狄格更接近于43512结构大于4531240诉Estruch等人/理论计算机科学电子笔记157（2006）35过滤不合适的信息。首先，我们查看connection属性的内部。由于每日连接数接近40而不是10，因此实例挂接到左侧第一级节点。然后，我们对结构属性重复相同的过程，在这种情况下，这个新网站的结构与表中第四个实例的结构比第三个更相似。然后，这个实例将被归类为体育新闻网站，并因此向用户列出。目前，我们正在思考如何将度量条件表达为与度量函数相关的模式（例如，属于可能是集合的模式）[9]，并获得包含如下规则的转换（更易于理解）模型：如果单词“football”出现在Content中，并且连接{（[football]，[match]），（[match]，[team，players]）}在Structure中找到，则此网站是体育媒体网站。4结论在 本 文 中 ， 我 们 已 经 研 究 了 DBDT 建 议 ， 以 解 决 Web 分 类 问 题 的fescherion。DBDT是用Java开发的（www.dsic.upv.es/users/elp/soft/），并针对结构化和非结构化、众所周知的分类问题进行了测试，显示出非常有趣的性能。出于这个原因，我们认为该算法可以应用于更具体的场景，例如分类Web。引用[1] S. 查克拉巴蒂湾Dom和P.因迪克使用超链接增强超文本分类在SIGMOD会议，第307-318页[2] M. Craven和S.斯莱特里关系学习与统计谓词发明：超文本的更好模型。Machine Learning，43（1/2）：97[3] V. Estruch，C. Ferri，J. 海恩和埃兹还有M. J. 是我D是结构化数据类型的基于数据的决策。技术报告，DSIC，UPV，2004年。[4] O. Etzioni万维网：泥潭还是金矿？Communications of the ACM，39（11）：65[5] 胡文臣。 Webclass：使用修改的决策树进行Web文档分类。[6] S. Slattery和T. M.米切尔关系域中测试集的发现。第十七届国际机器学习会议（ICML 2000），第895-902页[7] A. Sun，E.- P. Lim和W.- K. Ng.使用支持向量机的Web分类。在第四届国际会议上， 网络信息和数据管理讲习班，第96-99页，2002年11月。[8] 克里斯·桑顿。从垃圾中找出真相：学习如何变得有意义麻省理工学院出版社，马萨诸塞州剑桥，2000年。[9] J. 他不在，他在。 Estruch，C. 我和M. J. 是我 我确定是否有必要使用基于距离的方法。在第19届国际人工智能联合会议上，IJCAI05提交了。