一种基于马尔可夫链的高维离群点挖掘算法  

New outlier detection algorithm based on Markov chain

作　　者：唐志刚[1,2] 杨炳儒[1] 杨珺[1] 

机构地区：[1]北京科技大学信息工程学院,北京100083 [2]南华大学数理学院,湖南衡阳421001

出　　处：《系统工程与电子技术》2010年第12期2721-2724,共4页Systems Engineering and Electronics

基　　金：国家自然科学基金(69835001;60675030;60875029);教育部科技重点资金([2000]175)资助课题

摘　　要：提出了一种基于马尔可夫链的离群点检测(outlier detection algorithms based on Markov chain,MRKFOD)算法。该算法把基本数据集看作一个加权无向图,数据集中的每个数据表示一个节点,用每条加权边表示节点之间的相似度;形成一个邻接矩阵,把邻接矩阵当作马尔可夫链中的概率转移矩阵;寻求概率转移矩阵的主要特征向量;把每个节点的主要特征向量值作为每个数据的离群度。实验结果表明,该算法与其他高维离群点挖掘算法相比,在效率及有效处理的维数方面均有显著提高。An outlier detection algorithm based on Markov chain（MRKFOD algorithm） is presented.First,the basic data set is regarded as a weighted undirected graph,in which each datum represents a node,and each weighted edge denotes the similarity between nodes;so it forms an adjacency matrix,and then the adjacency matrix is regarded as a probability transition matrix in Markov chain.Secondly,the algorithm seeks the main feature vector of the probability transition matrix.Finally,the main feature vector of each node is looked upon as the outlier degree of each datum.The experimental results show that both the efficiency of MRKFOD algorithm and the maximum number of dimensions processed are obviously improved compared with other high-dimensional outlier mining algorithms.

关 键 词：数据挖掘 离群点 高维数据集 马尔可夫链 加权无向图 

分 类 号：TP182[自动化与计算机技术—控制理论与控制工程]