1. Clustering High-Dimensional Noisy Categorical Data.
- Author
-
Tian, Zhiyi, Xu, Jiaming, and Tang, Jen
- Abstract
AbstractClustering is a widely used unsupervised learning technique that groups data into homogeneous clusters. However, when dealing with real-world data that contain categorical values, existing algorithms can be computationally costly in high dimensions and can struggle with noisy data that has missing values. Furthermore, except for one algorithm, no others provide theoretical guarantees of clustering accuracy. In this article, we propose a general categorical data encoding method and a computationally efficient spectral-based algorithm to cluster high-dimensional noisy categorical data (nominal or ordinal). Under a statistical model for data on
m attributes fromn subjects inr clusters with missing probabilityϵ , we show that our algorithm exactly recovers the true clusters with high probability when mn(1−ϵ)≥CMr2 log 3M, with M=max(n,m) and a fixed constantC . In addition, we show that mn(1−ϵ)2≥rδ/2 with 0<δ<1 is necessary forany algorithm to succeed with probability at least (1+δ)/2. In cases wherem =n andr are fixed, the sufficient condition matches with the necessary condition up to a polylog(n) factor. In numerical studies our algorithm outperforms several existing algorithms in both clustering accuracy and computational efficiency. Supplementary materials for this article are available online. [ABSTRACT FROM AUTHOR]- Published
- 2023
- Full Text
- View/download PDF