基于网络社区发现的标签传播聚类算法

高维数据的聚类特性通常难以直接观测. 将其构建为复杂网络, 节点间的拓扑结构可以反映样本之间的关系. 对网络中的节点进行社区发现, 可实现对数据更直观的聚类. 提出一种基于网络社区发现的低随机性标签传播聚类算法. 首先, 用半径和最近邻方法将数据集构建为稀疏的全连通网络. 之后, 根据节点相似度进行节点标签预处理, 使得相似的节点具有相同的标签. 用节点的影响力值改进标签传播过程, 降低标签选择的随机性. 最后, 基于内聚度进行社区的优化合并, 提高社区的质量. 在真实数据集和人工数据集上的实验结果表明, 该算法对各种类型的数据都具有较好的适应性.     

基于改进BP神经网络的非均衡数据分类算法

传统的分类算法大都默认所有类别的分类代价一致,导致样本数据非均衡时产生分类性能急剧下降的问题.对于非均衡数据分类问题,结合神经网络与降噪自编码器,提出一种改进的神经网络实现非均衡数据分类算法,在神经网络模型输入层与隐层之间加入一层特征受损层,致使部分冗余特征值丢失,降低数据集的不平衡度,训练模型得到最优参数后进行特征分类得到结果.选取UCI标准数据集的3组非均衡数据集进行实验,结果表明采用该算法对小数据集的分类精度有明显改善,但是数据集较大时,分类效果低于某些分类器.该算法的整体分类效果要优于其他分类器.     

类别混叠度对非均衡数据分类的有效性分析

类别混叠度是指不同类别数据之间互相交叠、混合的程度,其量化指标包含基于几何统计的和基于信息论的两类,用于衡量数据分类的难易。实际分类任务中存在大量的非均衡数据,大类与小类样本之间悬殊的数量差别给分类造成了极大的困难。本文采用实验研究的方法,验证类别混叠度量化指标指导非均衡数据分类的有效性,以减少甚至避免盲目试错带来的庞大计算开销。首先,针对两类分类问题,设计验证实验,在不同类数据非均衡率,不同别边界形状、不同特征类型、不同概率分布的非均衡仿真数据上研究类别混叠度的有效性。其次,在实验研究的基础上,分析数据的非均衡性对类别混叠度的影响规律,找出类别混叠度指导非均衡分类的有效方法。最后,在真实的非均衡数据上验证类别混叠度指导非均衡分类的实际效果。实验结果表明,对数据的非均衡率具有较强鲁棒性的类别混叠度量化指标可以有效地指导非均衡数据的分类器选择。     

基于距离度量学习的集成谱聚类

无监督学习聚类算法的性能依赖于用户在输入数据集上指定的距离度量,该距离度量直接影响数据样本之间的相似性计算,因此,不同的距离度量往往对数据集的聚类结果具有重要的影响。针对谱聚类算法中距离度量的选取问题,提出一种基于边信息距离度量学习的谱聚类算法。该算法利用数据集本身蕴涵的边信息,即在数据集中抽样产生的若干数据样本之间是否具有相似性的信息,进行距离度量学习,将学习所得的距离度量准则应用于谱聚类算法的相似度计算函数,并据此构造相似度矩阵。通过在UCI标准数据集上的实验进行分析,结果表明,与标准谱聚类算法相比,该算法的预测精度得到明显提高。     

社会网络顶点间相似性度量及其应用

集对分析作为处理系统确定性与不确定性相互作用的数学理论,可用来处理存在不确定关系的复杂社会网络。首先,应用集对分析理论,将社会网络作为一个同异反系统(确定不确定系统),采用集对联系度刻画顶点间的同异反关系,综合考虑顶点的局部特征和拓扑结构对顶点相似性的贡献,提出加权聚集系数联系度的顶点间相似性度量方法。该度量方法可以更好地刻画网络结构特征,克服传统局部相似性度量指标对某些顶点间相似性值的低估,降低全局相似性度量指标的计算复杂度。其次,为了将该相似性度量指标应用于社区发现,与凝聚型层次聚类算法相结合,使其适用于具有相似性度量对象的复杂网络社区发现问题。最后,在社会网络上进行社区挖掘实验,并与经典社区发现算法进行比较,实验结果表明了该相似性度量指标的正确性及有效性。     

基于联系度的主题关注网络社区发现方法研究

