用于聊天词汇的权重计算方法CDTF＊IDF

用于聊天词汇的权重计算方法CDTF＊IDF 用于聊天词汇的权重计算方法CDTF,IDF 第24卷第12期计算机仿真2007年12月 文章编号:1006—9348(2007)12—0332一o4 用于聊天词汇的权重计算方法CDTF术IDF 高鹏r,曹先彬 (1.中国科学技术大学计算机科学技术系,安徽合肥230027 2.安徽省计算机通讯软件重点实验室,安徽合肥230027) 摘要:随着聊天室的广泛使用,对聊天内容监控也变成亟待解决的问题.在聊天室 监控中,为衡量聊天数据中词汇对聊天内 容的描述能力,现在一般直接采用文本词汇的权重计算方法;然而,这种方法忽视 了聊天数据与静态文本结构上的差异,导 致计算出的权重并不能准确反应词汇描述聊天内容的能力.针对聊天数据的固有 特点,提出了一种专门针对聊天数据的词 汇权重计算方法CDTFIDF.该方法通过分别计算词汇在不同数据源中的权值并汇 总,并对重点词汇提高权重等方式来计 算聊天数据的词汇权重.基于IRC聊天室内容监控的实验表明:该方法能较好地衡 量聊天词汇的权重,同时基于该方法的监 控系统能够准确地识别出聊天数据中的话题. 关键词:聊天室监控;词汇权重;话题识别 中图分类号:TP3o1.6文献标识码:A' ACDTF:l:IDFAlgorithmforCalculatingTermWeightofChatData GAOPeng.CAOXian—bin' (1.DepartmentofComputerScienceandTechnology, UniversityofScienceandTechnologyofChina,HefeiAnhui230037,China; 2.AnhuiKeyLabofSoftwareinComputingandCommunication,HefeiAnhui230037.Chin a) ABSTRACT:Chatroommonitoringbecomesanurgenttaskwithitswideuse.Intheprocesso fchatroom monitoring,inordertoscaletheabilityoftermsdescribingthecontentsofchatdata,chatroommonitoring systemsatpresentgenerallyusethetexttermsweightcalculatingmethod.However,thismethodneglectsthe differencebetweenchatdataandtextinstructureaspect;hencetheweightcalculatedcannotresponsethe featureofchatdataaccurately.Thepaperpresentsanewmethodtocalculatethetermweightforchatdatanamed CDTF}IDF.CDTF}IDFconsidersthespecialfeaturesofchatdata.Itcalculateseachtermweightindifferent resources,andthengetsthefinalweightbyincreasingtheweightofkeytermsandsomeothermeans. ExperimentsbasedonIRCshowthatthismethodcancalculatethetermsweightaccurately;atthesametime,the chatroommonitoringsystembasedontheproposedmethodhasagoodperformanceintopicdetection. KEYWORDS:Chatdatamonitoring;Termweight;Topicdetection 1引言 随着Internet的飞速发展,基于文本方式的网络聊天工 具由于操作简单,话题丰富,隐私性好等特点,为越来越多的 人所接受.聊天室丰富了人们的交流方式,使世界各地的网 络用户可以直接交换信息而无需身份验证.用户可以根据兴 基金项目:国家自然科学基金(60204009),973课题(2004CB318109) 和中科院复杂系统与智能科学重点实验室开放基~(20040104) 收稿日期:2006一ll—l5修回日期:2006一ll一25 .—-—— 332...—— 趣加入几乎任何已有的话题进行讨论,也可以按自己的需要 建立新的话题.这种开放性在极大地方便信息交流的同时, 也带来了安全上的隐患.由于缺少对聊天内容的管理,它常 会被滥用作为非法活动的平台,如通过聊天进行儿童诱拐, 诈骗,传递有害信息等….因此,对聊天内容进行监控已成为 亟待解决的问题. 日前,专门针对聊天室内容监控的研究工作还比较少 见,采用的方法一般是首先建立聊天数据的向量空间模型 (VectorSpaceMode1),然后在此模型的基础上计算聊天数 据中词汇的权重,再采用文本分类的方式来识别用户正在讨 论的内容(主要是话题).由此可见,词汇权重的计算是整个 方法中的基础,其效果的优劣直接影响到监控的性能.例如, JasonBengel等人设计了一个相对比较完整的聊天室监控系 统ChatTrack,它实现了聊天数据的自动收集,检索和分 类;NeilW.等人设计的Butterfly系统则根据用户提出的话题 描述,找出含有相关话题的聊天频道并推荐给用户].在这 两个系统中,词汇权重的计算都直接采用TFIDF(Term FrequencyInverseDocumentFrequency)方法. 但是,TFIDF实际上是用于文本词汇的权重计算的, 并不完全适合聊天数据中词汇的权重计算.聊天数据与文本 数据不同,其自身的特殊性(如多数据源,各数据源数据量不 均衡等)决定了直接套用TFIDF方法计算出的聊天数据中 词汇的权重,不可能真实反应出聊天数据中词汇对聊天内容 的描述能力. 本文提出了一种专门用于聊天数据词汇的权重计算方 法CDTFIDF(ChatDataDocumentTermFrequencYInverse DocumentFrequency).该方法根据聊天数据的特殊性,通过 分数据源计算词汇权重并汇总,降低分类特性对权重计算的 影响,对重点词汇增量加权等方式,可以准确反应出词汇描 述对话内容的能力. 2聊天数据的特点及TFIDF方法的不足 2.1聊天数据的特点 聊天数据与文本数据不同,其内容是由不同用户的对话 组合而成的;这些对话类似口头交流,有着很差的语法,拼 写,噪声非常大.除此以外,聊天数据的特殊性主要体现在以 下几个方面: 1)聊天数据是多源的.在对聊天室进行监控时,聊天数 据可能由来自不同服务器中多个聊天室的聊天内容组成. 2)各个数据源的数据量不同.数据量的多少与当时该数 据源的用户在线人数,用户对话题的兴趣程度等多方面因素 有关,因此各数据源的数据量差别可能会很大. 3)数据源的分类性很弱.每个数据源都有一个事先定义 好的聊天主题,聊天数据存在相对明显的类别特征(比如,主 题为philosophy的聊天室的聊天数据的内容可能主要关注的 是philosophy方面),但这种预先定义的主题约束性是很弱 的,数据源中的话题会随着用户的变化或兴趣的变化而不断 的改变,对话内容往往不会按照预先设定的主题进行. 4)话题与用户对话有密切的联系.聊天数据的内容是由 不同用户的对话组织在一起的,用户通过对话内容表示其意 图.通过观察我们发现,用户在聊天过程中发言次数不同,他 们对聊天话题影响程度也不同;用户发言越多,他所表达的 意思就越清楚,对话题的影响就越大,而发言较少的用户则 对话题起不到影响作用.因此,发言较多的用户在其对话中 多次提到的词汇更能反应出这段对话的话题,将这些词汇称 为重点词汇. 另外,监控系统在收集聊天数据的过程中,无论是以收 集的时间为单位还是以收集的量为单位,都要对数据源中的 数据分段收集.这种收集方法可能使同一话题被拆分成两个 或多个片段,从而割裂了聊天数据在语义上的连续性.因此, 在同一数据源中收集到的多个数据片段中,分布较广的词汇 其反应话题的能力会更高一些. 2.2TFIDF方法的不足 TFIDF方法是针对文本词汇权重计算设计的,直接用 来计算聊天数据词汇的权重时存在以下几方面不足之处: 1)由TFIDF方法的结构可知,它是针对单数据源而设 计的,在处理单数据源文本集的情况下更有优势.而聊天数 据是多数据源的,且各数据源之间的类别差异很弱,计算词 汇权重时需要综合考虑词汇在各个数据源中的情况,因此直 接使用TFIDF方法计算聊天数据词汇权重不合适. 2)TFIDF方法采用文档频数型公式即IDF函数来调 整词汇权重,所有词汇在计算权重时是以总的文档数为 基,这显然是不合理的.特别是当某类的文档数相对较少时, 分类结果便容易出错.例如,在一个数据量较少的数据源中, 某词汇出现的频率很高,是一个可以反应对话内容的词汇, 但通过TFIDF得出的权重并不能说明该词是一个能够表 达数据源内容的重点词汇. 3)TFIDF忽视了聊天数据重点词汇对权重的影响.根 据聊天数据的特点可知,发言较多的用户在其对话中多次提 到的词汇更能反应出对话中的话题.通过TFIDF方法并不 能使这些能够反应话题的重点词汇权重更加突出. 由聊天数据特殊性和TFIDF算法不足可知,该算法并 不适合于计算聊天数据中词汇的权重,因此在进行聊天数据 监控时,需要一种针对聊天数据特点的权重计算方法来进一 步提高监控的准确率. 3CDTF:I:IDF方法及应用环境 3.1CDTFIDF方法实现 基于上一节分析的聊天数据特点,我们提出了一种针对 聊天数据词汇权重计算的方法CDTFIDF,该方法根据聊天 数据的多源性和弱分类性等特点,通过综合计算各数据源中 词汇权重,提高重要词汇的权值来衡量词汇权重.具体实现 如式(1),(2),(3)所示. = ?II(/).(1) II_一(2) ? f?f1f?q = (3) 【?f1.5f>q 其中为词的权重,d为数据源的总数,为词力生数据源 c内的基本权重,影响因子为一个大于1的数.n为数据 源c内含有词的聊天数据片段的数量,为数据源c内聊天 —— 333—— 数据片段的总数量.为数据源c内词汇的数量.P为一个大 于1的数,大小具体由实验确定.m为数据源c内的用户数 量t为用户在对话中提到词的次数.当用户在一个聊天数 据片段中提到该特征词的次数小于q时,按1计算,当大于q 时,按1.5计算. 从CDTFIDF方法的结构可以看出,该方法在计算词 汇权重时分为三个主要步骤: 1)计算各数据源中词汇的权重,其中包括弱化各数据 源的分类特性;通过影响因子来增大在同一数据源不同数据 片段中出现的词汇的权重;扩大重点词汇的权值; 2)规格化(normalize)各数据源所计算出的词汇权重; 3)综合各数据源计算出的权重作为词汇在聊天数据中 的权重. 其计算流程如图1所示. 图1CDTF}IDF方法计算流程图 从(1)式可以看出,词j的权重W等于j在各数据源中计 算出的权重的总和.通过汇总各数据源计算出的权重,使得 含有该词汇的所有数据源对词汇权重的影响都有所体现,实 现了权值计算的多源性.在该式中,IDF函数(N/n)l/p以各 数据源中的数据片段数量为基调整词汇的权重,避免了 TFIDF以文档总数为基计算词汇权重的缺点.考虑到数据 源的弱分类性,式中将P设置为大于2的数,即体现了聊天数 据的分类性,又减少了分类特性对权重计算的影响. 在(2)式中对数据源C中的词汇j出现的频率进行规格 化,避免了由于各数据源数据量的差异对权重计算的影响. 由聊天数据的特点可以知道,各数据源的数据量差异可能很 大,但无论数据量的大小,在监控过程中各数据源应该是平 等的,因此在计算词汇权重时要避免由于数据源的数据量不 同而造成对权重计算的负面影响.通过(2)式规格化词汇的 权重较好地解决了这一问题. 在(3)式中,通过对同一用户i在同一个聊天数据片段 中多次提到的词汇j更高的权值来提高该词的权重,其目的 是使能够反映话题的重点词汇在权重计算时更加突出. 考虑到收集数据过程中分片可能造成对同一话题的分 割,设置影响因子inf的作用是使在同一数据源中出现的同 一 词汇比在不同数据源中出现的同一词汇的权重有所提高. 3.2应用环境 使用CDTFIDF算法的聊天室监控系统对从不同数据 源收集到的聊天数据片段建立空问向量模型,计算出词汇权 ...—— 334...—— 重进行特征提取,选择出n个权重最高的词.过滤掉不包含 这些特征词的聊天数据片段.使用聚类方法对剩余的聊天数 据片段进行聚类,聚类后聊天数据片段集包含的特征词组合 反映了聊天数据片段集的话题.监控系统的工作流程如图2 所示. 收集聊天数据片段 J 算聊天数据词汇权重 申通过聚类识别聊 天数据片段话题 图2聊天室监控系统工作流程图 4实验及结果分析 IRC(InternetRelayChat)聊天系统是目前最具代表性 的网络聊天工具.为了验证CDTFIDF的效果,收集了IRC 聊天室的聊天对话作为实验数据,分别使用CDTF-kIDF和 TF-7~IDF计算词汇权重,察看其特征词及权重变化,并根据 3.2节介绍建立了一个原型系统,通过识别聊天话题来验证 CDTFIDF方法的优越性. 4.1试验数据准备 实验所用的数据取自IRC聊天室,随机选择2个服务器 的4个聊天室下载聊天数据.收集聊天数据时,以十分钟为 一 个片段保存聊天数据,共下载了500个片段.分为5组进行 实验,每组100个片段.对收集到的聊天数据片段进行预处 理,包括:用停用词表(stop—list)过滤,多昵称合并,对特定 词的处理,同根词合并等.在实验中,设置P=3,q=5,inf= 1.2. 4.2试验1:词汇权重计算结果比较 用TFIDF和CDTFIDF分别计算词汇权重,以第一组 实验为例,选取权重最高的前6项进行对比,察看其特征词 及权重变化,结合人工分析实验数据的结果,判断特征词反 应话题的能力. 在采用TFIDF算法计算词汇权重的这组实验中选择6 个权重最高的词汇如表1. 表1基于TFIDF算法的实验结果 在采用CDTFIDF算法计算词汇权重的这组实验中选 择6个权值最高的词汇如表2,为方便两组数据的对比,对权 值进行等比例放大.见表2. 表2基于CDTF$IDF算法的实验结栗 对比两组实验结果,发现由CDTFIDF算法计算出的 词汇权重略高于TFIDF;这是因为在CDTF-kIDF算法中, 在对同一对话片段中由同一用户多次提到的词汇进行增量 计算,扩大词汇间权重的差距,使权重能真实反应出词汇描 述话题时所起的重要程度.在CDTF-kIDF算法得到的6个词 中,有一个词在TFIDF算法选择的6个词中没有出现.通过 人工阅读聊天数据发现Hegelianism这个词在主题为 philosophy的聊天室多次出现,是一个能起到区分话题作用 的词.造成这种情况是由于聊天室philosophy数据量相较由 其它数据源小,通过TFIDF不能正确反映出表示该话题词 汇,而通过CDTFIDF算法达到了我们设计的初衷. 4.3试验2:话题发现结果比较 根据3.2节中描述的应用环境,建立起了聊天室监控原 型系统.在系统中分别使用两种TFIDF和CDTFIDF算法 . 计算词汇权重对实验数据进行话题识别.结果如表3所示表3用两种算法进行话题识别的结栗 通过表3可以看出,使用CDTFIDF算法的结果要优于 使用TFIDF算法,特别是在第2组和第4组实验中 CDTFIDF的优势要更为明显.这主要是由于第1,3,5组实 验中,各数据源的数据量都比较小,差距也不大,两种算法的 差别不是很明显.在第2,4组实验中各数据源的数据量差距 较大,CDTFIDF算法可以通过规格化来减少这种差距对权 重计算的影响,因此准确率高于TFIDF算法. 5结论 本文通过分析聊天数据的特点,提出了一种针对聊天数 据特点设计的词汇权重计算方法CDTFIDF通过实验证明 该方法性能优于目前聊天室监控系统中常用的TF-kIDF算 法.当然,目前的聊天室监控方法都是通过建立聊天数据的 VSM模型,利用词汇的统计特性来进行话题识别的,忽视了 用户与对话间的关系和对话间的时间线索.下一步将通过分 析对话间的时序关系,并结合用户的语义相似性,进一步加 强对聊天数据的监控能力. 参考文献: [1]MichealMedaris,CathyGirouald[R]Protectingchildrenin cyberspace:the1CACtaskforceprogramUS.OfficeofJustice andDelinquencyPrevention,2002. [2]GSahon.DevelopmentsinAutomaticTextRetrieval[C]. Science,1999,253.974—979. [3]GSahon,CBuckley.TermWeightingApproachesinAutomatic TextRetrieval[C].InformationProcessingandManagement, 1998,24:513—523 [4]JasonBengel,SusanGauch,EeraMittur,Rajan Vijayaraghavan.ChatTrack:ChatRoomTopicDetectionUsing Classification[C].Proceedingsof2ndSymposiumon IntelligenceandSecurityInformatics(ISI一2004).266—277. [5]WNeil,VanDyke,HLieberman,PMaes.Butterfly.A Conversation—FindingAgentforInternetRelayChat[C]. Proceedingsofthe1999InternationalConferenceonIntelligent UserInterfaces.1999.39—41. [6]TJoachims.AProbabilisticAnalysisoftheRocchioAlgorithm withTF—IDFforFextCategorization[C].Proceedingofthe 14thInternationalConferenceonMachineLearningICM~7, 1997.143—151. [作者简介】 高鹏(1978一),男(汉族),陕西西安人,硕士研 究生..研究方向:信息安全. 曹先彬(1969一),男(汉族),安徽省巢湖人,博士, 教授,博士生导师.研究方向:计算智能,网络与信 息安全. ...—— 335---——