A Fast Clustering Algorithm Merging The Expectation Maximization Algorithm and Markov Chain Monte Carlo
| dc.contributor.advisor | Ordonez, Carlos | |
| dc.contributor.committeeMember | Eick, Christoph F. | |
| dc.contributor.committeeMember | Azencott, Robert | |
| dc.creator | Matusevich, David Sergio 1969- | |
| dc.creator.orcid | 0000-0001-7494-095X | |
| dc.date.accessioned | 2017-07-24T18:21:36Z | |
| dc.date.available | 2017-07-24T18:21:36Z | |
| dc.date.created | May 2015 | |
| dc.date.issued | 2015-05 | |
| dc.date.submitted | May 2015 | |
| dc.date.updated | 2017-07-24T18:21:37Z | |
| dc.description.abstract | 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. | |
| dc.description.department | Computer Science, Department of | |
| dc.format.digitalOrigin | born digital | |
| dc.format.mimetype | application/pdf | |
| dc.identifier.citation | Portions of this document appear in: Matusevich, David, and Carlos Ordonez. "A clustering algorithm merging MCMC and EM methods using SQL queries." In Proceedings of the 3rd International Workshop on Big Data, Streams and Heterogeneous Source Mining: Algorithms, Systems, Programming Models and Applications, pp. 61-76. 2014. http://proceedings.mlr.press/v36/matusevich14.pdf | |
| dc.identifier.uri | http://hdl.handle.net/10657/1935 | |
| dc.language.iso | eng | |
| 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). | |
| dc.subject | Data mining | |
| dc.subject | Clustering | |
| dc.subject | Expectation maximization | |
| dc.subject | Bayesian Methods | |
| dc.subject | Markov Chain Monte Carlo | |
| dc.title | A Fast Clustering Algorithm Merging The Expectation Maximization Algorithm and Markov Chain Monte Carlo | |
| dc.type.dcmi | text | |
| dc.type.genre | Thesis | |
| thesis.degree.college | College of Natural Sciences and Mathematics | |
| thesis.degree.department | Computer Science, Department of | |
| thesis.degree.discipline | Computer Science | |
| thesis.degree.grantor | University of Houston | |
| thesis.degree.level | Masters | |
| thesis.degree.name | Master of Science |