第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·
·894· 智能系统学报 第14卷 有了一定的提高，当不平衡比率较大时，SVM的 对于数据集Haberman、Ecoli和waveform,本 分类效果会变得较差，DEC算法虽然考虑了数据 文算法的Gm值平均提高了2%左右，但是在数 的不平衡性，但没能很好地考虑到样本点的分布 据集Yeast和Vowel上，由于节点之间的关联信 情况，本文算法则较好地处理了这一问题，对样 息不明显，算法所能挖掘的网络信息受限，对部 本点间有关联特征的数据集如Haberman、Ecoli、 分测试点无法做出正确地判断，没有取得最好 Glass、Imagesegment、wireless和contraceptive本文 的效果，但与SVM、FSVM、DEC、SMOTE和Un- 算法均取得了最优的分类结果。 der-sampling分类方法所取得分类结果相差不 表3数据集信息 大，表明NT-DC算法仍有待改进。对于正负类 Table 3 Dataset information 总样本正类负类属性 不平衡 样本不平衡比率大的数据集，因为本文算法提 数据集 数量 数 数 度 比率 高了少数类分类性能，在Gm值一定的前提下， Haberman 306 81 225 3 2.78 当FP值变大时，Rc值变小，使得Glass、Vow- Ecoli 336 3 259 3.36 el和Yeast数据集上的F-value值有所波动，在处 Glass 214 13 201 10 15.46 理样本点个数较多的数据集如waveform上正 Innosphere 351 126 225 34 1.78 是因为考虑了数据点间的关联信息，所以才表 Yeast 1484 511433 28.10 Vowel 990 90 900 13 ⊙ 现出一定的优越性。综上分析，本文所提算法 wireless 2000 5001500 > J 在考虑到影响不平衡数据分类因素的条件下， Imagesegment 2310 3301980 19 6 表现出良好的分类性能，充分说明了将数据点 waveform 5000 16573343 2 2.02 之间关联特征作为数据分类性能影响因素的合 contraceptive 1473 333 1140 9 3.42 理性。 表4少数类分类结果 Table 4 The classification result of minority class 数据集 SVM FSVM DEC SMOTE Under-sampling NT-IDC Haberman 0.1989 0.4338 0.4346 0.5074 0.6010 0.6972 Ecoli 0.8087 0.8967 0.9083 0.9342 0.9483 0.9478 Glass 0.7288 0.7667 0.8337 0.9000 0.8667 0.9772 Innosphere 0.8332 0.8338 0.8403 0.8566 0.8425 0.8807 Yeast 0.4013 0.4919 0.8036 0.7956 0.8259 0.8218 Vowel 0.9112 0.9000 0.9467 0.9013 0.9612 0.9778 wireless 0.9640 0.9640 0.9720 0.9720 0.9660 0.9720 Imagesegment 0.9896 0.9911 0.9909 1.0000 1.0000 1.0000 waveform 0.8343 0.8248 0.7917 0.7892 0.7978 0.8668 contraceptive 0.3874 0.3272 0.5012 0.4801 0.5469 0.5885 表5数据集在不同算法下的分类结果 Table 5 The classification results of datasets under different algorithms 数据集 指标 SVM FSVM DEC SMOTE Under-sampling NT-IDC Haberman Gm 0.4213 0.5961 0.6314 0.6393 0.6496 0.6787 F-value 0.3126 0.4702 0.4698 0.4968 0.5233 0.5337 Ecoli Gm 0.8914 0.9257 0.9111 0.9395 0.9360 0.9580 F-value 0.8041 0.8800 0.8634 0.8867 0.8662 0.9243 Glass Gm 0.8346 0.8576 0.9113 0.9328 0.9309 0.9407 F-value 0.7314 0.7076 0.7457 0.8114 0.7619 0.7318 Innosphere Gm 0.9040 0.8941 0.8923 0.9066 0.8894 0.9173
有了一定的提高，当不平衡比率较大时，SVM 的 分类效果会变得较差，DEC 算法虽然考虑了数据 的不平衡性，但没能很好地考虑到样本点的分布 情况，本文算法则较好地处理了这一问题，对样 本点间有关联特征的数据集如 Haberman、Ecoli、 Glass、Imagesegment、wireless 和 contraceptive 本文 算法均取得了最优的分类结果。 表 3 数据集信息 Table 3 Dataset information 数据集 总样本 数量 正类 数 负类 数 属性 度 不平衡 比率 Haberman 306 81 225 3 2.78 Ecoli 336 77 259 8 3.36 Glass 214 13 201 10 15.46 Innosphere 351 126 225 34 1.78 Yeast 1 484 51 1 433 8 28.10 Vowel 990 90 900 13 10 wireless 2 000 500 1 500 7 3 Imagesegment 2 310 330 1 980 19 6 waveform 5 000 1 657 3 343 21 2.02 contraceptive 1 473 333 1 140 9 3.42 对于数据集 Haberman、Ecoli 和 waveform，本 文算法的 Gm 值平均提高了 2% 左右，但是在数 据集 Yeast 和 Vowel 上，由于节点之间的关联信 息不明显，算法所能挖掘的网络信息受限，对部 分测试点无法做出正确地判断，没有取得最好 的效果，但与 SVM、FSVM、DEC、SMOTE 和 Under-sampling 分类方法所取得分类结果相差不 大，表明 NT-IDC 算法仍有待改进。对于正负类 样本不平衡比率大的数据集，因为本文算法提 高了少数类分类性能，在 Gm 值一定的前提下， 当 FP 值变大时，Rc 值变小，使得 Glass、 Vowel 和 Yeast 数据集上的 F-value 值有所波动，在处 理样本点个数较多的数据集如 waveform 上正 是因为考虑了数据点间的关联信息，所以才表 现出一定的优越性。综上分析，本文所提算法 在考虑到影响不平衡数据分类因素的条件下， 表现出良好的分类性能，充分说明了将数据点 之间关联特征作为数据分类性能影响因素的合 理性。 表 4 少数类分类结果 Table 4 The classification result of minority class 数据集 SVM FSVM DEC SMOTE Under-sampling NT-IDC Haberman 0.198 9 0.433 8 0.434 6 0.507 4 0.601 0 0.697 2 Ecoli 0.808 7 0.896 7 0.908 3 0.934 2 0.948 3 0.947 8 Glass 0.728 8 0.766 7 0.833 7 0.900 0 0.866 7 0.977 2 Innosphere 0.833 2 0.833 8 0.840 3 0.856 6 0.842 5 0.880 7 Yeast 0.401 3 0.491 9 0.803 6 0.795 6 0.825 9 0.821 8 Vowel 0.911 2 0.900 0 0.946 7 0.901 3 0.961 2 0.977 8 wireless 0.964 0 0.964 0 0.972 0 0.972 0 0.966 0 0.972 0 Imagesegment 0.989 6 0.991 1 0.990 9 1.000 0 1.000 0 1.000 0 waveform 0.834 3 0.824 8 0.791 7 0.789 2 0.797 8 0.866 8 contraceptive 0.387 4 0.327 2 0.501 2 0.480 1 0.546 9 0.588 5 表 5 数据集在不同算法下的分类结果 Table 5 The classification results of datasets under different algorithms 数据集 指标 SVM FSVM DEC SMOTE Under-sampling NT-IDC Haberman Gm 0.421 3 0.596 1 0.631 4 0.639 3 0.649 6 0.678 7 F-value 0.312 6 0.470 2 0.469 8 0.496 8 0.523 3 0.533 7 Ecoli Gm 0.891 4 0.925 7 0.911 1 0.939 5 0.936 0 0.958 0 F-value 0.804 1 0.880 0 0.863 4 0.886 7 0.866 2 0.924 3 Glass Gm 0.834 6 0.857 6 0.911 3 0.932 8 0.930 9 0.940 7 F-value 0.731 4 0.707 6 0.745 7 0.811 4 0.761 9 0.731 8 Innosphere Gm 0.904 0 0.894 1 0.892 3 0.906 6 0.889 4 0.917 3 ·894· 智 能 系 统 学 报 第 14 卷
第5期 普事业，等：网络拓扑特征的不平衡数据分类 ·895· 续表5 数据集 指标 SVM FSVM DEC SMOTE Under-sampling NT-IDC F-value 0.8930 0.8756 0.8681 0.8883 0.8722 0.8996 Yeast Gm 0.5733 0.6895 0.8311 0.8323 0.8422 0.8304 F-value 0.3955 0.4758 0.6233 0.6217 0.7044 0.6004 Vowel Gm 0.9417 0.9358 0.9611 0.9214 0.9688 0.9642 F-value 0.8388 0.8940 0.9532 0.9033 0.9421 0.8572 wireless Gm 0.9304 0.9781 0.9809 0.9813 0.9802 0.9822 F-value 0.9253 0.9707 0.9710 0.9802 0.9761 0.9785 Imagesegment Gm 0.9732 0.9833 0.9954 0.9981 0.9997 0.9997 F-value 0.9459 0.9741 0.9954 0.9844 0.9910 0.9912 waveform Gm 0.8381 0.8427 0.8447 0.8545 0.8655 0.8805 F-value 0.7834 0.8011 0.8148 0.8137 0.7901 0.8207 contraceptive Gm 0.5584 0.5135 0.5862 0.5860 0.6021 0.6035 F-value 0.3712 0.3308 0.4019 0.4076 0.4327 0.4329 3.3参数敏感性分析 Ecoli,当c值大于2的时候，本文算法所取得的 为了更好地了解本文算法中参数对数据分类 Gm值波动范围较小，但Innosphere数据集对c值 效果的影响，在实际数据集Haberman、Glass、 比较敏感，实验过程中较难根据经验确定c的取 Inno-sphere、Ecoli,和Imagesegment.上分析不平衡 值；相比℃，参数k的取值对分类精度影响较小， 因子c(见图4)和KNN中的参数k(见图5)对分类 当k值从10增加到100时，除Innosphere外，其他 性能的影响。 数据集的Gm值并没有太大的波动，说明不平衡 1.0r 数据分类的问题中，正负类数据点样本个数的差 0.8 异对分类性能有较大影响，需要采用合适的策略 解 和方法来降低不平衡比。 …Ecoli(k=20 怎04 4结束语 .Glass (=30) --Hamberman (k=20) 0.2 --Imagesegment (K=50) 本文针对不平衡数据分类问题，考虑到传统 Innosphere (=44) 分类方法在实际数据集中存在的缺陷，提出一种 0 4 6 不平衡因子c 更符合数据集样本点真实关系的数据分类方法， 图4参数c对准确率Gm的影响 算法中除利用数据点的物理特征外，还充分挖掘 Fig.4 The influence of parameter c on accuracy Gm 了由这些数据点所建立的网络拓扑特征，实验结 果表明基于网络结构去解决不平衡数据分类问题 1.0 ◆ - 士 是一个可行的途径，除此之外，本文提出的算法 0.8 仍能够应用于多分类问题。在未来的研究中，将 的 0.6 探索如何更有效地挖掘隐藏在网络中的节点行 …Ecoli(c=2) 怎0.4 Glass (c=3.4) 为，找到更加符合数据样本点之间的拓扑特征， --Hamberman (c=4.7) 例如考虑除节点局部效率外的其他性质，不同的 0.2 -◆←Imagesegment(c=1) Innosphere (c=0.15) 数据集c值选取一般不固定，后续可以在参数的 20 4060 80100 优化上做进一步的研究。 近邻个数k 参考文献： 图5参数k对准确率Gm的影响 Fig.5 The influence of parameter k on accuracy Gm [1]HE Haibo,GARCIA E A.Learning from imbalanced 从图4中观察到，不平衡因子c对Gm影响 data[J].IEEE transactions on knowledge and data engin- 较明显，对于数据集Imagesegment、Glass和 eering,2009,21(9)1263-1284
3.3 参数敏感性分析 c k 为了更好地了解本文算法中参数对数据分类 效果的影响，在实际数据集 Haberman、Glass、 Inno-sphere、Ecoli、和 Imagesegment 上分析不平衡 因子 (见图 4) 和 KNN 中的参数 (见图 5) 对分类 性能的影响。 0 2 4 6 不平衡因子 c 0.2 0.4 0.6 0.8 1.0 Gm 准确率 Ecoli (k=20) Glass (k=30) Hamberman (k=20) Imagesegment (k=50) Innosphere (k=44) 图 4 参数 c 对准确率 Gm 的影响 Fig. 4 The influence of parameter c on accuracy Gm 近邻个数 k Gm 准确率 Ecoli (c=2) Glass (c=3.4) Hamberman (c=4.7) Imagesegment (c=1) Innosphere (c=0.15) 0 20 40 60 80 100 0.2 0.4 0.6 0.8 1.0 图 5 参数 k 对准确率 Gm 的影响 Fig. 5 The influence of parameter k on accuracy Gm 从图 4 中观察到，不平衡因子 c 对 Gm 影响 较明显，对于数据集 Imagesegment、 Glass 和 c c c c k k Ecoli，当 值大于 2 的时候，本文算法所取得的 Gm 值波动范围较小，但 Innosphere 数据集对 值 比较敏感，实验过程中较难根据经验确定 的取 值；相比 ，参数 的取值对分类精度影响较小， 当 值从 10 增加到 100 时，除 Innosphere 外，其他 数据集的 Gm 值并没有太大的波动，说明不平衡 数据分类的问题中，正负类数据点样本个数的差 异对分类性能有较大影响，需要采用合适的策略 和方法来降低不平衡比。 4 结束语 c 本文针对不平衡数据分类问题，考虑到传统 分类方法在实际数据集中存在的缺陷，提出一种 更符合数据集样本点真实关系的数据分类方法， 算法中除利用数据点的物理特征外，还充分挖掘 了由这些数据点所建立的网络拓扑特征，实验结 果表明基于网络结构去解决不平衡数据分类问题 是一个可行的途径，除此之外，本文提出的算法 仍能够应用于多分类问题。在未来的研究中，将 探索如何更有效地挖掘隐藏在网络中的节点行 为，找到更加符合数据样本点之间的拓扑特征， 例如考虑除节点局部效率外的其他性质，不同的 数据集 值选取一般不固定，后续可以在参数的 优化上做进一步的研究。 参考文献： HE Haibo, GARCIA E A. Learning from imbalanced data[J]. IEEE transactions on knowledge and data engineering, 2009, 21(9): 1263–1284. [1] 续表5 数据集 指标 SVM FSVM DEC SMOTE Under-sampling NT-IDC F-value 0.893 0 0.875 6 0.868 1 0.888 3 0.872 2 0.899 6 Yeast Gm 0.573 3 0.689 5 0.831 1 0.832 3 0.842 2 0.830 4 F-value 0.395 5 0.475 8 0.623 3 0.621 7 0.704 4 0.600 4 Vowel Gm 0.941 7 0.935 8 0.961 1 0.921 4 0.968 8 0.964 2 F-value 0.838 8 0.894 0 0.953 2 0.903 3 0.942 1 0.857 2 wireless Gm 0.930 4 0.978 1 0.980 9 0.981 3 0.980 2 0.982 2 F-value 0.925 3 0.970 7 0.971 0 0.980 2 0.976 1 0.978 5 Imagesegment Gm 0.973 2 0.983 3 0.995 4 0.998 1 0.999 7 0.999 7 F-value 0.945 9 0.974 1 0.995 4 0.984 4 0.991 0 0.991 2 waveform Gm 0.838 1 0.842 7 0.844 7 0.854 5 0.865 5 0.880 5 F-value 0.783 4 0.801 1 0.814 8 0.813 7 0.790 1 0.820 7 contraceptive Gm 0.558 4 0.513 5 0.586 2 0.586 0 0.602 1 0.603 5 F-value 0.371 2 0.330 8 0.401 9 0.407 6 0.432 7 0.432 9 第 5 期 普事业，等：网络拓扑特征的不平衡数据分类 ·895·
·896· 智能系统学报 第14卷 [2]KHOSHGOFTAAR T M,GOLAWALA M,VAN HULSE tions on neural networks,1993,4(1):127-135 J.An empirical study of learning from imbalanced data us- [15]WANG Meng,FU Weijie,HAO Shijie,et al.Learning on ing random forest[Cl//Proceedings of the 19th IEEE Inter- big graph:label inference and regularization with anchor national Conference on Tools with Artificial Intelligence. hierarchy[J].IEEE transactions on knowledge and data Patras,Greece,2007:310-317. engineering,2017,29(5):1101-1114. [3]LIN Chunfu,WANG Shengde.Fuzzy support vector ma- [16]CONG Chen,LIU Tongliang,TAO Dacheng,et al.De- chines[J].IEEE transactions on neural networks,2002, formed graph laplacian for semisupervised learning[J]. 13(2):464-471. IEEE transactions on neural networks and learning sys- [4]程险峰，李军，李雄飞.一种基于欠采样的不平衡数据分 tems,2015,26(10):2261-2274. 类算法).计算机工程，2011,37(13)147-149. [17刀顾苏杭，王土同.基于数据点本身及其位置关系辅助信 CHENG Xianfeng,LI Jun,LI Xiongfei.Imbalanced data 息挖掘的分类方法J几.模式识别与人工智能，2018. classification algorithm based on undersampling[J].Com- 31(3y197-207 puter engineering,2011,37(13):147-149. GU Suhang,WANG Shitong.Classification approach by [5]CHAWLA N V,BOWYER K W,HALL L O,et al. mining betweenness information beyond data points SMOTE:synthetic minority over-sampling technique[J]. themselves[J].Pattern recognition and artificial intelli- Journal of artificial intelligence research,2011,16(1): gence,2018,31(3:197-207. 321-357. [18]TSANG I W H.KWOK JT Y.ZURADA J M.General- [6]VEROPOULOS K.CAMPBELL I C G.CRISTIANINI N. ized core vector machines[J].IEEE transactions on neural Controlling the sensitivity of support vector machines[Cl// networks,2006,17(5):1126-1140. Proceedings of the International Joint Conference on Arti- [19]赵自翔，王广亮，李晓东.基于支持向量机的不平衡数 ficial Intelligence.Stockholm,Sweden,1999:55-60. 据分类的改进欠采样方法[).中山大学学报（自然科学 [7]张银峰，郭华平，职为梅，等.一种面向不平衡数据分类 版)，2012,51(6)：10-16. 的组合剪枝方法).计算机工程，2014,40(6)：157-161， ZHAO Zixiang,WANG Guangliang,LI Xiaodong.An 165 improved SVM based under-sampling method for classi- ZHANG Yinfeng,GUO Huaping,ZHI Weimei,et al.An fying imbalanced data[J].Acta Scientiarum Naturalium ensemble pruning method for imbalanced data classifica- Universitatis Sunyatseni,2012,51(6):10-16. tion[J].Computer engineering,2014,40(6):157-161,165. 作者简介： [8]SILVA T C.ZHAO Liang.Network-based high level data 普事业，男，1993年生，硕士研究 classification[J].IEEE transactions on neural networks and 生，主要研究方向为数据挖掘、复杂 learning systems,2012,23(6):954-970. 网络。 [9]SILVA TC,ZHAO Liang.High-level pattern-based classi- fication via tourist walks in networks[J].Information sci- ences,2015,294:109-126. [10]CARNEIRO M G,ZHAO Liang.Organizational data classification based on the importance concept of com- 刘三阳，男，1959年生，教授，博 plex networks[J].IEEE transactions on neural networks 土生导师，主要研究方向为最优化方 and learning systems,2018,29(8):3361-3373. 法及其应用研究、系统建模、信息网 [11]BERTINI JR J R,ZHAO Liang,MOTTA R,et al.A non- 络。先后主持国家自然科学基金项目 parametric classification method based on K-associated 5项、教育部项目10多项，获国家级 graphs[J].Information sciences,2011,181(24):5435- 教学成果奖3项。发表学术论文 5456. 500余篇，包括全球热点论文和 [12]LU Linyuan,ZHOU Tao.Link prediction in complex net- E$I高引论文及2015年中国百篇最具影响力学术论文，出 works:A survey[J].Physical A:statistical mechanics and 版教材10余部，其中2部获国家级奖项。 its applications,2011,390(6):1150-1170. 白艺光.男，1993年生，博士研究 [13]ZHANG Qianming,SHANG Mingsheng,LU Linyuan. 生，主要研究方向为复杂网络功能及 Similarity-based classification in partially Labeled net- 鲁棒性、大规模并行优化在网络中的 works[J].International journal of modern physical C, 应用。发表学术论文7篇。 2010.21(6:813-824. [14]BIRX D L,PIPENBERG S J.A complex mapping net- work for phase sensitive classification[J].IEEE transac-
KHOSHGOFTAAR T M, GOLAWALA M, VAN HULSE J. An empirical study of learning from imbalanced data using random forest[C]//Proceedings of the 19th IEEE International Conference on Tools with Artificial Intelligence. Patras, Greece, 2007: 310–317. [2] LIN Chunfu, WANG Shengde. Fuzzy support vector machines[J]. IEEE transactions on neural networks, 2002, 13(2): 464–471. [3] 程险峰, 李军, 李雄飞. 一种基于欠采样的不平衡数据分 类算法 [J]. 计算机工程, 2011, 37(13): 147–149. CHENG Xianfeng, LI Jun, LI Xiongfei. Imbalanced data classification algorithm based on undersampling[J]. Computer engineering, 2011, 37(13): 147–149. [4] CHAWLA N V, BOWYER K W, HALL L O, et al. SMOTE: synthetic minority over-sampling technique[J]. Journal of artificial intelligence research, 2011, 16(1): 321–357. [5] VEROPOULOS K, CAMPBELL I C G, CRISTIANINI N. Controlling the sensitivity of support vector machines[C]// Proceedings of the International Joint Conference on Artificial Intelligence. Stockholm, Sweden, 1999: 55–60. [6] 张银峰, 郭华平, 职为梅, 等. 一种面向不平衡数据分类 的组合剪枝方法 [J]. 计算机工程, 2014, 40(6): 157–161, 165. ZHANG Yinfeng, GUO Huaping, ZHI Weimei, et al. An ensemble pruning method for imbalanced data classification[J]. Computer engineering, 2014, 40(6): 157–161, 165. [7] SILVA T C, ZHAO Liang. Network-based high level data classification[J]. IEEE transactions on neural networks and learning systems, 2012, 23(6): 954–970. [8] SILVA T C, ZHAO Liang. High-level pattern-based classification via tourist walks in networks[J]. Information sciences, 2015, 294: 109–126. [9] CARNEIRO M G, ZHAO Liang. Organizational data classification based on the importance concept of complex networks[J]. IEEE transactions on neural networks and learning systems, 2018, 29(8): 3361–3373. [10] BERTINI JR J R, ZHAO Liang, MOTTA R, et al. A nonparametric classification method based on K-associated graphs[J]. Information sciences, 2011, 181(24): 5435– 5456. [11] LÜ Linyuan, ZHOU Tao. Link prediction in complex networks: A survey[J]. Physical A: statistical mechanics and its applications, 2011, 390(6): 1150–1170. [12] ZHANG Qianming, SHANG Mingsheng, LÜ Linyuan. Similarity-based classification in partially Labeled networks[J]. International journal of modern physical C, 2010, 21(6): 813–824. [13] BIRX D L, PIPENBERG S J. A complex mapping network for phase sensitive classification[J]. IEEE transac- [14] tions on neural networks, 1993, 4(1): 127–135. WANG Meng, FU Weijie, HAO Shijie, et al. Learning on big graph: label inference and regularization with anchor hierarchy[J]. IEEE transactions on knowledge and data engineering, 2017, 29(5): 1101–1114. [15] CONG Chen, LIU Tongliang, TAO Dacheng, et al. Deformed graph laplacian for semisupervised learning[J]. IEEE transactions on neural networks and learning systems, 2015, 26(10): 2261–2274. [16] 顾苏杭, 王士同. 基于数据点本身及其位置关系辅助信 息挖掘的分类方法 [J]. 模式识别与人工智能, 2018, 31(3): 197–207. GU Suhang, WANG Shitong. Classification approach by mining betweenness information beyond data points themselves[J]. Pattern recognition and artificial intelligence, 2018, 31(3): 197–207. [17] TSANG I W H, KWOK J T Y, ZURADA J M. Generalized core vector machines[J]. IEEE transactions on neural networks, 2006, 17(5): 1126–1140. [18] 赵自翔, 王广亮, 李晓东. 基于支持向量机的不平衡数 据分类的改进欠采样方法 [J]. 中山大学学报(自然科学 版), 2012, 51(6): 10–16. ZHAO Zixiang, WANG Guangliang, LI Xiaodong. An improved SVM based under-sampling method for classifying imbalanced data[J]. Acta Scientiarum Naturalium Universitatis Sunyatseni, 2012, 51(6): 10–16. [19] 作者简介： 普事业，男，1993 年生，硕士研究 生，主要研究方向为数据挖掘、复杂 网络。 刘三阳，男，1959 年生，教授，博 士生导师，主要研究方向为最优化方 法及其应用研究、系统建模、信息网 络。先后主持国家自然科学基金项目 5 项、教育部项目 10 多项，获国家级 教学成果奖 3 项。发表学术论文 5 0 0 余篇，包括全球热点论文 和 ESI 高引论文及 2015 年中国百篇最具影响力学术论文，出 版教材 10 余部，其中 2 部获国家级奖项。 白艺光，男，1993 年生，博士研究 生，主要研究方向为复杂网络功能及 鲁棒性、大规模并行优化在网络中的 应用。发表学术论文 7 篇。 ·896· 智 能 系 统 学 报 第 14 卷