1.2 Theoretical Background
1.2.6 The role of Values and Norms in migration
A principal contribuição deste trabalho foi propor três novas abordagens para gerar os centros iniciais no algoritmo de agrupamento Fuzzy C-Means, que podem também ser aplicadas em suas variantes. Neste trabalho os métodos de inicialização propostos foram utilizados para gerar os centros iniciais dos grupos na variante ckMeans. Esses métodos trouxeram uma aceleração no tempo de processamento, preservaram ou melhoraram a qualidade do agrupamento perante a aplicação dos algoritmos originais, onde os centros iniciais dos grupos são escolhidos aleatoriamente.
A análise de agrupamento usando o Fuzzy C-Means e ckMeans com inicialização aleatória não é um processo realizado em apenas uma execução. É necessária uma série de tentativas e repetições para uma dada configuração de parâmetros de entrada. Com os métodos determinísticos de inicialização propostos, o FCM e o ckMeans são executados uma única vez até convergir, eliminando a aleatoriedade.
Os experimentos realizados com os conjuntos de dados Iris, Spambase, Page Blocks, Blobs, S4 e Moons mostraram que as partições obtidas pelos algoritmos FCM e ckMeans utilizando os métodos propostos na inicialização dos centros, em termos de valores dos índices de validação DB, SF e CR na maioria das configurações dos parâmetros de entrada, tem qualidade superior ao agrupamento com o FCM e ckMeans originais. Apesar de não serem tão significativas as diferenças. Os experimentos também mostraram uma aceleração no tempo de execução dos algoritmos. Portanto, para estas bases de dados as propostas de inicialização, Método I, Método II e Método III, selecionam melhores centros iniciais.
7.1
Trabalhos Futuros
Entre os trabalhos futuros a serem realizados com base nos métodos de inicialização desenvolvidos encontram-se:
variantes do FCM;
• Comparar os três métodos de inicialização dos centros com outras propostas de inicialização disponíveis na literatura;
Referências
ABU-ZEID, N.; KASHIF, R.; BADAWY, O. M. Immune based clustering for medical diagnostic systems. In: IEEE. 2012 International Conference on Advanced Computer Science Applications and Technologies (ACSAT). [S.l.], 2012. p. 372–375.
ARNALDO, H. A.; BEDREGAL, B. R. Um novo método de inicializaçao para o algoritmo fuzzy c-means. Jornadas Chilenas de Computación 2013, 2013.
ARNALDO, H. A.; BEDREGAL, B. R. Uma nova forma de inicializar os centros dos grupos em algoritmos tipo fuzzy c-means. Terceiro Congresso Brasileiro de Sistemas Fuzzy, 2014.
ARNALDO, H. A.; BEDREGAL, B. R. C. A new way to obtain the initial centroid clusters in fuzzy c-means algorithm. In: IEEE. Theoretical Computer Science (WEIT), 2013 2nd Workshop-School on. [S.l.], 2013. p. 139–144.
BENTLEY, J. L. Multidimensional binary search trees used for associative searching. Communications of the ACM, v. 18, n. 9, p. 509–517, 1975.
BEZDEK, J. C. Pattern recognition with fuzzy objective function algorithms. [S.l.]: Kluwer Academic Publishers, 1981.
BEZDEK, J. C.; PAL, S. K. Fuzzy models for pattern recognition. [S.l.]: IEEE press New York, 1992.
BOCK, H. H.; DIDAY, E. Analysis of symbolic data: exploratory methods for extracting statistical information from complex data. [S.l.]: Springer, 2000.
CAMPELLO, R. J.; HRUSCHKA, E. R. A fuzzy extension of the silhouette width criterion for cluster analysis. Fuzzy Sets and Systems, v. 157, n. 21, p. 2858–2875, 2006. CARVALHO, F. d. A. de. Fuzzy c-means clustering methods for symbolic interval data. Pattern Recognition Letters, v. 28, n. 4, p. 423–437, 2007.
CHAH, E. et al. Automated spike sorting algorithm based on laplacian eigenmaps and k-means clustering. Journal of neural engineering, IOP Publishing, v. 8, n. 1, p. 016006, 2011.
CHENG, T. W.; GOLDGOF, D. B.; HALL, L. O. Fast fuzzy clustering. Fuzzy sets and systems, v. 93, n. 1, p. 49–56, 1998.
CHIANG, I. W.-Y.; LIANG, G.-S.; YAHALOM, S. The fuzzy clustering method: Applications in the air transport market in taiwan. The Journal of Database Marketing & Customer Strategy Management, v. 11, n. 2, p. 149–158, 2003.
DAVE, R. N. Characterization and detection of noise in clustering. Pattern Recognition Letters, v. 12, n. 11, p. 657–664, 1991.
DAVIES, D. L.; BOULDIN, D. W. A cluster separation measure. Pattern Analysis and Machine Intelligence, IEEE Transactions on, IEEE, n. 2, p. 224–227, 1979.
DEMŠAR, J. Statistical comparisons of classifiers over multiple data sets. The Journal of Machine Learning Research, JMLR. org, v. 7, p. 1–30, 2006.
DEVIJVER, P. A.; KITTLER, J. Pattern recognition: A statistical approach. [S.l.]: Prentice/Hall International Englewood Cliffs, NJ, 1982.
DUDA, R. O.; HART, P. E. et al. Pattern classification and scene analysis. [S.l.: s.n.], 1973.
DUDA, R. O.; HART, P. E.; STORK, D. G. Pattern classification. [S.l.]: John Wiley & Sons, 2012.
DUNN, J. C. A fuzzy relative of the isodata process and its use in detecting compact well-separated clusters. Journal of Cybernetics, Taylor & Francis, v. 3, n. 3, p. 32–57, 1973.
EL-SONBATY, Y.; ISMAIL, M. Fuzzy clustering for symbolic data. IEEE Transactions on Fuzzy Systems, v. 6, n. 2, p. 195–204, 1998.
ESCHRICH, S. et al. Fast accurate fuzzy clustering through data reduction. IEEE Transactions on Fuzzy Systems, v. 11, n. 2, p. 262–270, 2003.
EVERITT, B.; LANDAU, S.; LEESE, M. Cluster analysis. 4th. Arnold, London, 2001. FISHER, R. A. The use of multiple measurements in taxonomic problems. Annals of eugenics, v. 7, n. 2, p. 179–188, 1936.
FRIEDMAN, M. The use of ranks to avoid the assumption of normality implicit in the analysis of variance. Journal of the American Statistical Association, Taylor & Francis, v. 32, n. 200, p. 675–701, 1937.
FRIEDMAN, M. A comparison of alternative tests of significance for the problem of m rankings. The Annals of Mathematical Statistics, JSTOR, v. 11, n. 1, p. 86–92, 1940. GAO, X.; XIE, W. Research process of fuzzy clustering theory development and its application. Science Bulletin, v. 44, n. 21, p. 2241–2251, 1999.
GORDON, A. D. Classification, (chapman & hall/crc monographs on statistics & applied probability). Chapman and Hall/CRC, New York, USA, 1999.
GREGORY, M.; SCATA, R.; BROWN, E. Web document classification using machine learning clustering algorithms. Journal of Computing Sciences in Colleges, v. 21, n. 6, p. 276–277, 2006.
GUSTAFSON, D. E.; KESSEL, W. C. Fuzzy clustering with a fuzzy covariance matrix. In: IEEE. Decision and Control including the 17th Symposium on Adaptive Processes, 1978 IEEE Conference on. [S.l.], 1978. v. 17, p. 761–766.
HALKIDI, M.; BATISTAKIS, Y.; VAZIRGIANNIS, M. On clustering validation techniques. Journal of Intelligent Information Systems, v. 17, n. 2-3, p. 107–145, 2001. HAMMER, B. et al. Intuitive clustering of biological data. In: IEEE. Neural Networks, 2007. IJCNN 2007. International Joint Conference on. [S.l.], 2007. p. 1877–1882. HAN, J.; KAMBER, M.; PEI, J. Data mining: concepts and techniques. [S.l.]: Morgan kaufmann, 2006.
HATHAWAY, R. J.; BEZDEK, J. C. Nerf c-means: Non-euclidean relational fuzzy clustering. Pattern recognition, v. 27, n. 3, p. 429–437, 1994.
HATHAWAY, R. J.; BEZDEK, J. C. Fuzzy c-means clustering of incomplete data. Systems, Man, and Cybernetics, Part B: Cybernetics, IEEE Transactions on, v. 31, n. 5, p. 735–744, 2001.
HATHAWAY, R. J.; DAVENPORT, J. W.; BEZDEK, J. C. Relational duals of the c-means clustering algorithms. Pattern recognition, v. 22, n. 2, p. 205–212, 1989. HOLLANDER, M. W. Nonparametric statistical methods. J Wiley New York, 1999. HRBACEK, K.; JECH, T. Introduction to Set Theory, Revised and Expanded. [S.l.]: Crc Press, 1999.
HUBERT, L.; ARABIE, P. Comparing partitions. Journal of classification, Springer, v. 2, n. 1, p. 193–218, 1985.
HUNG, M.-C.; YANG, D.-L. An efficient fuzzy c-means clustering algorithm. In: IEEE. Data Mining, 2001. ICDM 2001, Proceedings IEEE International Conference on. [S.l.], 2001. p. 225–232.
JAIN, A. K.; DUBES, R. C. Algorithms for clustering data. [S.l.]: Prentice-Hall, Inc., 1988.
JAIN, A. K.; MURTY, M. N.; FLYNN, P. J. Data clustering: a review. ACM computing surveys (CSUR), v. 31, n. 3, p. 264–323, 1999.
KAYMAK, U.; SETNES, M. Fuzzy clustering with volume prototypes and adaptive cluster merging. Fuzzy Systems, IEEE Transactions on, v. 10, n. 6, p. 705–712, 2002. KERSTEN, P. R. Fuzzy order statistics and their application to fuzzy clustering. Fuzzy Systems, IEEE Transactions on, v. 7, n. 6, p. 708–712, 1999.
KOLEN, J. F.; HUTCHESON, T. Reducing the time complexity of the fuzzy c-means algorithm. Fuzzy Systems, IEEE Transactions on, v. 10, n. 2, p. 263–267, 2002.
KRISHNAPURAM, R.; JOSHI, A.; YI, L. A fuzzy relative of the k-medoids algorithm with application to web document and snippet clustering. In: IEEE. Fuzzy Systems Conference Proceedings, 1999. FUZZ-IEEE’99. 1999 IEEE International. [S.l.], 1999. v. 3, p. 1281–1286.
KRISHNAPURAM, R.; KELLER, J. M. A possibilistic approach to clustering. Fuzzy Systems, IEEE Transactions on, v. 1, n. 2, p. 98–110, 1993.
LI, C.; BECERRA, V.; DENG, J. Extension of fuzzy c-means algorithm. In: IEEE. Cybernetics and Intelligent Systems, 2004 IEEE Conference on. [S.l.], 2004. v. 1, p. 405–409.
MACQUEEN, J. et al. Some methods for classification and analysis of multivariate observations. In: CALIFORNIA, USA. Proceedings of the fifth Berkeley symposium on mathematical statistics and probability. [S.l.], 1967. v. 1, n. 281-297, p. 14.
MIWA, T. Tables of the Studentized range upper quantiles. 2014. Available online at http://cse.niaes.affrc.go.jp/miwa/probcalc/s-range/srng_tbl.html.
PAL, N. R.; BEZDEK, J. C. On cluster validity for the fuzzy c-means model. Fuzzy Systems, IEEE Transactions on, v. 3, n. 3, p. 370–379, 1995.
PAL, N. R.; PAL, K.; BEZDEK, J. C. A mixed c-means clustering model. In: IEEE. Fuzzy Systems, 1997., Proceedings of the Sixth IEEE International Conference on. [S.l.], 1997. v. 1, p. 11–21.
PAUL, R.; HOQUE, A. S. M. L. Clustering medical data to predict the likelihood of diseases. In: IEEE. Digital Information Management (ICDIM), 2010 Fifth International Conference on. [S.l.], 2010. p. 44–49.
R Core Team. R: A Language and Environment for Statistical Computing. Vienna, Austria, 2014. Disponível em: <http://www.R-project.org>.
RAND, W. M. Objective criteria for the evaluation of clustering methods. Journal of the American Statistical association, Taylor & Francis Group, v. 66, n. 336, p. 846–850, 1971. RUDIN, W. Principles of mathematical analysis (international series in pure & applied mathematics). McGraw-Hill Publishing Co., 1976.
SALICRU, M.; VIVES, S.; ZHENG, T. Inferential clustering approach for microarray experiments with replicated measurements. IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB), v. 6, n. 4, p. 594–604, 2009.
SATO, M.; JAIN, L. C. Innovations in fuzzy clustering: Theory and applications (studies in fuzziness and soft computing). Springer-Verlag, 2006.
SHELDON, M. R.; FILLYAW, M. J.; THOMPSON, W. D. The use and interpretation of the friedman test in the analysis of ordinal-scale data in repeated measures designs. Physiotherapy Research International, Wiley Online Library, v. 1, n. 4, p. 221–228, 1996. TAN, P.-N. et al. Introduction to data mining. [S.l.]: Pearson Education India, 2007. VARGAS, R. R. de. Uma Nova Forma de Calcular os Centros dos Clusters em Algoritmos de Agrupamento Tipo Fuzzy C-Means. Tese (Doutorado) — Tese (doutorado em ciência da computaçao), Departamento de Informática e Matemática Aplicada (DIMAp), UFRN, Natal, RN, 2012.
VARGAS, R. R. de; BEDREGAL, B. R. Interval ckmeans: An algorithm for clustering symbolic data. In: IEEE. Fuzzy Information Processing Society (NAFIPS), 2011 Annual Meeting of the North American. [S.l.], 2011. p. 1–6.
VERMA, N. K. et al. Medical image segmentation using improved mountain clustering approach. In: IEEE. Information Technology: New Generations, 2009. ITNG’09. Sixth International Conference on. [S.l.], 2009. p. 1307–1312.
WALCK, C. Handbook on statistical distributions for experimentalists. [S.l.]: University of Stockholm Internal Report SUF-PFY/96-01, available from www. physto. se/˜ walck, 2007.
WANG, W.; YANG, J.; MUNTZ, R. Sting: A statistical information grid approach to spatial data mining. In: VLDB. [S.l.: s.n.], 1997. v. 97, p. 186–195.
WU, K.-L.; YANG, M.-S. Alternative c-means clustering algorithms. Pattern recognition, v. 35, n. 10, p. 2267–2278, 2002.
WU, X. et al. Top 10 algorithms in data mining. Knowledge and Information Systems, v. 14, n. 1, p. 1–37, 2008.
WU, Z.-d.; XIE, W.-x.; YU, J.-p. Fuzzy c-means clustering algorithm based on kernel method. In: IEEE. Computational Intelligence and Multimedia Applications, 2003. ICCIMA 2003. Proceedings. Fifth International Conference on. [S.l.], 2003. p. 49–54. XIE, X. L.; BENI, G. A validity measure for fuzzy clustering. IEEE Transactions on Pattern Analysis and Machine Intelligence, v. 13, n. 8, p. 841–847, 1991.
XU, R.; WUNSCH, D. et al. Survey of clustering algorithms. Neural Networks, IEEE Transactions on, v. 16, n. 3, p. 645–678, 2005.
YAGER, R. R.; FILEV, D. P. Approximate clustering via the mountain method. Systems, Man and Cybernetics, IEEE Transactions on, v. 24, n. 8, p. 1279–1284, 1994. YANG, M.-S.; WU, K.-L. A new validity index for fuzzy clustering. In: IEEE. Fuzzy Systems, 2001. The 10th IEEE International Conference on. [S.l.], 2001. v. 1, p. 89–92. YANG, Y.; HUANG, S. Image segmentation by fuzzy c-means clustering algorithm with a novel penalty term. Computing and Informatics, v. 26, n. 1, p. 17–31, 2012.
ZADEH, L. A. Fuzzy sets. Information and control, v. 8, n. 3, p. 338–353, 1965.
ZHANG, K.-s. et al. New modification of fuzzy c-means clustering algorithm. In: Fuzzy Information and Engineering. [S.l.]: Springer, 2009. p. 448–455.
ZHANG, W.-b.; HU, H.-z.; LIU, W.-j. Rules extraction of interval type-2 fuzzy logic system based on fuzzy c-means clustering. In: IEEE. Fuzzy Systems and Knowledge Discovery, 2007. FSKD 2007. Fourth International Conference on. [S.l.], 2007. v. 2, p. 256–260.