·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 卷