Text

Non-Exhaustive, Overlapping Clustering

Traditional clustering algorithms, such as K-Means, output a clustering that is disjoint and exhaustive, i.e., every single data point is assigned to exactly one cluster. However, in many real-world datasets, clusters can overlap and there are often outliers that do not belong to any cluster. While this is a well-recognized problem, most existing algorithms address either overlap or outlier detection and do not tackle the problem in a unified way. In this paper, we propose an intuitive objective function, which we call the NEO-K-Means (Non-Exhaustive, Overlapping K-Means) objective, that captures the issues of overlap and non-exhaustiveness in a unified manner. Our objective function can be viewed as a reformulation of the traditional K-Means objective, with easy-to-understand parameters that capture the degrees of overlap and non-exhaustiveness. By considering an extension to weighted kernel K-Means, we show that we can also apply our NEO-K-Means idea to overlapping community detection, which is an important task in network analysis. To optimize the NEO-K-Means objective, we develop not only fast iterative algorithms but also more sophisticated algorithms using low-rank semidefinite programming techniques. Our experimental results show that the new objective and algorithms are effective in finding ground-truth clusterings that have varied overlap and non-exhaustiveness; for the case of graphs, we show that our method outperforms state-of-the-art overlapping community detection algorithms.

Ketersediaan

Informasi Detail

Judul Seri

IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE; Vol.41 Issue 11 November 2019

No. Panggil

-

Penerbit

: .,

Deskripsi Fisik

p. 2644 - 2659

Bahasa

English

ISBN/ISSN

-

Klasifikasi

-

Tipe Isi

-

Tipe Media

-

Tipe Pembawa

-

Edisi

-

Subjek

K-MEANS
SEMIDEFINITE PROGRAMMING
GRAPH CLUSTERING
COMMUNITY DETECTION
OUTLIER
OVERLAPPING CLUSTERING

Info Detail Spesifik

-

Pernyataan Tanggungjawab

Joyce Jiyoung Whang, Yangyang Hou, David F. Gleich, Inderjit S. Dhillon

Versi lain/terkait

Lampiran Berkas

Komentar