（计算机应用技术专业论文）大规模交往数据集的凝聚子群分析研究.pdf

中文摘要 随着近年来通信技术的蓬勃发展，通信领域内的各个企业都积累了大量的客 户交往数据集。客户交往数据集是一个信息量非常庞大的数据资源，如果能够采 用有效的方法和技术对其进行凝聚子群分析，我们将会从中获得许多有价值的规 律和知识。 本文提出了一种全新的进行交往数据集凝聚子群分析的方法一社会网络分 析方法，它从社会学的角度，对由用户和用户触的通信关系所构成的交往网络进 行了分析，从而在企业决策支持和犯罪侦查等多种领域提供服务。 社会网络分析方法是一种量化的社会学分柝方法。它将社会行动者映射为图 的节点，社会行动者之间的关系映射为图中的边，然后利用图论的相关知识来解 决社会网络的问题。 本文设计了一个基于社会网络分析方法的大规模交往数据集凝聚子群分析模 型，并对模型中的数据预处理、基本数据结构的定义、数据接口定义、关键图算 法的实现、社会网络分析中心性指标集的计算、凝聚子群分析以及数据可视化等 各个功能模块提出了具体的解决方案，并完成了其中部分模块的编码实现以及实 验验证。 关键词：交往数据集；社会网络分析；图；凝聚子群 分类号：t p l 8 2 r e c e n ty e a r s ，e v e r yc o r p o r a t i o ni nt h ec o m m u n i c a t i o nr e a l mh a sc o l l e c t e dal a r g e n u m b e ro fc o m m u n i c a t i o nd a t a s e to fc o n s u m e r sa l o n gw i t ht h ed e v e l o p m e n to f c o m m u n i c a t i o nt e c h n o l o g y n cc o m m u n i c a t i o nd a t a s e ti sav e r yv a l u a b l er e s o u r c e w h i c hc o n t a i n sm u c hu s e f u li n f o r m a t i o n i fw ec a nu s ee f f e c t i v et e c h n i q u e sa n d m e t h o d st oa n a l y z et h ed a t a s e t , w ew i l lg e tm u c hv a l u a b l ek n o w l e d g e t h et h e s i sa d o p t sa na b s o l u t e l yn e wm e t h o d s o c i a ln e t w o r ka n a l y s i sm e t h o d t 0 a n a l y z e t h ec o m m u n i c a t i o nd a t a s e lw el l s ct h eu e wm e t h o dt o a n a l y z e t h e c o m m u n i c a t i o nn e t w o r kc o m p o s e do fc o n s u m e r sa n dc o m m u n i c a t i o nr e l a t i o n s h i p s b e t w e e nt h e mf r o mt h ep o i n to fv i e wo fs o c i o l o g y a n dt h i sw i l lp r o v i d em u c h a s s i s t a n c ei nm a n yf i e l d ss u c ha sd e c i s i o ns u p p o r to f e n t e r p r i s ea n dc r i m ei n v e s t i g a t i o n s o c i a ln e t w o r ka n a l y s i sm e t h o di saq u a n t i t a t i v es o c i o l o g ym e t h o d i tt a k e sas o c i a l a c t o ra snv e r t e xo fag r a p h , a n dt a k e st h er e l a t i o n s h i pb e t w e e nt w oa c t o r sa sa ne d g eo f ag r a ma n dt h e nu s ct h ea l g o r i t h mo fg r a p ht h e o r yt or e s o l v et h ep m b l e m so fs o c i a l n e t w o r k t h et h e s i s d e s i g n s ac o h e s i v e s u b g r o u pa n a l y s i s m o d e lo f l a r g e - s c a l e c o m m u n i c a t i o nd a t a s e tb a s e do ns o c i a ln e t w o r ka n a l y s i sm e t h o d a n di tf i n i s h e sm a n y s u b s t a n t i a lr e s o l u t i o n st ot h em o d u l e so fd a t ap f e u e a t m e n t ，d e f i n eo fb a s i cd a t a s t r u c t u r e s , d e f i n eo fd a t ai n t e r f a c e ，i m p l e m e n to fp i v o t a lg r a p ha l g o r i t h m ，c a l c u l a t i o no f s o c i a ln e t w o r ka n a l y s i sc e n t r a l i t ym e a s u r e s , c o h e s i v es u b g r o u pa n a l y s i sa n dd a t a v i s u a l i z a t i o n m a n yo ft h em o d u l e sh a v eb e e ni m p l e m e n t e db yc o d i n ga n dv a l i d a t e db y e x p e r i m e n t i n g k e y w o r d s ：c o m m u n i c a t i o nd a t a s e t ；s o c i a ln e t w o r ka n a l y s i s ；g r a p h ；c o h e s i v e s u b g r o u p ( = i a s s n o ：1 下1 8 2 致谢 本论文的工作是在我的导师黄厚宽教授的悉心指导下完成的，黄教授严谨的 治学态度和科学的工作方法给了我极大的帮助和影响。在此衷心感谢黄厚宽老师 三年来对我的关心和指导。 林友芳副教授悉心指导我们完成了实验室的科研工作，在学习上和生活上都 给予了我很大的关心和帮助，在此向林友芳老师表示衷心的谢意。 在实验室工作及撰写论文期问，傅士光、徐娟娟、赵国斌、尹盛、刘俊彬等 同学对我论文中的算法实现工作给予傲了大量工作，在此向他们表达我的感激之 情。 另外也感谢我的家人，他们的理解和支持使我能够在学校专心完成我的学业 1 1 研究背景与目的 1 绪论 随着近年来通信技术蓬勃发展，通信领域内的各企业都积累了大量的客户交 往数据集。这些电子化的交往数据详细地记录了客户与客户之间的通信次数、通 信时间、通信时段、通信类型和通信费用等诸多信息，形成一个十分庞大的客户 交往资源库 如何将这些客户交往数据有效地利用起来，为企业的市场经营、客户关系管 理、财务管理以及欠费与防欺诈行为分析等各个业务领域提供更好的决策支持， 已成为各通信企业近年来最为关切的问题之一于是，很多企业都纷纷建立了自 己的大型数据仓库，并利用日益进步的数据挖掘技术对自己的业务数据进行分析 和挖掘，从中获取一些有价值的信息，服务于企业的战略决策。 另外，从犯罪侦查的角度出发，也可以利用这些详细的客户交往数据，结合 社会群体学和犯罪学的知识，经过一系列的人为干预和计算机分析之后，得到一 些关于黑社会组织或者犯罪团伙的信息，用于辅助犯罪侦查。 在当前所进行的一些交往数据集分析研究课题之中，大多采用传统的数据仓 库和数据挖掘技术在企业内部构建了一些分析模型来进行研究闱本文将采用社会 网络分析的方法来研究客户之问的关系，并按照不同的属性特征将客户划分为不 同规模和不同类型的凝聚子群，从而为通信企业的战略决策和公安部门的犯罪侦 查提供更好的帮助。 社会网络分析是人文社科领域内一门独立的学科，在国内外数十年的研究过 程中已经形成了比较完整的学科体系，也得到了广泛的应用。但是，将社会网络 分析方法应用于大规模交往数据集的凝聚子群分析，与先进的计算机技术结合起 来，则完全是一次全新的探索。 总体来说，本文拟达到以下研究目的： 1 、以通信企业内部积累的大规模客户交往数据集以及它所提供的数据库或数 据仓库平台为基础，结合一些具体的应用场景、建立一个基于社会网络分析方法 的大规模交往数据集凝聚子群分析模型，并完成分析模型结构设计、数据预处理、 基本数据结构定义、基本图论算法的实现、社会网络分析中心性指标集算法的实 现以及数据可视化等研究任务。 2 、根据所设计的模型搭建实验平台，并利用问卷调查或者模拟生成的大规模 客户交往数据集进行实验，验证模型的正确性，并总结研究成果，得出研究结论。 1 2 研究方法与步骤 由于交往数据集的凝聚子群分析具有理论与实际联系十分紧密的特点，而通 信行业所包含的范围又非常广泛( 比如电信、移动通信、电子邮件、网上聊天等等) ， 所以本文将以电信通话数据为例对交往数据集的凝聚子群分析进行研究，几种研 究方法如下： 1 、背景分析 对电信通话业务展开调研，弄清电信通话数据的逻辑结构、存储体系和访问 方式等，为后续研究打下基础 2 、理论研究 对于研究过程中所涉及的图论、社会网络分析和数据挖掘等学科的知识进行 深入的学习。 3 、技术借鉴 借鉴一些成熟的大规模数据处理技术、数据挖掘技术和社会网络分析方法， 将这些成熟的技术很好地应用于交往数据集的凝聚子群分析之中。 4 、实验验证 根据电信通话数据的逻辑结构，通过问卷调查与模拟生成两种方式，产生大 规模的电信通话数据集，然后进行反复的实验，验证大规模交往数据集凝聚子群 分析模型的正确性，并得出研究结论。 对于本文的研究内容，我们将采取以下三个步骤来进行研究： 1 、对电信通话业务背景进行调研，同时学习社会网络分析和图论算法等理论 知识，对本文研究内容的应用场景进行分析，并完成数据导入、结构优化、数据 加密、去除噪音、粗粒度化和建立视图等数据预处理工作 2 、进行大规模交往数据集凝聚子群分析模型的系统结构设计，完成其中的基 本数据结构定义、数据接口封装、关键图算法、社会网络分析中心性指标集的计 算以及凝聚子群分析方法等功能模块的设计与实现，并根据此模型搭建实验平台。 3 、利用问卷调查或者模拟生成的大规模电信通话数据集在实验平台上进行反 复的实验，并形成反馈信息，然后对模型进行反复的修正，直至得到一个比较理 想的研究结果。 1 3 论文组织与安排 本文一共分为6 章 第1 章介绍了本文的研究背景、研究目的、研究方法与研究流程以及本文的 2 组织结构 第2 章介绍了与本文研究内容紧密相关的理论知识，包括图论、社会网络分 析的概念，社会网络分析中心性指标集以及凝聚子群分析的概念等。 第3 章对本文研究内容的应用场景进行了简要的分析。 第4 章着重对大规模交往数据集凝聚子群分析模型进行结构设计，数据预处 理，基本数据结构的定义、关键图论算法的实现、社会网络分析中心性指标集算 法的实现、凝聚予群分析方法的设计与实现以及数据可视化等研究工作。 第5 章将对本文提出的两种凝聚子群分析方法进行实验验证。 第6 章将对本文的研究结论进行总结，分析目前所存在的缺陷，提出后续研 究的内容和方向 3 2 相关理论知识 本文将采用社会网络分析方法进行用户交往数据集的凝聚子群分析，而社会 网络分析又是以图作为最基本的形式化表达方式来表示社会网络的，因此图论的 基本概念和算法是本文研究过程中最重要的理论基础。 以“关系”作为基本研究对象的社会网络分析( s 0 c i a ln e t w o r ka n a l y s i s ) ，从量 化的角度来分析社会关系的内在结构特征，因此它不同于基于传统统计学意义上 的社会学i l j 。 本章将对研究过程中所涉及的图论和社会网络分析学科的一些基本概念进行 简要的阐述。 2 1 基本概念 2 1 ，1 图的基本概念 直观地说，给定多个点，把其中的一些点用曲线或者直线段连接起来，不考 虑点的位置与连线的长短，这样所形成的点与线的关系结构就是一个图。即由点 集合n 和点与点之台j 的连线集合e 所组成的集合对( n ，e ) 苇5 ：为图，用g ( n ，e ) 来表 示 n 中的元素称为节点，e 中的元素称为边 若图中所有的边都具有方向，即区分它的起始节点与终止节点，则该图为有 向图：若图中所有的边都没有方向，则该图为无向图；若部分边有方向，另一部 分边没有方向，则该图为混合图。 ， 若图中任意两个节点之间都存在边相连，则该图为完全图。 若图中任意两个节点之间的边只有存在于不存在之分，则该图为二值图。若 图中任意两个节点之间的边都赋了权值，则该图为赋权图。 若图中任意两个节点都可以经过一系列的边互相到达，则该图为连通图。 非连通图中的最大连通子图称之为组件。 从图中取出一个点集，再加上这些点之间存在的关系，构成一个新的子图， 这种生成子图的方式称为点生子图。 从图中耿出一个边集，再加上与这些边相连的节点，构成一个新的子图，这 种生成子图的方式称为线生子图阁 4 2 1 2 社会网络分析的基本概念 社会网络是指社会行动者( s o c i a la c t o r ) 及其之间关系的集合。 社会行动者可以是个体或者集体性的社会单位，比如说个人、家庭、组织、 村落、学校、社区、城市、国家等等。 社会网络这个概念强调行动者与其他行动者有或多或少的关系。研究人员建 立这些关系的分析模型，研究这些关系给社会网络整体结构或者网络内部的个体 带来的影响，这就是社会网络分析( s o c i a ln e t w o r k a n a l y s i s ) 社会网络分析用于描述和测量社会行动者之间的关系以及通过这些关系而流 动的各种有形或无形的东西，如信息、资源等 社会网络分析是社会科学中的一个独特视角，它建立在一个重要的假设基础 之上，即在互动的社会个体对象之间存在着非常重要的关系社会网络理论、模 型以及应用的基础都是关系数据，关系是社会网络分析理论的基础。随着社会网 络研究的深入，学者们逐渐在以下几个观点上达成共识： 社会行动者及其之间的行动是相互依赖的，而不是独立的、自主性的单位。 行动者之间的关系是资源( 物质的或者非物质的) 传递或者流动的“渠道” 个体网络模型认为，网络结构环境可以为个体的行动提供机会，也可以限 制其行动。 网络模型把结构( 社会结构、经济结构等) 概念化为各个行动者之间的关系模 型。 在社会网络的形式化表达中，用一个图来表示一个社会网络，图中的一个节 点表示一个社会行动者，一条边表示一对社会行动者之问的关系。 下面介绍社会网络分析中几个最基本的概念： l 、点的度数 与某个节点相邻的那些节点称为该点的“邻点”( n e i g h b o r h o o d ) ，一个点n i 的 邻点的个数称为该点的“度数”( n o d a ld e g r e e ) ，记作d ( n i ) ，也叫“关联度”( d e g r e e o f c o n n e c t i o n ) 这样，一个点的度数就是对其邻点多少的测量。实际上，一个点的 度数也就是与该点相连的线的条数。如果两个点由一条线相连，称这两个点之间 为“相邻的”( a d j a c e n t ) 。相邻是对两个行动者直接相关的图论表达。如果一个点 的度数为o ，称之为“孤立点”( i s o l a t e ) 。度数这个概念在对有向图进行分析时必 须考察线的方向。因此，一点的“度数”包括两类，分别称为“点入度”( i n d e g r e e ) 和“点出度”( o u t d e g r e e ) 一个点的点入度指的是直接指向该点的点的总数；点 出度指的是该点所直接指向的点的总数1 2 】 2 、线路、迹、途径 5 “线路”( w a 是由许多点和线首尾相接所构成的有序序列，这个序列起始于 一点并且终止于一点，记作w 。在线路中，点和线都允许重复。“线路的长度”( t h e l e n g t ho f aw a l k ) 指线路中线的条数。 “迹”( t r a i l ) 是特殊的线路，如果在一个线路中没有重复出现的线，则这样的 线路叫做迹。 “途径”( p a t h ) 也是一种特殊的线路，如果在一个线路中既没有重复出现的线， 也没有重复出现的点，则这样的线路叫做途径“途径的长度”( t h ei e n g t ho f ap a t 指构成该途径的线的条数【2 l 。 3 、测地线、距离、直径 在给定的两点之间可能存在长短不一的多条途径两点之间的长度最短的途 径叫做。测地线”如果两点之间存在多条最短途径，则这两个点之间存在多条测 地线。 两点之问的测地线的长度叫做测地线距离，简称为“距离”( d i s t a n c e ) 。也就 是说，两点之间的距离是指连接这两点的最短途径f s h o n c s tp a t h ) 的长度。我们把点 n i 和n i 之间的距离标记为d ( i ，j ) ，如果某两点之间不存在途径，刘称这两点之白j 的 距离是无限的。 一个图中一般有多条测地线，其长度也是不一样的我们把图中最长测地线 的长度叫做该图的“直径”( d i r e c t ) 。如果一个图是连通图，那么其直径可以测 定；如果不是连通图，那么其中有的点对之间的距离就是无限的，在这种情况下， 图的直径也是无限的i z i 4 、图的密度 “密度”( d e n s i t y ) 这个概念是为了汇总图中线的总分布情况。以便测量该图与 完全图的差距有多大。规模一定的点之间的连线越多，该图的密度就越大。具体 地说，密度是指一个图中各个点之间相关联的紧密程度。 密度的形式化定义用图中实际拥有的线数与最多可能存在的线数之比来表 示。假设一个图的实际线数为m ，节点数日，则对于无向图而言，其密度为2 m n ( n 1 ) ， 对于有向图而言，其密度为m n ( n - 1 p 。 2 2 社会网络分析中心性指标集 中心性是社会网络分析中对“权力”( p o w e 0 0 q - 个量化分析指标。所谓权力， 在社会学中，是指社会行动者之间存在或者潜在的互动模式，( i n f l u e n c e ) 和支配( d o m i i l a t i o n ) 两个维度。为了对权力进行形式化定义和量化分析，人们在社 会网络分析方法中引入了“中心性”这一指标集，中心性又包含中心度和中心势 6 两个方面，其中中心度是用来度量单个节点的中心性，而中心势则用来度量整个 图的中心性趋势。 2 2 1 点度中心性 点度中心性是一个以图中节点的度数为基础来量化中心性的指标。 1 、点度中心度 “点度中心度”( d e g r e ec e n t r a l i t y ) 是一个最简单、最直观的指标，它描述的是 一个节点位于图中“核心”位置的程度，刻画了该点与图中其他点发展交往关系 的能力 点度中心度又分为绝对点度中心度和相对点度中心度，点n i 绝对点度中心度 ( 用c 表示) 就是该点的度数，即： 一d “) 点n i 相对点度中心度( 用c r 表示) 是其绝对点度中心度的标准化形式， 点的度数与其最大可能的度数之比，即： ，d “) l m 。石 ( 1 ) 为该 ( 2 ) 其中n 为图中的节点数f 2 1 2 、点度中心势 一 “点度中心势”( d e g r e ec e n t r a l i z a t i o n ) 描述的是整个图的中心趋势，即该图是 否存在一个核心节点的趋势 中心势指标的导出思想是：首先找到图中所有节点中心度的最大值；然后计 算该最大值与其他所有节点的中心度的差值，并求出这些差值的总和；最后用这 个总和去除以上述差值总和的最大可能值。公式化描述如下： c 。二坠二曼! m a x 艺7 1 ( c m 一) 】 ( 3 ) 这一公式同样也是后面第2 2 2 节中的中间中心势和第2 2 3 节中的接近中心势的 导出思想 如果用绝对点度中心度来描述点度中心势，其形式为： 7 。驾专笋 如果用相对点度中心度来描述点度中心势，其形式为： 。墨坠竺二鱼! n - - 一? n 这里c a o = c 肋，即为c 反点度中心势尸 2 2 2 中间中心性 ( 5 ) 中间中心性是一个以图中节点对的测地线数量为基础来量化中心性的指标。 l 、中问中心度 “中间中心度”( b e 铆曲e 鼯c e n t r a l i t y ) 描述的是一个节点起到“中介”( 或者 。桥梁”) 作用的程度，它刻画了该点控制图中其他点之间交往关系的能力 中间中心度又分为绝对中问中心度和相对中间中心度。假设图中点n j 和毗之 间存在的测地线数目用g i k 来表示，第三点l l i 控制这两点交往的能力用b j k ( i ) 来表示， 定义为该点处于点n j 和i l k 之间测地线上的概率，点n i 和m 之间存在的经过点n l 测地线数目用舀k ( i ) 来表示，则： 6 。( f ) 。盟 。 g j ( 6 ) 点n i 的绝对中间中心度( 记为c a i ) 就是将该点对于图中所有点对的控制能力 加起来，即： c 腑- ：( f ) ，j a k ，呵t 七( 7 ) 点n i 的相对中间中心度( 记为c 嘣) 是其绝对中间中心度的标准化形式，为该点 的实际绝对中阃中心度与其最大可能的绝对中白j 中心度之比经证明，相对中间 中心度为： 气惫。瓣 凹 一般常用相对中问中心度来进行计算【2 l o 8 2 、中闻中心势 。中间中心势”( b e t v c e n l l c s s c e n t r a l i z a t i o n ) 描述的是整个图的中间性趋势，即 该图是否存在一个“中介”节点的趋势。 经证明，用绝对中问中心度来描述中间中心势，其形式为： 。艺n 二3 - 坠4 8 2 竺+ 5 二n 鱼- 2 1 用相对中间中心度来描述中间中心势，其形式为： c 。芝罢二型 n 一1 这里( ：曲= ( ：髓，即为似中间中心势) 【2 j 2 2 3 接近中心性 ( 9 ) 2 时很难给出n 一派系的社会 学的解释，其次是n 派系作为一个子图当某些边被去掉之后其直径可能比1 1 还大， 最后是一个n 派系可能会是一个不关联图1 2 1 2 3 31 1 一宗派 n 宗派( n - c l a n ) 也是建立在距离基础上的凝聚子群，它是指任何两点之间在子 图中的距离最大不超过n 的子图。 n - 宗派的概念比n 派系要严格，也更加具有实际意义，因为它克服了n 派系 在应用方面的后两个局限性，但是当n 2 时，我们依然难以给出1 1 宗派的社会学 解释( 2 i 2 3 4k 丛 k 丛( 1 【p l e x ) 是建立在点度基础上的凝聚子群，它是指满足如下条件的子图， 即该子图中任何一点都至少与子图中除了k 个点之外的其他所有点直接相连。也 就是说，如果一个凝聚子群的规模为n ，那么只有当其所有点的度数都不小于n - k 时，该凝聚子群才是一个k 丛。 k 丛比n 一派系更能体现。凝聚”的概念，尤其是当n 2 的时候，但是k 丛的 一个很大的问题就是k 的大小难以确定，一般只能根据一些简单的规则或者研究 者的经验来确定1 2 j 2 3 5k 核 k 核( k - c o r e ) 也是建立在点度基础上的凝聚子群，它是指满足如下条件的子图， 即该子图中任何一点都至少与子图中的k 个点直接相连。也就是晚，k - 核中任何一 点的度数都不小于k 1 2 这一概念与k - 丛是类似的。 2 3 6l a m b d a 集合 l a m b d a 集合是建立在子群内、外部成员之间关系强度基础上的节点集。l a m b d a 集合的概念来源于一个凝聚子群应该相对稳定这一思想，即一个凝聚子群不应该 因为从中去掉几条线而变得不关联。 为了形式化地描述l a m b d a 集合，首先引入一个边关联度的概念。点n i 与点n j 之闻的边关联度记为撕，j ) ，它等于为了使这两个点之间不存在任何途径而必须从 图中去掉的线的最小数目那么，九gj ) 值越大，说明n l 与n j 之间越稳健；x 0 ，j ) 值越小，n i 与n i 之间越敏感。 对于一个子图g s 的节点集n s ，如果满足以下条件，我们就说该节点集是一个 l a m b d a 集，即n s 内部的任何一对节点的边关联度都比来自n s 内部的一点和来自 n s 外部的一点所构成的节点对的边关联度要大。 l a m b d a 集的形式化描述如下： 设子图g s 的节点集n s c _ n ，如果对于任意节点h i , n i ，n k n s 以及n l e n - n s 来 说，都有撕，j ) 九( 1 【，1 ) ，那么我们称节点集n s 为一个l a m b d a 集1 2 1 3 应用场景分析 本文的研究内容以实际应用为最终且的，我们希望大规模交往数据集凝聚子 群分析的成果能够在各个不同的领域得到广泛的实际应用：同时，也希望通过发 掘更多的应用场景，来促进基于社会网络分析方法的凝聚子群分析研究工作不断 深入。 总体来说，由于客户交往数据集的覆盖面广( 几乎覆盖了所有的社会对象) 、信 息丰富( 通信时长、通信时间、通信时段和通信频率等信息在很大程度上能够代表 社会对象之间交往关系的紧密程度) ，所以本文的应用场景非常广泛。 本章将简单介绍几个本文重点关注的应用场景 3 1 企业决策支持 就通信企业本身而言，进行交往数据集凝聚子群分析的意义在于可以为企业 的发展战略提供良好的决策支持。在采用其他诸如数据仓库与数据挖掘技术所进 行的通信业务数据分析之中，同样也是以提供决策支持为目的而采用一种全新 的社会网络分析方法对用户交往数据集进行凝聚子群分析，也将会为企业提供良 好的决策支持。概括来说，大规模交往数据集的凝聚子群分析大致可以从以下几 个方面为企业提供决策支持： l 、营销策略分析 营销策略是一个电信企业在激烈的竞争环境中立足的根本，有很多方法可以 用来辅助决策者们制定出有效的营销策略，而基于社会网络分析方法的交往数据 集凝聚子群分析便是其中之一。 首先，我们可以从消费能力、消费习惯、消费周期等诸方面因素对用户群体 进行分类，找出潜在的大客户，然后针对这些大客户制定营销策略。 其次，我们可以对一个已知的用户群体运用社会网络分析方法进行凝聚子群 分析，找出某些具有相似特征或者紧密关系的凝聚子群，从整体上分析它们的消 费特征，然后制定相应的营销策略。 另外，我们还可以对电信通话网络中的静态几何量，比如节点度、密度、中 心势、聚集度、膨胀率等进行统计分析，或者根据现有的社会网络分析模型来研 究用户交往网络的特征，为通信企业提供决策支持 2 、防欺诈行为分析 目前，社会上存在一些不法分子利用通信网络进行欺诈活动。比如在电信网 韭塞窑通太呈亟堂焦监塞廛出堑基佥蚯 络中，部分不法分子以告知用户中奖来骗取用户回话这类电话号码往往具有一 些与众不同的特征。我们可以利用社会网络分析方法对这类电话号码与其欺诈对 象之间的通话关系进行分析，并根据分析得出的规律发现新的可疑号码，从而采 取一定的措旖杜绝该类欺诈行为的发生 3 客户关系管理 客户关系管理在通信行业内的作用举足轻重，在通信行业竞争日益激烈的情 况下，如何留住老客户、赢得新客户是一个企业发展的关键。 通过对现有老客户的研究，可以对老客户的消费状况、忠诚度、利润、消费 倾向等指标进行分析，以此制定相应的策略来挽留老客户，另外还可以通过客户 与非本企业客户之问的联系紧密程度、影响力( 可以通过用户的中间中心度进行度 量1 来发现港在的新客户，并以此制定吸引新客户的相关策略。 4 、特殊业务市场分析 通信企业一般会提供很多特殊业务，如电信企业的热线电话和声讯台网络 公司的v j p 邮箱等等，尤其是将通信业务与传统平面媒介的结合( 如电视台、广播 电台等1 ，给很多特殊业务带来了无限商机。比如各大电视台的节目一般都设有热 线电话和电子邮件地址，如果能吸引更多的客户参与进来，将会给通信企业带来 更大的利润 我们可以运用社会网络分析方法来提高特殊业务的市场占有率。在特殊业务 所形成的交往图中，通过社会网络分析方法对该交往图的各项指标进行量化分析， 找出其中影响力较高( 即中矧中心度较高) 的客户，然后对这些客户采取某些策略， _ 柬扩大特殊业务的影响范围。 3 2 犯罪侦查 以往所进行的交往数据集分析一般仅仅局限于为通信企业自身提供决簟支持 服务，如上述的营销策略分析、客户关系管理等等。但实际上，由于客户交往数 据集从一定程度上代表了社会对象之间的关系，由此便可以得到一个量化的社会 关系网络。这种量化的社会关系网络可以在很多领域得到广泛的应用，其中在安 全领域的应用更是值得探讨。 l 、可疑对象分析 假定在犯罪侦查中已经锁定了某个可疑对象。我们便可以以他为核心构建一 个交往网。在此交往图的基础上，通过社会网络分析方法进行凝聚子群分析，从 而判断可疑对象与其他人之间的关系、是否存在一个犯罪团体以及可疑对象在该 团体中所处的地位等等。 1 4 2 、可疑行为分析 电信客户的弃卡、频繁换号等行为通常是犯罪嫌疑人用来隐藏自己身份常用 的手段，这给犯罪侦查带来了一定难度，虽然犯罪嫌疑人可以弃卡、频繁换号， 但是他所处的社会关系网络应该不会频繁地发生变化，因此我们可以考虑对有上 述可疑行为的人所在的社会网络进行凝聚子群分析，找出有价值的犯罪侦查线索。 3 、犯罪团体分析 现实社会中，有许多严重的犯罪行为都是有组织的团体活动，如贩毒、抢劫、 走私等等，单靠一个人的力量是无法完成的。如何揭露这样的犯罪团体是犯罪侦 查的一个非常重要的问题，如果一些常规的侦查手段无法达到预期的效果，我们 就可以用交往数据集的凝聚子群分析来作为查找犯罪团体的辅助手段。 4 、犯罪心理分析 大规模交往数据集的凝聚子群分析也可以应用于犯罪心理学的研究。比如研 究犯罪人员产生犯罪行为的原因，是误入歧途，是心理畸变，还是仅仅只是报复 行为? 目前，国内外许多社会学者、心理学者对于互联网世界的社会关系网络进 行了大量的研究，并取得了丰硕的研究成果。而基于其他通信网络的社会关系网 络研究还很少，其实各种通信网络之间具有很大的相似性，因此将各种交往数据 集的凝聚子群分析应用于心理学、社会学的研究是有一定理论基础的，应该是可 行的。 3 3 其他应用领域 除了将交往数据集凝聚子群分析应用于上述的企业决策支持和犯罪侦查领域 之外，还有很多其他的应用场景，比如人力资源、提高生产效率、组织行为管理 等等，随着本课题研究工作的进一步深入，我们将逐步发掘更多的应用场景 而另一方面，随着新的应用场景的增加，也将会反过来促迸基础性研究工作 的不断深入和完善。 4 数据分析处理 数据分析处理是本文的核心研究内容，也是大规模交往数据集凝聚子群分析 过程中最重要、最复杂的一环它是一个以通信企业的客户交往数据为输入，利 用各种数学方法和计算机技术，得出某些运算结果的过程。此过程需要根据交往 数据流的变化，结合具体的应用场景，设计一个凝聚子群分析模型，并根据此模 型实现一个凝聚子群分析系统，然后在此系统之上进行凝聚子群的分析与处理。 本章将以电信通话数据构成的电信用户交往数据集为例进行数据分析处理。 4 1 凝聚子群分析模型的结构设计 从输入到输出的过程中，客户交往数据先后经过了若干个处理环节，每一个 处理环节完成不同的功能，各自的处理对象、处理方法和处理结果也互不相同。 根据这一思想，我们将大规模交往数据集的凝聚子群分析模型设计为一个基于数 据流的层次结构模型，如图4 - 1 所示。 初始条件结粜数据集 数据接口层数据预处理层 点生予圈与组生予图算法卜 ，、 厂、一教据统一建立视图 生 一查询语f 口 数 t 叫数据j 簋租粒度化 t 成 一数据加密排除噪音 圈属性与表字段映射关系k 壹 词 语 句 一结果数据囊一 不同类型数据库连接对霉卜 图4 - l 大规模交往数据集凝聚子群分析模型的层次结构 器 大规模交往数据集凝聚子群分析模型的层次结构从整体上来看共分为四层， 自底而上分别为数据预处理层、数据接口层、数据分析层和数据表现层。 l ，数据预处理层 数据分析模型所面对的原始数据源是通信企业内部的交往数据集。是客户之 间详尽的通信记录。为了对这些通信记录进行分析，需要进行一系列的数据预处 理工作。为了不影响企业主要业务的运营，首先应该将待分析的数据从业务平台 导入专门的分析平台；为了提高数据处理的速度，需要进行一些优化工作，比如 创建索引等；为了保护用户的隐私，需要对原始数据中的敏感信息( 比如电信通话 数据中的电话号码) 进行加密；原始数据中可能存在一些对于数据分析工作无意义 的通信信息( 比如电信通话数据中用户拨打客服电话或声讯台电话的信息等等) ，对 于此类通信信息要予以捧除：然后进一步对数据进行统计汇总，实现粗粒度化； 最后根据数据分析过程的实际需要建立若干个视图 2 、数据接口层 不同的通信企业其数据库平台可能不同，有的可能是o r a c l e ，有的可能是d b 2 ， 等等，此外还要求实现后的凝聚子群分析系统能够接受手工输入或者模拟生成的 数据。因此，要求凝聚子群分析模型兼容不同的数据库平台，这就需要对数据库 连接对象重新进行封装。另外，不同的通信企业其数据库结构可能不同，而模型 中所定义的数据结构是一定的，这就需要在模型的数据结构与数据库的表字段之 问建立一一映射的关系。最后，接口层实现一些算法，其中最重要的是以一个或 者多个客户为核心按照通信关系的层数生成交往图的算法 数据接口层根据前台用户的指定或者凝聚子群分析过程的需要生成一系列查 询语句，并将从数据库中获取的数据结果集返回给前台 3 、数据分析层 数据分析层是本模型的核心层次，是大量进行数据计算的地方电信业务数 据从数据库中提取出来之后，需要转换成本模型中可进行分析研究的数据结构形 式，所以首先需要根据图论和社会网络分析的概念定义一套完整的数据结构，并 实现一些基本的算法，包括图的基本操作，求全最短路径的算法等；另外，还要 实现计算社会网络中心性指标集的算法，以及自我中心凝聚子群分析算法与整体 网络凝聚子群分析算法等。 随着实际应用场景的增加，数据分折层可麓还需要扩展一些自定义的算法， 以备数据分析过程中随时调用。 4 、数据表现层 数据表现层是数据分析系统中与用户直接进行交互的层次，本层中最关键的 功能是要实现数据的可视化。通过数据可视化，可以将从数据库中提取的数据集 以某种方式展现给用户，以便于用户从中选择要分析的对象交给数据分析层进行 分析；数据可视化还可以将数据分析层的分析结果提交给用户，以便于用户获取 有用的信息。另外，数据表现层还需要定义交往图对象的本地存储格式，将分析 过程中产生的中间数据或者结果数据以文件的形式在本地保存起来。此外还应为 用户提供指定初始分析条件和进行指导性人工干预的接口，以及用户导入自定义 数据源或者模拟数据源的接口。 4 2 数据预处理 大规模交往数据集的特点是数据量庞大、噪音信息多、粒度级别低，结构不 统一，保密要求高等，具有这些性质的数据进行分析和处理的难度较大。因此， 对这些原始数据进行预处理，将其规整为使用方便、访问高效的数据源，对于整 个凝聚子群分析模型而言，意义十分重大。 一般情况下，数据预处理的过程都很复杂，所需要的时间和空问代价都很高， 其中有些步骤是无法避免的，而有些步骤则可以通过一定的优化措施将效率提高 到比较满意的程度。 根据交往数据集的独特性质，其数据预处理大致包含了数据导入、结构优化、 信息加密、去除噪音、瓤粒度化、建立视图等六个过程。 4 2 1 数据导入 由于需要对原始数据进行复杂的预处理，这期闻可能会频繁地进行数据库操 作，另外在预处理过程中可能产生许多新的数据表或者固化视图，从而占用大量 的存储空间，因此在通信企业的业务数据库上直接进行数据分析是不现实的，也 是不安全的，将待分析的数据导入专门的数据分析平台之中是必然的。 大规模交往数据集一般都是结构化的数据，因此数据的导出导入相对比较容 易一般情况下，只需要针对某些数据表或者数据表分区利用数据库管理系统 ( d b m s ) 的导出导入工具( 比如o r a c l e8 i 的e x p i m p 工具) 就可以完成导出导入工作。 对于在线数据，还可以利用数据库管理系统中的数据链路方式( d b u n k ) 进行数据 拷贝。 如果业务数据库与分析数据库是异构的，则需要在不同的数据库管理系统之 间进行数据迁移，这就需要使用数据迁移- r 具( d a t at r a n s f o r mt a s k , d t s ) 来进行数 据的导出导入工作当然，我们也可以自己编写定制的数据迁移工具。 4 2 2 结构优化 由于待分析的数据量非常庞大，如果不对数据库进行一些结构优化，则进行 数据访问的速度可能无法忍受 在数据分析过程中，对原数据的操作主要是查询，基本不涉及插入和删除。 对于大规模交往数据集凝聚子群分析模型而言，创建索引是最佳的提高数据库访 问效率的方法，因为在不涉及插入和删除操作的情况下，就不需要花费巨大的时 间和空间代价对索引进行维护。 当然，由于数据量的庞大，创建索引的过程可能也需要较长的时间，但这为 以后的数据查询带来了效率的大幅度提高，所以是一劳永逸的事情 在创建索引的时候，我们既可以针对经常作为查询条件的单个字段建立索引， 也可以根据实际需要针对某几个字段建立联合索引 在索引种类的选择上，我们应该选择位图索引。因为交往数据集中的常用查 询字段( 如电信通话数据中的电话号码) 的集势( c a r d i n a l i t y ) 通常较低，位图索引的压 缩编码技术可以大大节省存储空间，减少d b m s 对数据块的访问；另外。在分析 型数据处理中很少进行插入和删除操作也降低了位图索引的维护代价。 在o r a c l e8 i 环境中创建位图索引的方法如下： 首先，我们需要在o r a c l e 的配置文件中设置c r e a t em t m a pa r e as i z e 参数，该参数用以确定创建位图索引时所使用内存空问的大小，其默认值为8 m ， 一般情况下，该项参数的值越大，创建位图索引的速度越快。 其次，位图索引只能在c b o ( c o s * 队s e d o p t i m i z e r ，o r a c l e 的一种优化 器) 模式下使用，如果数据库管理系统的当前优化模式不是c b o ，则需要首先将 其修改为c b o 模式 最后，创建位图索引。在数据表空问s 1 上为数据表t 1 的f 1 字段创建位图索 引的s q l 语句为： c r e a t eb i t m a pi n d e xi n d e x n a m eo n t i ( f 1 ) t a b l e s p a c es 1 ； 在数据表空阃s 1 上为数据表t l 的f 1 字段和f 2 字段创建位图联合索引的s o l 语 句为： c r e a t eb l t m a pi n d e xm d e x n a m eo nt i ( f 1 ，f 2 ) t a b l e s p a c es i ； 我们还可以在两个数据表上建立位图连接索引，这样当我们在位图索引上进行数 据检索的时候就不需要重新进行两个表的连接，在数据表t 1 和1 r 2 的f 1 字段上创 建位图连接索引的s o l 语句为： c r e a t eb i t m a pi n d e xi n d e x n a m eo nt i ( f 1 ) f r o mt 1 ，t 2w h e r e 1 1 f 1 = - 1 2 f 1 4 2 3 信息加密 交往数据集是通信企业客户之间的详尽通信数据的集合，属于客户的隐私。 为了不侵犯客户的隐私权，必须对交往数据集中的敏感信息f 比如电信通话数据中 的电话号码谜行加密。由于加密之前的原文与加密之后的密文是一一对应的，因 此不会影响到后面的凝聚子群分析工作。加密算法所采用的密钥由拥有相关权限 的管理员掌握。在数据分析过程之中或者完成之后需要进行信息解密的时候，由 掌握密钥的人在不侵犯客户隐私权的情况下提交密钥进行解密。 信息加密应在数据导入分析平台之后、数据分析过程开始之前进行。加密算 法多种多样，各有优劣。 本文所采用的数据库管理系统为o r a c l e8 i ，信息加密工作是通过数据库函数 和存储过程完成的，加密规则是自定义的，算法比较简单，但其密钥是通过数据 库系统函数生成的一个长达5 0 位的随机字符串，因此在没有密钥的情况下想要破 解密文基本是不可能的。 我们首先设计了一个加密函数f u n e n c r y 0 ，它的输入为待加密的原文字符串和 密钥字符串，返回值为密文字符串。具体的加密规则此处从略 然后编写了数据库存储过程p r o g e t k