一种基于通信网络数据分析的关键人物挖掘方法及系统

摘要

本发明提出一种基于通信网络数据分析的关键人物挖掘方法及系统，该方法包括步骤1，获取通信记录并进行预处理，根据预处理后的通信记录构建有向加权通信网络，根据所述有向加权通信网络构建有权邻接矩阵，并计算权威值与枢纽值；步骤2，根据所述权威值，及所述有向加权通信网络中两节点链接边的权重，计算新权威值与新枢纽值；步骤3，设置异常特征参数α，并根据所述新权威值与所述新枢纽值，计算最终权威值，对所述最终权威值进行最大‑最小规范化，获得关键人物。本发明能够快速有效的获取通信网络中关键人物的信息，缩短关键人物发现时间，减少工作量。

说明书

技术领域

本发明涉及通信网络的数据分析领域，特别涉及一种基于通信网络数据分析的关键人物挖掘方法及系统。

背景技术

手机在我们当今社会生活中无疑是一种必不可少的日常通讯工具，使用手机这种日常通讯工具在进行通话或短信等通信行为活动中，会产生一系列的详细通信单数据，根据这种通信单，可以构建出全面详细的电话通信网络。

随着各行业业务数据量的井喷式增长，数据挖掘这门学科受到学术界和工业界的广泛关注。数据挖掘，一般是指在海量数据基础上，基于计算科学、统计学、机器学习、信息检索、数据仓库、模式识别等相关领域技术以及结合业务领域专家知识构建高效可用的数据挖掘模型，从已知数据中挖掘未知且极具价值的知识信息，适用于多种领域。

通信网络数据分析，是根据电话通信单构建出一种基于通信的社交网络基础上，使用或利用计算科学、统计学、社会心理学等多学科的融合理论和方法，为理解人类各种社交关系的形成、行为特点分析以及信息传播的规律等提供的分析方法，现有在社交网络拓扑中分析网络节点重要程度的主要技术有:

现有技术一：Hits算法，该算法出自于Kleinberg,Jon(1999)."Authoritativesources in a hyperlinked environment".Journal of the ACM.46(5):604–632.doi:10.1145/324133.324140.最早应用在信息检索领域，用于分析网页的重要程度，该算法是Web结构挖掘中最具权威性和使用最广泛的算法。Hits算法利用Web的链接结构进行挖掘，其核心思想是建立在页面链接关系的基础上，对链接结构的进行改进。Hits算法通过两个评价权值——权威值(Authority)和枢纽值(Hub)来对网页质量进行评估，其基本思想是利用页面之间的引用链接来挖掘隐含在其中的有用信息(如权威性)，具有计算简单且效率高的特点，HITS算法认为对每一个网页应该将其内容权威值(Authority)和枢纽值(Hub)分开来考虑，在对网页内容权威值(Authority)做出评价的基础上再对页面的枢纽值(Hub)进行评价，然后给出该页面的综合评价。权威值(Authority)与网页自身直接提供内容信息的质量相关，被越多网页所引用的网页，其权威值(Authority)越高；枢纽值(Hub)与网页提供的超链接页面的质量相关，引用越多高质量页面的网页，其枢纽值(Hub)越高。该算法用于社交网络拓扑中可以分别考虑权威值(Authority)和枢纽值(Hub)来计算该网络中的网络节点的重要性。

现有技术二：PageRank是Google提出的专有的算法，用于衡量特定网页相对于搜索引擎索引中的其他网页而言的重要程度。同样最早用于信息检索领域，计算页面的“得票数”，一个页面的“得票数”由所有链向它的页面的重要性来决定，到一个页面的链接相当于对该页投一票。一个页面的PageRank是由所有链向它的页面(“链入页面”)的重要性经过递归算法得到的。一个有较多链入页面的网页会有较高的等级，相反如果一个页面没有任何链入页面，那么它没有等级。该算法用于社交网络拓扑中时往往不考虑网络连接的有向性，单纯考虑网络中用户连接数去计算该网络中的网络节点的重要性。

社会生活中存在着各种各样需要对人物重要程度进行评价、以及关键人物发现等的应用场景。例如警察针对犯罪侦查过程中，，疑犯的锁定和排除是警察破案的关键。传统方法针对具有异常通信特征的关键人物发现中往往综合社会行为学、心理学、现代刑侦技术手段等。现有针对异常通信特征的关键人物发现技术主要有：

现有技术三，人工排查方法。这种人工排查方法，效果显著，但单纯靠人工去排查锁定，效率低，周期长，而且存在遗漏的可能。

