{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/106229"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/106229","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Query K-means clustering for crowdsourcing","abstract":"This thesis focuses on solving the $K$-means clustering problem approximately with side information provided by crowdsourcing. Both binary same-cluster oracle and general crowdsourcing framework are considered. It can be shown that, under some mild assumptions on the smallest cluster size, one can obtain a $(1+\\epsilon)$-approximation for the optimal potential with probability at least $1-\\delta$, where $\\epsilon>0$ and $\\delta\\in(0,1)$, using an expected number of $O(\\frac{K^3}{\\epsilon \\delta})$ noiseless same-cluster queries and comparison-based clustering of complexity $O(ndK + \\frac{K^3}{\\epsilon \\delta})$; here, $n$ denotes the number of points and $d$ the dimension of space. Compared to a handful of other known approaches that perform importance sampling to account for small cluster sizes, the proposed query technique reduces the number of queries by a factor of roughly $O(\\frac{K^6}{\\epsilon^3})$, at the cost of possibly missing very small clusters. This setting is extended to the case where some queries to the oracle produce erroneous information, and where certain points, termed outliers, do not belong to any clusters. Incorporating state-of-the-art results in crowdsourcing can further improve the performance of the algorithm. Note that the proof techniques used in this thesis differ from previous methods used for $K$-means clustering analysis, as they rely on estimating the sizes of the clusters and the number of points needed for accurate centroid estimation and subsequent nontrivial generalizations of the double Dixie cup problem. The performances of proposed algorithms are illustrated on both synthetic and real datasets, including MNIST and CIFAR $10$.","abstract_html":"This thesis focuses on solving the $K$-means clustering problem approximately with side information provided by crowdsourcing. Both binary same-cluster oracle and general crowdsourcing framework are considered. It can be shown that, under some mild assumptions on the smallest cluster size, one can obtain a <span class=\"etd-inline-math\">(1+&epsilon;)</span>-approximation for the optimal potential with probability at least <span class=\"etd-inline-math\">1-&delta;</span>, where <span class=\"etd-inline-math\">&epsilon;&gt;0</span> and <span class=\"etd-inline-math\">&delta;\\in(0,1)</span>, using an expected number of <span class=\"etd-inline-math\">O(\\frac{K<sup>3</sup>}{&epsilon; &delta;})</span> noiseless same-cluster queries and comparison-based clustering of complexity <span class=\"etd-inline-math\">O(ndK + \\frac{K<sup>3</sup>}{&epsilon; &delta;})</span>; here, $n$ denotes the number of points and $d$ the dimension of space. Compared to a handful of other known approaches that perform importance sampling to account for small cluster sizes, the proposed query technique reduces the number of queries by a factor of roughly <span class=\"etd-inline-math\">O(\\frac{K<sup>6</sup>}{&epsilon;<sup>3</sup>})</span>, at the cost of possibly missing very small clusters. This setting is extended to the case where some queries to the oracle produce erroneous information, and where certain points, termed outliers, do not belong to any clusters. Incorporating state-of-the-art results in crowdsourcing can further improve the performance of the algorithm. Note that the proof techniques used in this thesis differ from previous methods used for $K$-means clustering analysis, as they rely on estimating the sizes of the clusters and the number of points needed for accurate centroid estimation and subsequent nontrivial generalizations of the double Dixie cup problem. The performances of proposed algorithms are illustrated on both synthetic and real datasets, including MNIST and CIFAR $10$.","abstract_has_math":true,"creators":["Pan, Chao"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"M.S.","degree_level":"Thesis","degree_discipline":"Electrical & Computer Engr","degree_department":null,"school":null,"contributors":["Milenkovic, Olgica"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2020,"date_issued":"2020-03-02T21:58:19Z","date_published":"2020-03-02T21:58:19Z","updated_at":"2026-07-22T22:24:45Z","subjects":["K-means clustering","active learning","semi-supervised learning","coupon collector's problem","crowdsourcing"],"languages":["en"],"rights":["Copyright 2019 Chao Pan"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/2142/106229","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Milenkovic, Olgica"]},{"key":"dc:creator","label":"Author","values":["Pan, Chao"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2020-03-02T21:58:19Z","2019-12-02","2019-12"]},{"key":"dc:type","label":"Dc Type","values":["text"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Electrical & Computer Engr"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Thesis"]},{"key":"thesis:degree_name","label":"Degree Name","values":["M.S."]},{"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":["K-means clustering","active learning","semi-supervised learning","coupon collector's problem","crowdsourcing"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2019 Chao Pan"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/106229"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["This thesis focuses on solving the $K$-means clustering problem approximately with side information provided by crowdsourcing. Both binary same-cluster oracle and general crowdsourcing framework are considered. It can be shown that, under some mild assumptions on the smallest cluster size, one can obtain a $(1+\\epsilon)$-approximation for the optimal potential with probability at least $1-\\delta$, where $\\epsilon>0$ and $\\delta\\in(0,1)$, using an expected number of $O(\\frac{K^3}{\\epsilon \\delta})$ noiseless same-cluster queries and comparison-based clustering of complexity $O(ndK + \\frac{K^3}{\\epsilon \\delta})$; here, $n$ denotes the number of points and $d$ the dimension of space. Compared to a handful of other known approaches that perform importance sampling to account for small cluster sizes, the proposed query technique reduces the number of queries by a factor of roughly $O(\\frac{K^6}{\\epsilon^3})$, at the cost of possibly missing very small clusters. This setting is extended to the case where some queries to the oracle produce erroneous information, and where certain points, termed outliers, do not belong to any clusters. Incorporating state-of-the-art results in crowdsourcing can further improve the performance of the algorithm. Note that the proof techniques used in this thesis differ from previous methods used for $K$-means clustering analysis, as they rely on estimating the sizes of the clusters and the number of points needed for accurate centroid estimation and subsequent nontrivial generalizations of the double Dixie cup problem. The performances of proposed algorithms are illustrated on both synthetic and real datasets, including MNIST and CIFAR $10$.","Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2020-02-28 without embargo terms","The student, Chao Pan, accepted the attached license on 2019-11-27 at 16:53.","The student, Chao Pan, submitted this Thesis for approval on 2019-11-27 at 17:08.","This Thesis was approved for publication on 2019-12-02 at 08:52.","DSpace SAF Submission Ingestion Package generated from Vireo submission #14633 on 2020-02-28 at 17:14:40","Made available in DSpace on 2020-03-02T21:58:19Z (GMT). No. of bitstreams: 2 PAN-THESIS-2019.pdf: 644692 bytes, checksum: f5aca811f3a1f52bfb1bbc920649c83a (MD5) LICENSE.txt: 4205 bytes, checksum: 3caa1e413bb74da9a47c69904104d43c (MD5) Previous issue date: 2019-12-02"]},{"key":"dc:format","label":"Dc Format","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Query K-means clustering for crowdsourcing"]}]}],"canonical_facts":{"dc:contributor":["Milenkovic, Olgica"],"dc:creator":["Pan, Chao"],"dc:date":["2020-03-02T21:58:19Z","2019-12-02","2019-12"],"dc:description":["This thesis focuses on solving the $K$-means clustering problem approximately with side information provided by crowdsourcing. Both binary same-cluster oracle and general crowdsourcing framework are considered. It can be shown that, under some mild assumptions on the smallest cluster size, one can obtain a $(1+\\epsilon)$-approximation for the optimal potential with probability at least $1-\\delta$, where $\\epsilon>0$ and $\\delta\\in(0,1)$, using an expected number of $O(\\frac{K^3}{\\epsilon \\delta})$ noiseless same-cluster queries and comparison-based clustering of complexity $O(ndK + \\frac{K^3}{\\epsilon \\delta})$; here, $n$ denotes the number of points and $d$ the dimension of space. Compared to a handful of other known approaches that perform importance sampling to account for small cluster sizes, the proposed query technique reduces the number of queries by a factor of roughly $O(\\frac{K^6}{\\epsilon^3})$, at the cost of possibly missing very small clusters. This setting is extended to the case where some queries to the oracle produce erroneous information, and where certain points, termed outliers, do not belong to any clusters. Incorporating state-of-the-art results in crowdsourcing can further improve the performance of the algorithm. Note that the proof techniques used in this thesis differ from previous methods used for $K$-means clustering analysis, as they rely on estimating the sizes of the clusters and the number of points needed for accurate centroid estimation and subsequent nontrivial generalizations of the double Dixie cup problem. The performances of proposed algorithms are illustrated on both synthetic and real datasets, including MNIST and CIFAR $10$.","Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2020-02-28 without embargo terms","The student, Chao Pan, accepted the attached license on 2019-11-27 at 16:53.","The student, Chao Pan, submitted this Thesis for approval on 2019-11-27 at 17:08.","This Thesis was approved for publication on 2019-12-02 at 08:52.","DSpace SAF Submission Ingestion Package generated from Vireo submission #14633 on 2020-02-28 at 17:14:40","Made available in DSpace on 2020-03-02T21:58:19Z (GMT). No. of bitstreams: 2 PAN-THESIS-2019.pdf: 644692 bytes, checksum: f5aca811f3a1f52bfb1bbc920649c83a (MD5) LICENSE.txt: 4205 bytes, checksum: 3caa1e413bb74da9a47c69904104d43c (MD5) Previous issue date: 2019-12-02"],"dc:format":["application/pdf"],"dc:identifier":["http://hdl.handle.net/2142/106229"],"dc:language":["en"],"dc:rights":["Copyright 2019 Chao Pan"],"dc:subject":["K-means clustering","active learning","semi-supervised learning","coupon collector's problem","crowdsourcing"],"dc:title":["Query K-means clustering for crowdsourcing"],"dc:type":["text"],"thesis:degree_discipline":["Electrical & Computer Engr"],"thesis:degree_level":["Thesis"],"thesis:degree_name":["M.S."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:24:45Z"}