核聚类快速后向传播算法

后向传播神经网络算法是一种经典的分类算法,但是通常该算法训练时间较长。针对这种不足,提出了一种基于核聚类的快速后向传播算法。利用核聚类将原始样本划分为多个簇,对每一个簇计算簇中心样本,利用所有的簇中心样本作为新训练集进行神经网络学习。在UCI标准数据集和说话人识别数据集上的仿真实验,充分说明了算法较传统后向传播算法具有明显的速度优势。     

面向主动学习的模糊核聚类采样算法

针对主动学习中构造初始分类器难以选取代表性样本的问题,提出一种模糊核聚类采样算法。该算法首先通过聚类分析技术将样本集划分,然后分别在类簇中心和类簇边界区域选取样本进行标注,最后依此构造初始分类器。在该算法中,通过高斯核函数把原始样本空间中的点非线性变换到高维特征空间,以达到线性可聚的目的,并引入了一种基于局部密度的初始聚类中心选择方法,从而改善聚类效果。为了提高采样质量,结合划分后各类簇的样本个数设计了一种采样比例分配策略。同时,在采样结束阶段设计了一种后补采样策略,以确保采样个数达标。实验结果分析表明,所提算法可以有效地减少构造初始分类器所需的人工标注负担,并取得较高的分类正确率。     

CORES: fusion of supervised and unsupervised training methods for a multi-class classification problem

This paper describes in full detail a model of a hierarchical classifier (HC). The original classification problem is broken down into several subproblems and a weak classifier is built for each of them. Subproblems consist of examples from a subset of the whole set of output classes. It is essential for this classification framework that the generated subproblems would overlap, i.e. some individual classes could belong to more than one subproblem. This approach allows to reduce the overall risk. Individual classifiers built for the subproblems are weak, i.e. their accuracy is only a little better than the accuracy of a random classifier. The notion of weakness for a multiclass model is extended in this paper. It is more intuitive than approaches proposed so far. In the HC model described, after a single node is trained, its problem is split into several subproblems using a clustering algorithm. It is responsible for selecting classes similarly classified. The main scope of this paper is focused on finding the most appropriate clustering method. Some algorithms are defined and compared. Finally, we compare a whole HC with other machine learning approaches.     

一种处理多类分类问题的强化支持向量机方法

提出了一种强化支持向量机方法,将支持向量机与强化学习结合,逐步对未知类别标记样本进行访问,根据对该样本分类结果正确与否的评价标记访问点的类别,并对当前的分类器进行更新,给出了更新分类器的规则。对模拟数据和真实数据分别进行了实验,表明该方法在保证分类精度的同时,大大降低了对已知类别标记的训练样本的数量要求,是处理已知类别标记样本获取困难的多类分类问题的一种有效的方法。     

A heuristic supervised Euclidean data difference dimension reduction for KNN classifier and its application to visual place classification

In this paper, we propose a novel supervised dimension reduction algorithm based on K-nearest neighbor (KNN) classifier. The proposed algorithm reduces the dimension of data in order to improve the accuracy of the KNN classification. This heuristic algorithm proposes independent dimensions which decrease Euclidean distance of a sample data and its K-nearest within-class neighbors and increase Euclidean distance of that sample and its M-nearest between-class neighbors. This algorithm is a linear dimension reduction algorithm which produces a mapping matrix for projecting data into low dimension. The dimension reduction step is followed by a KNN classifier. Therefore, it is applicable for high-dimensional multiclass classification. Experiments with artificial data such as Helix and Twin-peaks show ability of the algorithm for data visualization. This algorithm is compared with state-of-the-art algorithms in classification of eight different multiclass data sets from UCI collection. Simulation results have shown that the proposed algorithm outperforms the existing algorithms. Visual place classification is an important problem for intelligent mobile robots which not only deals with high-dimensional data but also has to solve a multiclass classification problem. A proper dimension reduction method is usually needed to decrease computation and memory complexity of algorithms in large environments. Therefore, our method is very well suited for this problem. We extract color histogram of omnidirectional camera images as primary features, reduce the features into a low-dimensional space and apply a KNN classifier. Results of experiments on five real data sets showed superiority of the proposed algorithm against others.     

