Mining complex databases using the EM algorithm
CARLOS R. ORDÓÑEZ, Edward R. Omiecinski · 2000
This thesis focused on developing efficient data mining algorithms based on the Expectation-Maximization (EM) algorithm. The EM algorithm is a general numerical optimization method that solves many important statistical problems. In particular it can be used to perform clustering, and that is the aspect this work concentrated on. An algorithm to mine association rules from a collection of images segmented by EM was introduced. Experiments with synthetic images show the algorithm is reasonably accurate and fast. Then the problem of programming EM inside a relational DBMS was studied. Three efficient ways to implement the EM algorithm in the SQL language and important improvements were proposed. Then this work studied the general problem of clustering large data sets with high dimensionality. A fast and robust EM clustering algorithm was proposed for that purpose. This algorithm incorporates tunable initialization, sufficient statistics, cluster splitting, outlier handling and regularization techniques. Experimental evaluation shows the algorithm is fast and accurate. Finally, this thesis proved association rule mining can be solved as a clustering problem. The fast clustering algorithm was customized to build a statistical model for association rules. This model allows efficient approximate mining of association rules. The EM algorithm has had a proven success and it is still an active research topic in the Statistics and Machine Learning communities. It will be more widely used for Data Mining applications as it is better understood and optimized by database researchers. This work is a step in that direction.