第33卷 第8期2010年8月

计 算 机 学 报

Vol.33No.8

Aug.2010

一种基于随机游走模型的多标签分类算法

郑 伟 王朝坤 刘 璋 王建民

(清华大学软件学院 北京 100084)

(清华信息科学与技术国家实验室 北京 100084)(信息系统安全教育部重点实验室 北京 100084)

摘 要 在数据挖掘领域,传统的单分类和多分类问题已经得到了广泛的研究.但是多标签数据的普遍存在性和重要性直到近些年来才逐渐得到人们的关注.在多标签分类问题中,由于标签相关性的存在,传统的单分类和多分类问题的解决方法,无法简单地应用于多标签分类问题.文中提出了一种基于随机游走模型的多标签分类算法,称为多标签随机游走算法.首先,将多标签数据映射成为多标签随机游走图.当输入一个未分类数据时,建立一个多标签随机游走图系列.而后,对图系列中的每个图应用随机游走模型,得到遍历每个顶点的概率分布,并将这个点概率分布转化成每个标签的概率分布.最后,基于多标签随机游走算法,文中给出了一种新的阈值学习算法.真实数据集上的实验表明,多标签随机游走算法可以有效地解决多标签分类问题.关键词 多标签;分类算法;随机游走;阈值学习

中图法分类号TP181 DOI号:10.3724/SP.J.1016.2010.01418

AMult-iLabelClassificationAlgorithmBasedonRandomWalkModel

ZHENGWei WANGChao-Kun LIUZhang WANGJian-Min

(SchoolofSoftware,TsinghuaUniversity,Beijing 100084)

(TsinghuaNationalLaboratoryforInformationScienceandTechnology,Beijing 100084)(KeyLaboratoryforInformationSystemSecurity,MinistryofEducation,Beijing 100084)

Abstract Thereareextensiveliteraturesrelatedtotraditionalsingle-classandmult-iclassclass-i

ficationproblems,inwhicheachdatapointisassignedtoonecategory.Butinmanyapplications,adatapointmaybelongtomorethanonecategory.ThiskindofproblemiscalledtheMult-iLabel

Classification(MLC)problem.Duetotheexistingoflabelrelevance,thetraditionaldata-miningmethodscannotbedirectlyappliedtotheMLCproblems.ThispaperproposesanovelMLCalgo-rithmbasedontherandomwalkmodel,calledMult-iLabelRandomWalk(MLRW)algorithm.Firstly,amult-ilabelrandomwalkgraphisbuiltonthetrainingset.Asanunlabeleddataar-rives,amult-ilabelrandomwalkgraphsystemwillbebuilt,onwhichtherandomwalkprocess-ingiscarriedout.Afterthat,aprobabilitydistributionamongalllabelsisobtained.Atlast,a

thresholdlearningalgorithmisproposedbasedontheMLRWalgorithmsothatthefinalpredic-tiononeachlabelispresented.ExperimentalresultsonactualdatasetshowthattheMLRWa-lgorithmprovidesaneffectivesolutiontotheMLCproblems.

Keywords mult-ilabel;classification;randomwalk;thresholdlearning

收稿日期:2010-06-11.本课题得到国家自然科学基金(60803016)、国家 九七三 重点基础研究发展规划项目基金(2007CB310802,2009CB320706)和国家 八六三 高技术研究发展计划项目基金(2008AA042301,2007AA040602)资助.郑 伟,男,1986年生,硕士研究生,主要研究方向为多标签数据的分类和聚类、数字音乐信息检索.E-mail:zhengw04@http://www.wendangwang.com.王朝坤,男,1976年生,博士,讲师,主要研究方向为音乐数据管理与云计算.刘 璋,男,1985年生,博士研究生,主要研究方向为非结构化数据管理和音乐数据管理.王建民,男,1968年生,博士,教授,博士生导师,主要研究领域包括数据管理与信息系统、云环境下非结构化数据管理技术、业务过.