基于K-means的朴素贝叶斯分类算法的研究

将K-means算法引入到朴素贝叶斯分类研究中,提出一种基于K-means的朴素贝叶斯分类算法。首先用K-means算法对原始数据集中的完整数据子集进行聚类,计算缺失数据子集中的每条记录与k个簇重心之间的相似度,把记录赋给距离最近的一个簇,并用该簇相应的属性均值来填充记录的缺失值,然后用朴素贝叶斯分类算法对处理后的数据集进行分类。实验结果表明,与朴素贝叶斯相比,基于K-means思想的朴素贝叶斯算法具有较高的分类准确率。     

基于多维网格空间的改进K-means聚类算法

K-means算法是被广泛使用的一种聚类算法,传统的K-means算法中初始聚类中心的选择具有随机性,易使算法陷入局部最优,聚类结果不稳定。针对此问题,引入多维网格空间的思想,首先将样本集映射到一个虚拟的多维网格空间结构中,然后从中搜索出包含样本数最多且距离较远的子网格作为初始聚类中心网格,最后计算出各初始聚类中心网格中所包含样本的均值点来作为初始聚类中心。此法选择出来的初始聚类中心与实际聚类中心拟合度高,进而可据此初始聚类中心稳定高效地得到最终的聚类结果。通过使用计算机模拟数据集和UCI机器学习数据集进行测试,结果表明改进算法的迭代次数和错误率比较稳定,且均小于传统K-means算法测试结果的平均值,能有效避免陷入局部最优,并且聚类结果稳定。     

基于支持向量机与无监督聚类相结合的中文网页分类器

提出了一种将支持向量机与无监督聚类相结合的新分类算法,给出了一种新的网页表示方法并应用于网页分类问题。该算法首先利用无监督聚类分别对训练集中正例和反例聚类,然后挑选一些例子训练SVM并获得SVM分类器,任何网页可以通过比较其与聚类中心的距离决定采用无监督聚类方法或SVM分类器进行分类。该算法充分利用了SVM准确率高与无监督聚类速度快的优点。实验表明它不仅具有较高的训练效率,而且有很高的精确度。     

基于K-means的朴素贝叶斯分类算法的研究

将K-means算法引入到朴素贝叶斯分类研究中，提出一种基于K-means的朴素贝叶斯分类算法。首先用K-means算法对原始数据集中的完整数据子集进行聚类，计算缺失数据子集中的每条记录与k个簇重心之间的相似度，把记录赋给距离最近的一个簇，并用该簇相应的属性均值来填充记录的缺失值，然后用朴素贝叶斯分类算法对处理后的数据集进行分类。实验结果表明，与朴素贝叶斯相比，基于K-means思想的朴素贝叶斯算法具有较高的分类准确率。     

The Effect of Target Vector Selection on the Invariance of Classifier Performance Measures

In this paper, the multiclass supervised training problem is considered when a discrete set of classes is assumed. Upon generating affine models for finite data sets, we have observed the invariance of certain measures of performance after a trained classifier has been presented with test data of unknown classification. Specifically, after constructing mappings between training vectors and their desired targets, the class membership and ranking of test data has been found to remain either invariant or close to invariant under a transformation of the set of target vectors. Therefore, we derive conditions explaining how this type of invariance can arise when the multiclass problem is phrased in the context of linear networks. A bioinformatics example is then presented in order to demonstrate various principles outlined in this work.     

一种改进的K-means聚类算法

聚类是数据挖掘中的一种重要数据分析方法,K-means是一种基于划分的聚类算法。针对K-means算法中每次调整簇中心后确定新的簇中心需要大量的距离计算,提出一种利用簇中心的变化信息来确定新簇中心的方法,通过从动态簇中心集中选取候选集的方法减少了过滤算法的计算复杂度。理论分析表明,此算法在每一个迭代阶段能有效的减少距离计算数和计算时间。当数据集越大,维度越高时,算法的优越性越显著。     

改进SMOTE的不平衡数据集成分类算法

