Learning model order from labeled and unlabeled data for partially supervised classification, with application to word sense disambiguation

Previous partially supervised classification methods can partition unlabeled data into positive examples and negative examples for a given class by learning from positive labeled examples and unlabeled examples, but they cannot further group the negative examples into meaningful clusters even if there are many different classes in the negative examples. Here we proposed an automatic method to obtain a natural partitioning of mixed data (labeled data + unlabeled data) by maximizing a stability criterion defined on classification results from an extended label propagation algorithm over all the possible values of model order (or the number of classes) in mixed data. Our experimental results on benchmark corpora for word sense disambiguation task indicate that this model order identification algorithm with the extended label propagation algorithm as the base classifier outperforms SVM, a one-class partially supervised classification algorithm, and the model order identification algorithm with semi-supervised k-means clustering as the base classifier when labeled data is incomplete.     

Evolutionary semi-supervised fuzzy clustering

For learning classifier from labeled and unlabeled data, this paper proposes an evolutionary semi-supervised fuzzy clustering algorithm. Class labels information provided by labeled data is used to guide the evolution process of each fuzzy partition on unlabeled data, which plays the role of chromosome. The fitness of each chromosome is evaluated with a combination of fuzzy within cluster variance of unlabeled data and misclassification error of labeled data. The structure of the clusters obtained can be used to classify a future new pattern. The performance of the proposed approach is evaluated using two benchmark data sets. Experimental results indicate that the proposed approach can improve classification accuracy significantly, compared to classifier trained with a small number of labeled data only. Also, it outperforms a similar approach SSFCM.     

一种基于谱聚类的半监督聚类方法

半监督聚类利用少部分标签的数据辅助大量未标签的数据进行非监督的学习,从而提高聚类的性能。提出一种基于谱聚类的半监督聚类算法,其利用标签数据的信息,调整点与点之间的距离所形成的距离矩阵,而后基于被调整的距离矩阵进行谱聚类。实验表明,该算法较之于已提出的半监督聚类算法,获得了更好的聚类性能。     

一种改进的半监督聚类入侵检测算法

针对网络环境,提出了一种新的半监督聚类入侵检测算法,将主动学习策略应用于半监督聚类过程中,利用少量的标记数据,生成用于初始化算法的种子聚类,通过辅助聚类过程,根据网络数据的特点,检测已知和未知攻击。主动学习策略查询网络中未标记数据与标记数据的约束关系,对标记数据可以快速获得k个不相交的非空近邻集,经检测结果证明,改进了算法的性能,且表明了算法的可行性及有效性。     

基于模拟退火和半监督聚类的入侵检测方法

由于缺少监督数据,传统的基于聚类算法的入侵检测系统存在误报率高、检测率低等问题。针对这种情况,提出基于模拟退火和半监督K均值聚类的入侵检测方法。该方法首先利用少量标记入侵类型的网络数据改进聚类初始化过程,在K均值聚类算法中引入半监督学习,然后利用模拟退火算法跳出局部极值的能力与半监督K均值聚类算法结合以得到全局最优聚类,最后根据标记数据确定聚类类别,并应用于入侵行为的检测。基于KDDCUP99的对比实验表明,该方法利用监督数据和模拟退火算法改进了聚类算法,能够有效提高入侵检测的准确率。     

一种改进的半监督K-Means聚类算法

半监督聚类利用部分标签的数据辅助未标签的数据进行学习,从而提高聚类的性能。针对基于K-means的聚类算法发现非球状簇能力差的问题,本文提出新的处理思想,即把已标签数据对未标签数据的引力影响加入到类别分配决策中,给出了类与点的引力影响度定义,设计了带引力参数的半监督K-means聚类算法。实验表明,该算法在处理非球状簇分布的聚类时比现有的半监督K-means方法效果更好。     

基于分类的半监督聚类方法

提出一种基于分类的半监督聚类算法。充分利用了数据集中的少量标记对象对原始数据集进行粗分类,在传统k均值算法的基础上扩展了聚类中心点的选择方法;用k-meansGuider方法对数据集进行粗聚类,在此基础上对粗聚类结果进行集成。在多个UCI标准数据集上进行实验,结果表明提出的算法能有效改善聚类质量。     

半监督模式下社团结构划分方法

为了对有标签和无标签节点混合的网络进行分类,给出了一种基于半监督学习的信息传递分类算法,算法首先确定网络中无标签节点的分类参数,然后通过对网络中所有无标签节点进行有限次的迭代计算,可以对所有节点进行分类。实验数据分析证明了该算法在进行半监督分类时具有比较好的效果。     

