基于内容分析的短信种子客户挖掘模型与算法

2016-11-30黄志超陶俊才高胜保

电信科学 2016年2期

关键词：树型短信种子

黄志超，陶俊才，高胜保

（1.南昌大学信息工程学院计算中心，江西南昌330029；2.中国电信股份有限公司江西分公司，江西南昌330029）

研究与开发

基于内容分析的短信种子客户挖掘模型与算法

黄志超1，陶俊才1，高胜保2

（1.南昌大学信息工程学院计算中心，江西南昌330029；2.中国电信股份有限公司江西分公司，江西南昌330029）

为从海量的短信记录中挖掘短信种子客户，控制种子短信的传播路径，提高其传播效率，提出了一种基于内容分析的短信种子客户挖掘模型与算法。首先通过分析客户转发短信的兴趣性、随机性、单向性特征，构建客户转发短信的树型模型；其次，通过定义和应用综合评价函数生成优化的种子客户挖掘模型，并基于亲密群概念实现短信种子客户的挖掘；最后，使用电信运营商的实际数据进行实证分析，验证了上述模型与算法的有效性。

短信种子客户；内容分析；挖掘模型；挖掘算法；亲密群

1 引言

随着互联网的发展和智能终端的普及，短信、微博、微信等现代信息传播手段被广泛应用，它们都具有使用便捷、传播快速等优点。相对而言，短信对受众的年龄与知识水平、移动终端功能的要求较低而具有特定的优势，更适合信息广播、知识普及、亲情交流等场景。种子短信指承载某些特定信息的定制短信，如：政府发布的灾害预警、信息发布，企业的客服信息，增值服务商的亲情交互、幽默信息等。种子客户则是种子短信的首轮接收/转发者，由于他们应当对特定种子短信具有尽可能高的兴趣与短信转发量，因此对于信息的传播效率与成本具有决定性的影响。然而，目前确定种子客户的方法基本凭借人工经验寻找和筛选，其效率和准确率极不理想。因此，从海量的短信记录中挖掘出优质的短信种子客户，对于控制种子短信的传播路径、提高传播效率、降低传播成本，具有重要意义。

短信传播具有极强的兴趣性、随机性、单向性特征。兴趣性指不同的短信客户对于不同类型的短信（新闻、体育、幽默、益智、养生等）往往具有较强的兴趣偏好，因而种子短信的生成/首发者（以下称为短信中心）一般需将种子短信分成多个类别，以提高客户转发同一类型短信的概率，这就决定了需要通过短信内容的关联分析来识别同一客户感兴趣的短信类别，并有必要针对不同兴趣的客户群分类建立不同的挖掘模型。随机性是指短信客户转发短信的对象可能是随意的，也可能具有相对固定的客户群和一定的规律，为了提高种子短信的转发效率与传播速度，就需要从所有转发种子短信的客户中挖掘出规律性较强和拥有相对固定客户群的种子客户。单向性特征是指种子短信在传播过程中不会发生直接回传的现象，因为接收者没有必要把内容相同的短信再回发给短信的发出者，而对于可能出现的循环回传的种子短信不可能再被转发，故其回传没有增加信息的传播，对于识别种子客户没有任何价值，必须予以剔除。

既有的关于挖掘短信种子客户的可参考文献很少，参考文献［1］中关于构建树型网络的思想比较具有参考价值。然而，由于以下主要原因使其不适用于本文提出的短信种子客户挖掘任务：首先，其挖掘目标（短信种子用户）是指短信的创建/首发者，而不是短信首次接收/转发者；第二，其基于短信的时域特征而不是内容进行关联分析，准确性不够；最后，其挖掘路径是在树型网络中自底向上进行，与本文的要求正好相反。本文的主要工作在于：定义并构建新的基于内容分析的短信种子客户挖掘模型，提出新的种子客户挖掘算法，并基于完整的实际短信数据进行实证分析，验证本文研究成果的有效性。

2 原始模型构建

2.1 建立树型模型描述种子短信的转发关系

