1 引言

信息化时代加快了数据量的增长速度, 各行各业的数据总数日渐庞大, 为在海量数据资源中挖掘出隐藏规律, 聚类算法应运而生且重要性日益显著. 在同一数据集中, 若某类别样本个数远超出余下类别样本个数, 则该数据集叫做不平衡数据^[1]. 此类数据多用于故障诊断、目标检测等实际应用中, 但当前算法大部分都是以数据集均衡分布为前提的, 在处理不平衡数据时极易偏向多数类, 产生错分情况, 降低分类准度, 所以, 研究不平衡数据集的数据挖掘方法具有重要的实践意义.

向鸿鑫等人^[2]通过总结常用的不平衡数据预处理方法与挖掘算法, 从多维度梳理策略性能, 分析各应用领域的不平衡问题与解决方案后, 实现不平衡数据挖掘方法综述; 蔡莉等人^[3]构建出一种时空特征位置数据融合模型, 通过数据与算法层面, 解决不平衡数据的挖掘问题, 利用架构的综合评价指标, 反映聚类质量, 融合不平衡数据后, 完成热点区域挖掘; 文献[4]中许统德等人设计的多层级联式少数类聚类高精度数据挖掘算法中, 在聚类欠采样的前提下, 聚类多数类样本, 获取与少数类相同数量的质心, 架构新的平衡训练集, 采用合成少数类过采样技术(Synthetic Minority Oversampling TEchnique, SMOTE)过采样, 级联K-means聚类与C4.5决策树算法, 改善分类决策边界.

鉴于上述文献方法在融合不平衡数据样本时存在一定的盲目性, 故基于谱聚类欠取样, 采用自编码网络来构架一种不平衡数据挖掘方法. 通过谱聚类方法聚类多数类数据, 在更改数据空间结构的基础上, 有选择地欠取样处理了多数类数据集, 通过选取代表性数据作为训练数据, 经过数据筛选, 使分类边界适当偏移, 提升划分准确率; 利用自编码器升、降维数据, 实现初始数据重构; 引入网络调整操作, 增加了目标领域网络的学习空间, 使其与目标领域样本特征表示更匹配.

2 谱聚类欠取样分类

谱聚类就是按照谱图理论^[5]完成数据分类, 将聚类问题转换成无向图多路径划分问题.

用 $G = \left( {V,\;E} \right)$ 界定无向图, 其顶点集合为 $V = \{ {v_1}, $ $ {v_2},\cdots,{v_n} \}$ , 数据样本有n个, 若无向图 $G$ 为一个加权图, 则顶点 ${v_i}$ 与 ${v_j}$ 的连边为 ${w_{ij}}$ , 且 ${w_{ij}} > 0$ , 当 ${w_{ij}} = V$ 时, 说明两顶点之间不存在连接的边. 假设无向图加权连边矩阵的界定式是 $W' = \left( {{w_{ij}}} \right)$ , 且加权连接边满足 ${w_{ij}} = {w_{ji}}$ , 则顶点 ${v_i} \subset V$ 的度界定表达式为:

