Loading…
The early stop heuristic: A new convergence criterion for K-means
In this paper, an enhanced version of the K-Means algorithm that incorporates a new convergence criterion is presented. The largest centroid displacement at each iteration was used as mean to define whether the algorithm stops or not its execution. Computational experiments showed that in general, t...
Saved in:
| Main Authors: | , , , , , , |
|---|---|
| Format: | Conference Proceeding |
| Language: | English |
| Subjects: | |
| Online Access: | Get full text |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| cited_by | |
|---|---|
| cites | |
| container_end_page | |
| container_issue | 1 |
| container_start_page | |
| container_title | |
| container_volume | 1738 |
| creator | Mexicano, A. Rodríguez, R. Cervantes, S. Montes, P. Jiménez, M. Almanza, N. Abrego, A. |
| description | In this paper, an enhanced version of the K-Means algorithm that incorporates a new convergence criterion is presented. The largest centroid displacement at each iteration was used as mean to define whether the algorithm stops or not its execution. Computational experiments showed that in general, the Early Stop Heuristic is able to reduce the execution time of the standard version without a significant quality reduction. According to the experimentation, the Early Stop Heuristic reached a time reduction up to 87.06% only a quality reduction of 2.46% for the Transactions dataset, the worst case occurred when the Skin instance was grouped into 200 clusters obtaining a 79.04% in reduction time, and a 4.27% in quality reduction. |
| doi_str_mv | 10.1063/1.4952103 |
| format | conference_proceeding |
| fullrecord | <record><control><sourceid>proquest_scita</sourceid><recordid>TN_cdi_scitation_primary_10_1063_1_4952103</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><sourcerecordid>2121743128</sourcerecordid><originalsourceid>FETCH-LOGICAL-p253t-bf7eccf4bf7151b8986311f79c508fccafe5cf306a47b090da1cf9c8a09cd48b3</originalsourceid><addsrcrecordid>eNp9kMtKAzEYhYMoWKsL3yDgTpiaP5lMEneleMOCmwruQiaT2CntZEzSSt_ekRbcuTqb71w4CF0DmQCp2B1MSsUpEHaCRsA5FKKC6hSNCFFlQUv2cY4uUloRQpUQcoSmi6XDzsT1Hqccerx029im3Np7PMWd-8Y2dDsXP11nHbaxzS62ocM-RPxabJzp0iU682ad3NVRx-j98WExey7mb08vs-m86Clnuai9cNb6clDgUEslKwbghbKcSG-t8Y5bz0hlSlETRRoD1isrDVG2KWXNxujmkNvH8LV1KetV2MZuqNQUKIiSAZUDdXugkm2zycNW3cd2Y-Je70LUoI_36L7x_8FA9O-ffwb2AzlHZwg</addsrcrecordid><sourcetype>Aggregation Database</sourcetype><iscdi>true</iscdi><recordtype>conference_proceeding</recordtype><pqid>2121743128</pqid></control><display><type>conference_proceeding</type><title>The early stop heuristic: A new convergence criterion for K-means</title><source>American Institute of Physics:Jisc Collections:Transitional Journals Agreement 2021-23 (Reading list)</source><creator>Mexicano, A. ; Rodríguez, R. ; Cervantes, S. ; Montes, P. ; Jiménez, M. ; Almanza, N. ; Abrego, A.</creator><contributor>Simos, Theodore ; Tsitouras, Charalambos</contributor><creatorcontrib>Mexicano, A. ; Rodríguez, R. ; Cervantes, S. ; Montes, P. ; Jiménez, M. ; Almanza, N. ; Abrego, A. ; Simos, Theodore ; Tsitouras, Charalambos</creatorcontrib><description>In this paper, an enhanced version of the K-Means algorithm that incorporates a new convergence criterion is presented. The largest centroid displacement at each iteration was used as mean to define whether the algorithm stops or not its execution. Computational experiments showed that in general, the Early Stop Heuristic is able to reduce the execution time of the standard version without a significant quality reduction. According to the experimentation, the Early Stop Heuristic reached a time reduction up to 87.06% only a quality reduction of 2.46% for the Transactions dataset, the worst case occurred when the Skin instance was grouped into 200 clusters obtaining a 79.04% in reduction time, and a 4.27% in quality reduction.</description><identifier>ISSN: 0094-243X</identifier><identifier>EISSN: 1551-7616</identifier><identifier>DOI: 10.1063/1.4952103</identifier><identifier>CODEN: APCPCS</identifier><language>eng</language><publisher>Melville: American Institute of Physics</publisher><subject>Algorithms ; Convergence ; Criteria ; Experimentation ; Heuristic ; Iterative methods ; Reduction</subject><ispartof>AIP conference proceedings, 2016, Vol.1738 (1)</ispartof><rights>Author(s)</rights><rights>2016 Author(s). Published by AIP Publishing.</rights><lds50>peer_reviewed</lds50><woscitedreferencessubscribed>false</woscitedreferencessubscribed></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><link.rule.ids>309,310,314,780,784,789,790,23929,23930,25139,27923,27924</link.rule.ids></links><search><contributor>Simos, Theodore</contributor><contributor>Tsitouras, Charalambos</contributor><creatorcontrib>Mexicano, A.</creatorcontrib><creatorcontrib>Rodríguez, R.</creatorcontrib><creatorcontrib>Cervantes, S.</creatorcontrib><creatorcontrib>Montes, P.</creatorcontrib><creatorcontrib>Jiménez, M.</creatorcontrib><creatorcontrib>Almanza, N.</creatorcontrib><creatorcontrib>Abrego, A.</creatorcontrib><title>The early stop heuristic: A new convergence criterion for K-means</title><title>AIP conference proceedings</title><description>In this paper, an enhanced version of the K-Means algorithm that incorporates a new convergence criterion is presented. The largest centroid displacement at each iteration was used as mean to define whether the algorithm stops or not its execution. Computational experiments showed that in general, the Early Stop Heuristic is able to reduce the execution time of the standard version without a significant quality reduction. According to the experimentation, the Early Stop Heuristic reached a time reduction up to 87.06% only a quality reduction of 2.46% for the Transactions dataset, the worst case occurred when the Skin instance was grouped into 200 clusters obtaining a 79.04% in reduction time, and a 4.27% in quality reduction.</description><subject>Algorithms</subject><subject>Convergence</subject><subject>Criteria</subject><subject>Experimentation</subject><subject>Heuristic</subject><subject>Iterative methods</subject><subject>Reduction</subject><issn>0094-243X</issn><issn>1551-7616</issn><fulltext>true</fulltext><rsrctype>conference_proceeding</rsrctype><creationdate>2016</creationdate><recordtype>conference_proceeding</recordtype><recordid>eNp9kMtKAzEYhYMoWKsL3yDgTpiaP5lMEneleMOCmwruQiaT2CntZEzSSt_ekRbcuTqb71w4CF0DmQCp2B1MSsUpEHaCRsA5FKKC6hSNCFFlQUv2cY4uUloRQpUQcoSmi6XDzsT1Hqccerx029im3Np7PMWd-8Y2dDsXP11nHbaxzS62ocM-RPxabJzp0iU682ad3NVRx-j98WExey7mb08vs-m86Clnuai9cNb6clDgUEslKwbghbKcSG-t8Y5bz0hlSlETRRoD1isrDVG2KWXNxujmkNvH8LV1KetV2MZuqNQUKIiSAZUDdXugkm2zycNW3cd2Y-Je70LUoI_36L7x_8FA9O-ffwb2AzlHZwg</recordid><startdate>20160608</startdate><enddate>20160608</enddate><creator>Mexicano, A.</creator><creator>Rodríguez, R.</creator><creator>Cervantes, S.</creator><creator>Montes, P.</creator><creator>Jiménez, M.</creator><creator>Almanza, N.</creator><creator>Abrego, A.</creator><general>American Institute of Physics</general><scope>8FD</scope><scope>H8D</scope><scope>L7M</scope></search><sort><creationdate>20160608</creationdate><title>The early stop heuristic: A new convergence criterion for K-means</title><author>Mexicano, A. ; Rodríguez, R. ; Cervantes, S. ; Montes, P. ; Jiménez, M. ; Almanza, N. ; Abrego, A.</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-p253t-bf7eccf4bf7151b8986311f79c508fccafe5cf306a47b090da1cf9c8a09cd48b3</frbrgroupid><rsrctype>conference_proceedings</rsrctype><prefilter>conference_proceedings</prefilter><language>eng</language><creationdate>2016</creationdate><topic>Algorithms</topic><topic>Convergence</topic><topic>Criteria</topic><topic>Experimentation</topic><topic>Heuristic</topic><topic>Iterative methods</topic><topic>Reduction</topic><toplevel>peer_reviewed</toplevel><toplevel>online_resources</toplevel><creatorcontrib>Mexicano, A.</creatorcontrib><creatorcontrib>Rodríguez, R.</creatorcontrib><creatorcontrib>Cervantes, S.</creatorcontrib><creatorcontrib>Montes, P.</creatorcontrib><creatorcontrib>Jiménez, M.</creatorcontrib><creatorcontrib>Almanza, N.</creatorcontrib><creatorcontrib>Abrego, A.</creatorcontrib><collection>Technology Research Database</collection><collection>Aerospace Database</collection><collection>Advanced Technologies Database with Aerospace</collection></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext</fulltext></delivery><addata><au>Mexicano, A.</au><au>Rodríguez, R.</au><au>Cervantes, S.</au><au>Montes, P.</au><au>Jiménez, M.</au><au>Almanza, N.</au><au>Abrego, A.</au><au>Simos, Theodore</au><au>Tsitouras, Charalambos</au><format>book</format><genre>proceeding</genre><ristype>CONF</ristype><atitle>The early stop heuristic: A new convergence criterion for K-means</atitle><btitle>AIP conference proceedings</btitle><date>2016-06-08</date><risdate>2016</risdate><volume>1738</volume><issue>1</issue><issn>0094-243X</issn><eissn>1551-7616</eissn><coden>APCPCS</coden><abstract>In this paper, an enhanced version of the K-Means algorithm that incorporates a new convergence criterion is presented. The largest centroid displacement at each iteration was used as mean to define whether the algorithm stops or not its execution. Computational experiments showed that in general, the Early Stop Heuristic is able to reduce the execution time of the standard version without a significant quality reduction. According to the experimentation, the Early Stop Heuristic reached a time reduction up to 87.06% only a quality reduction of 2.46% for the Transactions dataset, the worst case occurred when the Skin instance was grouped into 200 clusters obtaining a 79.04% in reduction time, and a 4.27% in quality reduction.</abstract><cop>Melville</cop><pub>American Institute of Physics</pub><doi>10.1063/1.4952103</doi><tpages>4</tpages></addata></record> |
| fulltext | fulltext |
| identifier | ISSN: 0094-243X |
| ispartof | AIP conference proceedings, 2016, Vol.1738 (1) |
| issn | 0094-243X 1551-7616 |
| language | eng |
| recordid | cdi_scitation_primary_10_1063_1_4952103 |
| source | American Institute of Physics:Jisc Collections:Transitional Journals Agreement 2021-23 (Reading list) |
| subjects | Algorithms Convergence Criteria Experimentation Heuristic Iterative methods Reduction |
| title | The early stop heuristic: A new convergence criterion for K-means |
| url | http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2025-01-13T04%3A44%3A19IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-proquest_scita&rft_val_fmt=info:ofi/fmt:kev:mtx:book&rft.genre=proceeding&rft.atitle=The%20early%20stop%20heuristic:%20A%20new%20convergence%20criterion%20for%20K-means&rft.btitle=AIP%20conference%20proceedings&rft.au=Mexicano,%20A.&rft.date=2016-06-08&rft.volume=1738&rft.issue=1&rft.issn=0094-243X&rft.eissn=1551-7616&rft.coden=APCPCS&rft_id=info:doi/10.1063/1.4952103&rft_dat=%3Cproquest_scita%3E2121743128%3C/proquest_scita%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-p253t-bf7eccf4bf7151b8986311f79c508fccafe5cf306a47b090da1cf9c8a09cd48b3%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_pqid=2121743128&rft_id=info:pmid/&rfr_iscdi=true |