打开文本图片集
摘要：三支决策将传统的正域、负域的二支决策语义拓展为正域、负域和边界域的三支决策语义。目前对边界域处理已成为三支决策模型需要解决的一个重要问题，本文在层次粒化社团划分算法框架的基础上，将代价敏感的边界域处理引入社团划分中，给出了一种新的获取非重叠社团划分的方法。基于代价敏感边界域处理的社团发现算法C-TWD在四个典型社交网络数据集karate、football、dolphin和lesmis上取得了优于相关社团划分算法GN、NFA和LPA的性能。同时，本文选取某市移动通讯的实际应用数据，根据通讯基站间是否有信号切换决定两基站节点间是否有边存在来构建网络模型，实验结果表明C-TWD算法同样适用于实际问题的求解。
关键词：三支决策；层次粒化；代价敏感；边界域处理
中图分类号：TP391 文献标识码：A 文章编号：1672-9129（2017）03-0006-04
Abstract： The three-way decision theory is constructed based on the notions of acceptance， rejection and non-commitment， which can be directly generated by the three regions： positive region POS（X）， negative region NEG（X） and boundary region BND（X）. In this paper， we introduce cost-sensitive boundary region processing to detect community on basis of hierarchical granulation. Then，Cost-sensitive Three-Way community Detection algorithm Based on boundary region processing（C-TWD） is proposed. Compared with classical detection algorithms （GN， NFA， LPA）， the experiments on karate， football， dolphin and lesmis show that our method can gain higher modularity. On other hand，we select partial mobile data to construct actual network. An edge between two nodes means that the signal changes between two nodes. C-TWD also works well on actual network.
Key words： the three-way decision； hierarchical granulation；cost-sensitive；boundary regions processing；
引言
在现实世界中，许多事物的联系都是以网络的形式存在的，而许多实际网络中都存在着社团结构[1-3]。每个社团内部的节点之间连接相对紧密而社团之间的连接相对比较稀疏，如何有效地进行社团划分是社团研究者们一直致力于研究的一个重要方向之一。
近年来，许多学者分别从不同角度对社团划分进行了研究，随着研究的深入，人们发现在进行社团划分时经常会出现重叠部分，即一个节点被多个社团包含。实际上，将重叠节点划分到单个社团中更有助于发现社团内存在的规律，并预测网络的行为和功能[4]。因此，将社团重叠部分拆分，从而构造非重叠的社团划分是十分必要的。
对于非重叠社团划分的研究也引起了很多学者的关注和研究。Newman快速算法（NFA） [5]依靠模块度获得最优社团结构；Radicchi等提出了自包含GN 算法（Self-Contained GN Algorithm） [6]，给出了强社团和弱社团结构两种量的定义，为如何确定社团结构提供了一种衡量标准；赵[7]等将粒计算思想引入到网络的社团划分中，通过对网络结构的聚类粒化实现社团划分，其时间复杂度低、收敛速度快、精确度高实现了时间复杂度与精确度之间的平衡。这些现有的非重叠社团划分算法从不同的角度和应用层面对非重叠社团的划分进行了研究，并取得了丰硕的研究成果。
上述算法对重叠部分处理时都只应用了传统的二支决策方法，即根据已有的信息只做出接受或拒绝决策。但重叠部分的节点往往因为信息量不够才会出现在重叠部分，强制做出决策，可能影响最终非重叠社团划分的结果。姚一豫教授在粗糙集和决策粗糙集的研究中提出了三支决策理论[8-10]，该理论将传统的正域、负域的二支决策语义拓展为正域、边界域和负域的三支决策语义，即额外增加一个边界域，表示延迟决策。由正域 生成的一个正规则对应做出接受决策，由负域 生成的负规则对应做出拒絕决策，而由边界域 生成的边界域规则对应做出延迟决策[11]。
现实中，重叠问题除了信息不足之外，往往还具有代价敏感性。除了追求分类精度的提高，一定要注意尽可能的降低分类的损失代价。代价敏感学习的目标是为了获得最小测试代价和误分类代价[12-13]，也是机器学习研究中一个重要挑战。
因此，本文将代价敏感引入三支决策思想处理社团重叠部分，提出了基于代价敏感边界域处理的社团发现算法C-TWD，以划分出更合理的非重叠社团。该算法通过初始粒化后进行聚类粒化，形成重叠的社团划分结果；再将两个存在重叠部分的社团的左边社团非重叠部分定义为正域，右边社团的非重叠部分定义为负域，而两个社团的重叠部分定义为边界域，定义划分代价函数 ，计算边界域中的节点与正域和负域的代价函数，依据代价敏感原则对边界域中的节点进行二次划分。对于二次划分后仍然留在边界域中的节点将利用投票的方法决定其最终归属，最终获得非重叠的社团结构。
2 基于代价敏感边界域处理的社团发现算法
代价敏感分类问题中，当分类问题中不同的分类错误会引起不同的分类代价，而社团重叠部分的划分正是一个代价敏感问题。因此，本文在之前三支决策模型基础之上，提出了基于代价敏感边界域处理的社团发现算法。该模型将重叠节点划分后的模块度差异 作为代价函数，使分类损失最小化，同时使最终获得社团结构模块度更高。
本文是在聚类粒化的社团发现算法框架下获得后边界域（ ），正域（ ）和负域（ ），再将边界域部分进行二次划分。此时，为了获得最好的模块度，即最小的划分损失。
公式（4）定义了边界域中的节点进行二次划分后的损失函数。对于 ，
据此本文提出了基于代价敏感边界域处理的社团发现算法C-TWD，算法具体过程如下：
3 实验结果及分析
为了验证C-TWD算法的有效性和可行性，采用了四个典型社交网络数据集作为测试数据集，分别是著名的空手道俱乐部网络（Zachary’s karate club）、足球联盟网络（American college football） 、海豚网络（dolphin social network） 和悲惨世界网络（lesmis）。实验数据集的基本信息如表1所示。
作者将本章算法与其他相关社团划分算法（GN、NFA、LPA）在四个真实的网络数据集上的模块度 值进行了对比，实验结果如表2所示。其中，GN：经典的分裂式层次社团挖掘算法；NFA： Newman快速算法，是基于模块度优化的凝聚式社团挖掘算法；LPA：快速标签传播算法。从表2中可以看出，本文提出的算法 C-TWD 在 karate 和lesmis、football 上都获得了最高的模块度值，表明基于代价敏感边界域处理的三支决策模型用以社团发现也具有很好的性能。
为了进一步验证本文所提出的C-TWD算法的有效性，以某市移动通讯的实际应用数据为例进行相关实验。实验数据是根据通讯基站间是否有信号切换决定两基站节点间是否有边存在来构建网络模型。构建的无权无向网络如图1所示，其中包含3644个顶点，69876条边。因该数据的实际意义，采用统一的频点标注算法对上述三种社团划分结果进行频点设置。标注频点时，随即选取任意社团内部点首先设置频点，再将其所有邻居节点标注为有一定差异的数值，以保持社团内部频点间的差异，此后再选取下一社团，以当前社团边界点频点与已标注社团最近边界点频点保持差异进行迭代设置，直到所有节点被标注[15]，从而使得全网干扰最小。本文仅对比网络社团特性，对比NFA算法、LPA算法和C-TWD算法的计算结果如图2所示，因为网络规模过大，GN算法复杂度过高，不具有实用性，因此不再与GN进行对比。从图2可以看出，在真实数据集网络中，采用本算法进行社团划分依然具有有效性。
4 结语
本文将代价敏感引入三支决策思想处理社团重叠部分，提出了基于代价敏感边界域处理的社团发现算法C-TWD，以划分出更合理的非重叠社团。算法定义划分代价函数 ，计算边界域中的节点与正域和负域的代价函数，依据代价敏感原则对边界域中的节点进行二次划分，最终获得非重叠的社团结构。本文选取了四个典型社交网络数据集作为测试数据集与经典社团算法进行了对比；并选取真实的移动通讯数据构建网络进行测试，实验结果进一步说明了本文所提算法的有效性。针对算法的实际效果，作者将进一步研究移动通讯网络的整体性能优化问题。
参考文献：
[1]Shen H， Cheng X， Cai K， et al. Detect overlapping and hierarchical community structure in networks. Physica A： Statistical Mechanics and its Applications， 2009， 388（8）： 1706-1712.
[2]Liu Y， Pan L， Jia X， et al. Three-way decision based overlapping community detection. Rough Sets and Knowledge Technology. Springer Berlin Heidelberg， 2013： 279-290.
[3]汪小帆， 李翔， 陈关荣. 复杂网络理论及其应用. 清华大学出版社有限公司， 2006.
[4]金弟， 杨博， 刘杰， 等. 复杂网络簇结构探测——基于随机游走的蚁群算法. 软件学报， 2012， 23（3）.
[5]Newman M E J. Fast algorithm for detecting community structure in networks. Physical review E， 2004， 69（6）： 066133.
[6]Radicchi F， Castellano C， Cecconi F， et al. Defining and identifying communities in networks. Proceedings of the National Academy of Sciences of the United States of America， 2004， 101（9）： 2658-2663.
[7]趙姝， 柯望， 陈洁， 等. 基于聚类粒化的社团发现算法. 计算机应用， 2014， 34（10）： 2812-2815.
[8]Yao Y Y. Three-way decision： an interpretation of rules in rough set theory. Proceedings of the 4th International Conference on Rough Sets and Knowledge Technology，Gold Coast， Australia， July 14-16， 2009： 642-649.
[9]Yao Y Y， Wong S K M. A decision theoretic framework for approximating concepts. International Journal of Man-Machine Studies， 1992， 37（6）：793-809.
[10]Yao Y Y. Two Semantic Issues in a Probabilistic Rough Set Model. Fundamenta Informaticae， 2011， 108（3-4）：249-265.
[11]刘盾， 姚一豫， 李天瑞. 三枝决策粗糙集. 计算机科学， 2011， 38（1）： 246-250.
[12]Elkan C. The foundations of cost-sensitive learning. Proceedings of the 17th International joint conference on artificial intelligence. Seattle， Washington， 2001， 17（1）： 973-978.
[13]李秋洁， 赵亚琴， 顾洲. 代价敏感学习中的损失函数设计. 控制理论与应用， 2015 （5）： 689-694.
[14]Newman M E J， Girvan M. Finding and evaluating community structure in networks. Physical review E， 2004， 69（2）： 026113.
[15]王博岩， 卢肖， 陈洁， 张燕平. 基于精英遗传算法的 GSM 网络频点优化设计[J]. 计算机技术与发展， 2013， 2：23-27.