黃志超，陶俊才，高勝保

（1.南昌大學信息工程學院計算中心，江西南昌330029；2.中國電信股份有限公司江西分公司，江西南昌330029）

研究與開發(fā)

基于內容分析的短信種子客戶挖掘模型與算法

黃志超1，陶俊才1，高勝保2

（1.南昌大學信息工程學院計算中心，江西南昌330029；2.中國電信股份有限公司江西分公司，江西南昌330029）

為從海量的短信記錄中挖掘短信種子客戶，控制種子短信的傳播路徑，提高其傳播效率，提出了一種基于內容分析的短信種子客戶挖掘模型與算法。首先通過分析客戶轉發(fā)短信的興趣性、隨機性、單向性特征，構建客戶轉發(fā)短信的樹型模型；其次，通過定義和應用綜合評價函數生成優(yōu)化的種子客戶挖掘模型，并基于親密群概念實現短信種子客戶的挖掘；最后，使用電信運營商的實際數據進行實證分析，驗證了上述模型與算法的有效性。

短信種子客戶；內容分析；挖掘模型；挖掘算法；親密群

1 引言

隨著互聯網的發(fā)展和智能終端的普及，短信、微博、微信等現代信息傳播手段被廣泛應用，它們都具有使用便捷、傳播快速等優(yōu)點。相對而言，短信對受眾的年齡與知識水平、移動終端功能的要求較低而具有特定的優(yōu)勢，更適合信息廣播、知識普及、親情交流等場景。種子短信指承載某些特定信息的定制短信，如：政府發(fā)布的災害預警、信息發(fā)布，企業(yè)的客服信息，增值服務商的親情交互、幽默信息等。種子客戶則是種子短信的首輪接收/轉發(fā)者，由于他們應當對特定種子短信具有盡可能高的興趣與短信轉發(fā)量，因此對于信息的傳播效率與成本具有決定性的影響。然而，目前確定種子客戶的方法基本憑借人工經驗尋找和篩選，其效率和準確率極不理想。因此，從海量的短信記錄中挖掘出優(yōu)質的短信種子客戶，對于控制種子短信的傳播路徑、提高傳播效率、降低傳播成本，具有重要意義。

短信傳播具有極強的興趣性、隨機性、單向性特征。興趣性指不同的短信客戶對于不同類型的短信（新聞、體育、幽默、益智、養(yǎng)生等）往往具有較強的興趣偏好，因而種子短信的生成/首發(fā)者（以下稱為短信中心）一般需將種子短信分成多個類別，以提高客戶轉發(fā)同一類型短信的概率，這就決定了需要通過短信內容的關聯分析來識別同一客戶感興趣的短信類別，并有必要針對不同興趣的客戶群分類建立不同的挖掘模型。隨機性是指短信客戶轉發(fā)短信的對象可能是隨意的，也可能具有相對固定的客戶群和一定的規(guī)律，為了提高種子短信的轉發(fā)效率與傳播速度，就需要從所有轉發(fā)種子短信的客戶中挖掘出規(guī)律性較強和擁有相對固定客戶群的種子客戶。單向性特征是指種子短信在傳播過程中不會發(fā)生直接回傳的現象，因為接收者沒有必要把內容相同的短信再回發(fā)給短信的發(fā)出者，而對于可能出現的循環(huán)回傳的種子短信不可能再被轉發(fā)，故其回傳沒有增加信息的傳播，對于識別種子客戶沒有任何價值，必須予以剔除。

既有的關于挖掘短信種子客戶的可參考文獻很少，參考文獻［1］中關于構建樹型網絡的思想比較具有參考價值。然而，由于以下主要原因使其不適用于本文提出的短信種子客戶挖掘任務：首先，其挖掘目標（短信種子用戶）是指短信的創(chuàng)建/首發(fā)者，而不是短信首次接收/轉發(fā)者；第二，其基于短信的時域特征而不是內容進行關聯分析，準確性不夠；最后，其挖掘路徑是在樹型網絡中自底向上進行，與本文的要求正好相反。本文的主要工作在于：定義并構建新的基于內容分析的短信種子客戶挖掘模型，提出新的種子客戶挖掘算法，并基于完整的實際短信數據進行實證分析，驗證本文研究成果的有效性。

2 原始模型構建

2.1 建立樹型模型描述種子短信的轉發(fā)關系

