Loading...
11 results
Search Results
Now showing 1 - 10 of 11
- An MML embedded approach for estimating the number of clustersPublication . Silvestre, Cláudia; Cardoso, Maria Margarida G. M. S.; Figueiredo, MárioAssuming that the data originate from a finite mixture of multinomial distributions, we study the performance of an integrated Expectation Maximization (EM) algorithm considering Minimum Message Length (MML) criterion to select the number of mixture components. The referred EM-MML approach, rather than selecting one among a set of pre-estimated candidate models (which requires running EM several times), seamlessly integrates estimation and model selection in a single algorithm. Comparisons are provided with EM combined with well-known information criteria – e.g. the Bayesian information Criterion. We resort to synthetic data examples and a real application. The EM-MML computation time is a clear advantage of this method; also, the real data solution it provides is more parsimonious, which reduces the risk of model order overestimation and improves interpretability
- Determining the number of clusters in categorical dataPublication . Silvestre, Cláudia; Cardoso, Margarida; Figueiredo, MárioCluster analysis for categorical data has been an active area of research. A well-known problem in this area is the determination of the number of clusters, which is unknown and must be inferred from the data. In order to estimate the number of clusters, one often resorts to information criteria, such as BIC (Bayesian information criterion), MML (minimum message length, proposed by Wallace and Boulton, 1968), and ICL (integrated classification likelihood). In this work, we adopt the approach developed by Figueiredo and Jain (2002) for clustering continuous data. They use an MML criterion to select the number of clusters and a variant of the EM algorithm to estimate the model parameters. This EM variant seamlessly integrates model estimation and selection in a single algorithm. For clustering categorical data, we assume a finite mixture of multinomial distributions and implement a new EM algorithm, following a previous version (Silvestre et al., 2008). Results obtained with synthetic datasets are encouraging. The main advantage of the proposed approach, when compared to the above referred criteria, is the speed of execution, which is especially relevant when dealing with large data sets.
- Feature selection for clustering categorical data with an embedded modelling approachPublication . Silvestre, Cláudia; Cardoso, Margarida; Figueiredo, MárioResearch on the problem of feature selection for clustering continues to develop. This is a challenging task, mainly due to the absence of class labels to guide the search for relevant features. Categorical feature selection for clustering has rarely been addressed in the literature, with most of the proposed approaches having focused on numerical data. In this work, we propose an approach to simultaneously cluster categorical data and select a subset of relevant features. Our approach is based on a modification of a finite mixture model (of multinomial distributions), where a set of latent variables indicate the relevance of each feature. To estimate the model parameters, we implement a variant of the expectation-maximization algorithm that simultaneously selects the subset of relevant features, using a minimum message length criterion. The proposed approach compares favourably with two baseline methods: a filter based on an entropy measure and a wrapper based on mutual information. The results obtained on synthetic data illustrate the ability of the proposed expectation-maximization method to recover ground truth. An application to real data, referred to official statistics, shows its usefulness.
- A clustering view on ESS measures of political interest: an EM-MML approachPublication . Silvestre, Cláudia; Cardoso, Margarida; Figueiredo, MárioIn this work, we perform the clustering of European regions, based on their citizens’ political interests and electoral participation, as expressed in data from the two most recent European Social Surveys (ESS) - 2012 (round 6) and 2014 (round 7). We resort to a new clustering approach, named EM-MML, which clusters categorical data and simultaneously determines the number of clusters. Clustering is applied to sets of questions referring to whether the citizens were involved in “different ways of trying to improve things in their country or help prevent things from going wrong” – e.g., signed a petition or worked in a political organisation or association. The results of the EM-MML approach are compared with results from the classical EM approach combined with several information criteria. EM-MML approach provides more parsimonious and robust solutions than those obtained by standard EM and it is also faster than the other methods considered, which is especially relevant when dealing with large data sets.
- O critério Minimum Message Length na estimação de modelos de mistura sobre dados mistosPublication . Silvestre, Cláudia; Cardoso, Margarida; Figueiredo, MárioO agrupamento sobre dados mistos é um problema prático comum, nomeadamente no âmbito das ciências sociais. Este pode referir-se, por exemplo, à constituição de segmentos homogéneos de indivíduos, considerando as suas características quer quantitativas, quer qualitativas. A abordagem metodológica deste problema tem sido diversa. Podem encontrar-se, por exemplo, versões do algoritmo K-Médias capazes de lidar com dados métricos e categoriais. Neste trabalho, consideramos o agrupamento de dados mistos, usando um modelo de mistura e propondo o uso do critério Minimum Message Lenght (MML) para a sua estimação. Este critério advém da teoria da informação, considerando um modelo mais adequado aquele que permite uma descrição mais sucinta das observações [3]. Figueiredo e Jain [1] foram pioneiros na utilização deste critério para estimação de misturas de gaussianas. Uma primeira proposta para a utilização do MML em misturas de multinomiais foi apresentada por Silvestre et al [2]. A análise proposta integra dados mistos considerando uma mistura de gaussianas e multinomiais e um algoritmo que é uma variante do conhecido expectation-maximization. A metodologia é testada comparativamente com critérios comuns para a seleção de modelos de mistura, nomeadamente o integrated completed lilelihood , que é particularmente adequado neste contexto. A análise é efetuada sobre 2 conjuntos de dados sintéticos e dados reais (do European Social Survey). São analisadas vantagens comparativas na robustez relativamente a diferentes processos de inicialização, no tempo de computação e na qualidade do agrupamento obtido.
- Model selection in discrete clustering: the EM-MML algorithmPublication . Silvestre, Cláudia; Cardoso, Margarida; Figueiredo, MárioFinite mixture models are widely used for cluster analysis in several areas of application. They are commonly estimated through likelihood maximization (using diverse variants of the expectation-maximization algorithm) and the number of components (or clusters) is determined resorting to information criteria: the EM algorithm is run several times and then one of the pre-estimated candidate models is selected (e.g. using the BIC criterion). We propose a new clustering approach to deal with the clustering of categorical data (quite common in social sciences) and simultaneously identify the number of clusters - the EM-MML algorithm. This approach assumes that the data comes from a finite mixture of multinomials and uses a variant of EM to estimate the model parameters and a minimum message length (MML) criterion to estimate the number of clusters. EM-MML thus seamlessly integrates estimation and model selection in a single algorithm. The EM-MML is compared with traditional EM approaches, using alternative information criteria. Comparisons rely on synthetic datasets and also on a real dataset (data from the European Social Survey). The results obtained illustrate the parsimony of the EM-MML solutions as well as their clusters cohesion-separation and stability. A clear advantage of EM-MML is also the computation time.
- An MML embedded approach for estimating the number of clustersPublication . Silvestre, Cláudia; Cardoso, Margarida; Figueiredo, MárioAssuming that the data originate from a finite mixture of multinomial distributions, we study the performance of an integrated Expectation Maximization (EM) algorithm considering Minimum Message Length (MML) criterion to select the number of mixture components. The referred EM-MML approach, rather than selecting one among a set of pre-estimated candidate models (which requires running EM several times), seamlessly integrates estimation and model selection in a single algorithm. Comparisons are provided with EM combined with well-known information criteria – e.g. the Bayesian information Criterion. We resort to synthetic data examples and a real application. The EM-MML computation time is a clear advantage of this method; also, the real data solution it provides is more parsimonious, which reduces the risk of model order overestimation and improves interpretability.
- Seleção do número de segmentos em modelos de mistura sobre dados categoriais – um estudo comparativoPublication . Silvestre, Cláudia; Cardoso, Margarida; Figueiredo, MárioA análise de agrupamento tem sido usada em inúmeras áreas de aplicação, tais como ciências sociais, medicina, sociologia, engenharia, biologia, ciências de computação e marketing. O seu crescente uso e os novos desafios que se associam à especificidade dos dados têm motivado a procura de novas metodologias e de soluções cada vez mais precisas. Os modelos de mistura finita [5] que têm uma longa tradição em agrupamento são um exemplo. Nestes modelos, a distribuição conjunta para as variáveis base de segmentação é considerada como sendo uma soma ponderada de distribuições intra-segmentos. Esta natureza probabilística/estatística subjacente à análise de agrupamento, feita através de estimação de modelos de mistura finita, tem várias vantagens. Uma delas é serem modelos muito fiexíveis permitindo a modelação de variáveis de natureza diferente. Nomeadamente, as variáveis contínuas são usualmente modeladas por distribuições gaussianas e as categoriais por distribuições multinomiais. Outra vantagem é a possibilidade de se abordar formalmente a determinação do número de segmentos a considerar. Determinar o número de componentes de mistura, ou seja, o número de segmentos, é um domínio ativo de investigação em agrupamento [4]. Neste âmbito, alguns autores têm usado critérios de informação, tais como o Bayesian Information Criterion (BIC) [9], o Akaike Information Criterion (AIC)[1] e suas variantes, ou o Integrated Completed Likelihood (ICL) [2]. Nestes casos, o agrupamento é feito para diferentes números de segmentos e escolhe-se a solução que corresponde ao melhor valor do critério pré-definido. Uma abordagem diferente considera a determinação do número de segmentos na estimação do modelo. Para a estimação de todos os parâmetros do modelo, incluíndo o número de segmentos, é usado (em [6]) o critério Minimum Message Length (MML). Neste trabalho, consideram-se dados categoriais e são usados modelos de mistura finita, com o objetivo de analisar comparativamente o desempenho dos critérios anteriormente apresentados: critérios em que a identificação do número de segmentosé feita após o agrupamento, i.e. a posteriori vs. critérios em que a mesma identificação é feita simultaneamente (embedded). As análises comparativas são feitas em relação ao tempo de computação, à qualidade do agrupamento obtido bem como à sua robustez, tendo em conta diferentes níveis de separação entre os segmentos. Como medidas de qualidade são usados indicadores de coesão-separação (e.g. índices Silhueta [8] e Calinski e Harabasz [3]) e são ainda usados índices de concordância com a estrutura conhecida (e.g. Adjusted Rand [7]). Referências [1] Akaike, H. Maximum Likelihood Identification of Gaussian Autorregressive Moving Average Models. Biometrika , 60, 255-265, 1973. [2] Biernacki, C.,Celeux, G., Govaert, G. Assessing a Mixture Model for Clustering with the Integrated Completed Likelihood. IEEE Transactions on Pattern analysis and Machine Intelligence, 22, 719-25, 2000. [3] Calinski, R. B., Harabasz, J. A dendrit method for cluster analysis. Communications in Statistics , 3(1), 1-27, 1974. [4] Celeux, G., Frühwirth-Schnatter,S., Robert, C. Model Selection for Mixture Models-Perspectives and Strategies . Handbook of Mixture Analysis, CRC Press, 2018. [5] Everitt, B. S. A -nite mixture model for the clustering of mixed-mode data. Statistics and probability letters , 6(5), 305-309, 1988. [6] Figueiredo, M. A. T., Jain, A. K. Unsupervised learning of finite mixture models. IEEE Transactions on Pattern Analysis and Machine Intelligence, 24(3), 381-396, 2002. [7] Hubert, L., Arabie, P. Comparing partitions. Journal of classification, 2(1), 193-218, 1985. [8] Kaufman, L., Rousseeuw, P. J. Finding groups in data: an Introduction to cluster analysis. Wiley, NY, 1990. [9] Schwarz, G. Estimating the Dimension of a Model The Annals of Statistics ,6, 46-464, 1978.
- Clustering and selecting categorical featuresPublication . Silvestre, Cláudia; Cardoso, Margarida; Figueiredo, MárioIn data clustering, the problem of selecting the subset of most relevant features from the data has been an active research topic. Feature selection for clustering is a challenging task due to the absence of class labels for guiding the search for relevant features. Most methods proposed for this goal are focused on numerical data. In this work, we propose an approach for clustering and selecting categorical features simultaneously. We assume that the data originate from a finite mixture of multinomial distributions and implement an integrated expectation-maximization (EM) algorithm that estimates all the parameters of the model and selects the subset of relevant features simultaneously. The results obtained on synthetic data illustrate the performance of the proposed approach. An application to real data, referred to official statistics, shows its usefulness.
- The number of clusters on trustPublication . Silvestre, Cláudia; Cardoso, Margarida; Figueiredo, MárioIn this work we analyse the perfomance of a new Expectation Maximization (EM) clustering approach. This method is based on the Minimum Message Lenght (MML) criterion and simultaneously yields clustering of categorical data and the number of clusters. We group European citizens based on their trust in institutions, using Europen Social Survey data. The results obtained illustrate the parsimony, the cohesion-separation and stability of the EM-MML solutions, when compared to traditional information criteria EM based approaches.