基于用户身份特征的多标签分类算法

郑晓雪，张大方，刁祖龙

(1.湖南大学 信息科学与工程学院，长沙410082； 2.湖南大学 可信系统与网络实验室，长沙410082)

基于用户身份特征的多标签分类算法

郑晓雪1,2*，张大方1,2，刁祖龙1,2

(1.湖南大学 信息科学与工程学院，长沙410082； 2.湖南大学 可信系统与网络实验室，长沙410082)

(*通信作者电子邮箱zhengxiaoxue@hnu.edu.cn)

目前对于智慧校园中的家校沟通，缺乏一种衡量和参考的方法。针对智慧校园中特有的聊天特点即存在明显的身份特征，提出了一种基于用户身份特征的多标签分类算法——Adaboost.ML。首先,新增加了启发式规则;然后,引入Adaboost.MH算法，同时摒弃了把数据集进行分片的概念;最后,直接利用单条数据作为分析的焦点，减少了由于时间片边缘带来的误差和推断时间，综合决策出聊天用户之间的关联关系。实验结果表明，与基于规则的启发式方法相比，所提算法在智慧校园数据集上的误报率、漏报率分别降低了53%、66%，同时在微信数据集上也具有良好的分类效果。该算法已应用到智慧校园项目中，能够迅速并准确地了解到家校沟通的情况。

社会网络；智慧校园；启发式规则；多标签判断；集成学习

0 引言

在社会信息化的大背景下，构建“智慧型”校园，利用学校为主体的教育信息化推进过程，成为教育信息化的重要组成部分[1]。智慧校园中家校沟通模块充分体现了学校与家长之间的互动和联系，通过对沟通情况的分析能够有效地反映用户之间存在的本质关联。

本文研究把聊天用户之间的沟通判断抽象为分类中的多标签分类判断，同时避免了由于时间片带来的边缘误差问题。分类是数据挖掘领域应用的一个分支，分类是根据数据集的特征构造一个对应的分类器，利用该分类器对未知类别的对象赋予类别的一种技术，其中包括单标签分类和多标签分类问题。针对单标签分类问题的分类算法有很多，例如朴素贝叶斯(Naive Bayes, NB)分类算法、K最近邻(K-Nearest Neighbour, KNN)分类算法、支持向量机(Support Vector Machine, SVM)分类算法等[2]。对于多标签分类问题大致分为两种：算法适应和问题转换[3]。算法适应意味着把处理单标签分类问题的算法改造为能处理多标签问题的算法，比如Adaboost.MH(Multiclass,multi-label version of Adaboost based on Hamming loss)算法[4]、Boos Texter(a Boosting-based system for Text categorization )算法[5]、RankSVM(Ranking Support Vector Machine)算法[6]等。问题转换意味着把多标签分类问题转换为多个可解的单标签分类问题，该方法转化后可以使用前面提到的算法进行标签判断，转换的常用方法有一对一分解法[7]、一对多分解法[8-9]、幂集法[10]等。

如何在群聊中准确快速地判断用户间存在的交流关系是一个极具挑战性的问题。1)时间片问题。一般的聊天室，用户身份相同没有很明确的身份特征，只能通过时间片来缩小研究的范围至一个回话长度来研究两个用户间的交流特征。2)交流对象判断问题。当对一个时间片或者会话进行研究的时候，如何快速有效地准确判断这段消息的交流对象。

目前关于群聊数据处理方面的研究已经延伸为小型社会网络挖掘，通过此类挖掘可以有效地分析用户之间的关联、行为规律、活动模式等。国内外具有代表性的研究有：最初利用基于时序特征的启发式方法来挖掘聊天用户之间的社会网络[11]，实验表明此方法可以取得一定的效果，但是受到单一时序特征的限制产生了很高的漏报率；文献[12]在文献[11]的基础上引入内容相似性特征,提出了一种结合内容相似性和时序性的社会网络挖掘方法，首先提取聊天数据中的时序特征和内容特征,然后使用Adaboost算法判断两两用户之间是否存在交流关系；文献[13]针对对象可以赋予多个类别的分类问题，提出了一种基于浮动阈值分类器的Adaboost算法(Adaboost algorithm with Floating Threshold, Adaboost.FT)，该算法虽然用浮动阈值方法取代了固定时间片分片方式，但是时间片带来的误差问题依然存在。文献[6]提出了最小化排序损失的SVM的多标签分类算法(RankSVM)，但是该算法计算复杂度比较高。

