Clustering and outlier detection using isoperimetric number of trees
作者：
Highlights：
• A new graph-cut based, O(nlogn) time, data clustering algorithm is introduced.
• A precise definition is proposed for the concept of an outlier-set.
• The outlier profile of a data-set is defined and hardness results are proved.
• Approximation algorithms are given to extract clusters and outliers at the same time.
• Comparative performance analysis is presented on benchmarks and handmade examples.
摘要
Highlights•A new graph-cut based, O(nlogn) time, data clustering algorithm is introduced.•A precise definition is proposed for the concept of an outlier-set.•The outlier profile of a data-set is defined and hardness results are proved.•Approximation algorithms are given to extract clusters and outliers at the same time.•Comparative performance analysis is presented on benchmarks and handmade examples.
论文关键词：Isoperimetric constant,Cheeger constant,Normalized cut,Graph partitioning,Perceptual grouping,Data clustering,Outlier detection
论文评审过程：Received 31 July 2012, Revised 26 April 2013, Accepted 5 May 2013, Available online 22 May 2013.
论文官网地址：https://doi.org/10.1016/j.patcog.2013.05.015
