A Fast Clustering Algorithm Merging The Expectation Maximization Algorithm and Markov Chain Monte Carlo

Clustering is an important problem in Statistics and Machine Learning that is usually solved using Likelihood Maximization methods, of which the Expectation-Maximization algorithm (EM) is the most common. In this work we present an algorithm merging Markov Chain Monte Carlo methods with the EM algorithm to find qualitatively better solutions for the clustering problem. We present brief introductions to two popular clustering algorithms, K-Means and EM, as well as the Markov Chain Monte Carlo algorithm. We show how these algorithms can be combined and incorporated into a Database Management System (DBMS) using a combination of SQL queries and User Defined Functions (UDFs). Even though SQL is not optimized for complex calculations, as it is constrained to work on tables and columns, it is unparalleled in handling all aspects of storage management, security of the information, fault management, etc. Our algorithm makes use of these characteristics to produce portable solutions that are comparable to the results obtained by other algorithms and are more efficient since the calculations are all performed inside the DBMS. To simplify the calculation we use very simple scalar UDFs, of a type that is available in most DBMS. The solution has linear time complexity on the size of the data set and it has a linear speedup with the number of servers in the cluster. This was achieved using sufficient statistics and a simplified model that assigns the data-points to different clusters during the E-step in an incremental manner and the introduction of a Sampling step in order to explore the solution space in a more efficient manner. Preliminary experiments show very good agreement with standard solutions.

Name thesis:degree_name

Master of Science

Level thesis:degree_level

Masters

Discipline thesis:degree_discipline

Computer Science

Grantor

University of Houston

Year dc:date.issued

2015

Author dc:creator

• Matusevich, David Sergio 1969-

Advisor dc:contributor.advisor

• Ordonez, Carlos

Committee members dc:contributor.committeemember

• Eick, Christoph F.
• Azencott, Robert

• Data mining
• Clustering
• Expectation maximization
• Bayesian Methods
• Markov Chain Monte Carlo

Statement dc:rights

• The author of this work is the copyright owner. UH Libraries and the Texas Digital Library have their permission to store and provide access to this work. UH Libraries has secured permission to reproduce any and all previously published materials contained in the work. Further transmission, reproduction, or presentation of this work is prohibited except with permission of the author(s).

Language dc:language.iso

eng

Handle dc:identifier.uri

http://hdl.handle.net/10657/1935

OAI identifier oai:identifier

oai:uh-ir.tdl.org:10657/1935