第14卷第5期 智能系统学报 Vol.14 No.5 2019年9月 CAAI Transactions on Intelligent Systems Sept.2019 D0:10.11992/tis.201812014 网络出版地址：http:/kns.cnki.net/kcms/detail/23.1538.TP.20190527.0921.002.html 网络拓扑特征的不平衡数据分类 普事业，刘三阳，白艺光 (西安电子科技大学数学与统计学院，陕西西安710126) 摘要：现实中的数据集普遍具有非均衡性。针对不平衡分类问题，建立数据集网络结构来充分挖掘隐藏在样 本点位置信息外的拓扑特征，分析网络节点的连接特性并赋予节点不同的效率。计算待测节点与每个子网络 的相似性测度，依据新型的概率模型，进一步推算出该节点与各子网络的整体性测度。构建了一种基于网络拓 扑特征的不平衡数据分类方法，算法中引入不平衡因子c用以诚小由正负类样本数量差异所带来的影响。实 验结果表明，该算法能有效提高分类精度，特别是对拓扑特征明显的数据集，在分类性能和适应能力上相比传 统分类方法都得到进一步提升。 关键词：不平衡数据；相似度；网络结构；准确率；拓扑；物理特征 中图分类号：TP391.9文献标志码：A文章编号：1673-4785(2019)05-0889-08 中文引用格式：普事业，刘三阳，白艺光.网络拓扑特征的不平衡数据分类J.智能系统学报，2019,14（⑤）：889-896. 英文引用格式：PU Shiye,,LIU Sanyang,BAI Yiguang.Imbalanced data classification of network topology characteristiesJ.CAAI transactions on intelligent systems,2019,14(5):889-896. Imbalanced data classification of network topology characteristics PU Shiye,LIU Sanyang,BAI Yiguang (School of Mathematics and Statistics,Xidian University,Xi'an 710126,China) Abstract:This paper aims to solve the imbalanced data classification problem,which has been proven to be common in real applications.The dataset network structure is established to fully mine the topological features hidden outside the position information of sample points,analyze the connection characteristics of network nodes,and give these nodes dif- ferent efficiencies.The similarity measure between the node to be tested and each sub-network is calculated,and the in- tegrity measure between the node and each sub-network is further calculated according to the new probability model.A classification method of imbalanced data based on network topology features is constructed.An imbalanced factor c is introduced into the algorithm to reduce the influence caused by the difference in the number of positive and negative samples.The experimental results show that the algorithm can effectively improve the classification accuracy,espe- cially for datasets with significant topological features.The classification performance and adaptability are further im- proved compared with the traditional classification method. Keywords:imbalanced data;similarity;network structure;accuracy rate;topology;physical feature 在数据分类的研究中，普遍存在类别分布不持向量机(SVM)在处理不平衡数据时，分类超平 平衡的问题，即某一类别的样本数量远远多于 面往往会向少数类偏移，导致对少数类的识别率 另一类（分别称为多数类和少数类），具有这样特降低，而随机森林(random forest,,RF分类时易 征的数据集视为不平衡。传统的分类算法，如支 出现分类不佳、泛化误差变大等问题。针对支持 收稿日期：2018-12-12.网络出版日期：2019-05-27. 向量机在训练样本点过程中存在的噪声和野点问 基金项目：国家自然科学基金项目(61877046)：陕西省自然科 题，不少研究学者提出了相应的改进算法。如台 学基金项目(2017JM1001). 通信作者：普事业.E-mail:psy2361@126.com 湾学者Lin等1提出模糊支持向量机(fuzzy sup-
DOI: 10.11992/tis.201812014 网络出版地址: http://kns.cnki.net/kcms/detail/23.1538.TP.20190527.0921.002.html 网络拓扑特征的不平衡数据分类 普事业，刘三阳，白艺光 （西安电子科技大学 数学与统计学院，陕西 西安 710126） 摘 要：现实中的数据集普遍具有非均衡性。针对不平衡分类问题，建立数据集网络结构来充分挖掘隐藏在样 本点位置信息外的拓扑特征，分析网络节点的连接特性并赋予节点不同的效率。计算待测节点与每个子网络 的相似性测度，依据新型的概率模型，进一步推算出该节点与各子网络的整体性测度。构建了一种基于网络拓 扑特征的不平衡数据分类方法，算法中引入不平衡因子 c 用以减小由正负类样本数量差异所带来的影响。实 验结果表明，该算法能有效提高分类精度，特别是对拓扑特征明显的数据集，在分类性能和适应能力上相比传 统分类方法都得到进一步提升。 关键词：不平衡数据；相似度；网络结构；准确率；拓扑；物理特征 中图分类号：TP391.9 文献标志码：A 文章编号：1673−4785(2019)05−0889−08 中文引用格式：普事业, 刘三阳, 白艺光. 网络拓扑特征的不平衡数据分类 [J]. 智能系统学报, 2019, 14(5): 889–896. 英文引用格式：PU Shiye, LIU Sanyang, BAI Yiguang. Imbalanced data classification of network topology characteristics[J]. CAAI transactions on intelligent systems, 2019, 14(5): 889–896. Imbalanced data classification of network topology characteristics PU Shiye，LIU Sanyang，BAI Yiguang (School of Mathematics and Statistics, Xidian University, Xi’an 710126, China) Abstract: This paper aims to solve the imbalanced data classification problem, which has been proven to be common in real applications. The dataset network structure is established to fully mine the topological features hidden outside the position information of sample points, analyze the connection characteristics of network nodes, and give these nodes different efficiencies. The similarity measure between the node to be tested and each sub-network is calculated, and the integrity measure between the node and each sub-network is further calculated according to the new probability model. A classification method of imbalanced data based on network topology features is constructed. An imbalanced factor c is introduced into the algorithm to reduce the influence caused by the difference in the number of positive and negative samples. The experimental results show that the algorithm can effectively improve the classification accuracy, especially for datasets with significant topological features. The classification performance and adaptability are further improved compared with the traditional classification method. Keywords: imbalanced data; similarity; network structure; accuracy rate; topology; physical feature 在数据分类的研究中，普遍存在类别分布不 平衡[1] 的问题，即某一类别的样本数量远远多于 另一类 (分别称为多数类和少数类)，具有这样特 征的数据集视为不平衡。传统的分类算法，如支 持向量机 (SVM) 在处理不平衡数据时，分类超平 面往往会向少数类偏移，导致对少数类的识别率 降低，而随机森林 (random forest，RF[2] )分类时易 出现分类不佳、泛化误差变大等问题。针对支持 向量机在训练样本点过程中存在的噪声和野点问 题，不少研究学者提出了相应的改进算法。如台 湾学者 Lin 等 [3] 提出模糊支持向量机 (fuzzy sup- 收稿日期：2018−12−12. 网络出版日期：2019−05−27. 基金项目：国家自然科学基金项目 (61877046)；陕西省自然科 学基金项目 (2017JM1001). 通信作者：普事业. E-mail：psy2361@126.com. 第 14 卷第 5 期 智 能 系 统 学 报 Vol.14 No.5 2019 年 9 月 CAAI Transactions on Intelligent Systems Sept. 2019
·890· 智能系统学报 第14卷 port vector machines,.FSVM),根据不同数据样本对 tolopogy characteristics,NT-IDC)。首先利用 分类的贡献不同，赋予不同的隶属度，将噪声和 KNN法建立与每类数据点对应的网络结构，将数 野点与有效样本区分开，然而实际数据集中除了 据样本实例对应网络中的节点，使具有相同类别 存在噪声和野点，不同类别的样本个数差异也会 的网络节点之间产生连边，并依据其连接特性计 影响算法的分类精度。目前对不平衡数据分类的 算出每个节点的局部效率作为拓扑信息，应用基 研究主要集中在算法层面和数据层面的改进，如 于距离倒数的相似度作为两个节点产生连边概率 通过对不平衡数据集进行欠采样(under--sampling、 的物理特征，将拓扑特征与样本点的物理特征一 过采样(SMOTE卧、不同惩罚因子的方法(differ-- 起作为判别测试点类别归属的依据，为了克服由 ent error costs,.DEC和集成学习方法I等，这些 不同类别的数据样本点个数差异带来的影响，构 方法在处理不平衡数据时一定程度上提高了少数 建了一种引入不平衡因子c的新型概率模型。本 类的分类精度，然而欠采样在删除样本点时易造 文所建立的基于数据点物理特征和拓扑特征的分 成重要信息的丢失，过采样又会带来信息的冗 类模型更加符合实际数据集样本点的分布情况， 余，并增大算法时间复杂度，代价敏感学习算法 实验验证了本文所提方法具有可行性和有效性， 虽然定义了正负类不同的惩罚因子，但却没有考 与传统的分类器模型有着一定的区别。 虑到样本点的实际分布情况，这些问题又会直接 影响算法的分类效果。传统的分类方法在构建分 1相关概念 类模型时仅考虑了数据样本点的物理特征（如距 基于网络拓扑特征的不平衡数据分类算法包 离、相似度等)，并没有更深层次地挖掘数据点之 括两个阶段：网络的构建和测试点的类别预测。 间的关联特征，但实际应用中的数据集样本之间 并不是孤立存在的，它们之间除了位置上的差 利用较为常见的KNN法对训练数据集 X={x,,,xw}中的每一个样本点，从其前k个 异，关联信息也是不可忽略的。 Silva等⑧.)将仅考虑样本点物理特征的传 最近的邻居节点中找到标签信息相同的节点并在 统分类方法视为低层次分类，把数据样本点看作 两点之间建立一条有向边，每个数据样本点 网络节点，提出了基于网络信息特征的高层次数 x(i=1,2,…N与网络中的节点.(i=1,2,…,W)对 据分类方法，在训练样本点分类模型时既考虑了 应，且节点”与样本点：具有相同的标签类型， 样本点的位置关系，又考虑到了数据点之间的拓 建立网络邻接矩阵A,这样就将整个数据集映射 扑特征，将两个层次的分类器有效地结合，并在 成带有节点标签信息的网络G(VE,L),V是节点 数字图像识别中取得较高的准确度。Carnerio 集合，E是边的集合，L={l,2,…,lm}是标签集合。 等1提出了基于复杂网络的新型分类器，通过 在预测阶段，利用文中构建的分类模型去判断测 KNN法或KAOG)法建立子网络模型，利用谷 试数据样本点Y={xN+1,xw2,,xw+m}的标签类型， 歌PageRank度量方法赋予网络节点不同影响力 对于已经判断过标签类型的测试节点，选择直接 概念，依据Spatio structural effi-.ciency和节点间的 丢弃的策略，不再归合到由训练点所建立的子网 距离特征实现分类。文献[12]针对复杂网络中 络结构中，图1为本文实现数据分类的几个步骤 的链路预测问题介绍了多种基于局部和全局结 的图解，假设建立网络中k=3,最终将测试点归 构的节点相似度模型，分析出实际复杂系统中网 为整体性测度大的类别。 络节点的相互影响关系，两个节点之间产生连边 1.1节点局部效率 的概率大小是由网络拓扑结构和几何结构共同 复杂网络由图论逐渐发展而来，基于图论的 决定的。文献[13]中把链路预测问题视为一个 网络结构模型在表达数据之间的关系时具有明显 二分类问题，提出了一个数据分类问题的概率模 的优势416，本文所提出的方法在计算网络节点 型，将待测样本点的类别归属于相似度分数高 局部效率时正是建立在图论的基础上。网络中的 的类。 节点可以既是起点又是尾点，因此由数据样本点 鉴于高层次数据分类方法在无偏数据集上的 的连接关系所建立的图是有向的，为了更多地挖 优越性，本文从数据样本点的物理特征和拓扑特 掘网络中的数据点之间的拓扑关系，在数据样本 征方向出发，综合考虑数据点之间的位置关系和 点训练阶段，充分考虑每个节点的连接特性，赋 关联信息，提出基于网络拓扑特征的不平衡数据 予节点不同的效率，使节点之间具有差异性，本 分类方法(imbalanced data classification of network 文计算网络节点的局部效率公式切为
port vector machines，FSVM)，根据不同数据样本对 分类的贡献不同，赋予不同的隶属度，将噪声和 野点与有效样本区分开，然而实际数据集中除了 存在噪声和野点，不同类别的样本个数差异也会 影响算法的分类精度。目前对不平衡数据分类的 研究主要集中在算法层面和数据层面的改进，如 通过对不平衡数据集进行欠采样 (under-sampling[4] )、 过采样 (SMOTE[5] )、不同惩罚因子的方法 (different error costs，DEC[6] ) 和集成学习方法[7] 等，这些 方法在处理不平衡数据时一定程度上提高了少数 类的分类精度，然而欠采样在删除样本点时易造 成重要信息的丢失，过采样又会带来信息的冗 余，并增大算法时间复杂度，代价敏感学习算法 虽然定义了正负类不同的惩罚因子，但却没有考 虑到样本点的实际分布情况，这些问题又会直接 影响算法的分类效果。传统的分类方法在构建分 类模型时仅考虑了数据样本点的物理特征 (如距 离、相似度等)，并没有更深层次地挖掘数据点之 间的关联特征，但实际应用中的数据集样本之间 并不是孤立存在的，它们之间除了位置上的差 异，关联信息也是不可忽略的。 Silva 等 [8-9] 将仅考虑样本点物理特征的传 统分类方法视为低层次分类，把数据样本点看作 网络节点，提出了基于网络信息特征的高层次数 据分类方法，在训练样本点分类模型时既考虑了 样本点的位置关系，又考虑到了数据点之间的拓 扑特征，将两个层次的分类器有效地结合，并在 数字图像识别中取得较高的准确度。Carnerio 等 [10] 提出了基于复杂网络的新型分类器，通过 KNN 法或 KAOG[11] 法建立子网络模型，利用谷 歌 PageRank 度量方法赋予网络节点不同影响力 概念，依据 Spatio structural effi-ciency 和节点间的 距离特征实现分类。文献 [12] 针对复杂网络中 的链路预测问题介绍了多种基于局部和全局结 构的节点相似度模型，分析出实际复杂系统中网 络节点的相互影响关系，两个节点之间产生连边 的概率大小是由网络拓扑结构和几何结构共同 决定的。文献 [13] 中把链路预测问题视为一个 二分类问题，提出了一个数据分类问题的概率模 型，将待测样本点的类别归属于相似度分数高 的类。 鉴于高层次数据分类方法在无偏数据集上的 优越性，本文从数据样本点的物理特征和拓扑特 征方向出发，综合考虑数据点之间的位置关系和 关联信息，提出基于网络拓扑特征的不平衡数据 分类方法 (imbalanced data classification of network c tolopogy characteristics，NT-IDC)。首先利用 KNN 法建立与每类数据点对应的网络结构，将数 据样本实例对应网络中的节点，使具有相同类别 的网络节点之间产生连边，并依据其连接特性计 算出每个节点的局部效率作为拓扑信息，应用基 于距离倒数的相似度作为两个节点产生连边概率 的物理特征，将拓扑特征与样本点的物理特征一 起作为判别测试点类别归属的依据，为了克服由 不同类别的数据样本点个数差异带来的影响，构 建了一种引入不平衡因子 的新型概率模型。本 文所建立的基于数据点物理特征和拓扑特征的分 类模型更加符合实际数据集样本点的分布情况， 实验验证了本文所提方法具有可行性和有效性， 与传统的分类器模型有着一定的区别。 1 相关概念 X = {x1, x2,· · ·, xN} k xi(i = 1,2,· · ·,N) vi(i = 1,2,· · ·,N) vi xi G(V,E,L) V {l1,l2,· · ·,lm} {xN+1, xN+2,· · ·, xN+m} k = 3 基于网络拓扑特征的不平衡数据分类算法包 括两个阶段：网络的构建和测试点的类别预测。 利用较为常见 的 K N N 法对训练数据集 中的每一个样本点，从其前 个 最近的邻居节点中找到标签信息相同的节点并在 两点之间建立一条有向边，每个数据样本点 与网络中的节点 对 应，且节点 与样本点 具有相同的标签类型， 建立网络邻接矩阵 A，这样就将整个数据集映射 成带有节点标签信息的网络 ， 是节点 集合，E 是边的集合，L = 是标签集合。 在预测阶段，利用文中构建的分类模型去判断测 试数据样本点 Y = 的标签类型， 对于已经判断过标签类型的测试节点，选择直接 丢弃的策略，不再归合到由训练点所建立的子网 络结构中，图 1 为本文实现数据分类的几个步骤 的图解，假设建立网络中 ，最终将测试点归 为整体性测度大的类别。 1.1 节点局部效率 复杂网络由图论逐渐发展而来，基于图论的 网络结构模型在表达数据之间的关系时具有明显 的优势[14-16] ，本文所提出的方法在计算网络节点 局部效率时正是建立在图论的基础上。网络中的 节点可以既是起点又是尾点，因此由数据样本点 的连接关系所建立的图是有向的，为了更多地挖 掘网络中的数据点之间的拓扑关系，在数据样本 点训练阶段，充分考虑每个节点的连接特性，赋 予节点不同的效率，使节点之间具有差异性，本 文计算网络节点的局部效率公式[17] 为 ·890· 智 能 系 统 学 报 第 14 卷
第5期 普事业，等：网络拓扑特征的不平衡数据分类 ·891· 6,D=0 为尾点的边；d,是节点i与j间的距离；6是一个 Pi= aΣd4D>0 (1) 很小的正数，利用数据样本点建立的网络分类器 式中：p:为节点的局部效率；D为以节点y为 可有效地减弱噪声和野点的影响，当节点是噪声 起点的有向边的个数；e表示以节点i为起点，j 点或野点时，其局部效率为6，可忽略不计。 ●正类 ● 正类 D:1d:0.62 ●正类 p:1.612 p:1.983 O负类 负类 D:1 负类 d:0.87 D:2d:1.54 D:3 p:1.298 d:1.24 p:0.413p:1.625 9a:1.0 】 D:2 D:3 p:1.215 ○p:1.124 -O Qd0.33 +0 0p:2.011 D:1d:0.54 p:0.895 p:1.852 (a)建立网络 (b)节点连接属性 (c)局部效率 ●正类 ●正类 ●正类 O负类 ○负类 负类 △测试类 △测试类 =1.866 02=0.374 ○负类 c=1.346 p2=0.819 (相似性测度 (e)整体性测度 (①分类结果 图1NT-DC的图解 Fig.1 The diagram of NT-IDC 1.2基于相似度的类别归属 pllu)决定，如果最大值不止一个，随机选择其中 将数据样本点映射成网络节点，则待测样本 一个。其解释性过程如图2所示，节点5处于由 点的类别归属与网络中的每个节点都有关系，一 节点1、2、3、4所围成的正方形的中心，且节点 般来说，距离越近的两个节点属于同类的可能性 1、3属于a类，节点2、4属于b类，计算未知标签 就越大。 节点与其余节点之间的距离，满足关系S15+S5= 基于这种思想，本文用距离倒数表示网络节 S25+S45,故节点5属于a类和b类的概率相等， 点之间的物理特征，则节点y,和y之间的相似度 此时随机选择所属类别。 可表示为 1 Si=D(i.j) b 节点1 节点2 式中Di,)代表节点和v,之间的欧式距离。 任给一个网络，未知标签信息的节点类别用 0表示，对网络中任意一对节点“和v,存在相应 节点5 的距离相似度Sv,则无标签节点u属于1的概 率为 ∑Su 节点4 节点3 pllu）)=h*ud b a ∑Sx th*,Index(v)≠0j 图2预测节点的标签说明 式中：，∈L;节点“的预测标签类别是由最大的 Fig.2 Description of the node label prediction
pi = δ, Di = 0 1 Di ∑ ei j di j, Di > 0 (1) pi vi Di vi ei j i j 式中： 为节点 的局部效率； 为以节点 为 起点的有向边的个数； 表示以节点 为起点， di j i j δ δ 为尾点的边； 是节点 与 间的距离； 是一个 很小的正数，利用数据样本点建立的网络分类器 可有效地减弱噪声和野点的影响，当节点是噪声 点或野点时，其局部效率为 ，可忽略不计。 正类 负类 正类 负类 正类 负类 (a) 建立网络 (c) 局部效率 p: 1.612 p:1.983 p:1.298 p:0.413 p:1.625 p:1.215 p:1.124 p:2.011 p:0.895 p:1.852 (b) 节点连接属性 D:1d:0.62 D:1d:0.54 D:2d:1.54 D:1 D:3 D:2 D:3 d:0.87 d:1.24 d:1.01 d:0.33 正类 负类 负类 (e) 整体性测度 (f) 分类结果 φ2= 0.374 φ2= 0.819 正类 负类 测试类 正类 负类 (d) 相似性测度 测试类 ε2= 1.866 ε2= 1.346 图 1 NT-IDC 的图解 Fig. 1 The diagram of NT-IDC 1.2 基于相似度的类别归属 将数据样本点映射成网络节点，则待测样本 点的类别归属与网络中的每个节点都有关系，一 般来说，距离越近的两个节点属于同类的可能性 就越大。 vi vj 基于这种思想，本文用距离倒数表示网络节 点之间的物理特征，则节点 和 之间的相似度 可表示为 S i, j = 1 D(i, j) 式中 D(i, j) 代表节点 vi 和 vj 之间的欧式距离。 u v S u,v u li 任给一个网络，未知标签信息的节点类别用 0 表示，对网络中任意一对节点 和 ，存在相应 的距离相似度 ，则无标签节点 属于 的概 率为 p(li |u) = ∑ {v|v,u ,Index(v)=li} S u,v ∑ {v|v,u ,Index(v),0} S u,v l 式中： i ∈ L ；节点 u 的预测标签类别是由最大的 p(li |u) S 1,5 +S 3,5 = S 2,5 +S 4,5 决定，如果最大值不止一个，随机选择其中 一个。其解释性过程如图 2 所示，节点 5 处于由 节点 1、2、3、4 所围成的正方形的中心，且节点 1、3 属于 a 类，节点 2、4 属于 b 类，计算未知标签 节点与其余节点之间的距离，满足关系 ，故节点 5 属于 a 类和 b 类的概率相等， 此时随机选择所属类别。 节点 1 节点 2 节点 4 a b ? b a 节点 3 节点 5 图 2 预测节点的标签说明 Fig. 2 Description of the node label prediction 第 5 期 普事业，等：网络拓扑特征的不平衡数据分类 ·891·
·892· 智能系统学报 第14卷 2不平衡数据分类 节点属于该类的可能性就越大，即判定节点属于 此类别。 本文算法是从网络节点的连接特性中提取出 2.3算法步骤和时间复杂度 拓扑特征与数据样本点的距离相似度，并一起用 算法网络拓扑特征的不平衡数据分类 于实现数据分类。具体地，在引入不平衡因子的 输入训练集X={(x1,C1),(,C2),…,(xw,Cw), 条件下，将子网络中每个节点的局部效率与节点 其中N是训练样本个数，每个数据样本点 间的欧式距离结合起来，根据测试样本点与每个 x={a1,a2,…,aa}都是一个d维特征向量，C,eL表 子网络的整体性测度来确定类别归属。 示第i个样本的标签；测试集Y={xw+,xw+2, 2.1相似性测度 xw+m;KNN中的参数k;不平衡因子c。 文献[10]中是将子网络效率与待测节点之间 输出测试集标签{Cw+1,CN+2,…,Cwtm。 的物理特征结合在一起，考虑到网络中摇摆节点 1)构建网络； 的存在，仅仅利用平均功率无法有效地分辨出对 2)根据式(1)计算网络节点局部效率； 分类结果影响较小的节点，为了更好地区别单个 3)根据式(2)计算待测节点与每个子网络的 节点对测试点分类结果的影响，本文将每个节点 相似性测度； 的局部效率分别与物理特征结合到一起，可以对 4)根据式(3)计算待测节点与每个子网络的 影响较小的样本点有较好的识别，其表达式为 整体性测度； (2) S.a 5)依据整体性测度的大小预测待测样本点的 标签。 式中：P:为网络中每个节点的局部效率；i是子网 对于本文所提算法的时间复杂度分析：假设 络n中的节点；m为每个测试点t与子网络n的 用于建立网络的样本点个数为N,邻居节点数为 相似性测度；P,>S时说明该测试点更符合节点i k,且满足k《N,以每个节点为起点的最大有向 所在的子网络结构模式。 边数为k,故整个网络中的有向边最多为kW条； 2.2整体性测度 1)构建网络时需要计算任意一对节点之间的距 传统的有监督和无监督的分类器构建多是以 数据样本点的物理特征作为判别依据，但实际数 离，耗时较长，计算量为OW2+kW);2)在计算节 据集中的数据点并不是孤立存在的，正如链路预 点局部效率时需要计算节点的度，其时间复杂度 测问题中一个节点的两个邻居节点之间是否建立 为OW);3)中计算待测点与每个子网络的相似性 连边除了受共同邻居个数的影响外，还与共同邻 测度，已知网络节点个数为N,故这一阶段时间 居的性质，如度、聚类系数和介数中心性等有 复杂度为OW；4)中最坏的情况是整个网络节点 关。把每个节点看成独立或同等分布是有缺陷 的类别数较多，其计算量不大于OW):5)中依据 的，不符合实际数据集的样本点之间的关系，利 测试样本点与哪类子网络的整体性测度大，就确 用整体性测度大小去判断待测样本点的类别归 定该节点的类别，这步完成需要时间量为O(1)。 属，正是将数据点的物理特征和关联特征结合在 通过上面的分析，把算法步骤各个阶段的时间复 起的体现，对于测试样本点t,整体性测度定义为 杂度整合到一起，得出本文方法时间复杂度为 Ei+C 9m= (3) OW2+kW+N+N+N+1),取最高阶，时间复杂度 ∑em+PmC 为OW),这与SVM的时间复杂度1oW)~OW23) 式中：n为任一子网络；m为整个网络中的子网络 仍具有可比性。 个数；pm为测试点t与子网络n的整体性测度；Pm 3实验结果及分析 为训练样本集中每类的训练样本数：c为不平衡 调节因子，用来降低由不同类别的样本个数差异 3.1评价指标 对分类结果造成的影响，对于不同的数据集c的 传统的分类方法多采用正确率（测试样本点 取值一般不同，c值的大小可根据不同类别的样 中正确分类的个数占总的个数的比例)作为评价 本个数确定，也可以通过网格搜索结合交叉验证 指标，其对应的混淆矩阵可用来表示实际分类情 的方法确定。最后根据待测节点t与每个子网络 况，见表1所示。表1中，TP+FN=W,FP+TN=W, 的整体性测度大小来确定标签信息，测度越高， N为测试样本正类数，N为测试样本负类数
2 不平衡数据分类 本文算法是从网络节点的连接特性中提取出 拓扑特征与数据样本点的距离相似度，并一起用 于实现数据分类。具体地，在引入不平衡因子的 条件下，将子网络中每个节点的局部效率与节点 间的欧式距离结合起来，根据测试样本点与每个 子网络的整体性测度来确定类别归属。 2.1 相似性测度 文献 [10] 中是将子网络效率与待测节点之间 的物理特征结合在一起，考虑到网络中摇摆节点 的存在，仅仅利用平均功率无法有效地分辨出对 分类结果影响较小的节点，为了更好地区别单个 节点对测试点分类结果的影响，本文将每个节点 的局部效率分别与物理特征结合到一起，可以对 影响较小的样本点有较好的识别，其表达式为 εtn = ∑ i pi S t,i (2) pi i n εtn t n pi > S t,i i 式中： 为网络中每个节点的局部效率； 是子网 络 中的节点； 为每个测试点 与子网络 的 相似性测度； 时说明该测试点更符合节点 所在的子网络结构模式。 2.2 整体性测度 t 传统的有监督和无监督的分类器构建多是以 数据样本点的物理特征作为判别依据，但实际数 据集中的数据点并不是孤立存在的，正如链路预 测问题中一个节点的两个邻居节点之间是否建立 连边除了受共同邻居个数的影响外，还与共同邻 居的性质，如度、聚类系数和介数中心性等有 关。把每个节点看成独立或同等分布是有缺陷 的，不符合实际数据集的样本点之间的关系，利 用整体性测度大小去判断待测样本点的类别归 属，正是将数据点的物理特征和关联特征结合在 一起的体现，对于测试样本点 ，整体性测度定义为 φtn = εtn +c ∑m n=1 εtn +ρn · c (3) n m φtn t n ρn c c c t 式中： 为任一子网络； 为整个网络中的子网络 个数； 为测试点 与子网络 的整体性测度； 为训练样本集中每类的训练样本数； 为不平衡 调节因子，用来降低由不同类别的样本个数差异 对分类结果造成的影响，对于不同的数据集 的 取值一般不同， 值的大小可根据不同类别的样 本个数确定，也可以通过网格搜索结合交叉验证 的方法确定。最后根据待测节点 与每个子网络 的整体性测度大小来确定标签信息，测度越高， 节点属于该类的可能性就越大，即判定节点属于 此类别。 2.3 算法步骤和时间复杂度 算法 网络拓扑特征的不平衡数据分类 X = {(x1,C1),(x2,C2),· · ·,(xN,CN)} N xi = {a1,a2,· · ·,ad} d Ci ∈ L i Y = {xN+1, xN+2,· · ·, xN+m} k c 输入 训练集 ， 其 中 是训练样本个数，每个数据样本点 都是一个 维特征向量， 表 示第 个样本的标签；测试集 ；KNN 中的参数 ；不平衡因子 。 输出 测试集标签 {CN+1,CN+2,· · ·,CN+m}。 1) 构建网络； 2) 根据式 (1) 计算网络节点局部效率； 3) 根据式 (2) 计算待测节点与每个子网络的 相似性测度； 4) 根据式 (3) 计算待测节点与每个子网络的 整体性测度； 5) 依据整体性测度的大小预测待测样本点的 标签。 N k k ≪ N k kN O(N 2 +kN) O(N) N O(N) O(N) O(1) O(N 2 +kN +N +N +N +1) O(N 2 ) O(N) ∼ O(N 2.3 ) 对于本文所提算法的时间复杂度分析：假设 用于建立网络的样本点个数为 ，邻居节点数为 ，且满足 ，以每个节点为起点的最大有向 边数为 ，故整个网络中的有向边最多为 条 ； 1) 构建网络时需要计算任意一对节点之间的距 离，耗时较长，计算量为 ；2) 在计算节 点局部效率时需要计算节点的度，其时间复杂度 为 ；3) 中计算待测点与每个子网络的相似性 测度，已知网络节点个数为 ，故这一阶段时间 复杂度为 ；4) 中最坏的情况是整个网络节点 的类别数较多，其计算量不大于 ；5) 中依据 测试样本点与哪类子网络的整体性测度大，就确 定该节点的类别，这步完成需要时间量为 。 通过上面的分析，把算法步骤各个阶段的时间复 杂度整合到一起，得出本文方法时间复杂度为 ，取最高阶，时间复杂度 为 ，这与 SVM 的时间复杂度[18] 仍具有可比性。 3 实验结果及分析 3.1 评价指标 传统的分类方法多采用正确率 (测试样本点 中正确分类的个数占总的个数的比例) 作为评价 指标，其对应的混淆矩阵可用来表示实际分类情 况，见表 1 所示。表 1 中，TP+FN=N + ，FP+TN=N − ， N +为测试样本正类数，N −为测试样本负类数。 ·892· 智 能 系 统 学 报 第 14 卷
第5期 普事业，等：网络拓扑特征的不平衡数据分类 ·893· 表1混淆矩阵 集上运行20次五折交叉验证取平均值，并将最大 Table 1 Confusion matrix 的Gm值和F-value值用黑体标出。 分类 预测正类 预测负类 3.2.1人造数据集 实际正类 TP FN 在二维空间中随机生成样本点不平衡比为 实际负类 FP TN 1000:50的线性不可分数据集（见图3），其样本点 符合正态分布，多数类含有1000个样本点，少数 然而，对于非平衡数据集则采用不平衡分类 类含有50个样本点，采用基于网络拓扑特征的不 中的敏感性Se和特异性Sp作为性能评价的两个 平衡数据分类方法与其他经典算法相比较，表2 辅助指标，几何平均值Gm和F-value作为综合性 给出了各算法在该数据集上的分类结果，从表中 指标，它们在一定程度上可用来衡量算法的优 可以看出，本文所提方法对不平衡数据集具有良 劣，其定义为 Se=TP/(TP+FN) 好的分类性能。 (4) Sp=TN/(FP+TN) (5) 6 Gm=SexSp (6) 式中：Se代表分类器在少数类样本上的预测能力： Sp代表分类器在多数类样本上的预测能力。Se和 Sp的值越大表示分类效果越好，但现实不平衡数据 中往往少数类样本携带更有价值的信息，所以在实 2 。负类 一3 际应用中更应该想着如何提高Se值。 ·正类 -3-2-10123456 F-value是查全率Rc和敏感性Se的平均值，B 是一个相对重要性参数，在不平衡数据分类问题 图3人工数据集 中一般设置为1，查全率定义为Rc=TP/TP+FP), Fig.3 Artificial data set 则指标F-value为 F-value=(1+B)xRcxSe 表2人工数据集的分类结果 (7) Table 2 The result of the artificial dataset B2xRc+Se 算法 Gm F-value 3.2实验结果及分析 为了验证本文所提分类方法的有效性，首先 SVM 0.8650 0.7659 用一个人造数据集给出证明，实验中得出的结果 FSVM 0.8977 0.7751 均是在MATLAB2012a软件上运行得出的，台式 SMOTE 0.8777 0.7449 计算机具体配置为：系统为64位的Windows10企 DEC 0.9057 0.7475 业版，处理器为Intel(R)Core(TM)i7-6700CPU,内 Under-sampling 0.9169 0.7672 存大小8GB。本文实验中非线性的核函数使用 NT-IDC 0.9249 0.7757 较为广泛的Gauss径向基(RBF)核函数。考虑到 SVM在数据分类上是具有代表性的算法，本文用 3.2.2真实数据集 来对比的算法均使用SVM作为基分类器，Under- 从UCI机器学习数据库选择了10组不平衡的 sampling中使用基于欧氏距离的欠采样方法u, 数据集来进行实验。所用数据集样本点个数范围 DEC中正负类样本的惩罚因子设置为样本个数 为214~5000，样本点的属性维数范围为3~34，有 不平衡比，SMOTE中最近邻个数设置k=5,通过 的数据集可能有多种类别，本文仅考虑二分类问 网格搜索算法得到A和惩罚参数C,所有对比算 题，对于类别不是两类的就先把数据集都变为两 法中惩罚参数C的候选集设定为{2,21，…，21，入 类，把其中某类或某几类看作正类，剩下的所有类 的候选集设定为(1,2，，20，均取最优时的数值参 合并为负类，10个数据集的详细信息如表3所示。 加计算。本文使用五折交叉验证的方法对数据集 为了验证算法在真实数据集上的有效性， 进行验证，每次迭代选择其中4组作为训练集， 表4和表5分别给出了不同算法在少数类和综合 1组作为测试集，每组训练集和测试集中的正负 指标性能上的对比结果。在表4中，本文算法在 类样本点数量差异均定义为不平衡比，把本文算 少数类预测能力上效果较好，除Yeast和Ecoli 法分类结果与SVM、FSVM、DEC、SMOTE和Un- 外，其余数据集都优于对比算法。表5中，相比 der-sampling算法结果进行比较，每种算法在数据 较SVM,其他算法在不平衡数据分类中的精度都
表 1 混淆矩阵 Table 1 Confusion matrix 分类 预测正类 预测负类 实际正类 TP FN 实际负类 FP TN 然而，对于非平衡数据集则采用不平衡分类 中的敏感性 Se 和特异性 Sp 作为性能评价的两个 辅助指标，几何平均值 Gm 和 F-value 作为综合性 指标，它们在一定程度上可用来衡量算法的优 劣，其定义为 Se = TP/(TP+FN) (4) Sp = TN/(FP+TN) (5) Gm = √ Se×Sp (6) 式中：Se 代表分类器在少数类样本上的预测能力； Sp 代表分类器在多数类样本上的预测能力。Se 和 Sp 的值越大表示分类效果越好，但现实不平衡数据 中往往少数类样本携带更有价值的信息，所以在实 际应用中更应该想着如何提高 Se 值。 β Rc = TP/(TP+FP) F-value 是查全率 Rc 和敏感性 Se 的平均值， 是一个相对重要性参数，在不平衡数据分类问题 中一般设置为 1，查全率定义为 ， 则指标 F-value 为 F−value = (1+β 2 )×Rc×Se β 2 ×Rc+Se (7) 3.2 实验结果及分析 k = 5 λ C C {2 0 ,2 1 ,· · ·,2 13} λ {1,2,· · ·,20} 为了验证本文所提分类方法的有效性，首先 用一个人造数据集给出证明，实验中得出的结果 均是在 MATLAB 2012a 软件上运行得出的，台式 计算机具体配置为：系统为 64 位的 Windows10 企 业版，处理器为 Intel(R) Core(TM) i7-6700CPU，内 存大小 8 GB。本文实验中非线性的核函数使用 较为广泛的 Gauss 径向基 (RBF) 核函数。考虑到 SVM 在数据分类上是具有代表性的算法，本文用 来对比的算法均使用 SVM 作为基分类器，Undersampling 中使用基于欧氏距离的欠采样方法[19] ， DEC 中正负类样本的惩罚因子设置为样本个数 不平衡比，SMOTE 中最近邻个数设置 ，通过 网格搜索算法得到 和惩罚参数 ，所有对比算 法中惩罚参数 的候选集设定为 ， 的候选集设定为 ，均取最优时的数值参 加计算。本文使用五折交叉验证的方法对数据集 进行验证，每次迭代选择其中 4 组作为训练集， 1 组作为测试集，每组训练集和测试集中的正负 类样本点数量差异均定义为不平衡比，把本文算 法分类结果与 SVM、FSVM、DEC、SMOTE 和 Under-sampling 算法结果进行比较，每种算法在数据 集上运行 20 次五折交叉验证取平均值，并将最大 的 Gm 值和 F-value 值用黑体标出。 3.2.1 人造数据集 在二维空间中随机生成样本点不平衡比为 1000:50 的线性不可分数据集 (见图 3)，其样本点 符合正态分布，多数类含有 1 000 个样本点，少数 类含有 50 个样本点，采用基于网络拓扑特征的不 平衡数据分类方法与其他经典算法相比较，表 2 给出了各算法在该数据集上的分类结果，从表中 可以看出，本文所提方法对不平衡数据集具有良 好的分类性能。 −4 −3 −2 −1 0 1 2 3 4 5 6 x −3 −2 −1 0 1 2 3 4 5 6 y 负类 正类 图 3 人工数据集 Fig. 3 Artificial data set 表 2 人工数据集的分类结果 Table 2 The result of the artificial dataset 算法 Gm F-value SVM 0.865 0 0.765 9 FSVM 0.897 7 0.775 1 SMOTE 0.877 7 0.744 9 DEC 0.905 7 0.747 5 Under-sampling 0.916 9 0.767 2 NT-IDC 0.924 9 0.775 7 3.2.2 真实数据集 从 UCI 机器学习数据库选择了 10 组不平衡的 数据集来进行实验。所用数据集样本点个数范围 为 214~5 000，样本点的属性维数范围为 3~34，有 的数据集可能有多种类别，本文仅考虑二分类问 题，对于类别不是两类的就先把数据集都变为两 类，把其中某类或某几类看作正类，剩下的所有类 合并为负类，10 个数据集的详细信息如表 3 所示。 为了验证算法在真实数据集上的有效性， 表 4 和表 5 分别给出了不同算法在少数类和综合 指标性能上的对比结果。在表 4 中，本文算法在 少数类预测能力上效果较好，除 Yeast 和 Ecoli 外，其余数据集都优于对比算法。表 5 中，相比 较 SVM，其他算法在不平衡数据分类中的精度都 第 5 期 普事业，等：网络拓扑特征的不平衡数据分类 ·893·