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

doi:10.26599/BDMA.2018.9020023

Big Data Mining and Analytics

2018, Vol. 01

Issue (03): 245-256 DOI: 10.26599/BDMA.2018.9020023

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

Ziling Pang, Guoyin Wang^*, Jie Yang

^∙ Ziling Pang, Guoyin Wang, and Jie Yang are with the Chongqing Key Laboratory of Computational Intelligence, Chongqing University of Post and Telecommunication, Chongqing 400060, China. E-mail: woshi@pangziling.com; 530966074@qq.com.

Download:

PDF (1524 KB)

HTML
Export: BibTeX | EndNote (RIS)

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.

Key words： multi-granularity task decomposition density peaks complex network

Received: 08 September 2017 Published: 13 January 2020

Corresponding Authors: Guoyin Wang


	Service

	E-mail this article
	Add to my bookshelf
	Add to citation manager
	E-mail Alert
	RSS
	Articles by authors
	Ziling Pang
	Guoyin Wang
	Jie Yang

Cite this article:

Ziling Pang, Guoyin Wang, Jie Yang. A Multi-granularity Decomposition Mechanism of Complex Tasks Based on Density Peaks. Big Data Mining and Analytics, 2018, 01(03): 245-256.

URL:

http://bigdata.tsinghuajournals.com/10.26599/BDMA.2018.9020023 OR http://bigdata.tsinghuajournals.com/Y2018/V01/I03/245

Fig. 1 (a) Dataset DS which contains the latitude and longitude of 13 cities; (b) Leading tree of DS; and (c) Clustering result of DS.

$i$	$Nneigh i$	$C ? L$
1	12	1
2	13	1
3	12	1
4	12	1
5	6	2
6	13	2
7	8	2
8	6	2
9	11	3
10	11	3
11	12	3
12	13	1
13	0	1

Table 1 The intermediate results of DS.

Fig. 2 The real social structure of Dolphin network.

$i$	$δ i$	$ρ i$	Nneigh $i$
1	2.21	0.75	48
2	2.42	0.79	55
3	1.08	0.81	11
4	0.92	0.79	60
$⋯$	$⋯$	$⋯$	$⋯$
31	1.76	0.73	48
32	0.20	1.00	18
$⋯$	$⋯$	$⋯$	$⋯$
62	0.60	11.00	38

Table 2 The intermediate results of DPC in Dolphin network.

Fig. 3 The global task leading tree of Dolphin network.

i	$δ i$	$ρ i$	$Nneigh i$	$o ? r ? d ? γ i$
1	2.21	0.75	48	46
2	2.42	0.79	55	15
3	1.08	0.81	11	14
4	0.92	0.79	60	38
$⋯$	$⋯$	$⋯$	$⋯$	34
31	1.76	0.73	48	52
32	0.20	1	18	$⋯$
$⋯$	$⋯$	$⋯$	$⋯$	$⋯$
62	0.61	1	38	61

Table 3 The redundant centers CT of Dolphin network.

$i$	Similarity ( $i$ )
46	—
15	0.436
14	0.129
38	0.291
34	0.290
52	0.290

Table 4 Popping process for the first member of final center task set.

Fig. 4 (a) Global leading tree structure of Dolphin network; (b) Progress of the first granulation, where node 14 is one of the community center, so the tree splits two sub trees, and they are constituted as a fine granularity task solving layer; (c) Granulating process triggered by center node 52, and they form a fine granular solving layer with three subtask sets.

$i$	Similarity ( $i$ )
46	—
15	0.559
38	0.500
34	0.529
52	0.317
$⋮$	$⋮$

Table 5 Popping process for the second member of final center task set.

$i$	Similarity ( $i$ )
46	—
15	0.559
38	0.500
34	0.529
$⋮$	$⋮$

Table 6 Popping process for the third member of final center task set.

Fig. 5 The structure of Dolphin network by MrGDM.

Table 7 Compared methods and their description.

Table 8 Experimental applications of the compared methods for the selected datasets.

