IDEAS home Printed from https://ideas.repec.org/a/eee/phsmap/v535y2019ics0378437119313123.html
   My bibliography  Save this article

A three-way clustering method based on an improved DBSCAN algorithm

Author

Listed:
  • Yu, Hui
  • Chen, LuYuan
  • Yao, JingTao
  • Wang, XingNan

Abstract

Clustering is a fundamental research field and plays an important role in data analysis. To better address the relationship between an element and a cluster, a Three-Way clustering method based on an Improved DBSCAN (3W-DBSCAN) algorithm is proposed in this paper. 3W-DBSCAN represents a cluster by a pair of nested sets called lower bound and upper bound respectively. The two bounds classify objects into three status: belong-to, not belong-to and ambiguity. Objects in lower bound certainly belong to the cluster. Objects in upper bound while not in the lower bound are ambiguous because they are in a boundary region and might belong to one or more clusters. Objects beyond the upper bound certainly do not belong to the same cluster. This clustering representation can well explain the clustering result and consist with human cognitive thinking. By improving similarity calculation, improved DBSCAN is presented to obtain initial clustering results, then three-way decision strategies are used to acquire the positive and boundary regions of a cluster. Three benchmarks Accuracy (Acc), F-measure (F1), NMI and ten datasets including three synthetic datasets, three UCI datasets and four shape datasets are used in experiments to evaluate the effectiveness of 3W-DBSCAN. Experimental results suggest that 3W-DBSCAN has a good performance and is effective in clustering.

