黃志超，陶俊才，高勝保

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

研究與開發(fā)

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

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

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

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

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

1 引言

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

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

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

2 原始模型構(gòu)建

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

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

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

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

2.2 模型的分類

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

3 種子客戶挖掘算法

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

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

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

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

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

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

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

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

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

方法類似于α。

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

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

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

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

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

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

其中，yi為客戶i歸一化的結(jié)果，Mi為客戶i的評分，Min為客戶評分的最低分?jǐn)?shù)，Max為客戶評分的最高分?jǐn)?shù)，n為客戶的個數(shù)。

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

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

（1）基本思路

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

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

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

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

（2）算法過程

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

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

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

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

（3）算法實現(xiàn)

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

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

步驟1計算Users中每個節(jié)點出現(xiàn)的次數(shù)即C=［C1，C2，…，Cn］，其中n表示Users個數(shù)；

步驟2初始化結(jié)果集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中出現(xiàn)Users［i］-＞Children［j］的次數(shù)

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算法結(jié)束，輸出結(jié)果。

上述步驟中，步驟1和步驟2的時間復(fù)雜度為O（n），其中，n為二次優(yōu)化模型中的節(jié)點數(shù)；步驟3的時間復(fù)雜度為O（n2m2），其中，m表示二次優(yōu)化模型中父子節(jié)點的子節(jié)點數(shù)，由于一般m遠(yuǎn)遠(yuǎn)小于n，所以該階段總的時間復(fù)雜度為O（n2）。

4 實證分析

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

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

·對3類短信分別構(gòu)建樹型轉(zhuǎn)發(fā)模型。

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

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

表1 客戶短信數(shù)據(jù)格式

表2 客戶評分

·進(jìn)一步應(yīng)用親密群概念進(jìn)行挖掘，得到的種子客戶見表3（γ取值0.65）。

由表2和表3可知，從1萬條手機短信中挖掘出的種子客戶數(shù)為40名。為進(jìn)一步分析閾值α、β、γ對挖掘結(jié)果的影響，另外選取2萬條短信與上述結(jié)果進(jìn)行比較，相關(guān)情況如圖4、圖5所示。圖4為設(shè)定β=0.7、γ=0.65，種子客戶數(shù)隨α變化的結(jié)果，當(dāng)α≥2時，曲線趨于平緩；圖5為設(shè)定α=3、γ=0.65，種子客戶數(shù)隨β變化的結(jié)果，當(dāng)β≥0.7時，曲線趨于平緩；這些變化趨勢與實際情況完全吻合。因此，可以選擇α=2、β=0.7作為挖掘種子客戶時的參考值，必要時可以根據(jù)需要調(diào)整。

5 結(jié)束語

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

表3 種子客戶

圖4 種子客戶數(shù)隨α的變化關(guān)系

圖5 種子客戶數(shù)隨β的變化關(guān)系

［1］李永立，吳沖，胡冬冬，等.基于樹型網(wǎng)絡(luò)分析的短信種子客戶挖掘模型及其實證分析［J］.中國管理科學(xué)，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.機器學(xué)習(xí)實戰(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］.廣州：華南理工大學(xué)，2013：1-52.LI B C.The research of SMS seed users’identification［D］.Guangzhou：South China University of Technology，2013：1-52.

［4］陸旭.文本挖掘中若干關(guān)鍵問題研究［M］.合肥：中國科學(xué)技術(shù)大學(xué)出版社，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的文本分類特征選擇與分類算法的研究與改進(jìn)［D］.廈門：廈門大學(xué)，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］王博.文本分類中特征選擇技術(shù)的研究［D］.長沙：國防科學(xué)技術(shù)大學(xué)，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.數(shù)據(jù)挖掘概念與技術(shù)第三版［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

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

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

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

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