目前,以兴趣或主题分享等为目的的兴趣型社交网络则引领着社交网络改革的浪潮。融合社交关系和兴趣爱好关系构建一个新型社交网络模型--主题关注模型。在此模型基础上,采用集对联系度刻画顶点间相似性度量指标,该度量方法可以更好地刻画网络结构特征,提高传统局部相似性度量指标对某些顶点间相似性值的计算精度,降低全局相似性度量指标的计算复杂度。综合考虑主题影响和社交关系,将集对联系度与凝聚型聚类算法相结合,提出一种新的主题社区发现方法。在Karate网络和豆瓣数据集上进行主题社区发现,实验结果表明,考虑主题影响的划分具有更好的社区结构。     

状态依赖的类内聚度量

类是面向对象软件中的模块,包含属性和方法。类内聚度量是对类属性和方法相关程度的度量。通过对类方法和属性的分类及其与类状态之间的关系分析,提出了类核的概念和状态依赖的类内聚度量方法。该方法有利于克服类内聚度量复杂性和判断模糊性问题,并可以在设计阶段对类的内聚进行度量。     

一种加权稠密子图社区发现算法

目前,针对复杂网络的社区发现算法大多仅根据网络的拓扑结构来确定社区,然而现实复杂网络中的边可能带有表示连接紧密程度或者可信度意义的权重,这些先验信息对社区发现的准确性至关重要.针对该问题,提出了基于加权稠密子图的重叠聚类算法（overlap community detection on weighted networks,简称OCDW）.首先,综合考虑网络拓扑结构及真实网络中边权重的影响,给出了一种网络中边的权重定义方法;进而给出种子节点选取方式和权重更新策略;最终得到聚类结果.OCDW算法在无权网络和加权网络都适用.通过与一些经典的社区发现算法在9个真实网络数据集上进行分析比较,结果表明算法OCDW在F度量、准确度、分离度、标准互信息、调整兰德系数、模块性及运行时间等方面均表现出较好的性能.     

基于深度编码器的复杂网络社区发现算法 #br#

复杂网络是复杂系统的典型表现形式,社区结构是复杂网络最重要的结构特征之一。针对目前社区发现算法精确度低以及不适合大规模网络的问题,提出一种新的算法DA-EF和用于度量节点之间相似度的影响力扩散指标。DA-EF利用多层自动编码器与森林编码器构成二级级联模型,相似度矩阵进行降维和表征学习处理,转化成低维高阶特征矩阵,最终使用K-means得到准确的社区划分结果。级联结构在保持算法同等深度的情况下,大幅降低了算法时间复杂度。在人工合成数据集和真实数据集上的实验表明,DA-EF与同类算法K-means、DA-EML和CoDDA相比,其标准互信息NMI和模块度Q值高,而且聚类运行时间最少,具有精确度高和效率快的优势。在算法性能实验中,验证了算法的级联结构、自动编码器的深度以及影响力扩散指标的合理性和有效性。     

QoS多层本体的双向度量模型

针对传统质量评估模式中指标权重赋值依据单一的问题,首先将服务描述本体分为共享本体和专属本体两个抽象层次,构建具有“抽象-应用-度量”多层结构的QoS本体,用于QoS度量的对象描述和数据采集;然后建立基于深度信任网络和回归模型的双向度量模型DM-QSM,将服务描述信息和类似服务历史数据作为训练样本数据集对DM-QSM进行正向训练,再结合用户反馈对DM-QSM进行逆向调优,以实现QoS度量指标权重及其偏好度的自适应调节。最后选用可编程建模环境NetLogo为实验平台、公共服务数据集QWS为训练样本集、电子商务应用服务为测试样本集,验证了DM-QSM的可行性和有效性。     

多任务学习的不平衡SVM+算法

处理不平衡数据分类时,传统支持向量机技术（SVM）对少数类样本识别率较低。鉴于SVM+技术能利用样本间隐藏信息的启发,提出了多任务学习的不平衡SVM+算法（MTL-IC-SVM+）。MTL-IC-SVM+基于SVM+将不平衡数据的分类表示为一个多任务的学习问题,并从纠正分类面的偏移出发,分别赋予多数类和少数类样本不同的错分惩罚因子,且设置少数类样本到分类面的距离大于多数类样本到分类面的距离。UCI数据集上的实验结果表明,MTL-IC-SVM+在不平衡数据分类问题上具有较高的分类精度。     

A genetic algorithm-based rule extraction system