本文首次引入Adaboost.MH算法来进行群聊数据分析和多标签判断。该方法是一个弱分类器集成算法，其中每个弱分类器对整体的判断准确度不是特别高，但是对符合自身这个特征的信息而言判断的准确度很高。这样经过多次训练和迭代形成强分类器，一直应用于语法分析、人脸识别等领域，能够进行多标签判断，同时针对智慧校园聊天数据的特点提出了6个时序特征，重要的是摒弃了时间片的概念，直接利用单条数据作为研究焦点，根据提出的时序特征进行交流判断，这样既减少了时间片带来的误差问题同时也提高了判断的准确率。

1 综合特征提取

聊天数据是一种不固定的短文本形式，只能通过挖掘数据存在的特征来判断用户交流关系。本文在内容相似性特征和原有的时序特征的基础上新增加符合智慧校园聊天数据的几个特征，以此提高准确率。

1.1 数据预处理

聊天数据有很多种类型文件，在智慧校园平台中首先获取聊天数据的log类型文件，分析里面的数据字段进行分隔符处理，获得消息记录的时间戳、发送者、接收者、发送者所属群组ID等重要类型信息。

图1(a)是聊天数据原本的log文档数据格式，经过代码处理后修改成图1(b)的数据格式进行数据分析。

1.2 特征提取

本文首先对收集的聊天数据进行人工判定，即判定此条消息的发送者、接收者，存在即为1，不存在即为-1，以此作为训练集集合。在文献[10-11]的基础上选取了3个时序特征和1个内容相关性特征，由于在之前的群聊中发现每个人的身份都是一样的，交流的对象存在一定的随机性，而在智慧校园中存在明显的身份特征，家长发言多数是对前面发言的老师说的，所以又新增加了两个针对性的时序特征判断，共6个时序特征，详情如下：

1)简略回答特征。

对于待分析的消息片段中存在“好”“ok”“收到”等之类的词语时，会根据消息中的用户身份属性进行判断，家长群中存在三种身份的角色：家长、老师、管理员。对于此条消息的接收者可能存在两种身份：一是同等身份的其他人，二是不同身份的人。如果消息的发送者是管理员，那么很大概率可以认为是发给上一个不同身份的人；如果发送者是老师，则此条信息可判断为是发给上一个发言的家长；如果发送者是家长，那么可以认为是发送给前面的老师。

图1 实验数据处理结果对比

本文主要针对群聊数据进行处理，而一般家长之间的聊天会进行单聊操作。当对群聊数据进行分析时，发现家长之间聊天并回复“好”“ok”等词，确实会对分类器的判断造成误差。但是，在智慧校园身份特征比较明显的环境下，这种情况的数据很少，造成的影响有限,所以判定当发送者是家长时认为是发送给前面的老师。

2)缺省特征。

对于待分析的消息片段中有多名用户发送消息，则认为在教师群中，此条消息是发送给上一个人；在家长群中，若发送者为管理员，默认是发送给上一个人，若发送者为老师，则认为是发送给上一个家长，若发送者为家长，同时满足间隔响应特征时，则认为是发送给上一个不同身份的人。

3)接收者特征。

对于待分析的消息片段中两个用户A和B，扫描用户A的消息，如果其中含有“大家”“各位”等信息，则认为此条消息是发送给群里所有用户；如果其中含有某用户B的昵称，则认为用户A在向用户B发送消息，将用户B作为该消息的接收者；如果其中没有用户B的昵称，则用户B不是该消息的接收者。

4)时间接近特征。

对于待分析的消息片段中的时间戳进行判定，这个特征是指在一段时间的寂静之后，某用户A发布了一个消息，紧接着另一个用户B也发布了一个消息，则认为用户B对用户A的消息作出了响应。

