{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/46604"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/46604","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Pattern extraction and clustering for high-dimensional discrete data","abstract":"We explore connections of low-rank matrix factorizations with interesting problems in data mining and machine learning. We propose a framework for solving several low-rank matrix factorization problems, including binary matrix factorization, constrained binary matrix factorization, weighted constrained binary matrix factorization, densest k-subgraph, and orthogonal nonnegative matrix factorization. These combinatorial problems are NP-hard. Our goal is to develop effective approximation algorithms with good theoretical properties and apply them to solve various real application problems. We reformulate each of the problems as a special clustering problem that has the same optimal solution as the corresponding original problem. Making use of this property, we develop clustering algorithms to solve corresponding low-rank matrix factorization problems. We prove that most of our clustering algorithms have constant approximation ratios, which is a highly desirable property for NP-hard problems. We apply the proposed algorithms and compare them with existing methods for real applications in pattern extraction, document clustering, transaction data mining, recommender systems, bicluster discovery in gene expression data, social network mining, and image representation.","abstract_html":"We explore connections of low-rank matrix factorizations with interesting problems in data mining and machine learning. We propose a framework for solving several low-rank matrix factorization problems, including binary matrix factorization, constrained binary matrix factorization, weighted constrained binary matrix factorization, densest k-subgraph, and orthogonal nonnegative matrix factorization. These combinatorial problems are NP-hard. Our goal is to develop effective approximation algorithms with good theoretical properties and apply them to solve various real application problems. We reformulate each of the problems as a special clustering problem that has the same optimal solution as the corresponding original problem. Making use of this property, we develop clustering algorithms to solve corresponding low-rank matrix factorization problems. We prove that most of our clustering algorithms have constant approximation ratios, which is a highly desirable property for NP-hard problems. We apply the proposed algorithms and compare them with existing methods for real applications in pattern extraction, document clustering, transaction data mining, recommender systems, bicluster discovery in gene expression data, social network mining, and image representation.","abstract_has_math":false,"creators":["Jiang, Peng"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Computer Science","degree_department":null,"school":null,"contributors":["Heath, Michael T.","Olson, Luke N.","Zhai, ChengXiang","Park, Haesun"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2014,"date_issued":"2014-01-16T17:55:55Z","date_published":"2014-01-16T17:55:55Z","updated_at":"2026-07-22T22:25:36Z","subjects":["low-rank matrix factorization","binary matrix factorization","k-means clustering","approximation algorithm","pattern extraction","association rule mining","document clustering","weighted binary matrix factorization","bicluster discovery","densest k-subgraph","social network mining"],"languages":["en"],"rights":["Copyright 2013 Peng Jiang"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/2142/46604","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Heath, Michael T.","Olson, Luke N.","Zhai, ChengXiang","Park, Haesun"]},{"key":"dc:creator","label":"Author","values":["Jiang, Peng"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2014-01-16T17:55:55Z","2013-12"]},{"key":"dc:type","label":"Dc Type","values":["text"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Computer Science"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Dissertation"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Ph.D."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["low-rank matrix factorization","binary matrix factorization","k-means clustering","approximation algorithm","pattern extraction","association rule mining","document clustering","weighted binary matrix factorization","bicluster discovery","densest k-subgraph","social network mining"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2013 Peng Jiang"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/46604"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["We explore connections of low-rank matrix factorizations with interesting problems in data mining and machine learning. We propose a framework for solving several low-rank matrix factorization problems, including binary matrix factorization, constrained binary matrix factorization, weighted constrained binary matrix factorization, densest k-subgraph, and orthogonal nonnegative matrix factorization. These combinatorial problems are NP-hard. Our goal is to develop effective approximation algorithms with good theoretical properties and apply them to solve various real application problems. We reformulate each of the problems as a special clustering problem that has the same optimal solution as the corresponding original problem. Making use of this property, we develop clustering algorithms to solve corresponding low-rank matrix factorization problems. We prove that most of our clustering algorithms have constant approximation ratios, which is a highly desirable property for NP-hard problems. We apply the proposed algorithms and compare them with existing methods for real applications in pattern extraction, document clustering, transaction data mining, recommender systems, bicluster discovery in gene expression data, social network mining, and image representation.","Item withdrawn by Laura Spradlin (lspradl2@illinois.edu) on 2013-11-21T21:19:18Z Item was in collections: University of Illinois Theses & Dissertations (ID: 1) No. of bitstreams: 1 Jiang_Peng.pdf: 10599343 bytes, checksum: 43484d41a082d8f682f84ffa3fc19efb (MD5)","Made available in DSpace on 2014-01-16T17:55:55Z (GMT). No. of bitstreams: 2 Peng_Jiang.pdf: 10599343 bytes, checksum: 43484d41a082d8f682f84ffa3fc19efb (MD5) license.txt: 4059 bytes, checksum: bacbdfafa8a1c82c9f2327121d20b480 (MD5)"]},{"key":"dc:title","label":"Title","values":["Pattern extraction and clustering for high-dimensional discrete data"]}]}],"canonical_facts":{"dc:contributor":["Heath, Michael T.","Olson, Luke N.","Zhai, ChengXiang","Park, Haesun"],"dc:creator":["Jiang, Peng"],"dc:date":["2014-01-16T17:55:55Z","2013-12"],"dc:description":["We explore connections of low-rank matrix factorizations with interesting problems in data mining and machine learning. We propose a framework for solving several low-rank matrix factorization problems, including binary matrix factorization, constrained binary matrix factorization, weighted constrained binary matrix factorization, densest k-subgraph, and orthogonal nonnegative matrix factorization. These combinatorial problems are NP-hard. Our goal is to develop effective approximation algorithms with good theoretical properties and apply them to solve various real application problems. We reformulate each of the problems as a special clustering problem that has the same optimal solution as the corresponding original problem. Making use of this property, we develop clustering algorithms to solve corresponding low-rank matrix factorization problems. We prove that most of our clustering algorithms have constant approximation ratios, which is a highly desirable property for NP-hard problems. We apply the proposed algorithms and compare them with existing methods for real applications in pattern extraction, document clustering, transaction data mining, recommender systems, bicluster discovery in gene expression data, social network mining, and image representation.","Item withdrawn by Laura Spradlin (lspradl2@illinois.edu) on 2013-11-21T21:19:18Z Item was in collections: University of Illinois Theses & Dissertations (ID: 1) No. of bitstreams: 1 Jiang_Peng.pdf: 10599343 bytes, checksum: 43484d41a082d8f682f84ffa3fc19efb (MD5)","Made available in DSpace on 2014-01-16T17:55:55Z (GMT). No. of bitstreams: 2 Peng_Jiang.pdf: 10599343 bytes, checksum: 43484d41a082d8f682f84ffa3fc19efb (MD5) license.txt: 4059 bytes, checksum: bacbdfafa8a1c82c9f2327121d20b480 (MD5)"],"dc:identifier":["http://hdl.handle.net/2142/46604"],"dc:language":["en"],"dc:rights":["Copyright 2013 Peng Jiang"],"dc:subject":["low-rank matrix factorization","binary matrix factorization","k-means clustering","approximation algorithm","pattern extraction","association rule mining","document clustering","weighted binary matrix factorization","bicluster discovery","densest k-subgraph","social network mining"],"dc:title":["Pattern extraction and clustering for high-dimensional discrete data"],"dc:type":["text"],"thesis:degree_discipline":["Computer Science"],"thesis:degree_level":["Dissertation"],"thesis:degree_name":["Ph.D."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:25:36Z"}