Suggested Citation

  • Yu, Hui & Chen, LuYuan & Yao, JingTao & Wang, XingNan, 2019. "A three-way clustering method based on an improved DBSCAN algorithm," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 535(C).
    • Handle: RePEc:eee:phsmap:v:535:y:2019:i:c:s0378437119313123
    DOI: 10.1016/j.physa.2019.122289
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0378437119313123
    Download Restriction: Full text for ScienceDirect subscribers only. Journal offers the option of making the article available online on Science direct for a fee of $3,000
    File URL: https://libkey.io/10.1016/j.physa.2019.122289?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Cheng, Qing & Lu, Xin & Liu, Zhong & Huang, Jincai & Cheng, Guangquan, 2016. "Spatial clustering with Density-Ordered tree," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 460(C), pages 188-200.
    2. Yutong Song & Yong Deng, 2019. "A new method to measure the divergence in evidential sensor data fusion," International Journal of Distributed Sensor Networks, , vol. 15(4), pages 15501477198, April.
    3. Moshfegh, S. & Ashouri, A. & Mahdavifar, S. & Vahedi, J., 2019. "Integrable-chaos crossover in the spin-1∕2 XXZ chain with cluster interaction," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 516(C), pages 502-508.
    4. Jiang, Jianhua & Chen, Yujun & Hao, Dehao & Li, Keqin, 2019. "DPC-LG: Density peaks clustering based on logistic distribution and gravitation," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 514(C), pages 25-35.
    5. Akbarzadeh, Meisam & Salehi Reihani, Sayed Farzin & Samani, Keivan Aghababaei, 2019. "Detecting critical links of urban networks using cluster detection methods," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 515(C), pages 288-298.
    6. Jiang, Jianhua & Hao, Dehao & Chen, Yujun & Parmar, Milan & Li, Keqin, 2018. "GDPC: Gravitation-based Density Peaks Clustering algorithm," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 502(C), pages 345-355.
    7. Minicozzi, Pamela & Rapallo, Fabio & Scalas, Enrico & Dondero, Francesco, 2008. "Accuracy and robustness of clustering algorithms for small-size applications in bioinformatics," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 387(25), pages 6310-6318.
    8. Wei, Bo & Deng, Yong, 2019. "A cluster-growing dimension of complex networks: From the view of node closeness centrality," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 522(C), pages 80-87.
    9. He, Chaobo & Tang, Yong & Liu, Hai & Fei, Xiang & Li, Hanchao & Liu, Shuangyin, 2019. "A robust multi-view clustering method for community detection combining link and content information," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 514(C), pages 396-411.
    10. Dong, Gaogao & Tian, Lixin & Du, Ruijin & Fu, Min & Stanley, H. Eugene, 2014. "Analysis of percolation behaviors of clustered networks with partial support–dependence relations," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 394(C), pages 370-378.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Hu, Dingding & Zhou, Kaile & Li, Fangyi & Ma, Dawei, 2022. "Electric vehicle user classification and value discovery based on charging big data," Energy, Elsevier, vol. 249(C).
    2. Jiachen Fan & Xiaoxiao Wang & Tingfeng Wu & Jin Zhu & Pingxin Wang, 2022. "Three-Way Ensemble Clustering Based on Sample’s Perturbation Theory," Mathematics, MDPI, vol. 10(15), pages 1-19, July.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Jiang, Jianhua & Chen, Yujun & Meng, Xianqiu & Wang, Limin & Li, Keqin, 2019. "A novel density peaks clustering algorithm based on k nearest neighbors for improving assignment process," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 523(C), pages 702-713.
    2. Jiang, Jianhua & Chen, Yujun & Hao, Dehao & Li, Keqin, 2019. "DPC-LG: Density peaks clustering based on logistic distribution and gravitation," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 514(C), pages 25-35.
    3. Muneeb A Khan & Muazzam A Khan & Anis U Rahman & Asad Waqar Malik & Safdar A Khan, 2019. "Exploiting cooperative sensing for accurate target tracking in industrial Internet of things," International Journal of Distributed Sensor Networks, , vol. 15(12), pages 15501477198, December.
    4. Shijun Xu & Yi Hou & Xinpu Deng & Peibo Chen & Kewei Ouyang & Ye Zhang, 2021. "A novel divergence measure in Dempster–Shafer evidence theory based on pignistic probability transform and its application in multi-sensor data fusion," International Journal of Distributed Sensor Networks, , vol. 17(7), pages 15501477211, July.
    5. Ortega, Emilio & Martín, Belén & Aparicio, Ángel, 2020. "Identification of critical sections of the Spanish transport system due to climate scenarios," Journal of Transport Geography, Elsevier, vol. 84(C).
    6. Wang, Jiang-Pan & Guo, Qiang & Yang, Guang-Yong & Liu, Jian-Guo, 2015. "Improved knowledge diffusion model based on the collaboration hypernetwork," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 428(C), pages 250-256.
    7. Lin, Pengfei & Weng, Jiancheng & Fu, Yu & Alivanistos, Dimitrios & Yin, Baocai, 2020. "Study on the topology and dynamics of the rail transit network based on automatic fare collection data," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 545(C).
    8. Dong, Youheng & Zhao, Geng, 2021. "A spatiotemporal chaotic system based on pseudo-random coupled map lattices and elementary cellular automata," Chaos, Solitons & Fractals, Elsevier, vol. 151(C).
    9. Liu, Xiaoxiao & Sun, Shiwen & Wang, Jiawei & Xia, Chengyi, 2019. "Onion structure optimizes attack robustness of interdependent networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 535(C).
    10. Jin, Kun & Wang, Wei & Li, Xinran & Hua, Xuedong & Chen, Siyuan & Qin, Shaoyang, 2022. "Identifying the critical road combination in urban roads network under multiple disruption scenarios," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 607(C).
    11. He, Chaobo & Zhang, Qiong & Tang, Yong & Liu, Shuangyin & Zheng, Jianhua, 2019. "Community detection method based on robust semi-supervised nonnegative matrix factorization," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 523(C), pages 279-291.
    12. Johan Rose Santos & Nur Diana Safitri & Maya Safira & Varun Varghese & Makoto Chikaraishi, 2021. "Road network vulnerability and city-level characteristics: A nationwide comparative analysis of Japanese cities," Environment and Planning B, , vol. 48(5), pages 1091-1107, June.
    13. Elisa Frutos Bernal & Angel Martín del Rey, 2019. "Study of the Structural and Robustness Characteristics of Madrid Metro Network," Sustainability, MDPI, vol. 11(12), pages 1-24, June.
    14. Dong, Chen & Xu, Guiqiong & Meng, Lei & Yang, Pingle, 2022. "CPR-TOPSIS: A novel algorithm for finding influential nodes in complex networks based on communication probability and relative entropy," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 603(C).
    15. Wang, Jian & Fang, Hongying & Qin, Xiaolin, 2019. "Targeted attack on correlated interdependent networks with dependency groups," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 536(C).
    16. Pavón-Domínguez, Pablo & Moreno-Pulido, Soledad, 2022. "Sandbox fixed-mass algorithm for multifractal unweighted complex networks," Chaos, Solitons & Fractals, Elsevier, vol. 156(C).
    17. Li Zhang & Ming Liu & Bo Wang & Bo Lang & Peng Yang, 2021. "Discovering communities based on mention distance," Scientometrics, Springer;Akadémiai Kiadó, vol. 126(3), pages 1945-1967, March.
    18. Jiang, Jianhua & Hao, Dehao & Chen, Yujun & Parmar, Milan & Li, Keqin, 2018. "GDPC: Gravitation-based Density Peaks Clustering algorithm," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 502(C), pages 345-355.
    19. Fu, Xin & Qiang, Yongjie & Liu, Xuxu & Jiang, Ying & Cui, Zhiwei & Zhang, Deyu & Wang, Jianwei, 2022. "Will multi-industry supply chains' resilience under the impact of COVID-19 pandemic be different? A perspective from China's highway freight transport," Transport Policy, Elsevier, vol. 118(C), pages 165-178.
    20. Liguo Fei & Jun Xia & Yuqiang Feng & Luning Liu, 2019. "A novel method to determine basic probability assignment in Dempster–Shafer theory and its application in multi-sensor information fusion," International Journal of Distributed Sensor Networks, , vol. 15(7), pages 15501477198, July.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:eee:phsmap:v:535:y:2019:i:c:s0378437119313123. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Catherine Liu (email available below). General contact details of provider: http://www.journals.elsevier.com/physica-a-statistical-mechpplications/ .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.