5)夹逼准则特征(本文增加的时序特征)。

对于待分析的消息片段中一个用户A发送一条消息，接着一个用户B发送消息，之后用户A又发送了一条消息，则认为此种情况下存在一定的夹逼性，即用户A和B之间存在交流。

6)问答特征。

对于待分析的片段中用户A发布了一个类似疑问形式的消息(内容涵盖“谁”“吗”“？”等疑问词)，若内容中涵盖“谁”“你们”“大家”和“？”或者“吗”“呢”等疑问词，则判断该内容是发给所有人；若内容中涵盖“你”和“？”或者“吗”“呢”等疑问词，则判断该内容是发给上一个发消息的人。同时若在发送内容中涵盖某用户B的昵称，则认为该条消息是发给用户B的；若没有发现用户昵称，则认为该条消息是发送给群组内的所有用户。

2 基于用户身份特征的多标签分类算法

本文使用集成学习的方式，提出了一种基于用户身份特征多标签分类算法即Adaboost.ML算法(Multiclass, multi-Label version of Adaboost based on user identity)。该算法引入Adaboost.MH算法进行多标签判断。Adaboost.MH算法的核心思想是设计相应的弱分类器，通过不断地迭代和计算样本权重，获得每一个弱分类器的权重，最终组合成一个强分类器进行用户交流判断。该算法应用简单，同时不会产生overfitting的情况，只需要增加新的分类器，不需要变动原有分类器就可增加分类的准确率。

本文方法的社会网络挖掘过程和分类器训练过程如图2(a)～(b)所示。

图2 Adaboost.ML算法分类器训练过程

2.1 弱分类器设计

本文提出的弱分类器分别对应上述6个特征，现将特征设计如下：

1)对于简略回答特征，若消息中存在简略词语，需要根据发送者的身份判断接收者。若为管理员，则判断信息接收者是上一个身份不同的用户；若为老师，则认为是发送给上一个家长；若为家长，则认为是发送给上一个老师；

2)对于缺省特征，根据信息的发送者和所处的群判断信息的接收者。

3)对于接收者特征，扫描用户信息，查看其中是否含有其他用户昵称，若含有则认为两用户存在交谈。

4)对于时间接近特征，设定寂静时间为T1，用户A、B信息间隔时间为T2，当T1≥5T2时，认为用户A、B存在交流。

5)对于夹逼准则特征，当用户B发送的信息前后均为用户A的消息，则认为用户A、B存在交流。

6)对于问答特征，当用户A发送信息中含有疑问词语，若疑问词是“谁”“你们”“大家”和“?”或者“吗”和“呢”等，则认为用户A与所有用户存在交流；若其中是“你”和“？”或者“吗”“呢”等疑问词则认为用户A与上一个发信息者存在交流。用户B的消息出现在其之后，则认为用户A、B存在交流。

2.2 算法描述

Adaboost.MH算法的主要思想是维持训练集上的一个分布或权重集(表示为Dt)。初始状态下，分布D的权值是相同的。在每次迭代中,运用给定的调整公式调整每个样本的权值，使每次输入弱学习器的样本集具有不同的权重，让弱学习器集中学习使用前一弱分类器预测错误的样本，经过若干次迭代后,最终得到一个准确度更高的分类规则,即为最终的分类模型。该算法快速、简单并且易于编程，同样适合多类多标签的分类问题。

在获得特征向量的时候，除了1、-1，另设了0作为弃权标志，0代表当前信息用当前分类器无法进行判断，即不符合当前分类器的判断情景时就会自动弃权，防止判断错误带来的误差。

Adaboost.MH算法的流程[4]如下：

1)设样本集S={(x1,Y1),(x2,Y2),…,(xm,Ym)}，其中：X为训练集,Y为词义标签集合,对应聊天群组的所有用户，记k=|Y|。样本(x,Y)为单一实例x和该实例对应的词义标签集合Y。

2)该算法在样本集S上维持一个m*k的权重分布D，初始状态下，分布D的权值是相同的。

