MS2OD: outlier detection using minimum spanning tree and medoid selection

Machine Learning Science and Technology, vol. 5, pp. 015025

Abstract

Abstract As an essential task in data mining, outlier detection identifies abnormal patterns in numerous applications, among which clustering-based outlier detection is one of the most popular methods for its effectiveness in detecting cluster-related outliers, especially in medical applications. This article presents an advanced method to extract cluster-based outliers by employing a scaled minimum spanning tree (MST) data structure and a new medoid selection method: 1. we compute a scaled MST and iteratively cut the current longest edge to obtain clusters; 2. we apply a new medoid selection method, considering the noise effect to improve the quality of cluster-based outlier identification. The experimental results on real-world data, including extensive medical corpora and other semantically meaningful datasets, demonstrate the wide applicability and outperforming metrics of the proposed method.

Authors 6

1. Jia Li corresponding Aachen Leiden Institute of Advanced Computer Science

   Leiden University · Xi'an Jiaotong University

   Affiliation as printed

   Leiden Institute of Advanced Computer Science, Leiden University, Snellius Gebouw, Niels Bohrweg 1, Leiden, 2300 RA, NETHERLANDS

   School of Software Engineering, Xi'an Jiaotong University, Xianning West Road, Xi'an, Shaanxi, 710049, CHINA

2. Jiangwei Li corresponding Aachen Leiden Institute of Advanced Computer Science

   Leiden University · Xi'an Jiaotong University

   Affiliation as printed

   Leiden Institute of Advanced Computer Science, Leiden University, Snellius Gebouw, Niels Bohrweg 1, Leiden, 2300 RA, NETHERLANDS

   School of Software Engineering, Xi'an Jiaotong University, Xianning West Road, Xi'an, Shaanxi, 710049, CHINA

3. Chenxu Wang

   Second Affiliated Hospital of Xi'an Jiaotong University · Xi'an Jiaotong University

   Affiliation as printed

   The Second Affiliated Hospital of8 Xi’an Jiaotong University, Xi'an Jiaotong University, Yanta West Road, Xi'an, Shaanxi, 710049, CHINA

   The Second Affiliated Hospital of8 Xi'an Jiaotong University, Xi'an Jiaotong University, Yanta West Road, Xi'an, Shaanxi, 710049, CHINA

4. Fons J. Verbeek Aachen Leiden Institute of Advanced Computer Science

   Leiden University

   Affiliation as printed

   Leiden Institute of Advanced Computer Science, Leiden University, Snellius Gebouw, Niels Bohrweg, Leiden, 2300 RA, NETHERLANDS

5. Tanja Schultz

   University of Bremen

   Affiliation as printed

   Cognitive Systems Lab, Universitat Bremen, Enrique-Schmidt-Str. 5, Bremen, 28359, GERMANY

6. Hui Liu corresponding

   University of Bremen

   Affiliation as printed

   Cognitive Systems Lab, University of Bremen, Enrique-Schmidt-Str. 5, Cartesium, 2-Etg., Bremen, Bremen, Bremen, 28359, GERMANY