Clustering is an important data exploration technique with many applications in different areas of engineering, including engineering design, manufacturing system design, quality assurance, production planning and process planning, modelling, monitoring, and control. The clustering problem has been addressed by researchers from many disciplines. However, efforts to perform effective and efficient clustering on large data sets only started in recent years with the emergence of data mining. The current paper presents an overview of clustering algorithms from a data mining perspective. Attention is paid to techniques of scaling up these algorithms to handle large data sets. The paper also describes a number of engineering applications to illustrate the potential of clustering algorithms as a tool for handling complex real-world problems.
FisherD.XuL.CarnesJ. R.ReichY.FenvesJ.ChenJ.ShiaviR.BiswasG.WeinbergJ.Applying AI clustering to engineering tasks. IEEE Expert, 1993, 8(6), 51–60.
2.
ZamirO.EtzioniO.MadaniO.KarpR. M.Fast and intuitive clustering of web documents. In Proceedings of the 3rd International Conference on Knowledge Discovery and Data Mining, Newport Beach, California, USA, 1997, pp. 287–290 (AAAI Press, Menlo Park, California, USA).
3.
KuoR. J.HoL. M.HuC. M.Integration of self-organizing feature map and k-means algorithm for market segmentation. Comput. Oper. Res., 2002, 29, 1475–1493.
4.
AuW.-H.ChanK. C. C.WongA. K. C.WangY.Attribute clustering for grouping, selection, and classification of gene expression data. IEEE/ACM Trans. Comput. Biol. Bioinf., 2005, 2(2), 83–101.
5.
KerstenP. R.LeeJ.-S.AinsworthT. L.Unsupervised classification of polarimetric synthetic aperture radar images using fuzzy clustering and EM clustering. IEEE Trans. Geosci. Remote Sens., 2005, 43(3), 519–527.
6.
XuY.Hybrid clustering with application to web mining. In Proceedings of the 4th International Conference on Active Media Technology (AMT-05), Takamastu, Japan, 2005, pp. 574–578.
7.
KlösgenW.ŻytkowJ. M.Handbook of data mining and knowledge discovery, 2002 (Oxford University Press, New York, USA).
HanJ.KamberM.Data mining: concepts and techniques, 2001 (Academic Press, San Diego, California, USA).
16.
MacQueenJ. B.Some methods for classification and analysis of multivariate observations. In Proceedings of the 5th Berkeley Symposium on Mathematical Statistics and Probability, vol. I, Statistics, Berkeley, California, 1967, pp. 281–297 (University of California Press, Los Angeles, California, USA).
17.
JainA. K.DubesR. C.Algorithms for clustering data, 1988 (Prentice Hall, Englewood Cliffs, New Jersey, USA).
18.
KaufmanL.RousseeuwP. J.Finding groups in data: an introduction to cluster analysis, 2nd edition, 2005 (John Wiley & Sons, New Jersey, USA).
19.
DempsterA. P.LairdN.RubinD. B.Maximum likelihood from incomplete data via the EM algorithm (with discussion). J. Roy. Stat. Soc. B, 1977, 39, 1–38.
20.
OrdonezC.OmiecinskiE.Accelerating EM clustering to find high-quality solutions. Knowl. Inf. Syst., 2005, 7, 135–157.
21.
BallG.HallD.ISODATA, a novel method of data analysis and classification. Technical report, AD-699616, SRI, Stanford, California, USA, 1965.
22.
BezdekD.Pattern recognition with fuzzy objective function algorithms, 1981 (Plenum Press, New York, USA).
23.
BabuG. P.MurtyM. N.A near-optimal seed value selection in k-means algorithm using a genetic algorithm. Pattern Recognit. Lett., 1993, 14(10), 763–169.
ZhangB.Generalized k-harmonic means - dynamic weighting of data in unsupervised learning. In Proceedings of the 1st SIAM International Conference on Data mining (SDM-01), Chicago, Illinois, USA, 5–7 April 2001, available from http://www.siam.org/meetings/sdm01/pdf/sdm01_06.pdf.
26.
CheungY.-M.K-Means: A new generalized k-means clustering algorithm. Pattern Recognit. Lett., 2003, 24, 2883–2893.
27.
KuoR. J.WangH. S.HuT.-L.ChouS. H.Application of ant k-means on clustering analysis. Comput. Math. Appl., 2005, 50, 1709–1724.
28.
Al-DaoudM. B.VenkateswarluN. B.RobertsS. A.Fast k-means clustering algorithms. Technical report, 95.18, School of Computer Studies, University of Leeds, UK, 1995.
29.
BottouL.BengioY.Convergence properties of the k-means algorithm. Adv. Neural Inf. Process. Syst., 1995, 7, 585–592.
30.
FritzkeB.The LBG-U method for vector quantization - an improvement over LBG inspired from neural networks. Neural Process. Lett., 1997, 5(1), 35–45.
31.
AlsabtiK.RankaS.SinghV.An efficient k-means clustering algorithm. In Proceedings of the 1st Workshop on High-performance Data Mining, Orlando, Florida, USA, 1998, available from ftp://ftp.cise.ufl.edu/pub/faculty/ranka.
32.
PellegD.MooreA.Accelerating exact k-means algorithms with geometric reasoning. In Proceedings of the 5th ACM International Conference of the Special Interest Group on Knowledge Discovery and Data Mining (ACM-SIGKDD-99), San Diego, California, USA, 1999, pp. 277–281.
33.
PellegD.MooreA.X-means: Extending k-means with efficient estimation of the number of clusters. In Proceedings of the 7th International Conference on Machine Learning (ICML-00), Stanford, California, USA, 2000, pp. 727–734.
34.
CastroV. E.YangJ.A fast and robust general purpose clustering algorithm. In Proceedings of the 4th European Workshop on Principles of Knowledge Discovery in Databases and Data Mining (PKDD-00), Lyon, France, 2000, pp. 208–218.
Al-DaoudM. B.VenkateswarluN. B.RobertsS. A.New methods for the initialisation of clusters. Pattern Recognit. Lett., 17, 1996, 451–455.
38.
BradleyS.FayyadU. M.Refining initial points for k-means clustering. In Proceedings of the 5th International Conference on Machine Learning (ICML-98), Madison, Wisconsin, USA, 1998, pp. 91–99 (Morgan Kaufmann, San Francisco, California, USA).
39.
EpterS.KrishnamoorthyM.ZakiM.Clusterability detection and initial seed selection in large data sets. Technical report 99–6, Department of Computer Science, Rensselaer Polytechnic Institute, Troy, New York, USA, 1999.
40.
YangS.-Z.LuoS.-W.A novel algorithm for initializing clustering centers. In Proceedings of the 4th International Conference on Machine Learning and Cybernetics, Guangzhou, China, 2005, pp. 5579–5583.
41.
PhamD. T.DimovS. S.NguyenC. D.An incremental k-means algorithm. Proc. Instn Mech. Engrs Part C: J. Mechanical Engineering Science, 2004, 218(C7), 783–795.
42.
HuangZ.Extensions to the k-means algorithm for clustering large data sets with categorical values. Data Min. Knowl. Discov., 1998, 2(3), 283–304.
43.
BradleyP. S.FayyadU. M.ReinaC.Scaling clustering algorithms to large databases. In Proceedings of the 4th International Conference on Knowledge Discovery and Data Mining (KDD-98), New York, USA, 1998, pp. 9–15 (AAAI Press, Menlo Park, California, USA).
44.
FarnstromF.LewisJ.ElkanC.Scalability for clustering algorithms revisited. SIGKDD Explorations Newsletter of the ACM Special Interest Group on Knowledge Discovery and Data Mining, 2000, 2(1), 51–57.
45.
PhamD. T.DimovS. S.NguyenC. D.A two-phase k-means algorithm for large datasets. Proc. Instn Mech. Engrs Part C: J. Mechanical Engineering Science, 2004, 218(C10), 1269–1273.
46.
ChenT.-S.TsaiT.-H.ChenY.-T.LinC.-CChenR.-CLiS.-Y.ChenH.-Y.A combined k-means and hierarchical clustering method for improving the clustering efficiency of microarray. In Proceedings of the 2005 International Symposium on Intelligent Signal Processing and Communication Systems, Hong Kong, China, 2005, pp. 405–408.
47.
JinlanT.LinZ.SuqinZ.LuL.Improvement and parallelism of k-means clustering algorithm. Tsinghua Sci. Technol., 2005, 10(3), 277–281.
48.
NgR. T.HanJ.Efficient and effective clustering methods for spatial data mining. In Proceedings of the 20th International Conference on Very Large Databases, Santiago, Chile, 1994, pp. 145–155.
49.
EsterM.KriegelH.-P.XuX. W.Knowledge discovery in large spatial databases: Focusing techniques for efficient class identification. In Proceedings of the 4th International Symposium on Large Spatial Databases, Portland, Maine, USA, 1995, pp. 67–82.
50.
SilvermanB. W.Density estimation for statistics and data analysis, 1986 (Chapman & Hill, London, UK).
51.
BradleyP.FayyadU.ReinaC.Scaling EM (expectation maximisation) clustering to large databases. Microsoft Research Technical Report, MSR-TR-98–35, Redmond, Washington, USA, 1998.
52.
DudaR. O.HartP. E.Pattern classification and scene analysis, 1973 (John Wiley & Sons, New York, USA).
53.
ZhangT.RamakrishnanR.LivnyM.BIRCH: A new data clustering algorithm and its applications. Int. J. Data Min. Knowl. Discov., 1997, 1(2), 141–182.
54.
GuhaS.RastogiR.ShimK.CURE: An efficient clustering algorithm for large databases. In Proceedings of the ACM International Conference of the Special Interest Group on Management of Data (ACM-SIGMOD-98), Seattle, Washington, USA, 1998, pp. 73–84.
55.
EsterM.KriegelH.-P.SanderJ.XuX. W.A density-based algorithm for discovering clusters in large spatial databases with noise. In Proceedings of the 2nd International Conference on Knowledge Discovery and Data Mining, Portland, Oregon, USA, 1996, pp. 226–231 (AAAI Press, Menlo Park, California, USA).
56.
AnkerstM.BreunigM.KriegelH.-P.SanderJ.OPTICS: Ordering points to identify the clustering structure. In Proceedings of the ACM International Conference of the Special Interest Group on Management of Data (ACM-SIGMOD-99), Philadelphia, USA, 1999, pp. 49–60.
57.
HinneburgA.KeimD.An efficient approach to clustering large multimedia databases with noise. In Proceedings of the 4th International Conference on Knowledge Discovery and Data Mining, New York, USA, 1998, pp. 58–65.
58.
WangW.YangJ.MuntzR.STING: A statistical information grid approach to spatial data mining. In Proceedings of the 23rd International Conference on Very Large Databases (VLDB-97), Athens, Greece, 1997, pp. 186–195.
59.
SheikholeslamiG.ChatterjeeS.ZhangA.WaveCluster: A multi-resolution clustering approach for very large spatial databases. In Proceedings of the 24th International Conference on Very Large Databases (VLDB-98), New York, USA, 1998, pp. 428–439.
60.
AgrawalR.GehrkeJ.GunopulosD.RaghavanP.Automatic subspace clustering of high dimensional data for data mining applications. In Proceedings of the ACM International Conference of the Special Interest Group on Management of Data (ACM-SIGMOD-98), Seattle, Washington, USA, 1998, pp. 94–105.
61.
AgrawalR.GehrkeJ.GunopulosD.RaghavanP.Automatic subspace clustering of high dimensional data. Data Min. Knowl. Discov., 2005, 11, 5–33.
62.
HöppnerF.KlawonnF.KruseR.RunklerT.Fuzzy cluster analysis: methods for classification, data analysis and image recognition, 1999 (John Wiley & Sons, New York, USA).
63.
CrespoF.WeberR.A methodology for dynamic data mining based on fuzzy clustering. Fuzzy Sets Syst., 2005, 150, 267–284.
BouchachiaA.PedryczW.Data clustering with partial supervision. Data Min. Knowl. Discov., 2006, 12, 47–78.
67.
ZhangH.-C.HaungS. H.Applications of neural networks in manufacturing: A state-of-the-art survey. Int. J. Prod. Res., 1995, 33(3), 705–728.
68.
PhamD. T.LiuX.Neural networks for identification, prediction and control, 1999 (Springer-Verlag, London, UK).
69.
MonostoriL.AI and machine learning techniques for managing complexity, changes and uncertainties in manufacturing. Eng. Appl. Artif. Intell., 2003, 16(3), 227–291.
CarpenterG. A.GrossbergS.RosenD. B.Fuzzy ART: Fast stable learning and categorization of analog patterns by an adaptive resonance system. Neural Netw., 1991, 4, 759–771.
FreitasA. A.Data mining and knowledge discovery with evolutionary algorithms, 2002 (Springer-Verlag, Berlin, Germany).
75.
SrikanthR.GeorgeR.WarsiN.A variable-length genetic algorithm for clustering and classification. Pattern Recognit. Lett., 1995, 16(8), 789–800.
76.
MurthyC. A.ChowdhuryN.In search of optimal clusters using genetic algorithms. Pattern Recognit. Lett., 1996, 17(8), 825–832.
77.
FräntiP.KivijärviJ.KaukorantaT.NevalainenO.Genetic algorithms for large scale clustering problems. Computer, 1997, 40(9), 547–554.
78.
HallL. O.OzyurtI. B.BezdekJ. C.Clustering with a genetically optimized approach. IEEE Trans. Evol. Comput., 1999, 3(2), 103–112.
79.
TsengL. Y.YangS. B.A genetic approach to the automatic clustering problem. Pattern Recognit., 2001, 34(2), 415–424.
80.
SarafisI.ZalzalaA. M. S.TrinderP. W.A genetic rule-based data clustering toolkit. In Proceedings of the 2002 Congress on Evolutionary Computation, Honolulu, Hawaii, USA, 2002, pp. 1238–1243.
MaP. C. H.ChanK. C. C.YaoX.ChiuD. K. Y.An evolutionary clustering algorithm for gene expression microarray data analysis. IEEE Trans. Evol. Comput., 2006, 10(3), 296–314.
83.
CassR.DePietroJ.Computational intelligence methods for process discovery. Eng. Appl. Artif. Intell., 1998, 11, 675–681.
84.
CaudellT. P.SmithS. D. G.JohnsonG. C.An application of neural networks to group technology. Appl. Artif. Neural Netw., 1994, 1490, 612–621.
85.
SmithS. D. G.EscobedoR.AndersonM.CaudellT. P.A deployed engineering design retrieval system using neural networks. IEEE Trans. Neural Netw., 1997, 8(4), 847–851.
86.
KuoR. J.ChiS. C.TengP. W.Generalized part family formation through fuzzy self-organizing feature map neural network. Comput. Ind. Eng., 2001, 40, 79–100.
LiaoT. W.LeeK. S.Integration of a feature-based CAD system and an ART-1 neural model for GT coding and part family coding. Comput. Ind. Eng., 1994, 26(1), 93–104.
89.
GindyN. N. Z.RatchevT. M.CaseK.Component grouping for GT applications - a fuzzy clustering approach with validity measure. Int. J. Prod. Res., 1995, 33(9), 2493–2509.
90.
ChangC. A.TsaiC.-Y.Using ART1 neural networks with destructive solid geometry for design retrieving systems. Comput. Ind., 1997, 34(1), 27–41.
91.
LeeS. Y.FischerG. W.Grouping parts based on geometrical shapes and manufacturing attributes using a neural network. J. Intell. Manuf., 1999, 10, 199–209.
92.
TsaiC.-Y.ChangC. A.Fuzzy neural networks for intelligent design retrieval using associative manufacturing features. J. Intell. Manuf., 2003, 14, 183–195.
93.
WangC.-B.ChenY.-J.ChenY.-M.ChuH.-C.Application of ART neural network to development of technology for functional feature-based reference design. Comput. Ind., 2005, 56(5), 428–441.
94.
RomanowskiC. J.NagiR.SuditM.Data mining in an engineering design environment: Or applications from graph matching. Comput. Oper. Res., 2006, 33, 3150–3160.
95.
KulkarniU. R.KiangM. Y.Dynamic grouping of parts in flexible manufacturing system - a selforganizing neural network approach. Eur. J. Oper. Res., 1995, 84, 192–212.
96.
DagliC.HuggahalliR.Machine-part family formation with the adaptive resonance theory paradigm. Int. J. Prod. Res., 1995, 33(4), 893–913.
97.
Al-AhmariA. M. A.A fuzzy analysis approach for partmachine grouping in cellular manufacturing systems. Integr. Manuf. Syst., 2002, 13(7), 489–497.
98.
KaparthiS.SureshN. C.CervenyR. P.An improved neural network leader algorithm for partmachine grouping in group technology. Eur. J. Oper. Res., 1993, 69, 342–356.
99.
MalakootiB.YangZ.An unsupervised neural network approach for machine-part cell design. In Proceedings of the IEEE International Conference on Neural Network Orlando Florida USA, 1994, vol. 2665–670.
100.
MalakootiB.YangZ.A variable-parameter unsupervised learning clustering neural network approach with application to machine-part group formation. Int. J. Prod. Res., 1995, 33(9), 2395–2413.
101.
ChenS.-J.ChengC.-S.A neural network-based cell formation algorithm in cellular manufacturing. Int. J. Prod. Res., 1995, 33(2), 293–318.
102.
KamalS.BurkeL. I.FACT: A new neural network-based clustering algorithm for group technology. Int. J. Prod. Res., 1996, 34(4), 919–946.
103.
MaznataA.SettineriL.Application of fuzzy clustering in cellular manufacturing. Int. J. Prod. Res., 1997, 35(4), 1077–1094.
104.
SusantoS.KennedyR.PriceJ.New fuzzy c-means and assignment techniques-based cell formation algorithm to perform part-type clusters and machine-type clusters separately. Prod. Plan. Control, 1999, 10(4), 375–388.
105.
JosienK.LiaoT. W.Integrated use of fuzzy c-means and fuzzy KNN for GT part family and machine cell formation. Int. J. Prod. Res., 2000, 38(15), 3513–3536.
106.
JosienK.LiaoT. W.Simultaneous grouping of parts and machines with an integrated fuzzy clustering method. Fuzzy Sets Syst., 2002, 126, 1–21.
OhtaH.NakamuraM.Cell formation with reduction in setup times. Comput. Ind. Eng., 2002, 42, 317–327.
109.
DimopoulosC.MortN.Evolving knowledge for the solution of clustering problems in cellular manufacturing. Int. J. Prod. Res., 2004, 42(19), 4119–4133.
110.
DurmusogluM. B.NomakA.GT cells design and implementation in a glass mould production system. Comput. Ind. Eng., 2005, 48, 525–536.
111.
SureshN. C.SlompJ.KaparthiS.Sequence-dependent clustering of parts and machines: A fuzzy ART neural network approach. Int. J. Prod. Res., 1999, 37(14), 2793–2816.
112.
LiaoT. W.Design of line-type cellular manufacturing systems for minimum operating and material-handling costs. Int. J. Prod. Res., 1994, 32(2), 387–397.
113.
KiangM. Y.KulkarniU. R.TamK. Y.Selforganizing map network as an interactive clustering tool - an application to group technology. Decis. Support Syst., 1995, 15, 351–374.
114.
NairG. J.NarendranT. T.CASE: A clustering algorithm for cell formation with sequence data. Int. J. Prod. Res., 1998, 36(1), 157–179.
115.
ParkS.SureshN. C.Performance of fuzzy ART neural network and hierarchical clustering of part-machine grouping based on operation sequences. Int. J. Prod. Res., 2003, 41(14), 3185–3216.
116.
LankalapalliK.ChatterjeeS.ChangT. C.Feature recognition using ART-2: A self-organizing neural network. J. Intell. Manuf., 1997, 8, 203–214.
117.
XueD.DongZ.Coding and clustering of design and manufacturing features for concurrent design. Comput. Ind., 1997, 34, 139–153.
118.
ZulkifliA. H.MeeranS.Decomposition of interacting features using a Kohonon self-organizing feature map neural network. Eng. Appl. Artif. Intell., 1999, 12, 59–78.
119.
LiW. S.OngS. K.NeeA. Y. C.A hybrid method for recognizing interacting machining features. Int. J. Prod. Res., 2003, 41(9), 1887–1908.
CesarottiV.RossiL.SantoroR.A neural network clustering model for miscellaneous components production planning. Prod. Plan. Control, 1999, 10(4), 305–316.
122.
SebzalliY. M.WangX. Z.Knowledge discovery from process operational data using PAC and fuzzy clustering. Eng. Appl. Artif. Intell., 2001, 14, 607–616.
123.
JolliffeI. T.Principle component analysis, 1986 (Springer, New York, USA).
124.
KunduB.WhiteK. P.JrMastrangeloC.Defect clustering and classification for semiconductor devices. In Proceedings of the 45th Midwest Symposium on Circuits and Systems, 2002, vol. 2 II-561-II-564.
125.
VernetA.KoppG. A.Classification of turbulent flow patterns with fuzzy clustering. Eng. Appl. Artif. Intell., 2002, 15, 315–326.
126.
CasalinoG.MinutoloF. M. C.A model for evaluation of laser welding efficiency and quality using an artificial neural network and fuzzy logic. Proc. Instn Mech. Engrs Part B: J. Engineering Manufacture, 2004, 218, 641–646.
127.
Al-GhanimA.An unsupervised learning neural algorithm for identifying process behaviour on control charts and a comparison with supervised learning approaches. Comput. Ind. Eng., 1997, 32, 627–639.
128.
PacellaM.SemeraroQ.AnglaniA.Manufacturing quality control by means of a Fuzzy ART network trained on natural process data. Eng. Appl. Artif. Intell., 2004, 17(1), 83–96.
129.
PacellaM.SemeraroQ.AnglaniA.Adaptive resonance theory-based neural algorithms for manufacturing process quality control. Int. J. Prod. Res., 2004, 42(21), 4581–4607.
130.
PacellaM.SemeraroQ.Understanding ART-based neural algorithms as statistical tools for manufacturing process quality control. Eng. Appl. Artif. Intell., 2005, 18(6), 645–662.
131.
AfifyA. A.DimovS.NaimM. M.ValevaV.Detecting cyclical disturbances in supply networks using data mining techniques. In Proceedings of the 2nd European Conference on Management of Technology, Birmingham, UK, 2006, pp. 1–8.
132.
AfifyA. A.DimovS.NaimM. M.ValevaV.Data mining: A tool for detecting cyclical disturbances in supply networks. Proc. IMechE Part B: J. Engineering Manufacture, 2007, 221, in press.
