Journal Home > Volume 1 , Issue 3

There are many algorithms for solving complex problems in supervised manner. However, unsupervised tasks are more common in real scenarios. Inspired by the idea of granular computing and the characteristics of human cognitive process, this paper proposes a complex tasks decomposition mechanism based on Density Peaks Clustering (DPC) to address complex tasks with an unsupervised process, which simulates the multi-granular observation and analysis of human being. Firstly, the DPC algorithm is modified to nullify its essential defects such as the difficulty of locating correct clustering centers and classifying them accurately. Then, the improved DPC algorithm is used to construct the initial decomposition solving space with multi-granularity theory. We also define subtask centers set and the granulation rules to guide the multi-granularity decomposing procedure. These rules are further used to decompose the solving space from coarse granules to the optimal fine granules with a convergent and automated process. Furthermore, comprehensive experiments are presented to verify the applicability and veracity of our proposed method in community-detection tasks with several benchmark complex social networks. The results show that our method outperforms other four state-of-the-art approaches.


menu
Abstract
Full text
Outline
About this article

A Multi-granularity Decomposition Mechanism of Complex Tasks Based on Density Peaks

Show Author's information Ziling PangGuoyin Wang( )Jie Yang
Chongqing Key Laboratory of Computational Intelligence, Chongqing University of Post and Telecommunication, Chongqing 400060, China.

Abstract

There are many algorithms for solving complex problems in supervised manner. However, unsupervised tasks are more common in real scenarios. Inspired by the idea of granular computing and the characteristics of human cognitive process, this paper proposes a complex tasks decomposition mechanism based on Density Peaks Clustering (DPC) to address complex tasks with an unsupervised process, which simulates the multi-granular observation and analysis of human being. Firstly, the DPC algorithm is modified to nullify its essential defects such as the difficulty of locating correct clustering centers and classifying them accurately. Then, the improved DPC algorithm is used to construct the initial decomposition solving space with multi-granularity theory. We also define subtask centers set and the granulation rules to guide the multi-granularity decomposing procedure. These rules are further used to decompose the solving space from coarse granules to the optimal fine granules with a convergent and automated process. Furthermore, comprehensive experiments are presented to verify the applicability and veracity of our proposed method in community-detection tasks with several benchmark complex social networks. The results show that our method outperforms other four state-of-the-art approaches.

Keywords: complex network, multi-granularity, task decomposition, density peaks

References(39)

