一种网络化数据挖掘方法研究

一种网络化数据挖掘方法研究：1 引 言

回顾数据挖掘与知识发现(DMKD)的初衷，就是要从大量的、不完全的、有噪声的、模糊的、随机的实际应用数据中，提取隐含在其中的、人们事先不知道的、但又是潜在有用的信息和知识。随着DMKD研究逐步走向深入，数据挖掘所发现的知识涉及到广义知识、关联知识、分类知识和预测知识等。广义知识(Generalization)主要指关于类别特征的概括性描述知识．根据数据的微观特性发现其表征的、带有普遍性的、较高层次概念的、中观和宏观的知识，反映同类事物共同性质，是对数据的概括、精炼和抽象；关联知识(Association)是反映一个事件和其他事件之间依赖或关联的知识，如果两项或多项属性之间存在关联，那么其中一项的属性值就可以依据其他属性值进行预测；分类知识(Classification & Clustering)则是反映同类事物共同性质的特征型知识和不同事物之间的差异型特征知识；预测型知识(Prediction)根据时间序列型数据，由历史的和当前的数据去推测未来的数据。

所有这些知识都可以在不同的概念层次上被发现，并随着概念层次的提升，从微观到中观、到宏观，以满足不同用户不同层次决策的需要。

但是，随着对复杂系统和复杂网络研究的深入，人们发现现实世界复杂网络无处不在，复杂网络结构中本身蕴含的知识，是一类新型的重要知识，称之为复杂网络的结构知识或拓扑知识(topolosy)。结构知识与上述四种类型的知识既有联系，又有区别。所谓网络化数据挖掘(Networked Data Mining)，就是将网络拓扑作为一种知识表示方式，将大规模实际数据对象及其关系抽象为网络拓扑的形式，采用复杂网络的理论和方法进行分析和挖掘，发现蕴涵在其中的、反映事物间联系规律的知识和信息。与传统数据挖掘方法相比。网络化数据挖掘的主要不同在于：①待处理的数据是网络化表示的数据对象及其关系，得到的结果是反映数据对象问内在联系的拓扑知识；②挖掘过程是根据复杂网络的理论和方法，通过网络拓扑特性分析、拓扑结构挖掘实现逐层迭代的网络约简和重要拓扑知识的抽取；③由于网络拓扑的可视化，网络化数据挖掘可以通过集成人的认知能力，实现交互式挖掘，提高挖掘结果的有效性和挖掘过程的可理解性。

可见，网络化数据挖掘的核心思想是对关联数据进行网络化表示，即把海量的关联数据表示为复杂网络拓扑，进而对复杂网络节点度分布规律、集聚系数、网络平均距离以及节点介数和边介数等网络拓扑基本度量参数进行分析，以此发现复杂网络中有典型意义的骨干网拓扑、对复杂网络性能具有敏感作用的重要节点和重要边、以及在复杂网络中具有本地局部特性的社区结构和抱团特性，从而发现蕴含在海量关联数据中的结构性知识。

一种网络化数据挖掘方法研究：2 网络节点重要性综合判据

网络化数据挖掘的核心，就是将相互关联的数据表示为网络拓扑模型，以网络统计特征参量作为评判依据，发现蕴含子其中的重要节点、骨干网络和反映抱团特性的本地社区结构。网络化数据挖掘不同于网络数据挖掘，其关键点是基于图论的数据挖掘，并且随着复杂网络研究的深入不断完善，而且这种理论上的探索也在不断向实际应用推进。

寻找重要节点对于分析复杂网络的性质非常重要。例如可以在罪犯关系网络中迅速定位到犯罪团伙的头目(相当于网络拓扑中的重要节点)，从而集中力量进行布控；或者在海量的WEB站点中快速找到与某个特定主题相关度最高的若干站点，并通过搜索引擎把正确的结果在恰当的时间返回给特定用户。评价节点重要程度的依据和发现重要节点的方法非常多，如节点度排序法、介数排序法、PageRank算法、HI髑算法等。通过建立复杂网络拓扑模型，可以分别计算节点的介数和度数分布，提取网络核心节点，形成骨干拓扑视图。