一种半监督K均值多关系数据聚类算法

提出了一种半监督K均值多关系数据聚类算法.该算法在K均值聚类算法的基础上扩展了其初始类簇的选择方法和对象相似性度量方法,以用于多关系数据的半监督学习.为了获取高性能,该算法在聚类过程中充分利用了标记数据、对象属性及各种关系信息.多关系数据库Movie上的实验结果验证了该算法的有效性.     

基于蜂群[k]-means算法的遥感图像聚类应用研究

在遥感领域，获取用于训练的标记数据耗费巨大且困难，因此许多非监督技术逐渐被发展和应用于标记样本有限的遥感图像。将[k]均值和蜂群算法相结合，提出一种新的非监督聚类算法。使用灰度共生矩阵和小波变换提取遥感图像特征，对特征数据集进行蜂群[k]-means聚类。整个聚类过程首先使用最大最小距离积邻域均值法产生初始聚类中心，将蜂群算法和[k]-means算法交替执行，实现遥感图像的聚类。通过UCI数据集和凉水国家级自然保护区的遥感数据的实验结果表明，该算法具有较高的聚类准确率，满足遥感图像聚类的应用需求。     

Learning with partly labeled data

Learning with partly labeled data aims at combining labeled and unlabeled data in order to boost the accuracy of a classifier. This paper outlines the two main classes of learning methods to deal with partly labeled data: pre-labeling-based learning and semi-supervised learning. Concretely, we introduce and discuss three methods from each class. The first three ones are two-stage methods consisting of selecting the data to be labeled and then training the classifier using the pre-labeled and the originally labeled data. The last three ones show how labeled and unlabeled data can be combined in a symbiotic way during training. The empirical evaluation of these methods shows: (1) pre-labeling methods tend be better than semi-supervised learning methods, (2) both labeled and unlabeled have positive effect on the classification accuracy of each of the proposed methods, (3) the combination of all the methods improve the accuracy, and (4) the proposed methods compare very well with the state-of-art methods.     

基于Seed集的半监督核聚类

提出了一种新的半监督核聚类算法——SKK-均值算法。算法利用一定数量的标记样本构成seed集,作为监督信息来初始化K-均值算法的聚类中心,引导聚类过程并约束数据划分;同时还采用了核方法把输入数据映射到高维特征空间,并用核函数来实现样本之间的距离计算。在UCI数据集上进行了数值实验,并与K-均值算法和核-K-均值算法进行了比较。     

Semi-supervised object recognition based on Connected Image Transformations

We present a novel semi-supervised classifier model based on paths between unlabeled and labeled data through a sequence of local pattern transformations. A reliable measure of path-length is proposed that combines a local dissimilarity measure between consecutive patters along a path with a global, connectivity-based metric. We apply this model to problems of object recognition, for which we propose a practical classification algorithm based on sequences of “Connected Image Transformations” (CIT). Experimental results on four popular image benchmarks demonstrate how the proposed CIT classifier outperforms state-of-the-art semi-supervised techniques. The results are particularly significant when only a very small number of labeled patterns is available: the proposed algorithm obtains a generalization error of 4.57% on the MNIST data set trained on 2000 randomly chosen patterns with only 10 labeled patterns per digit class.     

半监督聚类的若干新进展

半监督聚类方法利用少量标记数据提高聚类算法的性能,已逐渐发展成为模式识别及相关领域的研究热点.文中首先综述了半监督聚类算法的一些新进展,包括基于约束的方法、基于距离的方法和基于距离与约束的融合方法.然后提出一种基于约束的半监督模糊C-means聚类算法.实验表明,该算法与传统的模糊C-means及半监督K-means方法相比,具有更好的聚类精度.     

Semi-supervised model-based document clustering: A comparative study

Semi-supervised learning has become an attractive methodology for improving classification models and is often viewed as using unlabeled data to aid supervised learning. However, it can also be viewed as using labeled data to help clustering, namely, semi-supervised clustering. Viewing semi-supervised learning from a clustering angle is useful in practical situations when the set of labels available in labeled data are not complete, i.e., unlabeled data contain new classes that are not present in labeled data. This paper analyzes several multinomial model-based semi-supervised document clustering methods under a principled model-based clustering framework. The framework naturally leads to a deterministic annealing extension of existing semi-supervised clustering approaches. We compare three (slightly) different semi-supervised approaches for clustering documents: Seeded damnl, Constrained damnl, and Feedback-based damnl, where damnl stands for multinomial model-based deterministic annealing algorithm. The first two are extensions of the seeded k-means and constrained k-means algorithms studied by Basu et al. (2002); the last one is motivated by Cohn et al. (2003). Through empirical experiments on text datasets, we show that: (a) deterministic annealing can often significantly improve the performance of semi-supervised clustering; (b) the constrained approach is the best when available labels are complete whereas the feedback-based approach excels when available labels are incomplete. Editor: Andrew Moore     

