This paper describes a new semi-supervised clustering algorithm as part of a more general framework of interactive exploratory clustering, that favors the exploration of possible clustering solutions so that an expert tailors the best clustering according to her domain knowledge and preferences. Contrary to most existing approaches, the novel algorithm considers the feature space as a first class citizen for the exploration of alternative solutions. Our proposal represents and integrates quantitative preferences on attributes that will guide the exploration of possible solutions by learning an appropriate space metric. It also achieves a compromise clustering based on expert confidence, between a data-driven and a user-driven solution and converges with a good complexity. We show experimentally that our method is also able to deal with irrelevant user preferences and correct those choices in order to achieve a better solution. Experiments show that the best results may be achieved only with the addition of preferences to traditional metric learning algorithms and that our approach performs better than state-of-the-art algorithms.
Get full access to this article
View all access options for this article.
References
1.
AggarwalC.C. and ReddyC.K., Data clustering: algorithms and applications, CRC press, 2013.
2.
AgrawalR.GehrkeJ.GunopulosD. and RaghavanP., Automatic subspace clustering of high dimensional data for data mining applications, SIGMOD Rec27(2) (June 1998), 94–105.
3.
AlelyaniS.TangJ. and LiuH., Feature selection for clustering: A review, In Data Clustering: Algorithms and Applications, Chapman and Hall/CRC, 2013, pp. 29–60.
4.
AlexanderA. and GhoshJ., Cluster ensembles – a knowledge reuse framework for combining multiple partitions, Journal of Machine Learning Research3 (2003), 583–617.
5.
AntoineV. and LabrocheN., Semi-supervised fuzzy c-means variants: A study on noisy label supervision, In Information Processing and Management of Uncertainty, volume 2, 2018, pp. 51–62.
6.
AntoineV.LabrocheN. and VuV.-V., Evidential seed-based semi-supervised clustering, In Proc. of SCIS-ISIS, 2014.
7.
ArthurD. and VassilvitskiiS., k-means++: The advantages of careful seeding, In Proc. Symp. Discrete Algorithms, 2007, pp. 1027–1035.
8.
BaeE. and BaileyJ., Coala: A novel approach for the extraction of an alternate clustering of high quality and high dissimilarity, In Proceedings of the Sixth International Conference on Data Mining, ICDM ’06, 2006, pp. 53–62.
9.
BanerjeeA. and GhoshJ., Scalable clustering algorithms with balancing constraints, Data Mining and Knowledge Discovery13(3) (2006), 365–395.
10.
BanerjeeA. and GhoshJ., Clustering with balancing constraints, In Constrained Clustering, Chapman and Hall/CRC, 08 2008, pp. 171–200.
11.
BasuS.BanerjeeA. and MooneyR.J., Semi-supervised clustering by seeding, In Proc. of the 19th ICML, ICML ’02, Morgan Kaufmann Publishers Inc., 2002, pp. 27–34.
12.
BasuS.BanerjeeA. and MooneyR.J., Active semi-supervision for pairwise constrained clustering, In Proc. of the 2004 SIAM Inter, Conference on Data Mining, 2004, pp. 333–344.
13.
BilenkoM.BasuS. and MooneyR.J., Integrating constraints and metric learning in semi-supervised clustering, In In Proc. of the 21st ICML, ACM, 2004, p. 11.
14.
BradleyP.S.BennettK.P. and BhattacharyaI., Using assignment constraints to avoid empty clusters in k-means clustering, In Constrained Clustering, Chapman and Hall/CRC, 08 2008, pp. 201–220.
15.
BradleyP.S.BennettK.P. and DemirizA., Constrained k-means clustering, Technical Report MSR-TR-2000-65, Microsoft Research, 5 2000.
16.
CharradM. and Ben AhmedM., Simultaneous clustering: A survey, In Lect. Notes Comput. Sci. (including Subser. Lect. Notes Artif. Intell. Lect. Notes Bioinformatics), volume 6744 LNCS, Springer, Berlin, Heidelberg, 2011, pp. 370–375.
17.
ChauD.H.VreekenJ.van LeeuwenM. and FaloutsosC., editors, IDEA ’13: Proceedings of the ACM SIGKDD Workshop on Interactive Data Exploration and Analytics, New York, NY, USA, 2013, ACM.
18.
CovoesT.F.HruschkaE.R. and GhoshJ., A study of k-means-based algorithms for constrained clustering, Intelligent Data Analysis17(3) (2013), 485–505.
19.
DangX.-H. and BaileyJ., A hierarchical information theoretic technique for the discovery of non linear alternative clusterings, In Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD ’10, 2010, pp. 573–582.
20.
DaoT.B.H.VrainC.DuongK.C. and DavidsonI., A Framework for Actionable Clustering using Constraint Programming, In 22nd ECAI, Aug. 2016.
21.
DashM.ChoiK.ScheuermannP. and LiuH., Feature selection for clustering – a filter solution, In Proc. of the 2nd ICDM, 2002, pp. 115–122.
22.
David KincaidE.W.C. and KincaidD.R., Numerical Analysis: Mathematics of Scientific Computing, American Mathematical Soc., 2009.
23.
DavidsonI. and BasuS., A survey of clustering with instance level constraints, ACM Transactions on Knowledge Discovery from data, 2007, pp. 1–41.
24.
DavidsonI. and QiZ., Finding alternative clusterings using constraints, In Proceedings of the 2008 Eighth IEEE International Conference on Data Mining, ICDM ’08, 2008, pp. 773–778.
25.
DavidsonI. and RaviS., Clustering with constraints: Feasibility issues and the k-means algorithm, In Proceedings of the 2005 SIAM international conference on data mining, SIAM, 2005, pp. 138–149.
26.
DavidsonI.WagstaffK.L. and BasuS., Measuring constraint-set utility for partitional clustering algorithms, In Proc. of the 10th ECML PKDD, Springer-Verlag, 2006, pp. 115–126.
27.
DengZ.ChoiK.-S.JiangY.WangJ. and WangS., A survey on soft subspace clustering, Inf Sci348(C) (June 2016), 84–106.
28.
DubeyA.BhattacharyaI. and GodboleS., A cluster-level semi-supervision model for interactive clustering, In ECML PKDD, Berlin, Heidelberg, 2010, pp. 409–424.
29.
El MoussawiA.CheriatA.GiacomettiA.LabrocheN. and SouletA., Clustering with quantitative user preferences on attributes, In 2016 IEEE 28th International Conference on Tools with Artificial Intelligence, Nov 2016, pp. 383–387.
30.
EsterM.KriegelH.P.SanderJ. and XuX., A density-based algorithm for discovering clusters in large spatial databases with noise, AAAI Press, 1996, pp. 226–231.
31.
GanganathN.ChengC.T. and TseC.K., Data clustering with cluster size constraints using a modified k-means algorithm, In 2014 International Conference on Cyber-Enabled Distributed Computing and Knowledge Discovery, 2014, pp. 158–161.
32.
HanJ.PeiJ. and KamberM., Data mining: concepts and techniques, Elsevier, 2011.
33.
HanczarB. and NadifM., Using the bagging approach for biclustering of gene expression data, Neurocomputing74(10) (May 2011), 1595–1605.
34.
HöppnerF. and KlawonnF., Clustering with size constraints, In Computational Intelligence Paradigms, Springer, 2008, pp. 167–180.
35.
HuangJ.-J.TzengG.-H. and OngC.-S., Marketing segmentation using support vector clustering, Expert Systems with Applications32(2) (2007), 313–317.
36.
HungC. and TsaiC.-F., Market segmentation based on hierarchical self-organizing map for markets of multimedia on demand, Expert Systems with Applications34(1) (2008), 780–787.
37.
JainA.K., Data clustering: 50 years beyond k-means, Pattern Recognition Letters31(8) (2010), 651–666.
38.
JingL.NgM.K. and HuangJ.Z., An entropy weighting k-means algorithm for subspace clustering of high-dimensional sparse data, IEEE Trans on Knowl and Data Eng19(8) (Aug 2007), 1026–1041.
39.
KlawonnF. and HöppnerF., Equi-sized, homogeneous partitioning, In International Conference on Knowledge-Based and Intelligent Information and Engineering Systems, Springer, 2006, pp. 70–77.
40.
KriegelH.-P.KrögerP. and ZimekA., Clustering high-dimensional data: A survey on subspace clustering, pattern-based clustering and correlation clustering, ACM Trans Knowl Discov Data3(1) (Mar. 2009), 1:1–1:58.
41.
KriegelH.-P. and ZimekA., Subspace clustering, ensemble clustering, alternative clustering, multiview clustering: what can we learn from each other, In Proc. ACM SIGKDD Workshop MultiClust, 2010.
42.
KullbackS. and LeiblerR.A., On information and sufficiency, The Annals of Mathematical Statistics22(1) (1951), 79–86.
43.
KumarN. and KummamuruK., Semisupervised clustering with metric learning using relative comparisons, IEEE Transactions on Knowledge and Data Engineering20(4) (2008), 496–503.
44.
KumarV. and MinzS., Feature selection: A literature review, Smart CR4(3) (2014), 211–229.
45.
LampertT.DaoT.-B.-H.LafabregueB.SerretteN.ForestierG.CrémilleuxB.VrainC. and GançarskiP., Constrained distance based clustering for time-series: a comparative and experimental study, Data Mining and Knowledge Discovery, May 2018.
46.
LelisL. and SanderJ., Semi-supervised density-based clustering, In Proc. of the 9th IEEE ICDM, 2009, pp. 842–847.
47.
LiJ.YiK. and ZhangQ., Clustering with diversity, In International Colloquium on Automata, Languages, and Programming, Springer, 2010, pp. 188–200.
48.
LiY.DongM. and HuaJ., Localized feature selection for clustering, Pattern Recognition Letters29(1) (2008), 10–18.
49.
LiuE.Y.GuoZ.ZhangX.JojicV. and WangW., Metric learning from relative comparisons by minimizing squared residual, In Proc. IEEE 12th ICDM, 2012, pp. 978–983.
50.
LiuE.Y.ZhangZ. and WangW., Clustering with relative constraints, In Proceedings of the 17th ACM SIGKDD international conference on Knowledge discovery and data mining, ACM, 2011, pp. 947–955.
51.
LiuH. and FuY., Clustering with partition level side information, In IEEE ICDM, Nov 2015, pp. 877–882.
52.
LomaxR.G. and Hahs-VaughnD.L., Statistical concepts: A second course, Routledge, 2013.
53.
MacQueenJ.B., Some methods for classification and analysis of multivariate observations, In CamL.M.L. and NeymanJ., editors, Proc. of the 5th Berkeley Symposium on Mathematical Statistics and Probability, Volume 1, 1967, pp. 281–297.
54.
MurtaghF. and ContrerasP., Algorithms for hierarchical clustering: an overview, II, Wiley Interdiscip Rev Data Min Knowl Discov7(6) (Nov 2017), e1219.
55.
OkabeM. and YamadaS., Clustering by learning constraints priorities, In 2013 IEEE 13th ICDM, Volume 0, IEEE Computer Society, 2012, pp. 1050–1055.
56.
ParsonsL.HaqueE. and LiuH., Subspace clustering for high dimensional data: A review, SIGKDD Explor Newsl6(1) (June 2004), 90–105.
57.
PeiY.FernX.Z.RosalesR. and TjahjaT.V., Discriminative clustering with relative constraints, arXiv preprint arXiv:1501.00037, 2014.
58.
QiZ. and DavidsonI., A principled and flexible framework for finding alternative clusterings, In Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD ’09, 2009, pp. 717–726.
59.
RuizC.SpiliopoulouM. and MenasalvasE., Density-based semi-supervised clustering, Data Mining and Knowledge Discovery21(3) (2010), 345–370.
60.
SunJ.ZhaoW.XueJ.ShenZ. and ShenY., Clustering with feature order preferences, Intelligent Data Analysis14 (2010), 479–495.
61.
TsaiC.-F.HuY.-H. and LuY.-H., Customer segmentation issues and strategies for an automobile dealership with two clustering techniques, Expert Sys: J Knowl Eng32(1) (Feb. 2015), 65–76.
62.
VuV.V.LabrocheN. and Bouchon-MeunierB., Boosting clustering by active constraint selection, In Proc. of the 2010 19th ECAI, 2010, pp. 297–302.
63.
VuV.V.LabrocheN. and Bouchon-MeunierB., An efficient active constraint selection algorithm for clustering, In 2010 20th ICPR, 2010, pp. 2969–2972.
64.
WagstaffK.CardieC.RogersS. and SchroedlS., Constrained k-means clustering with background knowledge, In Proc. of the 18th ICML, 2001, pp. 577–584.
65.
WagstaffK.L., When is constrained clustering beneficial and why, In in AAAI, 2006.
66.
WagstaffK.L. and CardieC., Clustering with instance-level constraints, In Proc. of the 17th ICML, 2000, pp. 1103–1110.
67.
WangJ. and SuX., An improved K-Means clustering algorithm, In 2011 IEEE 3rd Int. Conf. Commun. Softw. Networks, IEEE, May 2011, pp. 44–46.
68.
WangJ.WuS. and LiG., Clustering with instance and attribute level side information, Int Journal of Computational Intelligence Systems3(6) (2010), 770–785.
69.
WangX. and DavidsonI., Flexible constrained spectral clustering, In Proc. of KDD, 2010, pp. 563–572.
70.
XingE.P.NgA.Y.JordanM. and RusselS., Distance metric learning, with application to clustering with side-information, In Proc. of NIPS, 2002, pp. 505–512.
71.
ZhuS.WangD. and LiT., Data clustering with size constraints, Knowledge-Based Systems23(8) (2010), 883–889.