短信中心创建并向客户发送种子短信，客户对感兴趣的种子短信进行转发，这种转发过程与关系可以用图1所示的原始模型来描述，其中的节点表示客户，边为客户之间的转发关系。节点的属性包括：发送号码、接收号码、短信内容、发送时间。如前所述，在该模型中，不可能出现直接回传的短信，而对于可能发生的循环回传（图1中的回路），则可用最小生成树算法予以剪除，从而得到如图2所示的树型模型。其中，第0层节点为短信中心，其发出的短信称为种子短信。第1层的各节点是种子短信的首轮接收/转发者，即前文所定义的种子客户，以下的节点则为其他客户。初始的种子客户只能根据经验通过人工筛选得到，之后则可应用本文研究成果自动挖掘优质的短信转发客户，作为种子客户群。

图1 种子短信转发的基本模型

图2 种子短信转发的树型模型

2.2 模型的分类

上述模型是针对某一类种子短信而建立的，如前所述，针对客户转发短信的兴趣性特征，短信中心一般需将种子短信分成多个类别，从而针对不同兴趣的客户群分类建立不同的挖掘模型。有多种算法可用于实现种子短信的分类［2-6］，本文采用简单的K NN算法［7］来实现。但为了提高挖掘种子客户的效率与准确率，需要进一步剔除冗余短信，为此需要对K NN算法进行下述调整：在分类结果中，一般存在与训练数据距离为0的测试数据，K NN算法的处理方法是直接将它们全部归入一类，实际上这些数据中包含着不少冗余数据，因此本文进一步采用内容匹配对其予以发现并剔除。

3 种子客户挖掘算法

为从图2的树型模型中挖掘种子客户，提出短信种子客户挖掘（seed customer mining，SCM）算法，该算法分为3个阶段。

3.1 发现和剔除一次转发量过小的节点

图2中有不少节点的一次转发量很小，这些节点对于计算结果的影响很小，为了降低计算复杂度，应当发现和剔除这些节点，为此作如下定义。

·一次转发量：某节点向其下邻层节点转发的种子短信数。

·一次转发量阈值α：需剔除节点的一次转发量的上限。显然，当阈值α取值大于图2中最大的节点一次转发量时，优化模型将只剩下根节点；当其取值为0时，则优化模型将与图2相同，其实际取值需要结合使用者的需求、经验，通过实验来调整和确定。本阶段将计算所有节点的一次转发量，将其中一次转发量小于α的节点剔除，以便在以下处理过程中被忽略，从而生成一次优化模型。

3.2 发现和剔除综合评分过低的节点

在一次优化模型的基础上，进一步发现和剔除其中综合评分过小的节点，得到二次优化模型，为此作如下定义。

·i子树：以任意子节点i为根形成的种子短信转发子树。

·评分阈值β：需剔除节点的综合评分上限，其取值

方法类似于α。

节点i的评分需要综合考虑i子树各层节点的转发短信数及其与节点i的距离，为此定义综合评价函数如下：

其中，i为第i个节点；Mi为第i个节点的得分；j为i子树的第j层；Lj为第j-1层向第j层转发的种子短信数；n为节点的个数；m为i子树的层数。在实际情况中，客户可能转发同一类型中的多条短信，从而一个客户可能存在多个节点评分，将其相加作为该客户的最终评分。根据式（1），显然可得出以下结论：

·i子树的各层转发短信数越大，节点i的评分越高；

·若i子树中某一节点与节点i的距离越远，则其转

发短信数对于节点i的评分的贡献越小。

为便于估算和调整阈值β，使用下面给出的式子对节点综合评分进行归一化处理，使β的取值范围为［0，1］：

其中，yi为客户i归一化的结果，Mi为客户i的评分，Min为客户评分的最低分数，Max为客户评分的最高分数，n为客户的个数。

通过计算一次优化模型中每个节点的综合评分，将其中评分小于β的节点剔除，即得到二次优化模型。显然，当β取值为0时，则二次优化模型将与一次优化模型相同；当其取值为1时，则二次优化模型只会保留评分最大的少数节点。