Algorithm	Complexity	Remark
ENBC^[28]	$O ? (n 2)$	Accurate communities, but still bound by cost
Local-T^[29]	$O ? (n 3)$	Identifies outliers, but for local communities
CDERS^[30]	$O ? (n 2)$	Accurate communities in small network
LICOD[^[31]	$O ? (n 3)$	Smaller and very inaccurate communities
SCAN^[38]	$O ? (m)$	Identifies outliers, but inaccurate communities
LeadF^[39]	$O ? (nm)$	Smaller communities in dense network
MrGDM	$O ? (n 2)$	Accurate communities, but for dense network

Table 9 Summary of complexity of community detection algorithms.


[1]	Hobbs J. R., Granularity, in Readings in Qualitative Reasoning about Physical Systems, Weld D. S. and De Kleer J., eds. Elsevier, 1990, pp. 542-545.
[2]	Zhang L. and Zhang B., Theory and Application of Problem Solving. Beijing, China: Tsinghua University Press, 1990.
[3]	Jang J. S. R., ANFIS: Adaptive-network-based fuzzy inference system, IEEE Trans. Syst., Man, and Cybern., vol. 23, no. 3, pp. 665-685, 1993.
[4]	Wang G. Y. and Shi H. B., TMLNN: Triple-valued or multiple-valued logic neural network, IEEE Trans. Neural Netw., vol. 9, no. 6, pp. 1099-1117, 1998.
[5]	Zhu L. Y., Yuan G. W., and Du Q., 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]	Jenkins R. E. and Yuhas B. P., 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]	Thiria S., Mejia C., Badran F., and Crépon M., Multimodular architecture for remote sensing operations, in Proc. 4th Int. Conf. Neural Information Processing Systems, Denver, CO, USA, 1991, pp. 675-682.
[8]	Rifkin R. and Klautau A., In defense of one-vs-all classification, J. Mach. Learn. Res., vol. 5, pp. 101-141, 2004.
[9]	Perdisci R., Gu G. F., and Lee W., 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.
[10]	Cobo L. C., Isbell C. L. Jr., and Thomaz A. L., 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]	Xu J. and Wang G. Y., Leading tree in DPCLUS and its impact on building hierarchies, arXiv preprint arXiv: 1506.03879, 2015.
[12]	Rodriguez A. and Laio A., Clustering by fast search and find of density peaks, Science, vol. 344, no. 6191, pp. 1492-1496, 2014.
[13]	Sun K., Geng X. R., and Ji L. Y., 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]	Chen Y. W., Lai D. H., Qi H., Wang J. L., and Du J. X., A new method to estimate ages of facial image for large database, Multimed. Tools Appl., vol. 75, no. 5, pp. 2877-2895, 2016.
[15]	Wu H. and Wan Y., Clustering assisted fundamental matrix estimation, arXiv preprint arXiv: 1504.03409, 2015.
[16]	Dean K. M., Davis L. M., Lubbeck J. L., Manna P., Friis P., Palmer A. E., and Jimenez R., High-speed multiparameter photophysical analyses of fluorophore libraries, Anal. Chem., vol. 87, no. 10, pp. 5026-5030, 2015.
[17]	Zeng A. P. and Huang Y. P., A text classification algorithm based on Rocchio and hierarchical clustering, in Proc. 7th Int. Conf. Advanced Intelligent Computing, Zhengzhou, China, 2011, pp. 432-439.
[18]	Wang M. M., Zuo W. L., and Wang Y., An improved density peaks-based clustering method for social circle discovery in social networks, Neurocomputing, vol. 179, pp. 219-227, 2016.
[19]	He W. and Xing M. D., 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]	Xu J., Wang G. Y., and Deng W. H., DenPEHC: Density peak based efficient hierarchical clustering, Inf. Sci., vol. 373, pp. 200-218, 2016.
[21]	Wang G. Y., Xu J., Zhang Q. H., and C Liu Y., Multi-granularity intelligent information processing, in Rough Sets, Fuzzy Sets, Data Mining, and Granular Computing, Yao Y. Y., Hu Q. H., Yu H., and Grzymala-Busse J. W., eds. Springer, 2015.
[22]	Wang S. L., Wang D. K., Li C. Y., Li Y., and Ding G. Y., Clustering by fast search and find of density peaks with data field, Chin. J. Electron., vol. 25, no. 3, pp. 397-402, 2016.
[23]	Qiu T., Yang K. F., Li C. Y., and Li Y. J., A physically inspired clustering algorithm: To evolve like particles, arXiv preprint arXiv: 1412.5902, 2014.
[24]	Du M. L., Ding S. F., and Jia H. J., Study on density peaks clustering based on k-nearest neighbors and principal component analysis, Knowl.-Based Syst., vol. 99, pp. 135-145, 2016.
[25]	Xu X. H., Ju Y. S., Liang Y. L., and He P., Manifold density peaks clustering algorithm, in Proc. 3rd Int. Conf. Advanced Cloud and Big Data, Yangzhou, China, 2015, pp. 311-318.
[26]	Zhang W. K. and Li J., Extended fast search clustering algorithm: Widely density clusters, no density peaks, arXiv preprint arXiv: 1505.05610, 2015.
[27]	Karypis G., Han E. H., and Kumar V., Chameleon: Hierarchical clustering using dynamic modeling, Computer, vol. 32, no. 8, pp. 68-75, 1999.
[28]	Biswas A. and Biswas B., Investigating community structure in perspective of ego network, Expert Syst. Appl., vol. 42, no. 20, pp. 6913-6934, 2015.
[29]	Fagnan J., Za?ane O., and Barbosa D., 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.
[30]	Lim K. H. and Datta A., A seed-centric community detection algorithm based on an expanding ring search, in Proc. 1st Australasian Web Conf., Adelaide, South Australia, 2013.
[31]	Yakoubi Z. and Kanawati R., LICOD: A leader-driven algorithm for community detection in complex networks, Vietnam J. Comput. Sci., vol. 1, no. 4, pp. 241-256, 2014.
[32]	Lusseau D., Schneider K., Boisseau O. J., Haase P., Slooten E., and Dawson S. M., 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]	Zachary W. W., An information flow model for conflict and fission in small groups, J. Anthropol. Res., vol. 33, no. 4, pp. 452-473, 2015.
[34]	Girvan M. and Newman M. E. J., Community structure in social and biological networks, Proc. Natl. Acad. Sci. USA, vol. 99, no. 12, pp. 7821-7826, 2002.
[35]	Lancichinetti A., Fortunato S., and Radicchi F., Benchmark graphs for testing community detection algorithms, Phys. Rev. E, vol. 78, no. 4, 2008.
[36]	Vinh N. X., Epps J., and Bailey J., Information theoretic measures for clusterings comparison: Variants, properties, normalization and correction for chance, J. Mach. Learn. Res., vol. 11, pp. 2837-2854, 2010.
[37]	Tabarzad M. A. and Hamzeh A., A heuristic local community detection method (HLCD), Appl. Intell., vol. 46, no. 1, pp. 62-78, 2017.
[38]	Xu X. W., Yuruk N., Feng Z. D., and Schweiger T. A. J., 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.
[39]	Shah D. and Zaman T., Community detection in networks: The leader-follower algorithm, arXiv preprint arXiv: 1011.0774 , 2010.

No related articles found!

Viewed

Full text

Abstract

Cited

Shared

Discussed