从无尺度网络特性来分析，在复杂的现实网络世界中，大量的节点具有少量的度，只有少量的节点具有较高的度，因此网络中的每一个节点的地位是不一样的。但是并不是网络中节点的度越高，节点就越重要，大部分情况是这样的，也有例外的情形。例如，新建的交通枢纽比旧的交通枢纽重要性高，但由于拓扑演化过程的时间因素，在度分布的外在表现上。两者的度数分布接近一致，仅从度分布难以准确反映节点的重要程度。实际上，节点的度数反映了拓扑模型的静态结构特征，而介数则反映了节点的流量状况，直接与节点的活动相关。因此，采用介数和度数综合判据对节点重要性进行评估，能够更好地反映两者的权衡。算法的基本思路是：

(1)计算每个节点的度数，计算网络平均度数；

(2)遍历网络的两两节点对，求解节点对最短路径，计算节点的介数；

(3)针对问题域背景，建立基于节点介数和度数的综合判据规则库；

(4)根据规则库知识对节点进行重要性分类。

实验结果如图1所示，根据重要节点挖掘算法，对一个小型社区活动网络(Node＝34)进行重要节点挖掘，左图是社区成员之间的关系拓扑，节点旁边标注的是人名，右图是由挖掘之后的重要节点构成的简约拓扑，得到前10个重要成员及其之间的连接关系。

图1 重要节点及骨干网挖掘

一种网络化数据挖掘方法研究：3 复杂网络拓扑的数据场视图与虚拟核

如上节所述，复杂网络拓扑中不同的节点具有不同的重要性，那些有着重要地位和作用的节点在网络中会有较大的影响范围，对周围邻居节点具有更大的辐射强度，其他节点都会在一定程度上受其影响，根据这种影响程度的大小，复杂网络可以被划分为不同的社区，从而挖掘出其抱团特性。其基本过程如下：

(1)挖掘网络拓扑中的重要节点，也就是发现那些地位较为重要的节点，作为社区的代表节点或生长节点；

(2)根据节点个体之间联系的强弱程度，把它们划分到不同的社区。衡量这种联系强度的方法可以依据网络拓扑上的距离，综合考虑相应的权值。

本文采用认知物理学中的数据场方法，作为描述数据对象之间相互作用关系的形象、直观的方法，计算网络节点的影响范围。数据场的势函数定义为：

其中，||x－xl||为对象xl与场点x间的距离，通常采用欧氏距离、曼哈顿距离或拓扑距离等；mi≥0为对象xi(i＝1…?n)的质量，σ为影响因子。势函数的内涵中有两个重要的因素，即节点的质量和节点间的距离。为了准确把握节点的特征，节点质量可以映射为现实网络中节点多种属性的综合叠加，节点间的距离可以取两个节点在网络中的最短路径。网络中的社区划分具有不确定性，在不同粒度上将得到不同规模的社区结构，粒度可以根据实际的需求确定，并可根据需要进行调整。其基本过程如下：

(1)依据上节中的算法挖掘前M个重要节点，并把它们作为根节点集合；

(2)把根集合中节点的综合权值作为质量，计算当前节点到每个根节点的势值，把此节点归属于拥有最大势值的根节点；

(3)遍历所有节点。

实验结果如图2所示。其中图2(a)表示某科研合作网络，共有286个节点和554条边，图2(b)是这个网络被划分为10个社区的情况，每种色彩代表不同的社区，其中五角星代表每个社区的核心人物，在此图中也可以清晰地看出各个社区之间存在的连接关系，图2(c)是这个网络被划分为10个社区的虚拟代表点，即虚拟核，节点的大小表示每个代表节点所在社区拥有的节点数目的比例。

图2 基于数据场的网络社区挖掘

一种网络化数据挖掘方法研究：4 结束语

二十一世纪学科发展的特点之一，就是在交叉研究中实现创新，这种大学科交叉的普遍趋势，在数据挖掘和复杂网络的交叉研究中表现得尤其突出。网络化数据挖掘方法把网络拓扑作为知识表示的新方法，采用复杂网络理论和方法研究人类从数据到知识的认知过程，有益于推动数据挖掘以及人工智能科学与应用的进展。通过引入认知物理学理论中的数据场思想，分析和提出基于节点介数和度数综合判据的节点重要性挖掘方法，挖掘复杂网络中的抱团结构，提取复杂网络的虚拟核，得到网络的简约化的拓扑资源视图，对于挖掘复杂网络中蕴含的结构知识，具有重要的意义，但是随着复杂网络规模的扩大，网络拓扑映射规律将更趋复杂，如何在算法中引入并行算法机制，提高挖掘算法处理大规模网络的效率，这也许将成为今后复杂网络和数据挖掘研究领域的一个极具挑战性的课题。