${d'_i} = \sum\limits_{j = 1}^n {{w_{ij}}} $

(1)

采用下列公式界定无向图G的度矩阵:

$D = {\rm{diag}}\left( {{{d'}_1},{{d'}_2},\cdots,{{d'}_n}} \right)$

(2)

通过标准化处理无向图 $G$ , 推导出下列拉普拉斯^[6]矩阵表达式:

${L_{\rm{sym}}} = I - {D^{ - \frac{1}{2}}}W'{D^{ - \frac{1}{2}}}$

(3)

谱聚类算法流程具体描述如下:

(1) 输入聚类个数k与相似矩阵 $\sigma \in {R^{n\times n}}$ ;

(2) 利用相似矩阵 $\sigma \in {R^{n\times n}}$ 完成无向图 $G = \left( {V,E} \right)$ 的构建, 其加权连接矩阵用 $W'$ 表示;

(3) 经过标准化处理建立拉普拉斯矩阵;

(4) 对拉普拉斯矩阵的前 $k$ 个特征向量进行求解, 得到 $\;{\mu _1},{\mu _2},\cdots,{\mu _k}$ ;

(5) 将所得 $\;{\mu _1},{\mu _2},\cdots,{\mu _k}$ 特征向量当做列, 构建矩阵 $U \in {R^{n\times k}}$ ;

(6) 标准化处理矩阵U各行, 令特征向量 $\;{\mu _{ij}}$ 满足等式 ${t_{ij}} = {\mu _{ij}}{\left( {\displaystyle\sum\nolimits_k {\mu _{ij}^2} } \right)^{\frac{1}{2}}}$ , 完成矩阵 $T \in {R^{n\times k}}$ 架构;

(7) 利用 ${t_i} \in {R^k}$ 构成矩阵T的第i行向量, 其中, i=1, 2,…,n;

(8) 通过K-means算法^[7]聚类 ${\left( {{t_i}} \right)_{i = 1,2,\cdots,n}}$ 所含数据, 组建为一个子集, 用 ${C_1},{C_2},\cdots,{C_k}$ 表示;

(9) 得到最终聚类结果 ${A_1},\cdots,{A_k}$ , 其中, ${A_i} = $ $ \left\{ {j\left| {{t_j} \in {C_j}} \right.} \right\}$ .

在不平衡数据挖掘过程中, 多数类数据通常会携带多个冗余数据信息与噪声数据, 导致分类边界偏移至少数类数据方向, 加大错分概率, 若想解决该问题, 就要对多数类数据实施相应处理, 即欠取样处理, 使分类边界偏移至多数类数据方向. 传统欠取样处理方法多为去除与边界距离较远的数据点, 或随机去除多数类数据, 这种不考虑数据信息的处理手段虽然均衡了不同类数据集, 但分类界限调整得并不够理想, 因此, 采用谱聚类方法聚类多数类数据, 在更改数据空间结构的基础上, 有选择地欠取样处理了多数类数据集, 通过选取代表性数据作为训练数据, 经过数据筛选, 获取分类边界偏移量.

3 基于自编码网络的不平衡数据挖掘

通过训练令网络输入与输出相等, 完成数据隐藏特征学习的一种神经网络模型就是自编码器 (AutoEncoder, AE)^[8], 作为深度学习网络的一种主要结构, 自编码网络在深度神经网络预训练中被广泛应用. 该网络即便不用带标签数据样本, 也能够达成训练目的, 也就是说, 其学习过程属于无监督学习. 自编码网络中的编码阶段是输入数据学习至高效表示特征, 解码阶段是以习得的隐藏特征为依据, 实现初始数据重构. 自编码器经过升、降维数据, 把提取出来的数据特征转换为适用、高效的隐藏特征后, 输送至有监督学习模型内, 即可实现挖掘目标. 图1所示为自编码器的基本框架形式, 由输入层、输出层以及隐含层组成, 近似于一个3层神经网络^[9].

假设 $\left( {{x_1},{x_2},\cdots,{x_i}} \right)$ 是一个输入样本, Sigmoid激活函数^[10]用S表示, 输入层与隐含层间、隐含层与输出层间的权值分别为 ${W_1}$ 与 ${W_2}$ , 则自编码器前向传播表达式如式(4)和式(5)所示.

$d = {\textit{S}}\left( {{W_1}x + {b_1}} \right)$

(4)

${h_{w,b}}\left( x \right) = {\textit{S}}\left( {{W_2}d + {b_2}} \right)$

(5)

式中, 偏置项为b_i, 输出层激活值为 ${h_{w,b}}\left( x \right)$ .

由于自编码器的训练标准期望是输入与输出相等, 所以, 采用下列表达式描述自编码器的最终学习结果:

${h_{w,{\textit{b}}}}\left( x \right) \approx x$

(6)

根据各隐藏单元数, 获取各维度隐藏特征, 升、降维处理初始数据, 通过堆叠多个自编码器, 结合约束条件, 实现各层面的数据高效表示学习.

利用无监督学习与有监督学习, 在谱聚类欠取样条件下架构用于挖掘不平衡数据的自编码网络. 因为无标签样本数据在源领域与目标领域中均可轻易取得, 因此, 当最大均值差异^[11]比预设阈值低时, 直接跳过网络调整阶段, 无监督训练目标领域数据; 反之, 当最大均值差异比预设阈值高时, 按照图2中所示的自编码网络形式进行调整, 并完成随机初始化. 网络调整操作增加了目标领域网络的学习空间, 使其与目标领域样本特征表示更匹配.

在自编码网络中输入谱聚类欠取样处理的不平衡数据集合, 依照以下流程实现数据挖掘:

(1) 设定 ${\textit{Major}}N = m×MinorN$ 为待训练数据, 其中, 多数类数据是 ${\textit{Major}}N$ , 少数类数据是 $MinorN$ , 两类个数比例是m.

(2) 若多数类数据样本有n个, 则高斯核^[12]相似矩阵表达式如下:

$\sigma \in {R^{n\times n}}$

(7)

(3) 利用谱聚类方法处理n个多数类数据样本, 获得聚类结果 ${A_1},{A_2},\cdots,{A_k}$ , ${\textit{Major}}N = k$ .

(4) 根据各聚类结果以及聚类中心与少数类数据点的间距大小, 选取代表性数据点, 使分类界面偏移至多数类样本, 并最大程度删除多数类数据点的边界点. 各聚类结果中, 数据点选用数量随着多数类样本个数的增加而增多, 随着聚类中心与少数类数据点间距的增加而上升, 基于此, 采用下列选取公式, 筛选出有效数据点.

${\textit{K}}Dis{t_{il}} = {\textit{K}}\left( {{x_i},{x_i}} \right) + {\textit{K}}\left( {{x_l},{x_l}} \right) - 2{\textit{K}}\left( {{x_i},{x_l}} \right)$

(8)

${\textit{I}}Dis{t_i} = \frac{1}{{{\textit{K}}si{\textit{z}}{e_i}\times MinorN}}\sum\limits_{i = 1}^{{\textit{K}}si{\textit{z}}{e_i}} {\sum\limits_{l = 1}^{MinorN} {{\textit{K}}Dis{t_{il}}} } $

(9)

$Radi{o_i} = \frac{{Ksi{\textit{z}}{e_i}}}{{\displaystyle\sum\limits_{i=1}^k {Ksi{\textit{z}}{e_i}} }}\times \frac{{IDis{t_i}}}{{\displaystyle\sum\limits_{i=1}^k {IDis{t_i}} }}$

(10)

${\textit{SS}}i{\textit{z}}e_{MA}^i = {\textit{Major}}N\times \frac{{Radi{o_i}}}{{\displaystyle\sum\limits_{i = 1}^k {Radi{o_i}} }}$

(11)

式里, ${\textit{K}}si{\textit{z}}{e_i}$ 表示聚类A_i的大小, ${\textit{I}}Dis{t_i}$ 表示聚类A_i与少数类数据的间距均值, ${\textit{SS}}i{\textit{z}}e_{MA}^i$ 表示各聚类所选样本个数.

(5) 采用各聚类结果里与少数类数据点间距均值最小的前 ${\textit{SS}}i{\textit{z}}e_{MA}^i$ 个数据点, 成为多数类样本中的训练子集数据.

(6) 训练上述多数类代表数据点与所有少数类数据, 将处理完的数据输入自编码网络, 在相同数据空间中, 实现其与谱聚类算法的无缝连接, 选取相同参数, 令网络和参数与谱聚类相似矩阵保持一致.

(7) 根据上述训练得出的分类界面, 完成不平衡数据挖掘.

4 不平衡数据挖掘模拟分析 4.1 数据集选取

选用具有不同实际应用背景的UCI数据集^[13], 从中抽取sonar、breast-w、vehicle、artificial、pendigits、letter、page-blocks、car、seg1、yeast5等10组数据作为测试集(如表1所示), 验证挖掘策略的有效性. 当数据包含多个类别时, 设定任意一类为少数类, 多数类则为其余各类别的合并结果, 所有不平衡数据集均经过谱聚类欠取样处理.

将表1中的不平衡度划分成下列等级表, 如表2所示.

sonar与breast-w两个低度不平衡等级数据集的选取原因是验证挖掘方法在处理一般数据集时的有效性.

4.2 性能评估指标

针对不平衡数据集, 采用合理的查全率 $Recall$ 、查准率 $Precision$ 、综合F-measure、AUC(Area Under ROC Curve, ROC曲线下方图面积)值、G-means等类别不平衡评估指标, 使少数类挖掘情况得以充分反映, 各指标均以表3中所示的混淆矩阵为依据完成创建.

其中, 具有描述少数类分类性能的指标为F-measure, 是查全率与查准率的调和均值; AUC作为不同判决阈值对应的分类性能反映指标, 性能随数值的增加而提升. 各评估指标表达式分别如下所示:

${{Precision }} = \frac{{TP}}{{TP + FP}}$

(12)

${{Recall }} = \frac{{TP}}{{TP + FN}}$

(13)

$F {\text{-}} {{ measure }} = \frac{{{2\times}{{{ Recall}}\times}{{ Precision }}}}{{{{ Recall }} + {{ Precision }}}}$

(14)

$AUC = \frac{{T{P_{{{{\rm{rate}} }}}} + T{N_{{{{\rm{rate}} }}}}}}{2}$

(15)

$G {\text{-}} {{ means }} = \sqrt {T{P_{{{{\rm{rate}} }}}}\times{N_{{{{\rm{rate}} }}}}} $

(16)

式中, ${\textit{T}}P_{\rm{rate}}$ 表示多类样本准确率, ${\textit{T}}N_{\rm{rate}}$ 表示少类样本准确率.

4.3 不平衡数据挖掘效果

分别模拟文献[2-4]方法以及本文方法在挖掘10组不平衡数据集时的效果, 通过对比不同方法的评估指标数据, 验证方法的适用性与可行性. 对比结果如表4–表6所示.

结合上列各表可以看出, 各方法少数类评估指标均随着不平衡度的增加而略有下降; 少数类样本数据个数总量相对较少, 导致文献[2-4]方法的F-measure值整体偏低; 造成文献方法AUC值与G-means指标较低的原因是未考虑样本属性间的相关性, 忽略了监督判别性的类别标签信息; 而本文方法因引用了自编码网络, 根据各隐藏单元数, 获取各维度隐藏特征, 实现了各层面的数据高效表示学习, 通过对比最大均值差异比预设阈值, 完成了网络调整与随机初始化, 利用K-means算法与自编码网络, 充分结合了无监督学习与有监督学习形式, 因此, 取得了较为理想的少数类样本分类效果.

5 结论

在多个实际应用数据里找到可用且易于用户理解的知识, 这一过程就叫做数据挖掘. 当挖掘的数据集内某类别样本个数与另外类别样本个数相差较大时, 该种数据集即为不平衡数据. 随着信息时代与大数据时代的来临, 网络入侵检测、文本分类、医疗诊断等各种领域中普遍存在不平衡数据, 一旦出现错分情况, 将引发极大损失, 因此, 本文以自编码网络为核心, 提出一种谱聚类欠取样下的不平衡数据挖掘方法. 由于时间限制, 方法未对运行时间展开针对性的改善, 准备将其作为下一步工作的研究重点, 结合创新型、组合型算法, 缩短挖掘时长; 谱聚类方法以图谱理论为基础, 因KNN图复杂度相对更低, 因此, 在今后的研究中需探索一种近似于KNN图的图构建方法, 减小复杂度.