现有技术的缺陷：通信网络是根据用户电话呼入呼出构建的一种有向图，不考虑的方向性现有技术二的PageRank方法去计算难以满足需求。而现有技术一的Hits算法尽管综合的考虑了有向性，计算权威值(Authority)和枢纽值(Hub)，却不能满足带权重的社交网络图，更不能满足我们应用到具有异常通信特征的关键人物挖掘场景。而现有技术三，人工排查的方法，尽管有效，但是挖掘周期长，甚至可能出现遗漏。

发明内容

针对现有技术的不足，本发明提出一种基于通信网络数据分析的关键人物挖掘方法及系统。

本发明提出一种基于通信网络数据分析的关键人物挖掘方法，包括：

步骤1，获取通信记录并进行预处理，根据预处理后的通信记录构建有向加权通信网络，根据所述有向加权通信网络构建有权邻接矩阵，并根据通信关系计算权威值与枢纽值；

步骤2，根据所述权威值，及所述有向加权通信网络中两节点链接边的权重，计算新权威值与新枢纽值；

步骤3，设置异常特征参数α，并根据所述新权威值与所述新枢纽值，计算最终权威值，对所述最终权威值进行最大-最小规范化，获得关键人物。

所述步骤1中预处理包括删除通信记录中的重复数据、非常规号码，将缺省值进行补全。

所述步骤1中构建有向加权网络包括根据通信网络中节点的“主叫”、“被叫”的频率构建有向加权通信网络。

所述步骤2中计算新权威值与新枢纽值的公式为：

Hub(u)＝∑(Authority(v)*edgePower/Σout_edgePower(u))

Authority(u)＝Σ(Hub(v)*edgePower/Σin_edgePower(u))

其中Hub(u)为枢纽值，Authority(v)为权威值，edgePower为节点u和节点v的链接边权重，Σout_edgePower(u)为节点u的出度的总和，Σin_edgePower(u)为节点u的入度的总和。

删除链接边权重小于预设阈值的边。

本发明还提出一种基于通信网络数据分析的关键人物挖掘系统，包括：

计算权威值与枢纽值模块，用于获取通信记录并进行预处理，根据预处理后的通信记录构建有向加权通信网络，根据所述有向加权通信网络构建有权邻接矩阵，并根据通信关系计算权威值与枢纽值；

计算新权威值与新枢纽值模块，用于根据所述权威值，及所述有向加权通信网络中两节点链接边的权重，计算新权威值与新枢纽值；

获得关键人物模块，用于设置异常特征参数α，并根据所述新权威值与所述新枢纽值，计算最终权威值，对所述最终权威值进行最大-最小规范化，获得关键人物。

所述计算权威值与枢纽值模块中预处理包括删除通信记录中的重复数据、非常规号码，将缺省值进行补全。

所述计算权威值与枢纽值模块中构建有向加权网络包括根据通信网络中节点的“主叫”、“被叫”的频率构建有向加权通信网络。

所述计算新权威值与新枢纽值模块中计算新权威值与新枢纽值的公式为：

Hub(u)＝∑(Authority(v)*edgePower/∑out_edgePower(u))

Authority(u)＝Σ(Hub(v)*edgePower/Σin_edgePower(u))

其中Hub(u)为枢纽值，Authority(v)为权威值，edgePower为节点u和节点v的链接边权重，Σout_edgePower(u)为节点u的出度的总和，Σin_edgePower(u)为节点u的入度的总和。

删除链接边权重小于预设阈值的边。

由以上方案可知，本发明的优点在于：

本发明实验采用一起真实案件的通信网络挖掘结果显示，排除10086、10010等非常规号码，最终真实有效的电话号码总共有1015个，经本发明的计算公式模型得出权威值(Authority)从大到小排序得结果的top 100中包含了经警察验证全部的疑犯使用的电话号码，其中top 10中包含5个疑犯使用电话号码。

附图说明

图1为具体实施方案流程图；

图2为有向无权图；

图3为有向加权图；

图4为包含准确率pred、召回率recall、F1值得测试结果图。

其中附图标记为：

步骤S01-S15。

具体实施方式

以下为本发明的实施例，如图1所示，具体实施方案为：

S01、将通信记录导入数据库中。通信记录中包含许多字段，取与本实施例相关的字段导入数据库，与本实施例相关字段有：id、src、IMEI、IMSI、dest、calltype、tmbetween、startdt，其中src是用于所导入数据库的通信记录的源号码；IMEI是存储是由15位数字组成的"电子串号"，它与每台移动电话机一一对应，而且该码是全世界唯一的国际移动设备身份码；IMSI是储存在SIM卡中用于存储区别移动用户的标志，可用于区别移动用户的有效信息的国际移动用户识别码；dest是存储与src电话号有过联系的目的电话号码；calltype用于存储src与dest的呼叫类型，主要值有‘主叫’、‘被叫’、‘短信发送’、‘短信接收’等通信数据类型；tmbetween字段用于存储src和dest的两个电话号码间通话的时长；startdt是存储src与dest通话开始时间，或者是短信发送时间等。

