{"id":{"repo_id":"houston","oai_identifier":"oai:uh-ir.tdl.org:10657/1935"},"canonical_url":"https://search.dev.ndltd.org/etd/houston/oai:uh-ir.tdl.org:10657/1935","repository":{"repo_id":"houston","name":"University of Houston","base_url":"https://uh-ir.tdl.org/server/oai/request"},"display":{"title":"A Fast Clustering Algorithm Merging The Expectation Maximization Algorithm and Markov Chain Monte Carlo","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.","abstract_html":"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.","abstract_has_math":false,"creators":["Matusevich, David Sergio 1969-"],"institution":"University of Houston","degree_name":"Master of Science","degree_level":"Masters","degree_discipline":"Computer Science","degree_department":null,"school":null,"contributors":[],"advisors":["Ordonez, Carlos"],"committee_chairs":[],"committee_members":["Eick, Christoph F.","Azencott, Robert"],"year":2015,"date_issued":"2015-05","date_published":"2015-05","updated_at":"2026-07-24T02:31:52Z","subjects":["Data mining","Clustering","Expectation maximization","Bayesian Methods","Markov Chain Monte Carlo"],"languages":["eng"],"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)."],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/10657/1935","outbound_label":"Handle","outbound_source":"dc:identifier.uri"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.advisor","label":"Advisor","values":["Ordonez, Carlos"]},{"key":"dc:contributor.committeemember","label":"Committee Member","values":["Eick, Christoph F.","Azencott, Robert"]},{"key":"dc:creator","label":"Author","values":["Matusevich, David Sergio 1969-"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2017-07-24T18:21:36Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2017-07-24T18:21:36Z"]},{"key":"dc:date.issued","label":"Date","values":["2015-05"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Computer Science"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Masters"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Master of Science"]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Houston"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Data mining","Clustering","Expectation maximization","Bayesian Methods","Markov Chain Monte Carlo"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language.iso","label":"Language (ISO)","values":["eng"]},{"key":"dc:rights","label":"Dc Rights","values":["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)."]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.uri","label":"Identifier URI","values":["http://hdl.handle.net/10657/1935"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["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."]},{"key":"dc:format.mimetype","label":"Dc Format Mimetype","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["A Fast Clustering Algorithm Merging The Expectation Maximization Algorithm and Markov Chain Monte Carlo"]}]}],"canonical_facts":{"dc:contributor.advisor":["Ordonez, Carlos"],"dc:contributor.committeemember":["Eick, Christoph F.","Azencott, Robert"],"dc:creator":["Matusevich, David Sergio 1969-"],"dc:date.accessioned":["2017-07-24T18:21:36Z"],"dc:date.available":["2017-07-24T18:21:36Z"],"dc:date.issued":["2015-05"],"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:format.mimetype":["application/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","Clustering","Expectation maximization","Bayesian Methods","Markov Chain Monte Carlo"],"dc:title":["A Fast Clustering Algorithm Merging The Expectation Maximization Algorithm and Markov Chain Monte Carlo"],"thesis:degree_discipline":["Computer Science"],"thesis:degree_level":["Masters"],"thesis:degree_name":["Master of Science"],"thesis:institution_name":["University of Houston"]},"updated_at":"2026-07-24T02:31:52Z"}