Magíster en Gestión de Operaciones. Ingeniero Civil Industrial / En este trabajo se desarrollar una metodología para enfrentar el problema de clustering cuando alguno de los atributos se encuentra incompleto y se va completando en forma dinámica. Y se implementa dicha metodología en un modelo particular. El modelo implementado en este trabajo se basa en el modelo de projected clustering (Proclus) desarrollado por Aggarwal et al. en 1999. Al problema de dinamismo se le agregan las siguientes restricciones: La imposibilidad de imputar los valores faltantes (los que todavía no llegan) al igual que la imposibilidad de marginalizar las las con dichos valores faltantes. Estas restricciones se imponen ya que de lo contrario el problema se puede resolver en fácilmente de forma estática y/o tiene soluciones dinámicas conocidas. Se modificó el modelo de proyected clustering para considerar las restricciones impuestas al igual que implementar el dinamismo buscado. Para evaluar el modelo se generaron datos de forma sintética (95000 filas), con diferentes instancias en las que se buscan generar distintos escenarios donde la estructura de los clusters cambia a medida que los nuevos datos llegan. La generación sintética permitió evaluar los resultados y observar la evolución en la detección de las dimensiones y los clusters. Dado el modelo base escogido dicha modificación manifiesta alguna de sus mismas limitaciones, como es el caso de necesitar un número elevado de dimensiones. Los resultados entregados por la implementación del modelo fueron satisfactorios. Encontrando las soluciones esperadas después de un número razonable de iteraciones y realizado las operaciones en un tiempo menor que la aplicación estática del modelo tras la llegada de cada lote de datos. De igual forma se generó una medida para analizar y/o detectar los cambios en la estructura de los clusters a medida que llegan los datos de la nueva columna. Finalmente, en relación a los objetivos planteados en este trabajo, se puede concluir que el modelo desarrollado logra cumplir con los objetivos planteados, logrando desarrollar un modelo y metodológica que enfrente en forma efectiva el problema antes descrito al igual que el aplicarlo a datos simulados y analizar dichos resultados.

The clustering problem has been discussed extensively in the database literature as a tool for many applications, for example, bioinformatics. Traditional clustering algorithms consider all of the dimensions of an input dataset in an attempt to learn as much as possible about each object described. In the high dimensional data, however, many of the dimensions are often irrelevant. Therefore, projected clustering is proposed. A projected cluster is a subset C of data points together with a subset D of dimensions such that the points in C are closely clustered in the subspace of dimensions D. There have been many algorithms proposed to find the projected cluster. Most of them can be divided into three kinds of classification: partitioning, density-based, and hierarchical. The DOC algorithm is one of well-known density-based algorithms for projected clustering. It uses a Monte Carlo algorithm for iteratively computing projected clusters, and proposes a formula to calculate the quality of cluster. The FPC algorithm is an extended version of the DOC algorithm, it uses the mining large itemsets approach to find the dimensions of projected cluster. Finding the large itemsets is the main goal of mining association rules, where a large itemset is a combination of items whose appearing times in the dataset is greater than a given threshold. Although the FPC algorithm has used the technique of mining large itemsets to speed up finding projected clusters, it still needs many user-specified parameters to work. Moreover, in the first step, to choose the medoid, the FPC algorithm applies a random approach for several times to get the medoid, which takes long time and may still find a bad medoid. Furthermore, the way to calculate the quality of a cluster can be considered in more details, if we take the weight of dimensions into consideration. Therefore, in this thesis, we propose an algorithm which improves those disadvantages. First, we observe that the relationship between parameters, and propose a parameter-relationship-based algorithm that needs only two parameters, instead of three parameters in most of projected clustering algorithms. Next, our algorithm chooses the medoid with the median, we choose the medoid only one time and the quality of our cluster is better than that in the FPC algorithm. Finally, our quality measure formula considers the weight of each dimension of the cluster, and gives different values according to the times of occurrences of dimensions. This formula makes the quality of projected clustering based on our algorithm better than that of the FPC algorithm. It avoids the cluster containing too many irrelevant dimensions. From our simulation results, we show that our algorithm is better than the FPC algorithm, in term of the execution time and the quality of clustering.