3)进入循环：令Dt为第t次迭代后的分布,为分布Dt上获得的弱规则,该规则由弱学习器产生，同时计算出错误率，即根据弱规则预测的值与正确值不同的样本占的比例。

根据错误率计算，并使用上面的公式更新样本权重，使每次输入弱学习器的样本集具有不同的权重,让弱学习器集中学习那些使用前一规则最难以预测的样本(x,Y)。

其中：ht(xi,l)表示对接收者标签l∈Y是否应该赋给实例xi的一种预测,其值|ht(x,l)|反映了这种预测的可信度。

4)获得最后的强分类器，其计算式如下：

2.3 算法特点

本文Adaboost.ML算法在传统群聊数据的处理上，主要作了以下改进：

1)引入Adaboost.MH算法作为多标签分类集成器，降低了算法的复杂度。

2)对于弱分类器，舍弃决策树和时间片的方式，而是以当前信息作为处理焦点，提出了新的特征，直接作多标签判断，舍弃了传统的单标签二分类判断，提升了准确度。

本文算法与多标签Adaboost.FT相比判断迭代的次数减少，直接进行多标签判断。下面用图形化方式分别展示使用Adaboost.FT算法和Adaboost.ML算法的判断过程。

利用Adaboost.FT算法、Adaboost.ML算法判断过程分别如图3、图4所示。其中A、B,…,E代表群聊成员，M1、M2,…,M8代表聊天信息，小圆圈数字代表判断的次数。

从图3中可以看出，针对M1进行处理，判断是否与A用户存在交流，不存在记为0。之后对M2进行处理，判断与A用户是否存在交流，若存在记为1，以此类推直到M8。A用户判断完毕，对B用户进行同样操作，直至所有用户依次判断完毕，设群聊人数为n，聊天信息数目为m，则时间复杂度为O(n*m)。

从图4中可以看出，Adaboost.ML算法直接以单条信息为焦点判断用户间是否存在交流。针对M1进行处理时，直接对所有用户进行判断，判断是否存在交流，之后对M2进行处理，以此类推直到M8，判断的迭代次数为m次，时间复杂度为O(m)，相比图3判断的迭代次数变少，时间复杂度明显降低。

图3 Adaboost.FT算法判断交互过程

图4 Adaboost.ML算法判断交互过程

3 实验结果及分析

3.1 实验方法和数据

本文使用智慧校园App群聊和单聊数据、微信聊天数据集作为实验数据集，一周的聊天数据作为一个分析的单元，目前获得两年的聊天数据，其中20周作为实验数据,然后人工分析出20周数据的聊天网络，最后对所有聊天数据进行自动挖掘，记录实验结果，并用平均值作为最终结果。

3.2 评估指标

本文使用漏报率(false_negative)和误报率(false_positive)来评估挖掘的准确性,即：

false_negative=(N-TN)/N

false_positive=(M-TN)/M

式中：N为经人工分析得到的社会网络关系的数目；M为由程序自动挖掘出的社会网络关系的数目；TN为自动推断出的社会网络关系中正确关系的数目。

3.3 实验结果与对比分析

第14周和第15周数据实验结果对比如图5所示。图5中，指标对比网络密度为0.299:0.053、网络平均度为14.64:3.40、平均聚类系数为0.623：0.398、平均路径长度为1.399:1.872。

图5中节点(家长姓名)的排列和顺序都有相应变化，从图5中指标对比可以看出，上一周(第14周)网络密度和平均度等都比下一周(第15周)要高一些，由此可以判断上一周的家长相对比较活跃，因此家长节点的度也增加了，并处于靠中心的位置，网络相对比较复杂；而下一周的图比较简单，类似只有一个老师中心，周围很多家长的小节点聊天次数较多，下一周就只有老师和少部分家长存在聊天记录。通过调查得知上一周进行了学生体能测试，需要在家里进行跳绳等项目测试并上报给班主任。

图5 家校沟通实验结果

表1列出了智慧校园数据集上使用基于规则的启发式方法[11]和Adaboost.FT算法、Adaboost.ML算法的平均性能。

