基于高维空间稀疏最小生成树自适应覆盖模型的一类分类算法  

One-Class Classification Algorithm Based on Sparse Minimum Spanning Tree Adaptive Covering Model in High-Dimensional Space

作　　者：胡正平[1] 路亮[1] 许成谦[1] 

机构地区：[1]燕山大学信息科学与工程学院,秦皇岛066004

出　　处：《模式识别与人工智能》2011年第3期444-451,共8页Pattern Recognition and Artificial Intelligence

基　　金：中国博士后自然科学基金(No.20080440124;200902356);河北省自然科学基金(No.F2010001297;F2008000891)资助

摘　　要：最小生成树数据描述(MSTCD)在刻画高维空间样本点分布时,将所有图形的边作为新增虚拟样本以提供目标类样本分布描述,这种描述存在分支多、覆盖模型复杂的问题.针对该问题,依据特征空间中同类样本分布的连续性规律,文中提出基于稀疏最小生成树覆盖模型的一类分类算法.该方法首先构建目标类数据集的稀疏k近邻图表示,通过递归图分割算法发现数据分布的微聚类,再以微聚类的中心为图节点构建目标类的稀疏最小生成树覆盖模型.实验结果表明,文中方法与MSTCD和其它一类分类器相比有较优的描述性能和较低的模型复杂度.Minimum spanning tree class descriptor （MSTCD） describes the target class with the assumption that all the edges of the graph are basic elements of the classifier, which offers additional virtual training data for a description of sample distribution in high-dimensional space. However, this descriptive model has too many branches, which results in the model being more complicated. According to the continuity law of the feature space of similar samples, a one-class classification algorithm based on sparse minimum spanning tree covering model is presented. The method firstly constructs sparse k-nearest-neighbor graph representation for the target class. Then, a recursive graph bipartition algorithm is introduced to find the micro-cluster. Finally, it builds sparse minimum spanning tree on the graph nodes which are centers of micro-cluster. Experimental results show that the presented algorithm performs better than MSTCD and other one-class classifiers.

关 键 词：一类分类器 高维空间 最小生成树(MST) 稀疏最小生成树 

分 类 号：TP391.41[自动化与计算机技术—计算机应用技术]