{"created":"2021-03-01T07:09:47.397935+00:00","id":48967,"links":{},"metadata":{"_buckets":{"deposit":"f8185604-5444-4069-8acc-bb1f2b395f05"},"_deposit":{"id":"48967","owners":[],"pid":{"revision_id":0,"type":"depid","value":"48967"},"status":"published"},"_oai":{"id":"oai:repository.dl.itc.u-tokyo.ac.jp:00048967","sets":["34:95:96","9:10:15"]},"item_2_biblio_info_7":{"attribute_name":"書誌情報","attribute_value_mlt":[{"bibliographicIssueDates":{"bibliographicIssueDate":"2000-06-25","bibliographicIssueDateType":"Issued"},"bibliographicIssueNumber":"6","bibliographicPageEnd":"1206","bibliographicPageStart":"1199","bibliographicVolumeNumber":"E83-D","bibliographic_titles":[{"bibliographic_title":"IEICE TRANSACTIONS on Information and Systems"}]}]},"item_2_description_5":{"attribute_name":"抄録","attribute_value_mlt":[{"subitem_description":"In this paper we consider the k-clustering problem for a set S of n points pi=(xi) in the d-dimensional space with variance-based errors as clustering criteria, motivated from the color quantization problem of computing a color lookup table for frame buffer display. As the inter-cluster criterion to minimize, the sum of intra-cluster errors over every cluster is used, and as the intra-cluster criterion of a cluster Sj, |Sj|α-1 Σpi Sj ||xi - - x (Sj)||2 is considered, where |||| is the L2 norm and - x (Sj) is the centroid of points in Sj, i. e. , (1/|Sj|)Σpi Sj xi. The cases of α=1,2 correspond to the sum of squared errors and the all-pairs sum of squared errors, respectively. The k-clustering problem under the criterion with α = 1,2 are treated in a unified manner by characterizing the optimum solution to the k-clustering problem by the ordinary Euclidean Voronoi diagram and the weighted Voronoi diagram with both multiplicative and additive weights. With this framework, the problem is related to the generalized primary shatter function for the Voronoi diagrams. The primary shatter function is shown to be O(nO(kd)), which implies that, for fixed k, this clustering problem can be solved in a polynomial time. For the problem with the most typical intra-cluster criterion of the sum of squared errors, we also present an efficient randomized algorithm which, roughly speaking, finds an ε-approximate 2-clustering in O(n(1/ε)d) time, which is quite practical and may be used to real large-scale problems such as the color quantization problem.","subitem_description_type":"Abstract"}]},"item_2_description_6":{"attribute_name":"内容記述","attribute_value_mlt":[{"subitem_description":"PAPER","subitem_description_type":"Other"}]},"item_2_publisher_20":{"attribute_name":"出版者","attribute_value_mlt":[{"subitem_publisher":"Institute of Electronics, Information and Communication Engineers"}]},"item_2_relation_25":{"attribute_name":"関係URI","attribute_value_mlt":[{"subitem_relation_type_id":{"subitem_relation_type_id_text":"https://search.ieice.org/","subitem_relation_type_select":"URI"}}]},"item_2_rights_12":{"attribute_name":"権利","attribute_value_mlt":[{"subitem_rights":"copyright©2000 IEICE"}]},"item_2_select_14":{"attribute_name":"著者版フラグ","attribute_value_mlt":[{"subitem_select_item":"publisher"}]},"item_2_text_4":{"attribute_name":"著者所属","attribute_value_mlt":[{"subitem_text_value":"Department of Information Science, University of Tokyo"},{"subitem_text_value":"the Department of Architecture and Architectural Systems, Kyoto University"}]},"item_creator":{"attribute_name":"著者","attribute_type":"creator","attribute_value_mlt":[{"creatorNames":[{"creatorName":"INABA, Mary"}],"nameIdentifiers":[{"nameIdentifier":"145502","nameIdentifierScheme":"WEKO"}]},{"creatorNames":[{"creatorName":"KATOH, Naoki"}],"nameIdentifiers":[{"nameIdentifier":"145503","nameIdentifierScheme":"WEKO"}]},{"creatorNames":[{"creatorName":"IMAI, Hiroshi"}],"nameIdentifiers":[{"nameIdentifier":"145504","nameIdentifierScheme":"WEKO"}]}]},"item_files":{"attribute_name":"ファイル情報","attribute_type":"file","attribute_value_mlt":[{"accessrole":"open_date","date":[{"dateType":"Available","dateValue":"2017-12-15"}],"displaytype":"detail","filename":"Variance-Based k-Clustering Algorithms by Voronoi Diagrams and Randomization 2000.pdf","filesize":[{"value":"401.1 kB"}],"format":"application/pdf","licensetype":"license_note","mimetype":"application/pdf","url":{"label":"Variance-Based k-Clustering Algorithms by Voronoi Diagrams and Randomization 2000.pdf","url":"https://repository.dl.itc.u-tokyo.ac.jp/record/48967/files/Variance-Based k-Clustering Algorithms by Voronoi Diagrams and Randomization 2000.pdf"},"version_id":"c976a88e-bb11-402e-ab63-dba2868571e2"}]},"item_language":{"attribute_name":"言語","attribute_value_mlt":[{"subitem_language":"eng"}]},"item_resource_type":{"attribute_name":"資源タイプ","attribute_value_mlt":[{"resourcetype":"journal article","resourceuri":"http://purl.org/coar/resource_type/c_6501"}]},"item_title":"Variance-Based k-Clustering Algorithms by Voronoi Diagrams and Randomization","item_titles":{"attribute_name":"タイトル","attribute_value_mlt":[{"subitem_title":"Variance-Based k-Clustering Algorithms by Voronoi Diagrams and Randomization"}]},"item_type_id":"2","owner":"1","path":["15","96"],"pubdate":{"attribute_name":"公開日","attribute_value":"2017-12-14"},"publish_date":"2017-12-14","publish_status":"0","recid":"48967","relation_version_is_last":true,"title":["Variance-Based k-Clustering Algorithms by Voronoi Diagrams and Randomization"],"weko_creator_id":"1","weko_shared_id":null},"updated":"2022-12-19T04:23:37.386554+00:00"}