（计算机软件与理论专业论文）基于社区标签图与维基百科的web对象分类研究.pdf

中山大学硕士学位论文 摘要 论文题目：基于社区标签图与维基百科的w e b 对象分类研究 专业：计算机软件与理论 硕士生：李裕东 指导老师：印鉴教授 摘要 近年来随着互联网的发展，网络社区化产生了许多具有研究价值的社区数 据，社区数据的相关研究已经成为w e b 挖掘领域的一个热点。基于社区标签图 的w e b 对象分类的方法是近年来w e b 挖掘领域的一个研究方向，它将社区标签 作为w e b 对象的特征，通过社区标签图来构建w e b 对象之间的联系，利用源领 域数据来指导目标领域数据的分类，解决了缺乏w e b 对象特征和缺乏类标记数 据的问题。但是，由于基于社区标签图的w e b 对象分类方法只通过社区标签匹 配的方式来构建对象之间联系，所以并不能更深层次地挖掘对象之间的潜在语 义联系。 本文研究在缺乏类标记数据环境下如何利用社区标签数据和维基百科知识 库来对w e b 对象进行分类，提出了一种基于维基百科概念图的w e b 对象分类算 法，从语义层面上挖掘w e b 对象之间的潜在联系。首先，本文研究了如何从维 基百科中提取语义联系，包括同义概念、多义概念、类概念以及关联概念等， 并将这些语义联系引入到社区标签图中，构造维基百科概念图。接着，本文将 维基百科概念和w e b 对象间的相邻性引入到分类算法中，提出了一种基于维基 百科概念图的w e b 对象分类算法。实验表明，本文提出的基于维基百科概念图 的w e b 对象分类方法能够有效挖掘w e b 对象之间的潜在联系，并且取得更好的 分类效果。 关键词：社区标签，维基百科，w e b 对象分类，w e b 挖掘 中山大学硕七学位论文 a b s t r a c t t i t l e ：r e s e a r c ho nw e bo b je c tc l a s s i f i c a t i o nb ye x p l o r i n gs o c i a lt a g g i n g g r a p h a n dw i k i p e d i a m a j o r ：c o m p u t e rs o f t w a r ea n dt h e o r y n a m e ：l iy u d o n g s u p e r v i s o r ：p r o f y i nj i n a b s t r a c t w i t ht h eg r o w t ho fi n t e m e t ，w ec a na c c e s sm o r ea n dm o r es o c i a li n f o r m a t i o n w i m g r e a tr e s e a r c hv a l u e r e s e a r c h0 1 1s o c i a li n f o r m a t i o nh a sb e c o m eah o tt o p i co f w e bm i n i n g i nr e c e n ty e a r s ，w e bo b j e c tc l a s s i f i c a t i o nm e t h o db a s e do ns o c i a l t a g g i n gg r a p ha l s ob e c o m e san e w r e s e a r c ht o p i co fw e b m i n i n g t h i sm e t h o db a s e d o ns o c i a lt a g g i n gg r a p ht a k e ss o c i a lt a g sa sf e a t u r e ，u s i n gs o u r c ed o m a i nd a t ah e l p 、析t l lt a r g e td o m a i nd a t a sc l a s s i f i c a t i o nt a s k , a n ds o l v e st h ep r o b l e mo fl a c ko f f e a t u r ea n dl a b e l e dd a t a h o w e v e r , w e bo b j e c tc l a s s i f i c a t i o nm e t h o db a s e do ns o c i a l t a g g i n gg r a p ho n l yb r i d g e sw e bo b j e c t sb ym a t c h i n gs o c i a lt a g s ，s 0t h a ti t sh a r dt o m i n i n gl a t e n ts e m a n t i cl i n k sb e t w e e nw e bo b j e c t s t h i sd i s s e r t a t i o nd o e sr e s e a r c h0 1 1h o wt ou t i l i z es o c i a lt a g sa n dw i k i p e d i at o h e l pw i t hw e bo b j e c tc l a s s i f i c a t i o n , a n dp r o p o s e s aw e bo b j e c tc l a s s i f i c a t i o n f r a m e w o r kb a s e do i ls o c i a lt a g g i n gg r a p ha n dw i k i p e d i aw i n ll e s sl a b e l e dd a t a i t a l s om i n e sl a t e n ts e m a n t i cl i n kb e t w e e nw e bo b j e c t s ，b r i d g i n gt h eg a pb e t w e e nd a t a t h es o u r c ed o m a i na n dt a r g e td o m a i n a tf i r s t ，t h i sd i s s e r t a t i o nd o e sr e s e a r c ho nh o w t oe x t r a c ts e m a n t i cl i n k sf r o mw i k i p e d i a , s u c ha ss y n o n y m , p o l y s e m e ，c a t e g o r y c o n c e p ta n da s s o c i a t ec o n c e p te t c ，t h e nc o n s t r u c t sw i k i p e d i ac o n c e p tg r a p hb y b r i n g i n gt h e s es e m a n t i cl i n k si n t os o c i a lt a g g i n gg r a p h n e x t ，i tp r o p o s e saw e b o b j e c t c l a s s i f i c a t i o nm e t h o db a s e d0 1 1 w i k i p e d i ac o n c e p tg r a p hb yb r i n g i n g w i k i p e d i ac o n c e p ta n dw e bo b j e c tn e i g h b o u r h o o d e x p e r i m e n tr e s u l t ss h o wt h a tt h e p r o p o s e dm e t h o do u t p e r f o r m st h es t a t e o f - a r ta l g o r i t h m ，m i n i n gl a t e n ts e m a n t i cl i n k b e t w e e nw e bo b j e c t s k e yw o r d s ：s o c i a lt a g ，w i k i p e d i a ，w e bo b j e c tc l a s s i f i c a t i o n ，w e bm i n i n g i i i 论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下， 独立进行研究工作所取得的成果。除文中已经注明引用的内容外， 本论文不包含任何其他个人或集体已经发表或撰写过的作品成果。 对本文的研究作出重要贡献的个人和集体，均己在文中以明确方式 标明。本人完全意识到本声明的法律结果由本人承担。 学位论文作者签名：越 日期：趔啤生幽一 学位论文使用授权声明 本人完全了解中山大学有关保留、使用学位论文的规定，即：学 校有权保留学位论文并向国家主管部门或其指定机构送交论文的电 子版和纸质版，有权将学位论文用于非赢利目的的少量复制并允许论 文进入学校图书馆、院系资料室被查阅，有权将学位论文的内容编入 有关数据库进行检索，可以采用复印、缩印或其他方法保存学位论文。 学位论文作者签名：蔗痒缛 日期：加i o 年g 月2q 1 日 导师签名： 印垮 日期：加。年g 月7 日 中山大学硕士学位论文第l 章引言 1 1 课题研究的背景 第1 章引言 随着互联网的迅速发展，互联网上的信息越来越丰富，呈爆炸式增长。海 量的互联网信息包含各种类型的数据，包括文本、图片、音乐、视频信息等等， 这些数据对象统称为w e b 对象。 目前对w e b 对象的研究主要关注于文本、图片、视频、音频等数据的挖掘 分析，而w e b 对象的分类问题是其中一个研究热点。对于文本分类问题，目 前许多研究主要集中在文本特征提取、分类方法改进、多标签文本分类、以及 半监督、迁移学习等分类学习方法上。对于图片、视频、音频等多媒体数据的 分类，研究的内容主要是基于内容的多媒体分类，而如何从图片、视频、音频 中提取有效的特征是其中的难点问题。 w e b 对象包含各种海量的异构数据，数据复杂而且非结构化。文献【l 】总结 了w r e b 对象分类的三大挑战性问题：第一，如何从这些非结构化的数据中提取 出有效的特征是关键，但是在实际中往往会遇到特征空间维度过大或者数据过 于稀疏等问题，而且缺乏有效的特征提取方法。第二，传统的w e b 对象分类方 法缺乏对w e b 对象之间的联系进行有效的挖掘。第三，对于分类问题而言，要 取得好的分类效果依赖于大量带有类标记的训练数据，但是现实中对数据进行 人工标记需要耗费大量的人力，缺乏足够带有类标签的训练数据。 近年来，随着w e b 2 0 的发展，互联网趋于社区化，越来越多的人开始在互 联网社区中分享信息。互联网社区化的发展不仅带来了许多社区化应用，也为 w e b 挖掘领域的研究提供了越来越多有研究价值的社区数据。比如，全球最大 的图片分享社区f l i c k r ，社区用户在f l i c k 上面上传和分享了成千上万张图片， f l i c k r 社区的用户可以使用标签来对图片进行标记；著名的网络书签网站 d e l i c i o u s ，社区用户可以分享各种新闻、资讯网页，d e l i c i o u s 社区的用户可以 使用标签来标记网页；全球最大的电子商务网站a m a z o n ，消费者可以对商品 的信息进行分享和交流，a m a z o n 的社区用户可以使用标签来对商品进行标记： 全球最大的百科全书系统维基百科( w i k i p e d i a ) ，通过社区用户协作编辑来创建 中山大学硕士学位论文基于社区标签图与维基百科的w e b 对象分类方法 和更新，汇集了多种语言对各种概念或对象的解释，是一个巨大的知识系统。 社区标签( s o c i a lt a g ) 是用户在分享网页、图片、音频、视频等w e b 对象时 用简洁的几个单词或短语来对w e b 对象进行标注的文本数据，它是社区用户基 于自身的理解而从不同角度对w e b 对象进行描述的数据。j i a w e ih a n 等人【l 】第 一次提出基于社区标签图的w e b 对象分类方法，利用w e b 对象的社区标签来 构造社区标签图( s o c i a lt a g g i n gg r a p h ) ，再通过优化迭代的过程来对w e b 对 象进行分类，解决了w e b 对象分类中缺乏对象特征和缺乏带有类标记样本的问 题。 本文的研究内容基于j i a w e ih a n 1 】等提出的基于社区标签图的w e b 对象分 类方法，结合维基百科提出了一种改进的w e b 对象分类方法。j i a w e ih a r t 1 】等 人提出的理论框架中，通过源领域数据来指导目标领域数据的分类学习，w e b 对象之间通过社区标签来建立联系。实际上源领域数据和目标领域数据存在差 异，仅仅通过社区标签匹配的方式难以挖掘w e b 对象之间的潜在联系。本文通 过引入维基百科，可以有效地填补源领域和目标领域数据间的领域差异，有效 地提高w e b 对象分类效果。 1 2 课题研究的意义 w e b 挖掘是近年来研究的一个热点，w e b 挖掘具有很广的应用领域，w e b 挖掘在组织w e b 数据、改进搜索引擎、增强社区个性化等方面都有重要的应用。 w e b 对象的分类问题作为w e b 挖掘的一个重要研究方向，具有很强的理论和应 用意义。随着w e b 2 0 的发展，出现了许多社区化的应用，如何组织和利用社 区化数据已经成为w e b 挖掘领域的一个新的研究热点。 本文研究如何将维基百科与社区化标签结合起来对w e b 对象进行分类，提 出了一种有效的w e b 对象分类方法。在基于社区信息的w e b 对象分类研究中， 本文提出的方法具有以下几方面的研究意义和贡献： 一、本文提出通过维基百科概念图来挖掘w e b 对象之间的语义关联，用维 基百科来填补源领域和目标领域之间的数据差异。利用维基百科来解决数据的 领域差异问题，不仅可以应用到基于社区标签图的异构w e b 对象分类问题，而 且可以拓展到其它基于文本的研究领域，因此本文提出的方法在一定程度上解 2 中山大学硕士学位论文第l 章引言 决了不同领域文本数据的差异问题。 二、实验结果表明，本文提出的基于维基百科概念图的w e b 对象分类方法 可以取得更好的分类效果。因此，本文提出的分类方法改进了基于社区标签图 的w e b 对象分类方法，实现了更好的分类效果。 1 3 论文的研究内容 w e b 对象分类问题是数据挖掘领域的一个研究热点，目前许多研究都集中 在同构数据的分类研究中，比如文本分类，图片分类、音频分类和视频分类等。 文献【l 】提出了基于社区标签的异构w e b 对象分类，通过社区标签图来利用源领 域的数据对目标领域的数据进行分类。文献【l 】提出了一种有效的w e b 对象分类 方法，可以有效地利用社区标签来挖掘不同领域对象间的联系，并解决了缺乏 类标记的数据问题。 本文基于文献【l 】提出的w e b 对象分类方法，将维基百科中的语义联系引入 到社区标签图中，提出了一种基于维基百科概念图的w 曲对象分类方法。本文 利用维基百科来建立不同领域对象间的潜在联系，通过挖掘对象间的同义词、 关联概念等信息来构建不同领域对象间的联系，利用对象间的关联来对w e b 对象进行分类，有效地解决了少量类标记样本的问题和不同领域之间数据的差 异问题。 如何利用不同领域数据间的潜在联系来进行w e b 对象分类是本文的研究重 点。文献【l 】中通过不同对象中所包含的相同社区标签来建立不同对象间的联系， 这种方法只能挖掘到不同对象间表层的联系。对于领域差别很大的数据来说， 这种简单的依靠社区标签相同来建立联系的方法就会很难奏效。本文通过从维 基百科中提取语义联系，包括同义概念、多义概念、类概念以及关联概念等， 并将这些语义联系引入到社区标签图中，可以有效地挖掘对象之间的联系。实 验表明，相比于文献【1 】提出的方法，本文提出的基于维基百科概念图的w e b 对 象分类方法可以有效挖掘w e b 对象之间的潜在语义联系，并且取得更好的分类 效果。 3 中山大学硕士学位论文基于社区标签图与维基百科的w e b 对象分类方法 1 4 论文的内容安排 本文的安排如下：第二部分介绍了w e b 对象分类的相关研究工作，包括各 种同构对象的分类方法的研究。第三部分阐述了w e b 对象分类面临的挑战和待 解决问题，并对w e b 对象分类问题进行抽象和描述。第四部分介绍文献提出 的基于社区标签的w e b 对象分类方法，并指出该方法存在的问题和待改善之处。 第五部分介绍了本文提出的利用维基百科来改进w r e b 对象分类的方法，阐述了 从维基百科中提取语义信息的方法，并基于维基百科概念图提出了w e b 对象分 类算法。第六部分介绍实验的对比结果，实验结果表明本文提出的方法整体上 优于文献提出的方法，提高了w e b 对象分类的效果。第七部分总结了本文的 研究内容和展望。 4 中山大学硕： 学位论文第2 章相关研究工作 第2 章相关研究工作 目前许多w e b 对象分类的方法大部分都关注于对同类数据的分类问题，比 如有文本分类，图片分类，视频分类以及音频分类等。本章总结了w e b 对象分 类的各种方法，包括分为传统基于内容的w e b 对象分类方法，基于社区标签的 相关研究和基于维基百科的w e b 对象分类方法，吸在缺少类标记训练样本环 境下的半监督学习、迁移学习等分类方法。 2 1 同构w e b 对象分类方法 w e b 对象包含网页对象、图片对象、视频对象等，同构w e b 对象分类方法 是指针对于同一种类型w e b 数据的分类方法，比如文本分类方法、视频分类方 法、图片分类方法等。同构w e b 对象分类方法的相关研究有很多，同构w e b 对象分类问题面临着一个共同的问题就是如何从这些复杂的数据类型中提取 出有效的特征来进行分类。尽管同构w e b 对象分类问题研究的数据类型不同， 但是它们使用的核心分类方法却大多一致，只是具体算法模型提取的特征不同， 因此具体的算法细节会有所不同。 本小节针对于不同类型的w e b 对象数据探讨其相关的研究，分为文本分类、 图片分类、音频分类和视频分类等四种类型的数据来介绍同构w e b 对象分类问 题。 2 1 1 文本分类方法 文本分类作为近年来研究的热点，综合了信息检索、自然语言处理、数据 挖掘、机器学习、概率统计等多个研究领域的方法。许多关于文本分类的分类 模型都是基于词袋( b a go fw o r d s ) 模型，即空间向量模型( v e c t o rs p a c em o d e l ) 。 这种模型使用t f i d f 来将文本数据转化成向量数据，然后再使用分类算法来 进行对文本进行分类。文献 2 1 介绍了基于空间向量模型的文本分类方法，包括 s v m 分类方法、基于概率模型的文本分类方法、决策树等。近年来基于n - g r a m 的分类方法的研究越来越多，在算法效果上也优于基于词袋模型的分类方法。 中山大学硕士学位论文基于社区标签图与维基百科的w e b 对象分类方法 n g r a m 模型是词袋模型的扩展，它能够捕获更多的文本语义，文献3 1 提出了一 个快速逻辑规约的方法，可以快速有效地利用n - g r a m 来分类。随着互联网的 发展，出现越来越多的网页信息，这些网页信息除了包含有文本数据之外，还 有超链接信息、h t m l 页面元素等。网页信息的分类算法将超链接、h t m l 的 元数据以及用户查询日志等作为特征来对文本进行分类【4 】【5 1 6 j 7 1 。 2 1 2 图片分类方法 图片分类问题也是近来研究的热点，其中一个主要的研究方向是如何利用 更多更有效的特征来对图片进行分类。传统的分类算法直接用于图片分类的效 果并不好，因为算法没有挖掘到图片所包含的图像信息和上下文信息等。除了 利用图像信息，如颜色直方图等基于图像内容的特征外8 l 【9 】【1 0 】【l l 】，也有将图像 内容和元数据结合的图像分类方法【1 2 】【1 3 】。 2 1 3 音频分类方法 音频分类问题的研究综合了语音识别、信息检索、数字信号处理、统计学 习等多个研究领域的方法。近年关于音频分类问题的研究主要有基于内容的音 频分类问题，以及基于信息处理技术来提取音频特征的问题，比如音调、频带 宽度、频谱流量等【1 4 】【1 5 】【1 6 】【1 7 】。 2 1 4 视频分类方法 视频分类也是近年来研究的热点，一方面由于互联网的发展，视频数据呈 爆炸式增长，如何更有效地组织视频数据成为研究的热点，另一方面，视频分 类也是同构w e b 对象分类问题中的难点。视频数据不仅包含音频数据，也包含 了相关描述文本和大量连续的视觉信息，比如颜色、纹理、形状等。按照特征 来划分可以分为基于描述文本的视频分类方法、基于音频信息的视频分类方法 和基于视觉信息的视频分类方法【1 8 】【1 9 1 1 2 0 1 。 6 中山大学硕士学位论文 第2 章相关研究工作 2 2 社区数据的相关研究 随着互联网社区化的发展，社区化应用开始越来越多，也产生了许多具有 研究价值的社区数据，基于社区数据的w e b 挖掘已经成为w e b 挖掘领域的个 热点，本小节介绍基于社区标签和维基百科等社区数据的相关研究。 2 2 1 基于社区标签的相关研究 随着w e b 2 0 的发展，网络社区成为人们生活不可或缺的一个组成部分。同 时，网络社区的发展带来了许多新的应用，这些新的应用产生了一些新的社区 数据，比如社区标签就是其中一个非常重要的社区数据。关于社区标签的研究 近年来也是w e b 挖掘的一个研究热点，社区标签已经应用到网页聚类2 、信 息检索【2 2 】【2 3 】【2 4 】【2 5 1 、用户信息挖掘等领域【2 6 1 。 2 2 2 基于维基百科的分类方法 维基百科是全球互联网用户共同协作编辑的百科全书系统【2 7 1 ，支持多种语 言，包括英语、法语、西班牙语、中文、日文等。对文本分类问题来说，维基 百科知识库包含了丰富的语义信息【2 8 l ，如何利用维基百科的语义信息来进行分 类成为研究的重点。文献【2 9 】【3 0 】利用维基百科来提取额外的特征向量，以此来提 高样本数据的特征。文献【3 1 】【3 2 】从维基百科中提取语义联系，包括同义联系、多 义联系、上下位关系等，然后利用这些语义联系来构建分类器。 2 3 缺乏类标记数据环境下的分类方法 对于分类问题而言，由于w e b 对象的类标记数据不易获取，因此如何在缺 乏类标记数据的环境下进行分类是w e b 对象分类中个关键问题。本小节介绍 了半监督学习和迁移学习两种在缺乏类标记数据的环境下的分类方法，半监督 分类算法利用大量的未标记数据来进行分类，而迁移学习则利用相似领域的标 记数据来指导目标领域数据的分类。 7 中山大学硕：i = 学位论文基于社区标签图与维基百科的w e b 对象分类方法 2 3 1 半监督分类方法 半监督分类算法用于解决缺少类标记样本的问题，现实情形中有类标记的 数据比较难获得，需要耗费大量的入力，半监督分类算法不需要大量有类标记 的数据，而利用大量未标记的数据来进行分类。文献f 3 3 】将半监督问题转化为基 于加权图的高斯随机域( g a u s s i a nr a n d o mf i e l d ) f 司题，文献【3 4 1 提出了一种可以实 现全局和局部一致性的半监督算法，这两种算法都基于图模型。另外，通过先 验知识，可以用其它算法对未标记数据进行估计也是其中一种半监督分类方法 f 。 2 3 1 迁移学习分类方法 迁移学习是近年来的研究热点，迁移学习研究如何利用两个或多个相似的 数据集来解决缺少标签数据的问题。迁移学习在解决少标记样本问题上有比较 明显的效果，利用多个相似领域的数据来指导少标记数据的分类。文献【3 5 】【3 6 】 基于线性文本分类器提出了迁移学习的方法，文献【3 7 1 总结出了归纳式迁移学习、 转换式迁移学习、半监督式迁移学习。 2 4 本章小结 本章介绍了相关研究工作，包括同构w e b 对象分类方法、基于社区标签的 相关研究、基于维基百科的分类方法、半监督分类方法以及迁移学习分类方法 等。本章首先介绍了同构w e b 对象分类方法，包括文本分类方法、图片分类方 法、音频分类方法和视频分类方法等。接着，本章介绍了基于社区标签的相关 研究，而基于社区标签的相关研究主要集中于信息检索、网页聚类等领域。接 着，本章介绍了基于维基百科的分类方法，近年来的许多研究都关注于如何利 用维基百科来指导文本分类，以及如何从维基百科中提取语义联系等。最后， 本章还介绍了在缺少类标记样本环境下的两种分类算法：半监督分类方法和迁 移学习分类方法。半监督分类方法利用少量标记样本和大量未标记样本来进行 分类，研究的重点是如何利用大量未标记样本来指导分类。迁移学习分类方法 将多个相似领域的数据迁移到目标领域中，用来指导目标领域数据的分类。 r 中山入学硕：仁学位论文第3 章问题描述 第3 章问题描述 本章介绍w e b 对象分类问题，首先介绍w e b 对象分类问题的研究现状，然 后阐述了当前w e b 对象分类研究中所遇到的问题。接着，本章后半部分基于社 区标签图和维基百科对w e b 对象分类问题进行抽象，定义了w e b 对象分类问题。 3 1 研究现状 基于社区标签图的w e b 对象分类方法由文献i l l 提出，通过社区标签图利用源 领域的数据来指导目标领域数据的分类。但是，文献【l 】没有解决源领域数据和目 标领域数据的差异性问题。本文利用维基百科来填补源领域数据和目标数据的差 异，并提出基于维基百科概念图的w r e b 对象方法。 维基百科知识库包含了丰富的语义信息【2 引，如何利用维基百科的语义信息来 进行分类成为研究的重点。文献【3 l 】【3 2 】从维基百科中提取语义联系，包括同义联 系、多义联系、上下位关系等，然后利用这些语义联系来构建分类器。 3 2 提出问题 本文研究基于社区标签图的w e b 对象分类，w e b 对象包括各种异构的w e b 数据，包括网页、图片、视频等。社区标签是随着w e b 社区的发展而产生的数 据，是社区用户用来描述网页、图片、视频等w e b 对象的简短描述。w e b 对象 包含多种类型的数据，这些数据缺乏有效的特征表示，因此很难准确表征数据。 文献【1 】总结了w e b 对象分类中的三个难点问题，包括： 一、对象缺乏有效的特征表示。许多w e b 对象分类相关的研究都基于w e b 对象的内容为特征的分类研究，但是诸如网页、图片、视频等数据，很难快速、 高效地从中提取出有效的特征来表征数据，而通过社区标签可以有效地表征w e b 对象的信息。如图3 - 1 ，通过社区用户挑选的标签可以有效表征w e b 对象的信 息。 二、对象之间缺乏关联。传统w e b 对象分类方法都是使用向量模型来表示 数据，缺乏对w e b 对象之间联系的挖掘。如图3 - 1 ，通过对象间的社区标签可 9 中m 大学i ，学位论z幕十札匡标整脚与堆基百科的w e b 对象分类方法 以有效地建立对象问的关系，包含相同社区标签的对象通过社区标签连接在一 起。 三、缺乏足够有类标记的样本数据。具有类标记的训练样本量往往对分类 效果有很大的影响，但是对样本进行标记需要耗费大量的人力，因此解决在缺 乏类标记样本的环境下的分类问题是一个重点。如图3 - 1 所示，图中包括图片、 网页、图书信息的多种异构数据，通过社区标签图，我们可以有效地利用不同 领域的数据，一个领域的类标记信息可以帮助另一个领域数据的分类。 图3 - 1w e b 对象关系图 文献【。1 提出通过利用社区标签作为w e b 对象的特 j i ：表示方式，可以有效地解 决以上三个难点问题。文献的实验表明社区标签可以很好地表征w e b 对象， 通过社区标签图可以挖掘不同对象问的关联，而且可以利用其它领域的数据来 解决缺乏类标记样本的问题。 文献的方法通过共享不同领域的社区标签信息可以有效地利用社区标签 信息，在一定程度上解决了以上的三个难点问题，但是文献构建对象联系的 方法只是基于字符串匹配，对象问只有包含相同标签才构成联系。实际e ，对 1 0 中山大学硕士学位论文第3 章问题描述 于不同领域间的数据，它们的社区标签数据的分布也会有比较大的差异，不同 领域的对象间可能并不包含相同的标签数据，因此如何利用领域差异较大的数 据进行w e b 对象分类同样是一个难点问题。 3 3 问题抽象 本文研究两种不同领域w e b 对象的分类问题，假设具有两种不同领域的数据 s 、t ( 比如，s 可以是文本数据，t 可以是图片数据) ， s ；g l t 两种数据都通过社区 标签来表征，我们任务是对数据t 进行分类。而s 是另外一个领域的数据，获取s 的类标记信息比较容易，s 的所有数据都是带有类标签的，而t 只有少量数据带 有类标签。 因此，对于t 而言，t 的数据分为有类标记和无类标记两种数据，而s 的数据 全部是带有类标签的。t 和s 都带有社区标签，每个社区标签都带有一定权值， 表示该对象被社区标签标记的次数，所有的社区标签构成集合t a g 。我们的任务 就是要如何利用社区标签t a g 和另外一个领域的数据s 来对t 中的无类标记的数 据进行标记。 3 4 问题定义 w e b 对象：包含多种类型的w e b 数据，比如w e b 数据可以来自网页、图 片、视频等不同领域，本文研究的是只包含两种类型w e b 对象的分类问题，因 此后面提到的w e b 对象都只包含两种领域的数据。 w e b 对象类标记：假设每个w e b 对象都只属于其中一个类，类标记的集合 为c ： c 1 ，c 2 ，c k ) ，其中k 为类别的数量。 社区标签：社区标签是随着w e b 2 0 技术的发展和应用而产生的数据，它是 社区用户根据自己对w e b 对象的观察和理解对其进行描述的词汇或短语。在 w e b 社区中每一个对象都包含了一个社区标签集合，这个集合是社区用户对其 进行标记的信息，从不同方面反应了w e b 对象的信息。另外，每个w e b 对象的 社区标签都包含一个权值，这个权值代表该w e b 对象被标记的次数。 社区标签图：假设只有两类不同领域的w e b 对象s 和t ，姊s 是源领域， t 是目标领域。s 中的对象都具有类标记，而t 中只有少量数据带有类标记。 中山大学硕士学位论文基于社区标签图与维基百科的w e b 对象分类方法 每个w e b 对象对应一个社区标签集合，用来表征w e b 对象的信息，所有的社区 标签构成标签集合t a g 。如图3 2 所示，每个w r e b 对象和社区标签都对应于社 区标签图中的一个点，黑色的点是带有类标记的w e b 对象，w e b 对象和社区标 签之间通过边来连接，边的权值表示w e b 对象被该社区标签标记的次数。 s l s 2s 3s 4s 5s 6 t lt 2t 3t 4t 5t 6t 7 图3 2 社区标签图 社区标签图g = “e ，每一个w e b 对象和社区标签对应图中的一个点， 如果一个w e b 对象a 与一个社区标签v 有联系，其中uv e v ，这u 和v 之间通 过边( u ，v ) e 连接，边的权值为w r u v 。节点集合v 包含四类节点，包括： v s ：源领域s 的w e b 对象集合。 v ：目标领域t 的带类标记的对象集合。 皑：目标领域t 的不带类标记的对象集合。 v 协g ：社区标签的集合。 w e b 对象分类任务： 假设有k 个类 c l ，c 2 ，c k ) ，社区标签图中每个节点都有一个类分布向 量f u ，表示该节点属于c 1 ，c z ，c k 的概率分布，其pe u 1 】+ f u 2 】+ + f u 【k 】 = l 。明显，在初始状态下，对于v s 和v 集合中的节点s ，如果s 节点属于c 类， 则：对于i 不等于c ，则f u i 】2 0 ，对于i 等于c ，贝j j f u i = l ；而对于w 和v 趣集合 中的节点而言，r e 1 】= f u 2 】= = f un = 1 k 。 1 2 中山大学硕士学位论文 第3 章阎题描述 w e b 对象分类任务就是利用有类标记的节点k 和v ，通过社区标签图来对 没有类标记的畔节点进行标记。 3 5 本章小结 本章对本文研究的问题进行了详细的阐述和定义，首先介绍了w e b 对象分 类问题的研究现状，然后提出基于社区标签的异构w e b 对象分类问题，之后描 述了w e b 对象分类问题，给出了对w e b 对象、社区标签图、w e b 对象分类任 务的定义。 中山大学硕士学位论文基于社区标签图与维基百科的w e b 对象分类方法 第4 章基于社区标签图的f f e b 对象分类方法 本章介绍文献【1 1 提出的基于社区标签图的w e b 对象分类方法，将分类问题 转化成了优化问题，并基于社区标签图提出了四点直观的假设，并根据这四点 直观假设提出一个目标函数，再通过迭代的方式来求解最优解从而实现对未标 记数据进行分类。 4 1 核心思想 文献【1 】首先基于四点直观假设提出一个目标函数，然后对该目标函数进行迭 代求解。文献【l 】是第一篇提出使用社区标签进行w e b 对象分类的文献，它的核 心思想是基于四点直观假设提出分类模型的目标函数。 社区标签是有类标签数据与无类标签数据间的纽带，而不管数据属于哪个 领域，社区标签都可以将不同领域的数据联系起来。文献提出了一个直观假 设： w e b 社区用户倾向于对同一类的w e b 对象使用相似的标签进行标记，而不 管w e b 对象属于哪个领域。 因此，具有相同社区标签的两个w e b 对象可能具有相同的类标签，两者与 社区标签的类分布接近。为了找到优化算法的目标函数，文献进步详细指出 在社区标签图上分类算法应该与以上假设一致，提出了四点直观假设。 1 在迭代过程中，k 中节点的类标记应该与其初始类标记保持一致。 2 在迭代过程中，v 中节点的类标记应该与其初始类标记保持一致。 3 如果w 中节点的类标签有先验估计，那么在迭代过程中应该与其初始类 标签保持一定程度上的一致。 4 社区标签图g 中的所有节点应该与其相邻节点的类标签保持一致。 以上四点是文献【l 】提出的w e b 对象分类方法遵循的直观假设，根据这四点 直观假设提出了优化算法的目标函数，并对其进行迭代求解。 1 4 中山大学硕士学位论文 第4 章基于社区标签图的w e b 对象分类方法 4 2 算法理论框架 文献【1 1 提出了一种基于社区标签图的w e b 对象分类的通用优化框架，其目 标函数如下： o f f ) = 仅o f u 一 u i l 2 + p o f u 一 u 1 1 2 u e v s u e v + y o f u 一气0 2 + w u v f u f v 2 ( 4 - 1 ) u v 芊 婶，v ) e 其中，w u v 边( u ，v ) 的权值，代表v 被标签u 标记的次数。 f u ：k 维的类分布向量，f u i 】表示节点u 属于类i 的概率，坠1f u i = 1 u ：对于节点u v suv uw ， u 表示对节点u 的类分布估计向量。 该目标函数实际上是对以上四点直观假设的量化表示，其中 1 e u v s i l f u 一 u 0 2 表示v s 中节点的类标记应该与其初始类标记保持一致。 2 u v 州f u 一旷表示v 中节点的类标记应该与其初始类标记保持一致。 3 u v 川f u 一 u 旷表示如果畔中节点的类标签有先验估计，那么在迭代过 程中应该与其初始类标签保持一定程度上的一致。 4 ( u ，v ) ew u vl i f u f v 2 表示社区标签图g 中的所有节点应该与其相邻节 点的类标签保持一致。 仅，p ，y 表示分别表示前三点直观假设的权重，不同的取值代表w e b 对象 分类模型的不同设置。 目标函数o ( f ) 对于s v s ，1 v ，u w 和v g 求偏导得： 3 0 a 。= 2 c 【( f s 一 s ) + 2e v v 臼。、 b ( f s - f o = 0 f s = 赤 s + 嚣 ( 4 2 ) 3 0 a l = 2 b ( 6 一 1 ) + 2e v v 啦w i v ( f j - f o = 0 6 = 赤n 器 ( 4 3 ) 3 0 a u = 2 y ( f u 一气) + 2e v v 臼。w r u v ( f u f v ) = 0 f u = i 赤+ 器 ( 4 4 ) 1 5 中山大学硕士学位论文基于社区标签图与维基百科的w e b 对象分类方法 筹= 一2 。e v 。w 如( f s f v ) 一2 i v rw l v ( f , - f , , ) - 2e u v w u v ( f u f v ) = o ，s v s w s v f s + l v ! r w l v f i + e u v 】j w u v f u k = 1 i 磊鬲瓦# ( 4 5 ) 分类的目标是找到最优解f + = a r g m i n0 ( 0 基于类分布，一个w ，e b 对象。的类标记c = a r gm a ) 【警等= a r g m a x 百v c c 万l o ) 因此，对于u w ，c = a r g m a x 南 4 3 算法过程 ( 4 6 ) 首先给社区标签图中没有类标记的节点初始化，初始化的值为l l 【，其中k 为类的种类大小。其次按照公式( 4 2 ) 、公式( 4 3 ) 、公式( 4 - 4 ) 、公式( 4 5 ) 依次迭代更新各个节点的类分布向量直到收敛为止。最后，依照公式( 4 6 ) 求 出每个u w 的类标记。 算法过程( 1 卜( 4 ) 步是初始化，其时间复杂度为o ( k l v l ) ，其中i v i 是社区标签 图节点个数。在迭代过程( 5 h 1 4 ) d 尸，时间复杂度为o ( 2 k ( i e i ) ) ，其中| e l 为社区 标签图边的个数，u v u ，l 。因此算法的时间复杂度为o ( k i v | + i t e r 堍( | e | ) ) ， 其中i t e r 为算法的迭代次数。算法过程如图4 1 所示： 1 6 中山大学硕上学位论文第4 章基于社区标签图的w e b 对象分类方法 输入：数据分类个数k ，对于x v su u v ，类标记映射函数c ( x ) 。 输出：对于所有x v 竿，求出所有x 的类标记c ( x ) 初始化 lf o r e a c hx v su 坼uv ud o 2 f x c ( x ) 】1 3f o r e a c hx vd o 4f o r e a c h i - 1t o k d of x i 】卜1 k 迭代过程 5r e p e a t 6f o r e a c hx v sd o 7 f ，x = 衰 x + 恚蠹 8 9 f o r e a c hx 蚺d o f ，x = 意暑 x + 垛 f o r e a c hx v ； d o - t f ，x = 意丢 x + 恚意 1 2f o r e a c hx v 岛d o f x s e v sw “+ l 讳w i x + y u e 蚌w 弧 1 4u t i lc o n v e r g e d ； 求出最终的类标记 1 5f o r e a c hx ud o 1 6 e ( x ) = a r g m a x l 亟看知 4 4 算法分析 图4 1 算法过程 文献指出通过配置不同的参数0 t ，b ，y ，可以实现不同的分类模型： 1 仅= 0 ，p 0 ，y = 0 。在这种参数配置下，只有目标领域的数据具有类 标记，而没有源领域的数据s 和先验知识，这种情形相当于单领域少量类标记 样本的分类。 1 7 中山大学硕士学位论文基于社区标签图与维基百科的w e b 对象分类方法 2 仅0 ，p = 0 ，y = 0 。在这种参数配置下，目标领域的数据没有类标记， 但是源领域的数据有类标记，仅的值越大说明源领域的数据越可信。 3 y 0 。在这种参数配置下，目标领域中没有类标记的数据在初始时被赋 予先验估计，先验估计可以来自其它分类算法，可以跟其它分类算法无缝集成。 4 仅0 ，b 0 ，y 0 。在这种参数配置下，既包含有先验知识，也包含 源领域的具有类标记的数据，这种情形可以看作是迁移学习、半监督学习与先 验知识的集成方法。 文献【1 】提出了基于社区标签图的分类框架，可以有效利用源领域的数据来辅 助目标领域的分类，但是文献【1 】的实验表明，当目标领域中具有类标记的数据 足够多时，加入源领域的数据反而会降低分类的效果，而且文酬l 】并没有考虑 源领域与目标领域的数据差异性问题。另外，文献【l 】中w 曲对象的相似性依靠 于两者是否包含相同的词汇或短语，这种方法明显不能挖掘w e b 对象间的潜在 语义联系。 因此，针对以上问题本文提出一种基于维基百科的更加有效的w e b 分类方 法，可以解决源领域和目标领域的数据差异性问题，而且可以更有效地挖掘w e b 对象间的潜在语义联系。 4 5 本章小结 在本章中，简单介绍了文献【1 1 提出的基于社区标签图的w e b 对象分类方法。 首先介绍了文献1 】的核心思想，阐述