Individual classifiers predict unknown objects. Although, these are usually domain specific, and lack the property of scaling up prediction while handling data sets with huge size and high-dimensionality or imbalance class distribution. This article introduces an accuracy-based learning system called DTGA (decision tree and genetic algorithm) that aims to improve prediction accuracy over any classification problem irrespective to domain, size, dimensionality and class distribution. More specifically, the proposed system consists of two rule inducing phases. In the first phase, a base classifier, C4.5 (a decision tree based rule inducer) is used to produce rules from training data set, whereas GA (genetic algorithm) in the next phase refines them with the aim to provide more accurate and high-performance rules for prediction. The system has been compared with competent non-GA based systems: neural network, Naïve Bayes, rule-based classifier using rough set theory and C4.5 (i.e., the base classifier of DTGA), on a number of benchmark datasets collected from UCI (University of California at Irvine) machine learning repository. Empirical results demonstrate that the proposed hybrid approach provides marked improvement in a number of cases.     

面向不均衡数据的融合谱聚类的自适应过采样法

分类是模式识别领域中的研究热点,大多数经典的分类器往往默认数据集是分布均衡的,而现实中的数据集往往存在类别不均衡问题,即属于正常/多数类别的数据的数量与属于异常/少数类数据的数量之间的差异很大。若不对数据进行处理往往会导致分类器忽略少数类、偏向多数类,使得分类结果恶化。针对数据的不均衡分布问题,本文提出一种融合谱聚类的综合采样算法。首先采用谱聚类方法对不均衡数据集的少数类样本的分布信息进行分析,再基于分布信息对少数类样本进行过采样,获得相对均衡的样本,用于分类模型训练。在多个不均衡数据集上进行了大量实验,结果表明,所提方法能有效解决数据的不均衡问题,使得分类器对于少数类样本的分类精度得到提升。     

基于马氏距离的孪生多分类支持向量机

孪生支持向量机(TWSVM)的研究是近来机器学习领域的一个热点。TWSVM具有分类精度高、训练速度快等优点,但训练时没有充分利用样本的统计信息。作为TWSVM的改进算法,基于马氏距离的孪生支持向量机(TMSVM)在分类过程中考虑了各类样本的协方差信息,在许多实际问题中有着很好的应用效果。然而TMSVM的训练速度有待提高,并且仅适用于二分类问题。针对这两个问题,将最小二乘思想引入TMSVM,用等式约束取代TMSVM中的不等式约束,将二次规划问题的求解简化为求解两个线性方程组,得到基于马氏距离的最小二乘孪生支持向量机(LSTMSVM),并结合有向无环图策略(DAG)设计出基于马氏距离的最小二乘孪生多分类支持向量机。为了减少DAG结构的误差累积,构造了基于马氏距离的类间可分性度量。人工数据集和UCI数据集上的实验均表明,所提算法不仅有效,而且相对于传统多分类SVM,其分类性能有明显提高。     

Imbalanced classification of mental workload using a cost-sensitive majority weighted minority oversampling strategy

Identifying the temporal variations in mental workload level (MWL) is crucial for enhancing the safety of human–machine system operations, especially when there is cognitive overload or inattention of human operator. This paper proposed a cost-sensitive majority weighted minority oversampling strategy to address the imbalanced MWL data classification problem. Both the inter-class and intra-class imbalance problems are considered. For the former, imbalance ratio is defined to determine the number of the synthetic samples in the minority class. The latter problem is addressed by assigning different weights to borderline samples in the minority class based on the distance and density meaures of the sample distribution. Furthermore, multi-label classifier is designed based on an ensemble of binary classifiers. The results of analyzing 21 imbalanced UCI multi-class datasets showed that the proposed approach can effectively cope with the imbalanced classification problem in terms of several performance metrics including geometric mean (G-mean) and average accuracy (ACC). Moreover, the proposed approach was applied to the analysis of the EEG data of eight experimental participants subject to fluctuating levels of mental workload. The comparative results showed that the proposed method provides a competing alternative to several existing imbalanced learning algorithms and significantly outperforms the basic/referential method that ignores the imbalance nature of the dataset.     

A multi-objective optimisation approach for class imbalance learning

Class imbalance limits the performance of most learning algorithms since they cannot cope with large differences between the number of samples in each class, resulting in a low predictive accuracy over the minority class. In this respect, several papers proposed algorithms aiming at achieving more balanced performance. However, balancing the recognition accuracies for each class very often harms the global accuracy. Indeed, in these cases the accuracy over the minority class increases while the accuracy over the majority one decreases. This paper proposes an approach to overcome this limitation: for each classification act, it chooses between the output of a classifier trained on the original skewed distribution and the output of a classifier trained according to a learning method addressing the course of imbalanced data. This choice is driven by a parameter whose value maximizes, on a validation set, two objective functions, i.e. the global accuracy and the accuracies for each class. A series of experiments on ten public datasets with different proportions between the majority and minority classes show that the proposed approach provides more balanced recognition accuracies than classifiers trained according to traditional learning methods for imbalanced data as well as larger global accuracy than classifiers trained on the original skewed distribution.     