[1]
J. R. Hobbs, Granularity, in Readings in Qualitative Reasoning about Physical Systems, D. S. Weld and J. De Kleer, eds. Elsevier, 1990, pp. 542-545.
DOI
[2]
L. Zhang and B. Zhang, Theory and Application of Problem Solving. Beijing, China: Tsinghua University Press, 1990.
[3]
J. S. R. Jang, ANFIS: Adaptive-network-based fuzzy inference system, IEEE Trans. Syst., Man, and Cybern., vol. 23, no. 3, pp. 665-685, 1993.
[4]
G. Y. Wang and H. B. Shi, TMLNN: Triple-valued or multiple-valued logic neural network, IEEE Trans. Neural Netw., vol. 9, no. 6, pp. 1099-1117, 1998.
[5]
L. Y. Zhu, G. W. Yuan, and Q. Du, An efficient explicit/implicit domain decomposition method for convection-diffusion equations, Numer. Methods Partial Differ. Equ., vol. 26, no. 4, pp. 852-873, 2010.
[6]
R. E. Jenkins and B. P. Yuhas, A simplified neural network solution through problem decomposition: The case of the truck backer-upper, IEEE Trans. Neural Netw., vol. 4, no. 4, pp. 718-720, 1993.
[7]
S. Thiria, C. Mejia, F. Badran, and M. Crépon, Multimodular architecture for remote sensing operations, in Proc. 4th Int. Conf. Neural Information Processing Systems, Denver, CO, USA, 1991, pp. 675-682.
[8]
R. Rifkin and A. Klautau, In defense of one-vs-all classification, J. Mach. Learn. Res., vol. 5, pp. 101-141, 2004.
[9]
R. Perdisci, G. F. Gu, and W. Lee, Using an ensemble of one-class SVM classifiers to harden payload-based anomaly detection systems, in Proc. 6th Int. Conf. Data Mining, Hong Kong, China, 2006, pp. 488-498.
DOI
[10]
L. C. Cobo, C. L. Isbell Jr., and A. L. Thomaz, Automatic task decomposition and state abstraction from demonstration, in Proc. 11th Int. Conf. Autonomous Agents and Multiagent Systems, Valencia, Spain, 2012, pp. 483-490.
[11]
J. Xu and G. Y. Wang, Leading tree in DPCLUS and its impact on building hierarchies, arXiv preprint arXiv: 1506.03879, 2015.
[12]
A. Rodriguez and A. Laio, Clustering by fast search and find of density peaks, Science, vol. 344, no. 6191, pp. 1492-1496, 2014.
[13]
K. Sun, X. R. Geng, and L. Y. Ji, Exemplar component analysis: A fast band selection method for hyperspectral imagery, IEEE Geosci. Remote Sens. Lett., vol. 12, no. 5, pp. 998-1002, 2015.
[14]
Y. W. Chen, D. H. Lai, H. Qi, J. L. Wang, and J. X. Du, A new method to estimate ages of facial image for large database, Multimed. Tools Appl., vol. 75, no. 5, pp. 2877-2895, 2016.
[15]
H. Wu and Y. Wan, Clustering assisted fundamental matrix estimation, arXiv preprint arXiv: 1504.03409, 2015.
[16]
K. M. Dean, L. M. Davis, J. L. Lubbeck, P. Manna, P. Friis, A. E. Palmer, and R. Jimenez, High-speed multiparameter photophysical analyses of fluorophore libraries, Anal. Chem., vol. 87, no. 10, pp. 5026-5030, 2015.
[17]
A. P. Zeng and Y. P. Huang, A text classification algorithm based on Rocchio and hierarchical clustering, in Proc. 7th Int. Conf. Advanced Intelligent Computing, Zhengzhou, China, 2011, pp. 432-439.
DOI
[18]
M. M. Wang, W. L. Zuo, and Y. Wang, An improved density peaks-based clustering method for social circle discovery in social networks, Neurocomputing, vol. 179, pp. 219-227, 2016.
[19]
W. He and M. D. Xing, Classification method for POLSAR images based on find of density peak, (in Chinese), Syst. Eng. Electron., vol. 38, no. 1, pp. 60-63, 2016.
[20]
J. Xu, G. Y. Wang, and W. H. Deng, DenPEHC: Density peak based efficient hierarchical clustering, Inf. Sci., vol. 373, pp. 200-218, 2016.
[21]
G. Y. Wang, J. Xu, Q. H. Zhang, and Y. C Liu, Multi-granularity intelligent information processing, in Rough Sets, Fuzzy Sets, Data Mining, and Granular Computing, Y. Y. Yao, Q. H. Hu, H. Yu, and J. W. Grzymala-Busse, eds. Springer, 2015.
[22]
S. L. Wang, D. K. Wang, C. Y. Li, Y. Li, and G. Y. Ding, Clustering by fast search and find of density peaks with data field, Chin. J. Electron., vol. 25, no. 3, pp. 397-402, 2016.
[23]
T. Qiu, K. F. Yang, C. Y. Li, and Y. J. Li, A physically inspired clustering algorithm: To evolve like particles, arXiv preprint arXiv: 1412.5902, 2014.
[24]
M. L. Du, S. F. Ding, and H. J. Jia, Study on density peaks clustering based on k-nearest neighbors and principal component analysis, Knowl.-Based Syst., vol. 99, pp. 135-145, 2016.
[25]
X. H. Xu, Y. S. Ju, Y. L. Liang, and P. He, Manifold density peaks clustering algorithm, in Proc. 3rd Int. Conf. Advanced Cloud and Big Data, Yangzhou, China, 2015, pp. 311-318.
DOI
[26]
W. K. Zhang and J. Li, Extended fast search clustering algorithm: Widely density clusters, no density peaks, arXiv preprint arXiv: 1505.05610, 2015.
[27]
G. Karypis, E. H. Han, and V. Kumar, Chameleon: Hierarchical clustering using dynamic modeling, Computer, vol. 32, no. 8, pp. 68-75, 1999.
[28]
A. Biswas and B. Biswas, Investigating community structure in perspective of ego network, Expert Syst. Appl., vol. 42, no. 20, pp. 6913-6934, 2015.
[29]
J. Fagnan, O. Zaïane, and D. Barbosa, Using triads to identify local community structure in social networks, in Proc. 2014 IEEE/ACM Int. Conf. Advances in Social Networks Analysis and Mining, Beijing, China, 2014, pp. 108-112.
DOI
[30]
K. H. Lim and A. Datta, A seed-centric community detection algorithm based on an expanding ring search, in Proc. 1st Australasian Web Conf., Adelaide, South Australia, 2013.
[31]
Z. Yakoubi and R. Kanawati, LICOD: A leader-driven algorithm for community detection in complex networks, Vietnam J. Comput. Sci., vol. 1, no. 4, pp. 241-256, 2014.
[32]
D. Lusseau, K. Schneider, O. J. Boisseau, P. Haase, E. Slooten, and S. M. Dawson, The bottlenose dolphin community of doubtful sound features a large proportion of long-lasting associations, Behav. Ecol. Sociobiol., vol. 54, no. 4, pp. 396-405, 2003.
[33]
W. W. Zachary, An information flow model for conflict and fission in small groups, J. Anthropol. Res., vol. 33, no. 4, pp. 452-473, 2015.
[34]
M. Girvan and M. E. J. Newman, Community structure in social and biological networks, Proc. Natl. Acad. Sci. USA, vol. 99, no. 12, pp. 7821-7826, 2002.
[35]
A. Lancichinetti, S. Fortunato, and F. Radicchi, Benchmark graphs for testing community detection algorithms, Phys. Rev. E, vol. 78, no. 4, 2008.
[36]
N. X. Vinh, J. Epps, and J. Bailey, Information theoretic measures for clusterings comparison: Variants, properties, normalization and correction for chance, J. Mach. Learn. Res., vol. 11, pp. 2837-2854, 2010.
[37]
M. A. Tabarzad and A. Hamzeh, A heuristic local community detection method (HLCD), Appl. Intell., vol. 46, no. 1, pp. 62-78, 2017.
[38]
X. W. Xu, N. Yuruk, Z. D. Feng, and T. A. J. Schweiger, SCAN: A structural clustering algorithm for networks, in Proc. 13th ACM SIGKDD Int. Conf. Knowledge Discovery and Data Mining, San Jose, CA, USA, 2007, pp. 824-833.
DOI
[39]
D. Shah and T. Zaman, Community detection in networks: The leader-follower algorithm, arXiv preprint arXiv: 1011.0774 , 2010.
Publication history
Copyright
Acknowledgements
Rights and permissions

Publication history

Received: 08 September 2017
Accepted: 30 March 2018
Published: 24 May 2018
Issue date: September 2018

Copyright

© The author(s) 2018

Acknowledgements

This work was supported by the National Natural Science Foundation of China (No. 61572091) and Chongqing Postgraduate Scientific Research and Innovation Project (No. CYB16106).

Rights and permissions

Return