A fundamental problem in machine learning is ensemble clustering, that is, combining multiple base clusterings to obtain improved clustering result. However, most of the existing methods are unsuitable for large-scale ensemble clustering tasks owing to efficiency bottlenecks. In this paper, we propose a large-scale spectral ensemble clustering (LSEC) method to balance efficiency and effectiveness. In LSEC, a large-scale spectral clustering-based efficient ensemble generation framework is designed to generate various base clusterings with low computational complexity. Thereafter, all the base clusterings are combined using a bipartite graph partition-based consensus function to obtain improved consensus clustering results. The LSEC method achieves a lower computational complexity than most existing ensemble clustering methods. Experiments conducted on ten large-scale datasets demonstrate the efficiency and effectiveness of the LSEC method. The MATLAB code of the proposed method and experimental datasets are available at https://github.com/Li-Hongmin/MyPaperWithCode.
AsuncionA. and NewmanD., Uci machine learning repository, 2007.
2.
BlackardJ.A. and DeanD.J., Comparative accuracies of artificial neural networks and discriminant analysis in predicting forest cover types from cartographic variables, Computers and Electronics in Agriculture24(3) (1999), 131–151.
3.
CaiD. and ChenX., Large scale spectral clustering via landmark-based sparse representation, IEEE Transactions on Cybernetics45(8) (2014), 1669–1680.
4.
CaiD.HeX. and HanJ., Speed up kernel discriminant analysis, The VLDB Journal20(1) (2011), 21–33.
5.
CaiD.HeX.HanJ. and HuangT.S., Graph regularized nonnegative matrix factorization for data representation, IEEE Transactions on Pattern Analysis and Machine Intelligence33(8) (2010), 1548–1560.
6.
DemšarJ., Statistical comparisons of classifiers over multiple data sets, The Journal of Machine Learning Research7 (2006), 1–30.
7.
FernX.Z. and BrodleyC.E., Solving cluster ensemble problems by bipartite graph partitioning, in: Proceedings of the Twenty-First International Conference on Machine Learning, 2004, p. 36.
8.
FowlkesC.BelongieS.ChungF. and MalikJ., Spectral grouping using the nystrom method, IEEE Transactions on Pattern Analysis and Machine Intelligence26(2) (2004), 214–225.
9.
FredA.L. and JainA.K., Combining multiple clusterings using evidence accumulation, IEEE Transactions on Pattern Analysis and Machine Intelligence27(6) (2005), 835–850.
10.
FreyP.W. and SlateD.J., Letter recognition using holland-style adaptive classifiers, Machine Learning6(2) (1991), 161–182.
11.
HuangD.LaiJ. and WangC.-D., Ensemble clustering using factor graph, Pattern Recognition50 (2016), 131–142.
12.
HuangD.LaiJ.-H. and WangC.-D., Combining multiple clusterings via crowd agreement estimation and multi-granularity link analysis, Neurocomputing170 (2015), 240–250.
13.
HuangD.LaiJ.-H. and WangC.-D., Robust ensemble clustering using probability trajectories, IEEE Transactions on Knowledge and Data Engineering28(5) (2015), 1312–1326.
14.
HuangD.WangC.-D. and LaiJ.-H., Locally weighted ensemble clustering, IEEE Transactions on Cybernetics48(5) (2017), 1460–1473.
15.
HuangD.WangC.-D.PengH.LaiJ. and KwohC.-K., Enhanced ensemble clustering via fast propagation of cluster-wise similarities, IEEE Transactions on Systems, Man, and Cybernetics: Systems, 2018.
16.
HuangD.WangC.-D.WuJ.-S.LaiJ.-H. and KwohC.-K., Ultra-scalable spectral clustering and ensemble clustering, IEEE Transactions on Knowledge and Data Engineering32(6) (2019), 1212–1226.
17.
Iam-OnN.BoongeonT.GarrettS. and PriceC., A link-based cluster ensemble approach for categorical data clustering, IEEE Transactions on Knowledge and Data Engineering24(3) (2010), 413–425.
18.
KiselevV.Y.KirschnerK.SchaubM.T.AndrewsT.YiuA.ChandraT.NatarajanK.N.ReikW.BarahonaM.GreenA.R. et al., Sc3: Consensus clustering of single-cell rna-seq data, Nature Methods14(5) (2017), 483.
19.
LiH.YeX.ImakurA. and SakuraiT., Ensemble learning for spectral clustering, in: 2020 IEEE International Conference on Data Mining (ICDM), IEEE, 2020, pp. 1094–1099.
20.
LiH.YeX.ImakuraA. and SakuraiT., Hubness-based sampling method for nyström spectral clustering, in: 2020 International Joint Conference on Neural Networks (IJCNN), IEEE, 2020, pp. 1–8.
21.
LiH.YeX.ImakuraA. and SakuraiT., Divide-and-conquer based large-scale spectral clustering, arXiv preprint, page 2104.15042, 2021.
22.
LiT.OgiharaM. and MaS., On combining multiple clusterings, in: Proceedings of the Thirteenth ACM International Conference on Information and Knowledge Management, 2004, pp. 294–303.
23.
LiuH.LiuT.WuJ.TaoD. and FuY., Spectral ensemble clustering, in: Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2015, pp. 715–724.
24.
LiuH.WuJ.LiuT.TaoD. and FuY., Spectral ensemble clustering via weighted k-means: Theoretical and practical evidence, IEEE Transactions on Knowledge and Data Engineering29(5) (2017), 1129–1143.
25.
LiuH.ZhaoR.FangH.ChengF.FuY. and LiuY.-Y., Entropy-based consensus clustering for patient stratification, Bioinformatics33(17) (2017), 2691–2698.
26.
NaldiM.C.CarvalhoA. and CampelloR.J., Cluster ensemble selection based on relative validity indexes, Data Mining and Knowledge Discovery27(2) (2013), 259–289.
27.
SlonimN. and TishbyN., Agglomerative information bottleneck, in: Advances in Neural Information Processing Systems, 2000, pp. 617–623.
28.
StrehlA. and GhoshJ., Cluster ensembles – a knowledge reuse framework for combining multiple partitions, Journal of Machine Learning Research3(Dec) (2002), 583–617.
29.
TandonA.AlbeshriA.ThayananthanV.AlhalabiW. and FortunatoS., Fast consensus clustering in complex networks, Physical Review E99(4) (2019), 042301.
30.
TaoZ.LiuH.LiS. and FuY., Robust spectral ensemble clustering, in: Proceedings of the 25th ACM International on Conference on Information and Knowledge Management, ACM, 2016, pp. 367–376.
31.
TopchyA.JainA.K. and PunchW., Combining multiple weak clusterings, in: Third IEEE International Conference on Data Mining, IEEE, 2003, pp. 331–338.
32.
Vega-PonsS. and Ruiz-ShulcloperJ., A survey of clustering ensemble algorithms, International Journal of Pattern Recognition and Artificial Intelligence25(03) (2011), 337–372.
33.
WangC.ArmasuS.M.KalliK.R.MaurerM.J.HeinzenE.P.KeeneyG.L.ClibyW.A.ObergA.L.KaufmannS.H. and GoodeE.L., Pooled clustering of high-grade serous ovarian cancer gene expression leads to novel consensus subtypes associated with survival and surgical outcomes, Clinical Cancer Research23(15) (2017), 4077–4085.
34.
WangF.WangX. and LiT., Generalized cluster aggregation, in: Twenty-First International Joint Conference on Artificial Intelligence, 2009.
35.
WangX.YangC. and ZhouJ., Clustering aggregation by probability accumulation, Pattern Recognition42(5) (2009), 668–675.
36.
WuJ.LiuH.XiongH.CaoJ. and ChenJ., K-means-based consensus clustering: A unified view, IEEE Transactions on Knowledge and Data Engineering27(1) (2014), 155–169.
37.
XuW.LiuX. and GongY., Document clustering based on non-negative matrix factorization, in: Proceedings of the 26th Annual International ACM SIGIR Conference on Research and Development in Informaion Retrieval, 2003, pp. 267–273.
38.
YanD.HuangL. and JordanM.I., Fast approximate spectral clustering, in: Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, ACM, 2009, pp. 907–916.
39.
YeX.LiH.SakuraiT. and LiuZ., Large scale spectral clustering using sparse representation based on hubness, in: 2018 IEEE SmartWorld, Ubiquitous Intelligence & Computing, Advanced & Trusted Computing, Scalable Computing & Communications, Cloud & Big Data Computing, Internet of People and Smart City Innovation (SmartWorld/SCALCOM/UIC/ATC/CBDCom/IOP/SCI), IEEE, 2018, pp. 1731–1737.
40.
YeX. and SakuraiT., Robust similarity measure for spectral clustering based on shared neighbors, ETRI Journal38(3) (2016), 540–550.
41.
YeX. and SakuraiT., Spectral clustering with adaptive similarity measure in kernel space, Intelligent Data Analysis22(4) (2018), 751–765.
42.
ZhengL.LiT. and DingC., A framework for hierarchical ensemble clustering, ACM Transactions on Knowledge Discovery from Data (TKDD)9(2) (2014), 1–23.
43.
ZhongC.YueX.ZhangZ. and LeiJ., A clustering ensemble: Two-level-refined co-association matrix with path-based transformation, Pattern Recognition48(8) (2015), 2699–2709.
44.
YiJ.YangT.JinR.JainA.K. and MahdaviM., Robust ensemble clustering by matrix completion, in: 2012 IEEE 12th International Conference on Data Mining, IEEE, 2012, pp. 1176–1181.
45.
ChenW.-Y.SongY.BaiH.LinC.-J. and ChangE.Y., Parallel spectral clustering in distributed systems, IEEE Transacions on Pattern Analysis and Machine Ntelligence33(3) (2010), 568–586.
