Shelved–Retrieved Method for Weakly Balanced Constrained Clustering Problems
Clustering problems are prevalent in areas such as transport and partitioning. Owing to the demand for centralized storage and limited resources, a complex variant of this problem has emerged, also referred to as the weakly balanced constrained clustering (WBCC) problem. Clusters must satisfy constr...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2023-10-01
|
| Series: | Algorithms |
| Subjects: | |
| Online Access: | https://www.mdpi.com/1999-4893/16/10/492 |
| _version_ | 1797574926540996608 |
|---|---|
| author | Xinxiang Hou Andong Qiu Lu Yang Zhouwang Yang |
| author_facet | Xinxiang Hou Andong Qiu Lu Yang Zhouwang Yang |
| author_sort | Xinxiang Hou |
| collection | DOAJ |
| description | Clustering problems are prevalent in areas such as transport and partitioning. Owing to the demand for centralized storage and limited resources, a complex variant of this problem has emerged, also referred to as the weakly balanced constrained clustering (WBCC) problem. Clusters must satisfy constraints regarding cluster weights and connectivity. However, existing methods fail to guarantee cluster connectivity in diverse scenarios, thereby resulting in additional transportation costs. In response to the aforementioned limitations, this study introduces a shelved–retrieved method. This method embeds adjacent relationships during power diagram construction to ensure cluster connectivity. Using the shelved–retrieved method, connected clusters are generated and iteratively adjusted to determine the optimal solutions. Further, experiments are conducted on three synthetic datasets, each with three objective functions, and the results are compared to those obtained using other techniques. Our method successfully generates clusters that satisfy the constraints imposed by the WBCC problem and consistently outperforms other techniques in terms of the evaluation measures. |
| first_indexed | 2024-03-10T21:30:00Z |
| format | Article |
| id | doaj.art-11332bcd531d4780b623474dbc6d3c96 |
| institution | Directory Open Access Journal |
| issn | 1999-4893 |
| language | English |
| last_indexed | 2024-03-10T21:30:00Z |
| publishDate | 2023-10-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Algorithms |
| spelling | doaj.art-11332bcd531d4780b623474dbc6d3c962023-11-19T15:23:56ZengMDPI AGAlgorithms1999-48932023-10-01161049210.3390/a16100492Shelved–Retrieved Method for Weakly Balanced Constrained Clustering ProblemsXinxiang Hou0Andong Qiu1Lu Yang2Zhouwang Yang3School of Mathematical Sciences, University of Science and Technology of China, Hefei 230026, ChinaSchool of Data Science, University of Science and Technology of China, Hefei 230026, ChinaSchool of Data Science, University of Science and Technology of China, Hefei 230026, ChinaSchool of Mathematical Sciences, University of Science and Technology of China, Hefei 230026, ChinaClustering problems are prevalent in areas such as transport and partitioning. Owing to the demand for centralized storage and limited resources, a complex variant of this problem has emerged, also referred to as the weakly balanced constrained clustering (WBCC) problem. Clusters must satisfy constraints regarding cluster weights and connectivity. However, existing methods fail to guarantee cluster connectivity in diverse scenarios, thereby resulting in additional transportation costs. In response to the aforementioned limitations, this study introduces a shelved–retrieved method. This method embeds adjacent relationships during power diagram construction to ensure cluster connectivity. Using the shelved–retrieved method, connected clusters are generated and iteratively adjusted to determine the optimal solutions. Further, experiments are conducted on three synthetic datasets, each with three objective functions, and the results are compared to those obtained using other techniques. Our method successfully generates clusters that satisfy the constraints imposed by the WBCC problem and consistently outperforms other techniques in terms of the evaluation measures.https://www.mdpi.com/1999-4893/16/10/492weakly balanced constrained clusteringconnectivityshelved–retrieved methodcentroidal power diagram |
| spellingShingle | Xinxiang Hou Andong Qiu Lu Yang Zhouwang Yang Shelved–Retrieved Method for Weakly Balanced Constrained Clustering Problems Algorithms weakly balanced constrained clustering connectivity shelved–retrieved method centroidal power diagram |
| title | Shelved–Retrieved Method for Weakly Balanced Constrained Clustering Problems |
| title_full | Shelved–Retrieved Method for Weakly Balanced Constrained Clustering Problems |
| title_fullStr | Shelved–Retrieved Method for Weakly Balanced Constrained Clustering Problems |
| title_full_unstemmed | Shelved–Retrieved Method for Weakly Balanced Constrained Clustering Problems |
| title_short | Shelved–Retrieved Method for Weakly Balanced Constrained Clustering Problems |
| title_sort | shelved retrieved method for weakly balanced constrained clustering problems |
| topic | weakly balanced constrained clustering connectivity shelved–retrieved method centroidal power diagram |
| url | https://www.mdpi.com/1999-4893/16/10/492 |
| work_keys_str_mv | AT xinxianghou shelvedretrievedmethodforweaklybalancedconstrainedclusteringproblems AT andongqiu shelvedretrievedmethodforweaklybalancedconstrainedclusteringproblems AT luyang shelvedretrievedmethodforweaklybalancedconstrainedclusteringproblems AT zhouwangyang shelvedretrievedmethodforweaklybalancedconstrainedclusteringproblems |