从表1中可以看出，本文的算法在智慧校园聊天数据集上无论是在误报率、漏报率和推断时间上都存在明显的优势，与基于规则的启发式方法相比在误报率、漏报率上分别降低了53%、66%。

表2列出了在智慧校园数据集上使用RankSVM方法和Adaboost.MH算法、Adaboost.FT算法、Adaboost.ML算法的五项度量指标(汉明损失、排序损失、覆盖率、1错误率、平均精度)的实验结果，这四种算法均利用机器学习的思想进行多标签分类。

从表2可以看出，本文的算法Adaboost.ML存在较好的性能表现，虽然在汉明损失指标上比Adaboost.FT算法高了4%，预测的错误率提高了，但是其他指标上均存在明显的优势，尤其是在平均精度指标上比Adaboost.FT算法提升了4%、比Adaboost.MH算法提升9%、比RankSVM算法提升14%。

表1 智慧校园聊天数据集实验结果

表2 智慧校园聊天数据集其他实验指标

微信数据集选取的是某个年级在两年内的聊天数据，里面包括辅导员、学生和部分家长。表3列出了在微信数据集上的不同方法的性能结果.

表3 微信聊天数据集实验结果

从表3中可以看出，在微信数据集上，本文算法在误报率、漏报率和推断时间上依然存在明显优势。

表4列出了在微信数据集上使用RankSVM方法和Adaboost.MH算法、Adaboost.FT算法、Adaboost.ML算法的五项度量指标。

从表4中可以看出，本文的算法Adaboost.ML在其中汉明损失和排序损失两项指标上存在优势，在其他的指标上也具有良好的表现，相对比较稳定。

表4 微信聊天数据集其他实验指标

4 结语

针对聊天信息判断的问题，本文扩展了常用的时序特征并新增了夹逼准则等特征，同时把消息判断抽象为多标签分类问题，提出了一种基于用户身份特征的多标签分类算法即Adaboost.ML算法。该算法运用集成学习算法思想，采用单条信息直接判断分类，利用特征值判断结果进行弱分类器学习，最终形成更加准确的强分类器。实验分析中，将本文算法与现有聊天信息挖掘算法进行对比，实验结果表明，本文算法的准确率相对较高，分类性能稳定，推断时间较短。在以后的研究中，将通过提高单聊数据的权重等其他方式来提高分类的准确性和稳定性，同时也将研究如何改善适应更多情况的分类。

)

[1]HUANGRH,ZHANGJB,HUYB,etal.Smartcampus:thedevelopingtrendsofdigitalcampus[J].OpenEducationResearch, 2012, 18(4): 12-17.

[2]KEERTHISS,SHEVADESK,BHATTACHARYYAC,etal.ImprovementstoPlatt’sSMOalgorithmforSVMclassifierdesign[J].NeuralComputation, 2001, 13(3): 637-649.

[3]TSOUMAKASG,KATAKISI,TANIARD.Multi-labelclassification:anoverview[J].InternationalJournalofDataWarehousingandMining, 2007, 3(3): 1-13.

[4]SCHAPIRERE,SINGERY.Improvedboostingalgorithmsusingconfidence-ratedpredictions[J].MachineLearning, 1999, 37(3): 297-336

[5]SCHAPIRERE,SINGERY.BoosTexter:aboostingbasedsystemfortextcategorization[J].MachineLearning, 2000, 39(2/3): 135-168

[6]ELISSEEFFA,WESTONJ.Akernelmethodformulti-labelledclassification[C]//NIPS2001:ProceedingsoftheAnnualConferenceonNeuralInformationProcessingSystems.Cambridge,MA:MITPress, 2001: 681-687.

[7] 万书鹏.基于两类和三类支持向量机的快速多标签分类算法[D].南京:南京师范大学,2008:4-7.(WANSP.Afastmulti-labelclassificationalgorithmbasedonbinaryandtripleclasssupportvectormachines[D].Nanjing:NanjingNormalUniversity,2008:4-7.)