Online Feature Selection of Class Imbalance via PA Algorithm

Imbalance classification techniques have been frequently applied in many machine learning application domains where the number of the majority (or positive) class of a dataset is much larger than that of the minority (or negative) class. Meanwhile, feature selection (FS) is one of the key techniques for the high-dimensional classification task in a manner which greatly improves the classification performance and the computational efficiency. However, most studies of feature selection and imbalance classification are restricted to off-line batch learning, which is not well adapted to some practical scenarios. In this paper, we aim to solve high-dimensional imbalanced classification problem accurately and efficiently with only a small number of active features in an online fashion, and we propose two novel online learning algorithms for this purpose. In our approach, a classifier which involves only a small and fixed number of features is constructed to classify a sequence of imbalanced data received in an online manner. We formulate the construction of such online learner into an optimization problem and use an iterative approach to solve the problem based on the passive-aggressive (PA) algorithm as well as a truncated gradient (TG) method. We evaluate the performance of the proposed algorithms based on several real-world datasets, and our experimental results have demonstrated the effectiveness of the proposed algorithms in comparison with the baselines.     

基于集成的非均衡数据分类主动学习算法

当前,处理类别非均衡数据采用的主要方法之一就是预处理,将数据均衡化之后采取传统的方法加以训练.预处理的方法主要有过取样和欠取样,然而过取样和欠取样都有自己的不足,提出拆分提升主动学习算法SBAL( Split-Boost Active Learning),该算法将大类样本集根据非均衡比例分成多个子集,子集与小类样本集合并,对其采用AdaBoost算法训练子分类器,然后集成一个总分类器,并基于QBC( Query-by-committee)主动学习算法主动选取有效样本进行训练,基本避免了由于增加样本或者减少样本所带来的不足.实验表明,提出的算法对于非均衡数据具有更高的分类精度.     

基于留一交叉验证的类不平衡危害预评估策略

近年来,类不平衡问题已逐渐成为人工智能﹑机器学习和数据挖掘等领域的研究热点,目前已有大量实用有效的方法.然而,近期的研究结果却表明,并非所有的不平衡数据分类任务都是有害的,在无害的任务上采用类不平衡学习算法将很难提高,甚至会降低分类的性能,同时可能大幅度增加训练的时间开销.针对此问题,提出了一种危害预评估策略.该策略采用留一交叉验证法(LOOCV,Leave-one-out cross validation)测试训练集的分类性能,并据此计算一种称为危害测度(HM,Harmful-ness Measure)的新指标,用以量化危害的大小,从而为学习算法的选择提供指导.通过8个类不平衡数据集对所提策略进行了验证,表明该策略是有效和可行的.     

A dynamic over-sampling procedure based on sensitivity for multi-class problems

Classification with imbalanced datasets supposes a new challenge for researches in the framework of machine learning. This problem appears when the number of patterns that represents one of the classes of the dataset (usually the concept of interest) is much lower than in the remaining classes. Thus, the learning model must be adapted to this situation, which is very common in real applications. In this paper, a dynamic over-sampling procedure is proposed for improving the classification of imbalanced datasets with more than two classes. This procedure is incorporated into a memetic algorithm (MA) that optimizes radial basis functions neural networks (RBFNNs). To handle class imbalance, the training data are resampled in two stages. In the first stage, an over-sampling procedure is applied to the minority class to balance in part the size of the classes. Then, the MA is run and the data are over-sampled in different generations of the evolution, generating new patterns of the minimum sensitivity class (the class with the worst accuracy for the best RBFNN of the population). The methodology proposed is tested using 13 imbalanced benchmark classification datasets from well-known machine learning problems and one complex problem of microbial growth. It is compared to other neural network methods specifically designed for handling imbalanced data. These methods include different over-sampling procedures in the preprocessing stage, a threshold-moving method where the output threshold is moved toward inexpensive classes and ensembles approaches combining the models obtained with these techniques. The results show that our proposal is able to improve the sensitivity in the generalization set and obtains both a high accuracy level and a good classification level for each class.