短信中心創(chuàng)建并向客戶發(fā)送種子短信，客戶對感興趣的種子短信進行轉發(fā)，這種轉發(fā)過程與關系可以用圖1所示的原始模型來描述，其中的節(jié)點表示客戶，邊為客戶之間的轉發(fā)關系。節(jié)點的屬性包括：發(fā)送號碼、接收號碼、短信內容、發(fā)送時間。如前所述，在該模型中，不可能出現直接回傳的短信，而對于可能發(fā)生的循環(huán)回傳（圖1中的回路），則可用最小生成樹算法予以剪除，從而得到如圖2所示的樹型模型。其中，第0層節(jié)點為短信中心，其發(fā)出的短信稱為種子短信。第1層的各節(jié)點是種子短信的首輪接收/轉發(fā)者，即前文所定義的種子客戶，以下的節(jié)點則為其他客戶。初始的種子客戶只能根據經驗通過人工篩選得到，之后則可應用本文研究成果自動挖掘優(yōu)質的短信轉發(fā)客戶，作為種子客戶群。

圖1 種子短信轉發(fā)的基本模型

圖2 種子短信轉發(fā)的樹型模型

2.2 模型的分類

上述模型是針對某一類種子短信而建立的，如前所述，針對客戶轉發(fā)短信的興趣性特征，短信中心一般需將種子短信分成多個類別，從而針對不同興趣的客戶群分類建立不同的挖掘模型。有多種算法可用于實現種子短信的分類［2-6］，本文采用簡單的K NN算法［7］來實現。但為了提高挖掘種子客戶的效率與準確率，需要進一步剔除冗余短信，為此需要對K NN算法進行下述調整：在分類結果中，一般存在與訓練數據距離為0的測試數據，K NN算法的處理方法是直接將它們全部歸入一類，實際上這些數據中包含著不少冗余數據，因此本文進一步采用內容匹配對其予以發(fā)現并剔除。

3 種子客戶挖掘算法

為從圖2的樹型模型中挖掘種子客戶，提出短信種子客戶挖掘（seed customer mining，SCM）算法，該算法分為3個階段。

3.1 發(fā)現和剔除一次轉發(fā)量過小的節(jié)點

圖2中有不少節(jié)點的一次轉發(fā)量很小，這些節(jié)點對于計算結果的影響很小，為了降低計算復雜度，應當發(fā)現和剔除這些節(jié)點，為此作如下定義。

·一次轉發(fā)量：某節(jié)點向其下鄰層節(jié)點轉發(fā)的種子短信數。

·一次轉發(fā)量閾值α：需剔除節(jié)點的一次轉發(fā)量的上限。顯然，當閾值α取值大于圖2中最大的節(jié)點一次轉發(fā)量時，優(yōu)化模型將只剩下根節(jié)點；當其取值為0時，則優(yōu)化模型將與圖2相同，其實際取值需要結合使用者的需求、經驗，通過實驗來調整和確定。本階段將計算所有節(jié)點的一次轉發(fā)量，將其中一次轉發(fā)量小于α的節(jié)點剔除，以便在以下處理過程中被忽略，從而生成一次優(yōu)化模型。

3.2 發(fā)現和剔除綜合評分過低的節(jié)點

在一次優(yōu)化模型的基礎上，進一步發(fā)現和剔除其中綜合評分過小的節(jié)點，得到二次優(yōu)化模型，為此作如下定義。

·i子樹：以任意子節(jié)點i為根形成的種子短信轉發(fā)子樹。

·評分閾值β：需剔除節(jié)點的綜合評分上限，其取值

方法類似于α。

節(jié)點i的評分需要綜合考慮i子樹各層節(jié)點的轉發(fā)短信數及其與節(jié)點i的距離，為此定義綜合評價函數如下：

其中，i為第i個節(jié)點；Mi為第i個節(jié)點的得分；j為i子樹的第j層；Lj為第j-1層向第j層轉發(fā)的種子短信數；n為節(jié)點的個數；m為i子樹的層數。在實際情況中，客戶可能轉發(fā)同一類型中的多條短信，從而一個客戶可能存在多個節(jié)點評分，將其相加作為該客戶的最終評分。根據式（1），顯然可得出以下結論：

·i子樹的各層轉發(fā)短信數越大，節(jié)點i的評分越高；

·若i子樹中某一節(jié)點與節(jié)點i的距離越遠，則其轉

發(fā)短信數對于節(jié)點i的評分的貢獻越小。

為便于估算和調整閾值β，使用下面給出的式子對節(jié)點綜合評分進行歸一化處理，使β的取值范圍為［0，1］：

其中，yi為客戶i歸一化的結果，Mi為客戶i的評分，Min為客戶評分的最低分數，Max為客戶評分的最高分數，n為客戶的個數。

通過計算一次優(yōu)化模型中每個節(jié)點的綜合評分，將其中評分小于β的節(jié)點剔除，即得到二次優(yōu)化模型。顯然，當β取值為0時，則二次優(yōu)化模型將與一次優(yōu)化模型相同；當其取值為1時，則二次優(yōu)化模型只會保留評分最大的少數節(jié)點。

