·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] )、不同惩罚因子的方法 (differ￾ent 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 卷