S02、数据预处理。数据中存在许多缺省值、重复数据、非常规号码，为避免这类数据对最终结果造成严重的影响需对数据进行预处理。步骤如下：

取呼叫类型calltype为‘主叫’、‘被叫’两种类型，去掉重复的数据，例如某src主叫dest的记录A中与另一条记录B，其中记录A的dest号码为记录B的src，而记录A的src号码为记录B的dest，呼叫类型calltype却为被叫，且startdt字段中的值是一样的，为避免重复处理类似数据，将此类重复记录去掉。

缺省值处理，采取有一一对应关系的进行补全处理。例如数据中有字段src值为NULL的数据，采取依照IMSI与src一一对应关系进行补全。对于没有一一对应关系的数据采取舍去的处理方式。

对于如10086、10010等非常规号码，为避免非常规号码导致枢纽值(Hub)和权威值(Authority)计算出现错误，将该类号码的通话记录去掉。

S03、将S02中预处理好的数据用于构建通信网络的有向图。例如，号码A呼叫过号码B，或者说号码A给号码B打过电话，就将号码A与号码B连接方向由A到B。最终构建的有向图如图2所示形式，图2为号码A打给号码B和号码D，号码B和号码C打给号码A。

S04、根据S03方法构建好的有向图，构建与之相对应的表示有向图顶点邻接关系的邻接矩阵，图2中所示例子构建出连接矩阵形式为如下所示，横向表示点的出度，纵向表示点的入度。

S05、根据S02中处理好的数据及S03中的方法构建一种有向加权通信网络。本发明主要是根据通信网络中的节点‘主叫’、‘被叫’的频率构建有向加权通信网络图如图3所示。图3中E号码打给F号码2次打给G号码2次，F号码打给G号码2次，G号码打给E号码1次。

S06、根据S05的有向加权通信网络及S04的构建方法，构建有权邻接矩阵。考虑到号码间的通信频率的关键因素，不能单纯的通过考虑两号码是否有过练习计算权威值(Authority)，固依照构建的有向加权通信网络构建有权邻接矩阵。如按照图3构建有权邻接矩阵如下：

S07、通过S05、S06构建有向加权通信网络及相关的邻接矩阵的基础上进行权威值(Authority)计算。其中权威值(Authority)计算主要参考由康奈尔大学(CornellUniversity)的Jon Kleinberg博士于1997年首先提出的Hits算法。

Hits算法应用于通信网络这一场景恰好可以反映主叫被叫关系，也就是图2中节点的入度出度关系，主叫越多的权威值(Authority)大的号码其枢纽值(Hub)也会很大，而被叫越多的枢纽值(Hub)大的号码的权威值(Authority)也会变得很大，反复迭代最终衡量号码的重要程度。

该算法的主要计算公式为:

Hub(u)＝ΣAuthority(v)

其中v点是u在有向图中出度大于0的点。

Authority(u)＝ΣHub(v)

其中v点是u在有向图中入度大于0的点。

S08、将枢纽值(Hub)和权威值(Authority)的计算公式中引入两号码链接边的权重，公式如下：

Hub(u)＝Σ(Authority(v)*edgePower/∑out_edgePower(u))

Authority(u)＝∑(Hub(v)*edgePower/∑in_edgePower(u))

其中edgePower为节点u和节点v的链接边的权重，Σout_edgePower(u)为节点u的出度的总和，∑in_edgePower(u)为节点u的入度的总和，除以这样的总和是为了标准化各边的权重。

S09、在S08加入边的权重的计算中，往往会出现某些号码与某些权威值(Authority)和枢纽值(Hub)较大的号码只联系了一次而与某些权威值(Authority)和枢纽值(Hub)较低的值联系比较密切，最终结果权威值(Authority)和枢纽值(Hub)却很大这样的误判，去掉两号联系的次数低于2的边。这样的做法是依照通信专家经验两人联系‘有来有回’超过3次算比较熟悉的人，‘有来有回’是指如图2中A给B打过电话，B给A也打过电话的状态，这里考虑避免出现某些关键人物仅和其中一些特定的人少量联系‘只去不回’、‘只接不去’，‘只去不回’是指如图2中A给C打过电话而C给A没打过电话的状态，‘只接不去’是指如图2中C只接到A的电话而C没有给A回过电话的状态，却通知一些重要事情或者可能是某些重要信号，这里没有完全按照通信专家的经验去掉‘有来有回’总数低于3次的边，而是去掉两个号码联系，‘只去不回’或者是‘只接不去’的次数低于一定频率的边。