3.3 基于親密群概念挖掘種子客戶

（1）基本思路

以二次優(yōu)化模型為基礎，進一步發(fā)現親密群，并將其子節(jié)點予以剔除。定義如下。

·親密群：存在必然轉發(fā)關系的父子節(jié)點。

·親密群閾值γ：判定父子節(jié)點是否為親密群的評分標準，小于γ者不是親密群，否則為親密群，其取值范圍為［0，1］，取值方法類似于α。

例如，節(jié)點A在接收到種子短信后一定轉發(fā)給節(jié)點B，則A、B構成一個親密群。顯然，需將節(jié)點B剔除。

（2）算法過程

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

集合C和集合L分別為圖3（b）和圖3（c）所示；＜A，B＞表示客戶A轉發(fā)短信給客戶B；計數Q表示圖3（a）中的父子節(jié)點出現的次數。

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

其中，Hij為父子節(jié)點出現的概率，Pij為客戶i轉發(fā)給客戶j的種子短信條數，Ri為客戶i轉發(fā)的種子短信條數，m為集合L的元素個數，n為集合C的元素個數。

（3）算法實現

輸入：Users表示二次優(yōu)化模型中的節(jié)點，樹型結構為T，閾值為γ，MinC表示節(jié)點出現的最小次數。

輸出：親密群結果集Result，種子客戶群EndUsers。

步驟1計算Users中每個節(jié)點出現的次數即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］的孩子節(jié)點且該節(jié)點∈Users For j=1：length（Children）

ct=T中出現Users［i］-＞Children［j］的次數

If（ct！=0）

If（ct≥γ）/親密群客戶

Result=［Result Children［j］；

End If

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為二次優(yōu)化模型中的節(jié)點數；步驟3的時間復雜度為O（n2m2），其中，m表示二次優(yōu)化模型中父子節(jié)點的子節(jié)點數，由于一般m遠遠小于n，所以該階段總的時間復雜度為O（n2）。

4 實證分析

實證數據來源于某省電信分公司，從2015年2-3月份的短信中隨機抽取共1萬條手機短信和100條種子短信，格式見表1。

·種子短信集合用作訓練集，1萬條手機短信用作測試文本集，使用K NN算法析取出3類種子短信：情人節(jié)祝福短信、除夕拜年短信、元宵祝福短信。

·對3類短信分別構建樹型轉發(fā)模型。

·發(fā)現和剔除一次轉發(fā)量過小的節(jié)點（α取值3），得到一次優(yōu)化模型。

·在一次優(yōu)化模型的基礎上，應用第3.2節(jié)中的評價式（1）、式（2）對于不同短信類型計算每個客戶的評分，見表2。其中的類型1、2、3依次對應情人節(jié)種子短信、春節(jié)短信、元宵節(jié)短信，用序號表示不同的客戶。將表2中的評分結果與閾值β比較，剔除小于β的節(jié)點（β取值0.7），得到二次優(yōu)化模型。

表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 結束語

挖掘和利用短信種子客戶，可以有效控制短信傳播路徑、提高傳播效率、降低傳播成本。為了從海量的短信記錄中快速、準確地挖掘出種子客戶，用作各類種子短信的首發(fā)客戶，本文綜合考慮客戶轉發(fā)短信的興趣性、隨機性、單向性特征，提出了一種基于內容分析的短信種子客戶挖掘模型與挖掘算法。首先，針對種子短信按客戶興趣分類的特點，采用文本分類方法分別建立描述短信轉發(fā)關系的原始樹型模型；然后，基于本文提出的挖掘算法，對原始模型逐步優(yōu)化，并提出親密群的概念，最終挖掘出種子客戶群。最后，使用實際數據進行實證分析，驗證了本文研究成果的有效性。值得指出的是，本文研究成果也適用于微信等公共媒體的種子用戶挖掘。

表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.機器學習實戰(zhàn)［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］.范明，孟小峰，譯.北京：機械工業(yè)出版社，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

A

10.11959/j.issn.1000-0801.2016057

2015-06-13；

2016-01-07

國家自然科學基金資助項目（No.61262049）

黃志超（1990-），女，南昌大學碩士生，主要研究方向為數據挖掘、知識工程、軟件工程等。

陶俊才（1956-），男，南昌大學教授，主要研究方向為軟件工程、網絡計算機與系統(tǒng)集成、模式識別、知識管理與決策支持。

高勝保（1966-），男，中國電信股份有限公司江西分公司網絡運營支撐事業(yè)部副主任，主要研究方向為通信網絡運營、網絡信息安全、云及大數據分析等。