Abstract
The traditional minimum spanning tree clustering algorithm uses a simple Euclidean distance metric method to calculate the distance between two entities. For the processing of noise data, the similarity can’t be well described. In this regard, first of all, we integrate fuzzy set theory to improve, and propose a method with indeterminacy fuzzy distance measurement. In the distance metric method, fuzzy set theory is introduced to measure the differences between two entities. Moreover, the attributes are fuzzy weighted on this basis, which overcomes the shortcomings of the simple Euclidean distance measurement method. So, it not only has a good tolerance for data noise to solve the misclassification of noise information in the actual data, but also takes into account the difference of distinguishability contribution degree of attributes in classification. Thus, the accuracy of clustering is improved, and it also has significance in practical project application. Then, the proposed distance metric is applied into the traditional MST clustering algorithm. Compared with the traditional MST clustering algorithm and other classical clustering algorithms, the results show that the MST algorithm based on the new distance metric is more effective.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Change history
11 April 2019
In the original version of the book, the first affiliation “Princeton University, Princeton, NJ 08544, USA” has to be removed for chapter authors “Lu Sun” and “Yuan Tian” in chapters “A Minimum Spanning Tree Algorithm Based on Fuzzy Weighted Distance” and “Cuckoo Search Algorithm Based on Stochastic Gradient Descent”, respectively.
References
Xin, C.: Research on clustering analysis method based on minimum spanning tree. A master’s degree thesis. Chongqing University, Chongqing (2013)
Tang, F.: Data Structure Tutorial, pp. 158–276. Beihang University Press, Beijing (2005)
Barna, S., Pabitra, M.: Dynamic algorithm for graph clustering using minimum cut tree. In: Proceeding of Sixth IEEE International Conference on Data Mining (2006)
Wang, X., Wang, X., Wilkes, D.M.: A divide-and-conquer approach for minimum spanning tree-based clustering. IEEE Trans. Knowl. Data Eng. 21(7), 945–958 (2009)
Caetano Jr., T., Traina, A.J.M., Faloutsos, C.: Feature selection using fractal dimension-ten years later. J. Inf. Data Manag. 1(1), 17–20 (2010)
Zhong, C., Miao, D., Wang, R.: A graph-theoretical clustering method based on two rounds of minimum spanning trees. Pattern Recognit. 43(3), 752–766 (2010)
Moore, A.W.: An Introductory Tutorial on KD-Trees. University of Cambridge, UK (1991)
Olman, V., Mao, F., Wu, H., Xu, Y.: Parallel clustering algorithm for large data sets with applications in bioinformatics. IEEE Computer Society Press 6(2), 344–352 (2009)
Wang, H., Zhang, H., Ray, N.: Adaptive shape prior in graph cut image segmentation. Pattern Recogn. 46(5), 1409–1414 (2013)
Smarandache, F.: A unifying field in logics. Neutrosophy: Neutrosphic probability, set and logic. American Research Press, Rehoboth, D E (1999)
Zadeh, L.A.: In there a need for fuzzy logic? Inf. Sci. 178, 2751–2779 (2008)
Zhang, D.: Research on Motor Fault Diagnosis Method Based on Rough Set Theory. Bohai University, Jinzhou (2015)
Ye, J.: Single-valued neutrosophic similarity measures based on cotangent function and their application and their application in the fault diagnosis of steam turbine. Soft. Comput. 21(3), 1–9 (2017)
Wang, H., Smarandache, F., Zhang, Y.Q., Sunderraman, R.: Interval neutrosophic sets and logic: theory and applications in computing. Hexis, Phoenix, A Z (2005)
Wang, H.B., Smarandache, F., Zhang, Y.Q., et al.: Single valued neutrosophic sets. Multispace Multructure 4(10), 410–413 (2010)
Peng, J.J., Wang, J.Q., Zhang, H.Y., et al.: An outranking approach for multi-criteria decision-making problems with simplified neutrosophic sets. Appl. Soft Comput. 25(25), 336–346 (2014)
Biswas, P., Pramanik, S., Giri, B.C.: TOPSIS method for multi- attribute group decision-making under single-valued netrosophic environment. Neural Comput. Appl. 27(3), 727–737 (2016)
Majumdar, P., Damanta, S.K.: On similarity and entropy of neutrosophic sets. J. Intell. Fuzzy Syst. Appl. Eng. Technol. 26(3), 1245–1252 (2014)
Yan, W., Wu, W.: Data structure. Tsinghua University Press, Beijing (1992)
Graham, R.L., Hell, P.: On the history of the minimum spanning tree problem. Ann. Hist. Comput. 7(1), 43–57 (1985)
Atanassov, K.T.: Intuitionstic fuzzy sets. Fuzzy Syst. 20(1), 87–96 (1986)
Shi, Y., Shi, W., Jin, F.: Entropy and its application in the study of uncertainty in spatial data. Comput. Eng. 31 (24), 36–37 (2005)
Acknowledgement
We would like to thank the anonymous reviewers for their valuable comments and suggestions. This work is supported by The State Key Research Development Program of China under Grant 2016YFC0801403, Shandong Provincial Natural Science Foundation of China under Grant ZR2018MF009 and ZR2015FM013, the Special Funds of Taishan Scholars Construction Project, and Leading Talent Project of Shandong University of Science and Technology.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2019 Springer Nature Switzerland AG
About this paper
Cite this paper
Sun, L., Liang, Yq., Fan, Jc. (2019). A Minimum Spanning Tree Algorithm Based on Fuzzy Weighted Distance. In: Krömer, P., Zhang, H., Liang, Y., Pan, JS. (eds) Proceedings of the Fifth Euro-China Conference on Intelligent Data Analysis and Applications. ECC 2018. Advances in Intelligent Systems and Computing, vol 891. Springer, Cham. https://doi.org/10.1007/978-3-030-03766-6_9
Download citation
DOI: https://doi.org/10.1007/978-3-030-03766-6_9
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-03765-9
Online ISBN: 978-3-030-03766-6
eBook Packages: Intelligent Technologies and RoboticsIntelligent Technologies and Robotics (R0)