[8]FOXCR,CLEMENRT.Subjectiveprobabilityassessmentindecisionanalysis:partitiondependenceandbiastowardtheignoranceprior[J].ManagementScience, 2005, 51(9): 1417-1432.

[9]SPEIRS-BRIDGEA,FIDLERF,MCBRIDEM,etal.Reducingoverconfidenceintheinternaljudgmentsofexperts[J].RiskAnalysis, 2010, 30(3): 512-523.

[10]TROHIDISK,TSOUMARKSG,KALLIRISG,etal.Multi-labelclassificationofmusicintoemotions[C]//ISMIR2008:Proceedingsofthe9thInternationalConferenceonMusicInformationRetrieval.Philadelphia: [s.n.], 2008: 325-330.

[11]MUTTONP.InferringandvisualizingsocialnetworksonInternetrelaychat[C]//IV’04:Proceedingsofthe8thInternationalConferenceonInformationVisualization.Washington,DC:IEEEComputerSociety, 2004: 35-43.

[12] 张卫,曹先彬,尹洪章.基于多特征融合的聊天室社会网络挖掘方法[J].中国科学技术大学学报,2009,39(5):540-546.(ZHANGW,CAOXB,YINHZ.Chatroomsocialnetworkminingbasedonmulti-featuresfusion[J].JournalofUniversityofScienceandTechnologyofChina, 2009, 39(5): 540-546.)

[13] 张丹普,付忠良,王莉莉,等.基于浮动阈值分类器组合的多标签分类算法[J].计算机应用,2015,35(1):147-151.(ZHANGDP,FUZL,WANGLL,etal.Multi-labelclassificationalgorithmbasedonfloatingthresholdclassifierscombination[J].JournalofComputerApplications, 2015, 35(1): 147-151.)

ZHENG Xiaoxue, born in 1990, M. S. candidate. Her research interests include data mining, machine learning.

ZHANG Dafang, born in 1959, Ph. D., professor. His research interests include trusted system and network, software test, next generation Internet.

DIAO Zulong, born in 1988, Ph. D. candidate. His research interests include big data, data mining, machine learning.

Multi-label classification algorithm based on user identity

ZHENG Xiaoxue1,2*, ZHANG Dafang1,2, DIAO Zulong1,2

(1.CollegeofComputerScienceandElectronicEngineering,HunanUniversity,ChangshaHunan410082,China； 2.LaboratoryofDependableSystemsandNetwork,HunanUniversity,ChangshaHunan410082,China)

At present there lacks a way to measure home-school communication in a smart campus. Concerning the obvious identity characteristics when chatting in a smart campus, a new multi-label classification algorithm named Adaboost.ML (Multiclass, multi-label version of Adaboost based on user identity) was proposed. Firstly, the heuristic rule was added for the proposed algorithm. Then, the Adaboost.MH (Multiclass,multi-label version of Adaboost based on Hamming loss) algorithm was introduced, and the concept of dataset sharding was discarded. Finally, the single data was used as the focus of analysis, which reduced the inference time and the error caused by the edge of the time slice. The comprehensive decision-making about the relationship between the chat users was made out. The experimental results show that, compared with the heuristic algorithm based on rules, the false positive rate of the proposed algorithm is decreased by 53% while its false negative rate is reduced by 66% on the dataset of smart campus. The proposed algorithm also has good classification results on the dataset of WeChat. At present, the proposed algorithm has been applied to the smart campus project, and it can get home-school communication quickly and accurately.

social network; smart campus; heuristic rule; multi-label judgment; ensemble learning

2016- 11- 14;

2017- 01- 16。

郑晓雪(1990—)，女，吉林松原人，硕士研究生，主要研究方向：数据挖掘、机器学习； 张大方(1959—)，男，上海人，教授，博士，CCF会员，主要研究方向：可信系统与网络、软件测试、下一代互联网； 刁祖龙(1988—)，男，湖南株洲人，博士研究生，主要研究方向：大数据、数据挖掘、机器学习。

1001- 9081(2017)06- 1697- 05

10.11772/j.issn.1001- 9081.2017.06.1697

TP181;TP301.6

A