S10、从数据的观点出发，找出具备异常特征的号码。发明人在实验过程中发现一类特殊号码，这类号码在通话记录中的IMEI多次出现替换的现象。IMEI是用于存储是由15位数字组成的"电子串号"，该码是全世界唯一的国际移动设备身份码，除双卡双待的手机会出现两个IMEI，绝大多数手机都只具备唯一的IMEI。固依照经验考虑，普通公民这种行为出现频繁更换手机的几率比较小，找出频繁更换手机IMEI号的异常手机号。若两个号码u和v联系中都出现该行为特征，则将这类号码通话与正常通话做明显区分。固将两个联系号码同时出现这类特征的联系在计算的枢纽值(Hub)和权威值(Authority)中乘上一个很大的参数α(范围2-500)，出现该异常特征的参数α定为一个较大的参数，而普通联系参数定为1。

S11、根据上述步骤构建在通信网络中用于挖掘关键人物的数据分析算法公式。用于计算枢纽值(Hub)和权威值(Authority)的计算公式如下所示：

Hub(u)＝Σ(Authority(v)*edgePower*α/∑out_edgePower(u))

Authority(u)＝∑(Hub(v)*edgePower*α/Σin_edgePower(u))

S12、按照S11中构建的公式进行计算。具体步骤如下：

将所有通信网络中的节点也就是电话号码的枢纽值(Hub)和权威值(Authority)进行初始化，其中枢纽值(Hub)初始化为该电话号码主叫的总次数，而权威值(Authority)则初始化为该电话号码被叫的总次数。

初始化后将所有节点按照构建的通信网络的连接关系和计算公式，反复迭代，计算出最终的枢纽值(Hub)和权威值(Authority)。

S13、权威值(Authority)的计算是综合枢纽值(Hub)计算得出，将权威值(Authority)进行最大-最小规范化。最大-最小规范化的公式如下：

其中new_v是规范后的结果，old_v是规范化前的数据，old_min和old_max是规范化前的最小和最大值，new_max和new_min是新的映射区间。

S14、按照最大-最小规范化后的权威值(Authority)依照从大到小顺序进行排序，最终得出一个关于通信网络数据分析的关键人物挖掘结果。

S15、实验结果评价：主要评价指标有准确率pred、召回率recall、F1值，取权威值(Authority)的排序结果中topN，共N个，其中经警察验证的疑犯号码为accute准确率pred公式如下：

召回率recall公式中realSum为经警察验证的所有疑犯号码总数，召回率recall公式如下：

根据pred和recall可以计算F1值，F1值得计算公式如下：

根据上述三个公式依次取top10、top40、top70、top100计算准确率pred、召回率recall、F1值的计算图如下图4所示，计算结果表如下所示。

本发明还提出一种基于通信网络数据分析的关键人物挖掘系统，包括：

计算权威值与枢纽值模块，用于获取通信记录并进行预处理，根据预处理后的通信记录构建有向加权通信网络，根据所述有向加权通信网络构建有权邻接矩阵，并根据通信关系计算权威值与枢纽值；

计算新权威值与新枢纽值模块，用于根据所述权威值，及所述有向加权通信网络中两节点链接边的权重，计算新权威值与新枢纽值；

获得关键人物模块，用于设置异常特征参数α，并根据所述新权威值与所述新枢纽值，计算最终权威值，对所述最终权威值进行最大-最小规范化，获得关键人物。

所述计算权威值与枢纽值模块中预处理包括删除通信记录中的重复数据、非常规号码，将缺省值进行补全。

所述计算权威值与枢纽值模块中构建有向加权网络包括根据通信网络中节点的“主叫”、“被叫”的频率构建有向加权通信网络。

所述计算新权威值与新枢纽值模块中计算新权威值与新枢纽值的公式为：

Hub(u)＝∑(Authority(v)*edgePower/∑out_edgePower(u))

Authority(u)＝Σ(Hub(v)*edgePower/Σin_edgePower(u))

其中Hub(u)为枢纽值，Authority(v)为权威值，edgePower为节点u和节点v的链接边权重，Σout_edgePower(u)为节点u的出度的总和，∑in_edgePower(u)为节点u的入度的总和。

删除链接边权重小于预设阈值的边。