针对不平衡数据集的低分类准确性,提出基于改进合成少数类过采样技术（SMOTE）和AdaBoost算法相结合的不平衡数据分类算法（KSMOTE-AdaBoost）。首先,根据K近邻（KNN）的思想,提出噪声样本识别算法,通过样本的K个近邻中所包含的异类样本数目,对样本集中的噪声样本进行精确识别并予以滤除;其次,在过采样过程中基于聚类的思想将样本集划分为不同的子簇,根据子簇的簇心及其所包含的样本数目,在簇内样本与簇心之间进行新样本的合成操作。在样本合成过程中充分考虑类间和类内数据不平衡性,对样本及时修正以保证合成样本质量,平衡样本信息;最后,利用AdaBoost算法的优势,采用决策树作为基分类器,对平衡后的样本集进行训练,迭代多次直到满足终止条件,得到最终分类模型。选择G-mean、AUC作为评价指标,通过在6组KEEL数据集进行对比实验。实验结果表明,所提的过采样算法与经典的过采样算法SMOTE、自适应综合过采样技术（ADASYN）相比,G-means和AUC在4组中有3组最高;所提分类模型与现有的不平衡分类模型SMOTE-Boost,CUS-Boost,RUS-Boost相比,6组数据中：G-means均高于CUS-Boost和RUS-Boost,有3组低于SMOTE-Boost;AUC均高于SMOTE-Boost和RUS-Boost,有1组低于CUS-Boost。验证了所提的KSMOTE-AdaBoost具有更好的分类效果,且模型泛化性能更高。     

一种改进K-means聚类的FCMM算法

针对K-means算法易受初始聚类中心影响而陷入局部最优的问题,提出一种基于萤火虫智能优化和混沌理论的FCMM算法。首先利用最大最小距离算法确定聚类类别值K和初始聚类中心位置;然后以各聚类中心为基准点,利用Tent映射构建混沌空间,通过混沌搜索更新聚类中心,以降低初始聚类中心过于临近的影响,并改善算法易陷入局部最优的问题。仿真结果表明,FCMM算法的平均聚类精度相较于经典K-means算法和FA算法分别提高了7.51%和2.2%,成功避免算法陷入局部最优解,提高了划分初始数据集的效率和寻优精度。     

结合自然和共享最近邻的密度峰值聚类算法

基于快速搜索和寻找密度峰值聚类算法(DPC)具有无需迭代且需要较少参数的优点,但其仍然存在一些缺点:需要人为选取截断距离参数;在流形数据集上的处理效果不佳。针对这些问题,提出一种密度峰值聚类改进算法。该算法结合了自然和共享最近邻算法,重新定义了截断距离和局部密度的计算方法,并且算法融合了候选聚类中心计算概念,通过算法选出不同的候选聚类中心,然后以这些候选中心为新的数据集,再次开始密度峰值聚类,最后将剩余的点分配到所对应的候选中心点所在类簇中。改进的算法在合成数据集和UCI数据集上进行验证,并与K-means、DBSCAN和DPC算法进行比较。实验结果表明,提出的算法在性能方面有明显提升。     

K-Harmonic means type clustering algorithm for mixed datasets

K-means type clustering algorithms for mixed data that consists of numeric and categorical attributes suffer from cluster center initialization problem. The final clustering results depend upon the initial cluster centers. Random cluster center initialization is a popular initialization technique. However, clustering results are not consistent with different cluster center initializations. K-Harmonic means clustering algorithm tries to overcome this problem for pure numeric data. In this paper, we extend the K-Harmonic means clustering algorithm for mixed datasets. We propose a definition for a cluster center and a distance measure. These cluster centers and the distance measure are used with the cost function of K-Harmonic means clustering algorithm in the proposed algorithm. Experiments were carried out with pure categorical datasets and mixed datasets. Results suggest that the proposed clustering algorithm is quite insensitive to the cluster center initialization problem. Comparative studies with other clustering algorithms show that the proposed algorithm produce better clustering results.     

基于中心距离比值准则的无监督特征选择算法