3.3 基于亲密群概念挖掘种子客户

（1）基本思路

以二次优化模型为基础，进一步发现亲密群，并将其子节点予以剔除。定义如下。

·亲密群：存在必然转发关系的父子节点。

·亲密群阈值γ：判定父子节点是否为亲密群的评分标准，小于γ者不是亲密群，否则为亲密群，其取值范围为［0，1］，取值方法类似于α。

例如，节点A在接收到种子短信后一定转发给节点B，则A、B构成一个亲密群。显然，需将节点B剔除。

（2）算法过程

本阶段的算法过程如图3所示，其中，图3（d）中集合W由式（3）得到：

集合C和集合L分别为图3（b）和图3（c）所示；＜A，B＞表示客户A转发短信给客户B；计数Q表示图3（a）中的父子节点出现的次数。

图3（f）中集合S由式（4）得到：

其中，Hij为父子节点出现的概率，Pij为客户i转发给客户j的种子短信条数，Ri为客户i转发的种子短信条数，m为集合L的元素个数，n为集合C的元素个数。

（3）算法实现

输入：Users表示二次优化模型中的节点，树型结构为T，阈值为γ，MinC表示节点出现的最小次数。

输出：亲密群结果集Result，种子客户群EndUsers。

步骤1计算Users中每个节点出现的次数即C=［C1，C2，…，Cn］，其中n表示Users个数；

步骤2初始化结果集Result=［］，flag=0，close=［］，EndUsers=［］，k=1；

步骤3For i=1：n

If（Ci≥MinC）

图3 本阶段算法过程

Children=Users［i］的孩子节点且该节点∈Users For j=1：length（Children）

ct=T中出现Users［i］-＞Children［j］的次数

If（ct！=0）

If（ct≥γ）/亲密群客户

Result=［Result Children［j］；

End If

End For

End If

End For

步骤4 For i=1：n

If（i∉Result）

EndUsers=［EndUsers i］；

End If

End For

步骤5算法结束，输出结果。

上述步骤中，步骤1和步骤2的时间复杂度为O（n），其中，n为二次优化模型中的节点数；步骤3的时间复杂度为O（n2m2），其中，m表示二次优化模型中父子节点的子节点数，由于一般m远远小于n，所以该阶段总的时间复杂度为O（n2）。

4 实证分析

实证数据来源于某省电信分公司，从2015年2-3月份的短信中随机抽取共1万条手机短信和100条种子短信，格式见表1。

·种子短信集合用作训练集，1万条手机短信用作测试文本集，使用K NN算法析取出3类种子短信：情人节祝福短信、除夕拜年短信、元宵祝福短信。

·对3类短信分别构建树型转发模型。

·发现和剔除一次转发量过小的节点（α取值3），得到一次优化模型。

·在一次优化模型的基础上，应用第3.2节中的评价式（1）、式（2）对于不同短信类型计算每个客户的评分，见表2。其中的类型1、2、3依次对应情人节种子短信、春节短信、元宵节短信，用序号表示不同的客户。将表2中的评分结果与阈值β比较，剔除小于β的节点（β取值0.7），得到二次优化模型。

表1 客户短信数据格式

表2 客户评分

·进一步应用亲密群概念进行挖掘，得到的种子客户见表3（γ取值0.65）。

由表2和表3可知，从1万条手机短信中挖掘出的种子客户数为40名。为进一步分析阈值α、β、γ对挖掘结果的影响，另外选取2万条短信与上述结果进行比较，相关情况如图4、图5所示。图4为设定β=0.7、γ=0.65，种子客户数随α变化的结果，当α≥2时，曲线趋于平缓；图5为设定α=3、γ=0.65，种子客户数随β变化的结果，当β≥0.7时，曲线趋于平缓；这些变化趋势与实际情况完全吻合。因此，可以选择α=2、β=0.7作为挖掘种子客户时的参考值，必要时可以根据需要调整。

5 结束语