一种半监督K均值多关系数据聚类算法

提出了一种半监督K均值多关系数据聚类算法.该算法在K均值聚类算法的基础上扩展了其初始类簇的选择方法和对象相似性度量方法,以用于多关系数据的半监督学习.为了获取高性能,该算法在聚类过程中充分利用了标记数据、对象属性及各种关系信息.多关系数据库Movie上的实验结果验证了该算法的有效性.     

Clustering Analysis of Gene Expression Data based on Semi-supervised Visual Clustering Algorithm

When gene expression datasets contain some labeled data samples, the labeled information should be incorporated into clustering algorithm such that more reasonable clustering results can be achieved. In this paper, a novel semi-supervised clustering algorithm, Semi-supervised Iterative Visual Clustering Algorithm (Semi-IVCA), is presented to tackle with such datasets. The new algorithm first constructs the visual sampling image of the dataset based on visual theorem and obtains its attractors using the gradient learning rules, where each attractor denotes a cluster of the dataset. Then the new algorithm introduces an iterative clustering procedure to realize the semi-supervised learning. The new algorithm is a generalization of the current Visual Clustering Algorithm (VCA) presented by authors. Except for the advantage that Semi-IVCA can effectively utilize the labeled data information in clustering, it is robust and insensitive to initialization, and it has strong parameter learning capability and good interpretation for the clustering results. When the new algorithm Semi-IVCA is applied to the artificial and real gene expression datasets, the experimental results confirm the above advantages of algorithm Semi-IVCA.     

基于加权样本和共识率的标记传播算法

标记传播是使用最广泛的半监督分类方法之一。基于共识率的标记传播算法(Consensus Rate-based Label Propagation,CRLP)通过汇总多个聚类方法以合并数据各种属性得到的共识率来构造图。然而,CRLP算法与大多数基于图的半监督分类方法一样,在图中将每个标记样本视为同等重要,它们主要通过优化图的结构来提高算法的性能。事实上,样本不一定是均匀分布的,不同的样本在算法中的重要性也是不同的,并且CRLP算法容易受聚类数目和聚类方法的影响,对低维数据的适应性不足。针对这些问题,文中提出了一种基于加权样本和共识率的标记传播算法(Label Propagation Algorithm Based on Weighted Samples and Consensus-Rate,WSCRLP)。WSCRLP算法首先对数据集进行多次聚类,以探索样本的结构,并结合共识率和样本的局部信息构造图;然后为不同分布的标记样本分配不同的权重;最后基于构造的图和加权样本进行半监督分类。在真实数据集上的实验表明,WSCRLP算法对标记样本进行加权和构造图的方法可以显著提高分类准确率,在84%的实验中都优于对比方法。相比CRLP算法,WSCRLP算法不仅具有更好的性能,而且对输入参数具有鲁棒性。     

基于不完备标签数据的半监督聚类算法

针对seeded-K-means和constrained-K-means算法要求标签数据类别完备的限制,本文提出了基于不完备标签数据的半监督K-means聚类算法,重点讨论了未标签类别初始聚类中心的选取问题.首先给出了未标签类别聚类中心最优候选集的定义,然后提出了一种新的朱标签类别初始聚类中心选取方法,即采用K-mea...     

Least Square Transduction Support Vector Machine

Support vector machine (SVM) is a general and powerful learning machine, which adopts supervised manner. However, for many practical machine learning and data mining applications, unlabeled training examples are readily available but labeled ones are very expensive to be obtained. Therefore, semi-supervised learning emerges as the times require. At present, the combination of SVM and semi-supervised learning principle such as transductive learning has attracted more and more attentions. Transductive support vector machine (TSVM) learns a large margin hyperplane classifier using labeled training data, but simultaneously force this hyperplane to be far away from the unlabeled data. TSVM might seem to be the perfect semi-supervised algorithm since it combines the powerful regularization of SVMs and a direct implementation of the clustering assumption, nevertheless its objective function is non-convex and then it is difficult to be optimized. This paper aims to solve this difficult problem. We apply least square support vector machine to implement TSVM, which can ensure that the objective function is convex and the optimization solution can then be easily found by solving a set of linear equations. Simulation results demonstrate that the proposed method can exploit unlabeled data to yield good performance effectively.