特征选择是模式识别中的一个重要组成部分。针对未知类标号的样本集,提出基于中心距离比值准则的无监督特征选择算法。该算法利用爬山法确定聚类数目范围和估计初始聚类中心,再通过K-均值聚类算法确定特征子集的最佳分类数,然后用中心距离比值准则来评价特征子集的分类性能,并通过特征间的相关性分析,从中选择出分类效果好,相关程度低的特征组成特征子集。     

基于距离和权重改进的K-means算法

K-means聚类算法简单高效,应用广泛。针对传统K-means算法初始聚类中心点的选择随机性导致算法易陷入局部最优以及K值需要人工确定的问题,为了得到最合适的初始聚类中心,提出一种基于距离和样本权重改进的K-means算法。该聚类算法采用维度加权的欧氏距离来度量样本点之间的远近,计算出所有样本的密度和权重后,令密度最大的点作为第一个初始聚类中心,并剔除该簇内所有样本,然后依次根据上一个聚类中心和数据集中剩下样本点的权重并通过引入的参数[τi]找出下一个初始聚类中心,不断重复此过程直至数据集为空,最后自动得到[k]个初始聚类中心。在UCI数据集上进行测试,对比经典K-means算法、WK-means算法、ZK-means算法和DCK-means算法,基于距离和权重改进的K-means算法的聚类效果更好。     

Cluster center initialization algorithm for K-modes clustering

Partitional clustering of categorical data is normally performed by using K-modes clustering algorithm, which works well for large datasets. Even though the design and implementation of K-modes algorithm is simple and efficient, it has the pitfall of randomly choosing the initial cluster centers for invoking every new execution that may lead to non-repeatable clustering results. This paper addresses the randomized center initialization problem of K-modes algorithm by proposing a cluster center initialization algorithm. The proposed algorithm performs multiple clustering of the data based on attribute values in different attributes and yields deterministic modes that are to be used as initial cluster centers. In the paper, we propose a new method for selecting the most relevant attributes, namely Prominent attributes, compare it with another existing method to find Significant attributes for unsupervised learning, and perform multiple clustering of data to find initial cluster centers. The proposed algorithm ensures fixed initial cluster centers and thus repeatable clustering results. The worst-case time complexity of the proposed algorithm is log-linear to the number of data objects. We evaluate the proposed algorithm on several categorical datasets and compared it against random initialization and two other initialization methods, and show that the proposed method performs better in terms of accuracy and time complexity. The initial cluster centers computed by the proposed approach are close to the actual cluster centers of the different data we tested, which leads to faster convergence of K-modes clustering algorithm in conjunction to better clustering results.     

基于分类的未知病毒检测方法研究

文章提出了一种以PE文件静态信息作为特征,通过分类来对未知病毒进行检测的方法。采用初始聚类中心优化的K—means聚类算法实现对病毒文件的相似度检测,无需运行PE文件即可判定是否为病毒。该方法可以克服病毒特征码扫描技术无法识别未知病毒的缺点,且相对于API序列检测方法免去了对文件进行脱壳等复杂操作,明显提高了检测速度。实验结果表明分类检测方法具有较好的准确性,有一定的应用价值。     

The nearest subclass classifier: a compromise between the nearest mean and nearest neighbor classifier

We present the Nearest Subclass Classifier (NSC), which is a classification algorithm that unifies the flexibility of the nearest neighbor classifier with the robustness of the nearest mean classifier. The algorithm is based on the Maximum Variance Cluster algorithm and, as such, it belongs to the class of prototype-based classifiers. The variance constraint parameter of the cluster algorithm serves to regularize the classifier, that is, to prevent overfitting. With a low variance constraint value, the classifier turns into the nearest neighbor classifier and, with a high variance parameter, it becomes the nearest mean classifier with the respective properties. In other words, the number of prototypes ranges from the whole training set to only one per class. In the experiments, we compared the NSC with regard to its performance and data set compression ratio to several other prototype-based methods. On several data sets, the NSC performed similarly to the k-nearest neighbor classifier, which is a well-established classifier in many domains. Also concerning storage requirements and classification speed, the NSC has favorable properties, so it gives a good compromise between classification performance and efficiency.