挖掘和利用短信种子客户，可以有效控制短信传播路径、提高传播效率、降低传播成本。为了从海量的短信记录中快速、准确地挖掘出种子客户，用作各类种子短信的首发客户，本文综合考虑客户转发短信的兴趣性、随机性、单向性特征，提出了一种基于内容分析的短信种子客户挖掘模型与挖掘算法。首先，针对种子短信按客户兴趣分类的特点，采用文本分类方法分别建立描述短信转发关系的原始树型模型；然后，基于本文提出的挖掘算法，对原始模型逐步优化，并提出亲密群的概念，最终挖掘出种子客户群。最后，使用实际数据进行实证分析，验证了本文研究成果的有效性。值得指出的是，本文研究成果也适用于微信等公共媒体的种子用户挖掘。

表3 种子客户

图4 种子客户数随α的变化关系

图5 种子客户数随β的变化关系

［1］李永立，吴冲，胡冬冬，等.基于树型网络分析的短信种子客户挖掘模型及其实证分析［J］.中国管理科学，2012（S1）：48-54.LI Y L，WU C，HU D D，et al.The SMS seed customer mining model and empirical analysis based on tree network analysis［J］.Chinese Journal of Management Science，2012（S1）：48-54.

［2］HARRINGTON P.机器学习实战［M］.李锐，李鹏，曲亚东，等译.北京：人民邮电出版社，2013：32-52.HARRINGTON P.Machine Learning in Action［M］.Translated by LI R，LI P，QU Y D，et al.Beijing：Posts and Telecom Press，2013：32-52.

［3］李兵昌.短信种子客户识别的研究［D］.广州：华南理工大学，2013：1-52.LI B C.The research of SMS seed users’identification［D］.Guangzhou：South China University of Technology，2013：1-52.

［4］陆旭.文本挖掘中若干关键问题研究［M］.合肥：中国科学技术大学出版社，2008：13-29.LU X.Research on Some Key Issues in Text Mining［M］.Hefei：Press of University of Science and Technology of China，2008：13-29.

［5］黄娟娟.基于KNN的文本分类特征选择与分类算法的研究与改进［D］.厦门：厦门大学，2014：1-16.HUANG J J.Research and improvement on feature selection and classification algorithms for text classification based on KNN［D］.Xiamen：Xiamen University，2014：1-16.

［6］王博.文本分类中特征选择技术的研究［D］.长沙：国防科学技术大学，2009：1-46.WANG B.Related technologies research on feature selection for text categorization［D］.Changsha：National University of Defense Technology，2009：1-46.

［7］HAN J W，KAMBER M，PEI J.数据挖掘概念与技术第三版［M］.范明，孟小峰，译.北京：机械工业出版社，2012：288-319.HAN J W，KAMBER M，PEI J.Data Mining Concepts and Techniques，Third Edition［M］.Translated by FAN M，MENG X F.Beijing：China Machine Press，2012：288-319.

SMS seed customers Mining model and algorithm based on content analysis

HUANG Zhichao1，TAO Juncai1，GAO Shengbao2
1.Computing Center，Information Engineering College，Nanchang University，Nanchang 330029，China 2.Jiangxi Branch of China Telecom Co.，Ltd.，Nanchang 330029，China

In order to mining SMS（short message service）seed customers from massive text messages，control the spread of the seed messages path and improve the efficiency of its spread，a SMS seed customers mining model and algorithm was proposed，which was based on content analysis.First of all，by analyzing the interest，randomness and one-way characteristics of customer forwarding messages，the tree model of customer forwarding messages were constructed.Secondly，the optimal seed customers mining model was generated by definition and application of comprehensive evaluation function，and SMS seed customers mining was realized based on the concept of close group.Finally，by analyzing the actual data from telecom operators，the effectivity of the model and algorithm was verified.

SMS seed customer，content analysis，mining model，mining algorithm，close group

The National Natural Science Foundation of China（No.61262049）

TP311

10.11959/j.issn.1000-0801.2016057

2015-06-13；

2016-01-07

国家自然科学基金资助项目（No.61262049）