# Fuzzy Clustering Method Based on Improved Weighted Distance

Authors: Honghan Bei; Yingchao Mao; Wenyang Wang; Xu Zhang
Journal: Mathematical Problems in Engineering
 (2021)

---

## Abstract

As an essential data processing technology, cluster analysis has been widely used in various fields. In clustering, it is necessary to select appropriate measures to evaluate the similarity in the data. In this paper, firstly, a cluster center selection method based on the grey relational degree is proposed to solve the problem of sensitivity in initial cluster center selection. Secondly, combining the advantages of Euclidean distance, DTW distance, and SPDTW distance, a weighted distance measurement based on three kinds of reach is proposed. Then, it is applied to Fuzzy C-MeDOIDS and Fuzzy C-means hybrid clustering technology. Numerical experiments are carried out with the UCI datasets. The experimental results show that the accuracy of the clustering results is significantly improved by using the clustering method proposed in this paper. Besides, the method proposed in this paper is applied to the MUSIC INTO EMOTIONS and YEAST datasets. The clustering results show that the algorithm proposed in this paper can also achieve a better clustering effect when dealing with practical problems.


---

## Body

## 1. Introduction

Clustering analysis, clustering for short, is the process of subdividing data objects into subsets. Each subset is a cluster, and items in the same cluster have a high similarity, while objects in different clusters have a relatively high divergence. Clustering algorithms are widely used in engineering (such as artificial intelligence and machine learning), biomedical (such as blood pressure and electrocardiogram measurement), biometric data (facial recognition image data), sentiment analysis (sentiment classification scheme), meteorological data, physical particle tracking, and other fields [1].Data sequences are characterized by nonlinearity, high dimension, complexity, and redundancy. Although complex, they often contain the evolution law of things [2]. To find these potential rules, the data mining algorithm plays a vital role in data analysis, the clustering of which is one of the critical technologies. Three factors directly affect data clustering: correct acquisition of clustering number, efficient and excellent clustering algorithm, and distance function determining the similarity between data points.K-means is a classical clustering algorithm based on division. The main idea is to find out K clustering centers, divide the dataset into K classes, and make each data sequence belong to a specific class. However, it is difficult to determine the number of clustering K in this algorithm, and the unsuitable K is not worth the ideal clustering result. Therefore, Gupta and Srivastava proposed a document-based K-means algorithm that automatically selects K and refined clusters, thus solving cluster number selection problems [3]. Onan and Toolu have made generous contributions to the study of clustering. Onan, A. presents a consensus clustering-based undersampling approach to imbalanced learning. In this scheme, five supervised learning methods (namely, k -means, k -modes, k -means++, self-organizing maps, and DIANA algorithm), three ensemble learner methods, five clustering algorithms, and their combinations are adopted. In the clustering stage, Onan, A. proposes an improved clustering integration framework, which combines the traditional clustering methods (i.e., K-means, K-modes, K-means++, self-organizing mapping, and Diana algorithm) through iterative voting consistency. Onan and Toolu present a document-clustering model on MOOC discussion forum posts. In their study, four word-embedding schemes, four weighting functions, and four clustering algorithms (i.e., K-means, K-means++, self-organizing maps, and divisive analysis clustering algorithm) are used for document clustering [4]. Onanand Toolu augment the randomized seeding technique to overcome poor initialization of medoids in the PAM algorithm. The proposed approach (PAM++) is compared with other partitional clustering algorithms, such as K-means and K-means++ on text document clustering benchmarks, and evaluated in terms of F-measure. However, in practical applications, data sequences sometimes belong to multiple classes rather than just one class. To deal with this problem, fuzzy clustering methods, such as the FCM algorithm and the FBSA algorithm, came into being. Li et al. [5] summarize data mining research based on fuzziness theory, expound the research results of fuzzy clustering methods in recent years, and forecast the research prospect. The most representative fuzzy clustering algorithm is the fuzzy C-mean (FCM) algorithm. The fuzzy C-mean algorithm uses fuzzy theory to describe the data. This algorithm is a flexible partition that can obtain much clustering information and reflect the actual distribution of the samples more accurately. However, at the same time, this algorithm is sensitive to the selection of the initial clustering center point and prone to fall into the problem of an optimal local solution. To make up for the shortcomings of the algorithm and improve the accuracy of the algorithm, researchers always put forward improved clustering methods. Zhu et al. [6] proposed an improved fuzzy C-means algorithm combining genetic algorithm, particle swarm optimization, and FCM clustering algorithm. The enhanced algorithm optimized the performance of the clustering algorithm to some extent and reduced the dependence of the algorithm on the initial center point. Zhang and Wang [7] proposed a new method for cluster center selection, which took the midpoints of the two closest sample points as cluster center points for cluster analysis. Bharill and Tiwari [8] introduced a random sampling iterative optimized fuzzy C-mean (RSIO-FCM) clustering algorithm, which divided big data into different subsets, formed effective clustering, and eliminated the problem of overlapping clustering centers. Bulut et al. [9] have developed an efficient clustering scheme for microarray gene expression data. The algorithm utilizes the feature selection algorithm to overcome the high-dimensionality problem encountered in the bioinformatics domain. The clustering quality of the ant-based clustering algorithm is enhanced with the use of fuzzy c-means algorithm and heaps merging heuristic. Based on the improved fuzzy C-means method, Liu et al. [10] used the chaotic quantum particle swarm optimization algorithm to generate initialization and global optimal clustering center. They then applied the improved algorithm to the clustering problem of time series datasets, achieving a good clustering effect.Besides, in clustering, different distance functions often have a significant impact on the clustering results. Euclidean distance is a widely used distance function, but Euclidean distance is difficult to solve the linear drift problem. Rammal et al. studied infrared spectrum clustering and experimentally verified that the experimental results using L1 or Manhattan distance were superior to the Euclidean and Cheyne distances [11]. Petitjean et al. [12] proposed the average value method based on DTW. Izakian et al. [13] applied the average value method of Petitjean et al. to the FCMDD algorithm and achieved satisfactory results. Based on limited DTW, Kathiresan and Sumathi proposed an improved FCM algorithm [14], and the experimental results showed that the improved algorithm was more accurate.In this paper, a weighted distance method based on a fuzzy model is proposed to cluster different sequences. We first determined the initial clustering center based on the grey relational degree method, then applied the weighted distance of Euclidean distance, DTW, and SPDTW to the FCM algorithm, and carried out the optimal clustering for the sequence through the particle swarm optimization algorithm. Through numerical experiments, different datasets are clustered, and the experimental results show that the improved algorithm proposed in this paper is more accurate than the existing literature.The rest of the paper is organized as follows: Section2 introduces the basic principles of grey relational degree, fuzzy C-means clustering, and distance function. Section 3 introduces the implementation of the improved fuzzy C-means clustering method. In Section 4, the improved clustering method is applied to different datasets, and numerical experiments are carried out to verify the effectiveness of the method through comparison. Besides, the method proposed in this paper is applied to the self-care (SCADI) problems of children with physical and motor impairments. The clustering results show that the algorithm proposed in this paper can also achieve a better clustering effect when dealing with practical problems. Section 5 gives the summary.


## 2. Basic Knowledge

This section introduces the basic concepts and principles of grey relational degree, fuzzy C-means clustering, and distance function.


### 2.1. Grey Relational Degree Analysis

The basic ideas of grey relation analysis method are as follows: according to the comparative sequence, set up the constituent of a family of curves and the reference sequence curve to determine the geometric similarity degree between the reference sequence and compared sequence set, and the correlations between the comparative sequence consisting of the curve and constituent of the reference sequence curve geometry are similar, and the correlation is more significant. The comprehensive evaluation method using grey correlation analysis is as follows.Assuming that the evaluation problem is composed ofn objects and m indicators, xij represents the index value of the i object and the j index, and the original evaluation matrix is X=X1,X2,…,XnT, in which Xi=xi1,xi2,…,xim,i=1,2,…,n. According to the purpose of evaluation and index situation, the reference number is set as X0=x01,x02,…,x0j,…,xim. We begin by standardizing the index data (adopting different standardized processing strategies for different index types). The data sequence after standardized processing is recorded as Z=Z1,Z2,…,ZnT, in which Zi=zi1,zi2,…,zim,i=1,2,…,n. After standardized treatment, the reference number column is Z0=z01,z02,…,z0j,…,z0m. The absolute difference between the index sequence (comparison sequence) of each evaluated object and the corresponding element of the reference sequence is calculated one by one, zij−z0j,i=1,2,…,n, to confirm mini=1nminj=1mzij−z0j and maxi=1nmaxj=1mzij−z0j.Then, the correlation coefficient between the corresponding elements of each comparison sequence and the reference sequence is calculated:(1)ζij=mini=1nminj=1mzij−z0j+η⋅maxi=1nmaxj=1mzij−z0jzij−z0j+η⋅maxi=1nmaxj=1mzij−z0j,where η is the resolution ratio, the value of which is between (0, 1). The smaller the value of η is, the greater the difference between correlation coefficients is, and the stronger the resolution ability is. Usually, η=0.5.For each evaluation object, the mean value of the correlation coefficient of the corresponding element of each index and the reference sequence is calculated, respectively, to reflect the correlation degree of each evaluation object and the reference sequence, denoted as(2)Y=y01,…,y0i,…,y0nT,y0i=1m∑j=1mζijj,i=1,2,…,n;j=1,2,…,m.


### 2.2. Fuzzy C-Means Clustering

Fuzzy c-means (FCM) clustering uses membership to determine that each data point belongs to a certain degree of clustering of a fuzzy clustering algorithm. Its core idea is based on the fuzzy membership degree matrix obtained. The membership degree of each data sample’s power and the distance between every center-weighted clustering define the objective function. The fuzzy C-means clustering criterion is to find the membership matrix and the clustering center to minimize the objective function.Given datasetX=x1,x2,…,xn, fuzzy clustering is the division of samples into classes 2≤c≤n; denote V=v1,v2,…,vc as c center of clustering, U=uji is the degree of membership of ith data base xi corresponding to the jth sort, and then the clustering loss function based on membership function is(3)JU,V=∑i=1n∑j=1cujimd2xi,vj,s.t.0≤uji≤1,∑j=1cuji=1,where d is the distance measurement, and m is the fuzzy weighted index, also known as a smoothing factor, which controls the degree of fuzziness between fuzzy classes.Let loss functionJU,V be the partial derivative vj and uji is 0, so the necessary conditions for obtaining the formula minimum (3) are(4)vj=∑i=1nujimxi∑i=1nujim,(5)uji=1∑k=1cdxi,vj/dxi,vk2/m−1.Therefore, the membership matrix and clustering center are calculated as (4) and (5). By optimizing the objective function to minimize it, each sample point’s final membership matrix to all class centers is obtained, thus determining the optimal classification of all sample data.In this paper, we also mentioned the fuzzy C center point (FCMdd) clustering algorithm. FCMdd algorithm, like the FCM algorithm, uses (3) as the objective function and updates the clustering center and membership matrix through formulas (4) and (5). However, they have different choices for the initial clustering center. FCM uses the weighted average value of data or randomly generates a set of data as the initial clustering center, while FCMdd selects the existing data in the dataset as the initial center.


### 2.3. Distance Measurement

#### 2.3.1. Euclidean Distance

In many clustering algorithms, the Euclidean distance formula is used as the basis for clustering. The Euclidean distance (ED) formula can be expressed as(6)dxi,xj=∑k=1mxik−xjk2.In this paper, the weighted Euclidean distance [15] will be adopted, which can be expressed as(7)dED=dxi,xj=∑k=1mwkxik−xjk2,where wk is the weight. In the present paper, the weight is determined in the following form:(8)wk=vk∑k=1mvk,vk=σkx¯k,where σk is the standard deviation of the index k and x¯k is the average of the number k..


#### 2.3.2. Dynamic Time Structuring (DTW)

DTW is based on the idea of dynamic programming (DP). Given two discrete sequences, DTW can measure how similar the two sequences are, or how far apart they are. If two feature sequencesX and Y have i frames and j frames, respectively, it is assumed that the distance of every two frames between X and Y is calculated to obtain the difference matrix D=dij with i rows and j columns, and the element dij is expressed as(9)dij=di,j=DistXi,Yj,where DistXi,Yj is the deviation between Xi and Yj.The calculation formula of DTW is(10)DTWXj,Yj=minDTWXi−1,Yj−1,DTWXi−1,Yj,DTWXi,Yj−1+di,j,where DTWXi,Yj is the summation of the minimum differences between frame i of X sequence and frame j of Y sequence.Also, the SPDTW algorithm is an improvement on DTW. The calculation formula of the SPDTW algorithm is as follows:(11)SPDTWXi,Yj=DTWXi′,Yj′,Xi′=Xi−1−Xi,i=1,2,…,n−1.Compared with the DTW algorithm, the introduction of SPDTW will reduce computation and improve the clustering accuracy to a certain extent.


## 2.1. Grey Relational Degree Analysis

The basic ideas of grey relation analysis method are as follows: according to the comparative sequence, set up the constituent of a family of curves and the reference sequence curve to determine the geometric similarity degree between the reference sequence and compared sequence set, and the correlations between the comparative sequence consisting of the curve and constituent of the reference sequence curve geometry are similar, and the correlation is more significant. The comprehensive evaluation method using grey correlation analysis is as follows.Assuming that the evaluation problem is composed ofn objects and m indicators, xij represents the index value of the i object and the j index, and the original evaluation matrix is X=X1,X2,…,XnT, in which Xi=xi1,xi2,…,xim,i=1,2,…,n. According to the purpose of evaluation and index situation, the reference number is set as X0=x01,x02,…,x0j,…,xim. We begin by standardizing the index data (adopting different standardized processing strategies for different index types). The data sequence after standardized processing is recorded as Z=Z1,Z2,…,ZnT, in which Zi=zi1,zi2,…,zim,i=1,2,…,n. After standardized treatment, the reference number column is Z0=z01,z02,…,z0j,…,z0m. The absolute difference between the index sequence (comparison sequence) of each evaluated object and the corresponding element of the reference sequence is calculated one by one, zij−z0j,i=1,2,…,n, to confirm mini=1nminj=1mzij−z0j and maxi=1nmaxj=1mzij−z0j.Then, the correlation coefficient between the corresponding elements of each comparison sequence and the reference sequence is calculated:(1)ζij=mini=1nminj=1mzij−z0j+η⋅maxi=1nmaxj=1mzij−z0jzij−z0j+η⋅maxi=1nmaxj=1mzij−z0j,where η is the resolution ratio, the value of which is between (0, 1). The smaller the value of η is, the greater the difference between correlation coefficients is, and the stronger the resolution ability is. Usually, η=0.5.For each evaluation object, the mean value of the correlation coefficient of the corresponding element of each index and the reference sequence is calculated, respectively, to reflect the correlation degree of each evaluation object and the reference sequence, denoted as(2)Y=y01,…,y0i,…,y0nT,y0i=1m∑j=1mζijj,i=1,2,…,n;j=1,2,…,m.


## 2.2. Fuzzy C-Means Clustering

Fuzzy c-means (FCM) clustering uses membership to determine that each data point belongs to a certain degree of clustering of a fuzzy clustering algorithm. Its core idea is based on the fuzzy membership degree matrix obtained. The membership degree of each data sample’s power and the distance between every center-weighted clustering define the objective function. The fuzzy C-means clustering criterion is to find the membership matrix and the clustering center to minimize the objective function.Given datasetX=x1,x2,…,xn, fuzzy clustering is the division of samples into classes 2≤c≤n; denote V=v1,v2,…,vc as c center of clustering, U=uji is the degree of membership of ith data base xi corresponding to the jth sort, and then the clustering loss function based on membership function is(3)JU,V=∑i=1n∑j=1cujimd2xi,vj,s.t.0≤uji≤1,∑j=1cuji=1,where d is the distance measurement, and m is the fuzzy weighted index, also known as a smoothing factor, which controls the degree of fuzziness between fuzzy classes.Let loss functionJU,V be the partial derivative vj and uji is 0, so the necessary conditions for obtaining the formula minimum (3) are(4)vj=∑i=1nujimxi∑i=1nujim,(5)uji=1∑k=1cdxi,vj/dxi,vk2/m−1.Therefore, the membership matrix and clustering center are calculated as (4) and (5). By optimizing the objective function to minimize it, each sample point’s final membership matrix to all class centers is obtained, thus determining the optimal classification of all sample data.In this paper, we also mentioned the fuzzy C center point (FCMdd) clustering algorithm. FCMdd algorithm, like the FCM algorithm, uses (3) as the objective function and updates the clustering center and membership matrix through formulas (4) and (5). However, they have different choices for the initial clustering center. FCM uses the weighted average value of data or randomly generates a set of data as the initial clustering center, while FCMdd selects the existing data in the dataset as the initial center.


## 2.3. Distance Measurement

### 2.3.1. Euclidean Distance

In many clustering algorithms, the Euclidean distance formula is used as the basis for clustering. The Euclidean distance (ED) formula can be expressed as(6)dxi,xj=∑k=1mxik−xjk2.In this paper, the weighted Euclidean distance [15] will be adopted, which can be expressed as(7)dED=dxi,xj=∑k=1mwkxik−xjk2,where wk is the weight. In the present paper, the weight is determined in the following form:(8)wk=vk∑k=1mvk,vk=σkx¯k,where σk is the standard deviation of the index k and x¯k is the average of the number k..


### 2.3.2. Dynamic Time Structuring (DTW)

DTW is based on the idea of dynamic programming (DP). Given two discrete sequences, DTW can measure how similar the two sequences are, or how far apart they are. If two feature sequencesX and Y have i frames and j frames, respectively, it is assumed that the distance of every two frames between X and Y is calculated to obtain the difference matrix D=dij with i rows and j columns, and the element dij is expressed as(9)dij=di,j=DistXi,Yj,where DistXi,Yj is the deviation between Xi and Yj.The calculation formula of DTW is(10)DTWXj,Yj=minDTWXi−1,Yj−1,DTWXi−1,Yj,DTWXi,Yj−1+di,j,where DTWXi,Yj is the summation of the minimum differences between frame i of X sequence and frame j of Y sequence.Also, the SPDTW algorithm is an improvement on DTW. The calculation formula of the SPDTW algorithm is as follows:(11)SPDTWXi,Yj=DTWXi′,Yj′,Xi′=Xi−1−Xi,i=1,2,…,n−1.Compared with the DTW algorithm, the introduction of SPDTW will reduce computation and improve the clustering accuracy to a certain extent.


## 2.3.1. Euclidean Distance

In many clustering algorithms, the Euclidean distance formula is used as the basis for clustering. The Euclidean distance (ED) formula can be expressed as(6)dxi,xj=∑k=1mxik−xjk2.In this paper, the weighted Euclidean distance [15] will be adopted, which can be expressed as(7)dED=dxi,xj=∑k=1mwkxik−xjk2,where wk is the weight. In the present paper, the weight is determined in the following form:(8)wk=vk∑k=1mvk,vk=σkx¯k,where σk is the standard deviation of the index k and x¯k is the average of the number k..


## 2.3.2. Dynamic Time Structuring (DTW)

DTW is based on the idea of dynamic programming (DP). Given two discrete sequences, DTW can measure how similar the two sequences are, or how far apart they are. If two feature sequencesX and Y have i frames and j frames, respectively, it is assumed that the distance of every two frames between X and Y is calculated to obtain the difference matrix D=dij with i rows and j columns, and the element dij is expressed as(9)dij=di,j=DistXi,Yj,where DistXi,Yj is the deviation between Xi and Yj.The calculation formula of DTW is(10)DTWXj,Yj=minDTWXi−1,Yj−1,DTWXi−1,Yj,DTWXi,Yj−1+di,j,where DTWXi,Yj is the summation of the minimum differences between frame i of X sequence and frame j of Y sequence.Also, the SPDTW algorithm is an improvement on DTW. The calculation formula of the SPDTW algorithm is as follows:(11)SPDTWXi,Yj=DTWXi′,Yj′,Xi′=Xi−1−Xi,i=1,2,…,n−1.Compared with the DTW algorithm, the introduction of SPDTW will reduce computation and improve the clustering accuracy to a certain extent.


## 3. Improved Fuzzy Clustering Method

### 3.1. Selection of Initial Cluster Centers

In general fuzzy clustering algorithms, the selection of the initial clustering center is usually randomly generated. However, since FCM and FCMdd clustering algorithms are susceptible to selecting the initial clustering center, the randomly generated clustering center may not have a good clustering effect. Therefore, this paper proposes an initial cluster center selection method based on the highest density and grey relational degree principle to reduce the dependence of the algorithm on the initial center point.In the clustering analysis of datasets, the clustering center must be in the area with a high distribution density of sample points. If the region centered on a sequence contains the most samples, the sample is the densest sequence. Therefore, we can first find the first initial clustering center in the region with the densest data distribution, and the distance between sample points located in the region with dense data distribution is small, and the mean distance of sample points in the dense region is also small. If an appropriate distance mean threshold is given, the distance and the mean distance between the initial cluster center in the dense region and other sample points in the region are generally smaller than the threshold. In this paper, the distance threshold used is determined by the average distance of all data samples and expressed as follows:(12)davg=1Cn2∑i=1n−1∑j=i+1ndxi,xj,where dxi,xj represents the distance between data xi and xj and n represents the number of all sample points to be clustered.The clustering center selection algorithm based on the principle of highest density is as follows:Step 1. Calculate the average distance value of all sample sequences through formula (12) and use it as the threshold value in the above analysis;Step 2. Draw a circle with the radius of davg and the sample i1≤i≤n as the center. Calculate the Euclidean distance between the first sample and other samples. If d<davg, then the sample is placed in the circle with the center of the sample i. Calculate the number of samples contained in the circle with the center of the sample i, and write it as ni;Step 3. The corresponding sequence maxni,1≤i≤n is obtained as the sequence i with the highest density, which denoted C1 as the first initial clustering center.In the clustering analysis, we need to determineC clustering centers. The above algorithm has given the first initial clustering center, and the selection of the remaining initial centers is given based on the grey relational degree method. The more similar the geometric shapes of the curve formed by the comparison sequence and the curve formed by the reference sequence are, the greater the correlation degree will be; otherwise, the smaller the correlation degree will be. The clustering center selection algorithm based on the grey relational degree is as follows:Step 1. Take the first determined initial clustering center C1 as the reference sequence and remove the sequence C1 from the dataset sequence of the clustering as the evaluation matrix.Step 2. According to the grey relational degree calculation formula (1), the correlation coefficient ζij of corresponding elements between the index sequence of each evaluated object (comparison sequence) and the reference sequence is calculated, and the correlation degree of each evaluation index sequence is y0i=1/m∑jζijj, in which the corresponding sequence with the lowest correlation degree is denoted as the second cluster center, denoted as C2.Step 3. Take the second cluster center C2 as the reference sequence, remove the dataset C1, C2 of the cluster, and repeat Step 2 as the new evaluation matrix C3. Repeat the above steps and get C as the initial cluster center.


### 3.2. Determination of Weighted Distance

In the process of clustering, different distance functions often have a great influence on the clustering results. Euclidean distance and DTW distance are widely used distance functions for data series clustering.The Euclidean distance has translation and rotation invariance. The use of the Euclidean distance as the objective function has intuitive significance and is easy to calculate. However, the Euclidean distance only considers the direct geographical distance between data and ignores the other valuable information, and it cannot solve the problem of linear drift.Dynamic time structuring distance (DTW) can well support time axis bending by stretching and compressing sequences. It can measure nonisometric sequences, flexibly match time series data, and determine the similarity between any two sequences by stretching or compressing data segments. However, traditional DTW algorithms are often limited by their high time and space complexity and are affected to some extent in practical applications.SPDTW is the DTW distance after differentiating the data sequence. Pure SPDTW is not very useful as a general distance metric. For example, a classification algorithm uses the nearest neighbor method, which tends to be less effective than DTW on a large database of time series. However, SPDTW can attenuate sequence fluctuations in many datasets and provide good results. This case is often used in conjunction with other distances.To overcome the disadvantages of different distance measurements, we combine the three kinds of distance measurement advantages. There may be a larger dataset dependent on a certain distance or a different degree depending on the distance measure problem (see Section4). This paper proposes a new method of weighted distance measurement, and it can be expressed as a linear combination of the form:(13)distX1,X2=a⋅dist1X1,X2+b⋅dist2X1,X2+c⋅dist3X1,X2,where a,b,c∈0,1, a+b+c=1.Based on the measurement method introduced in this article, we make the following transformation:(14)a=x1,b=x2,c=1−x1+x2,x1∈0,1,x2∈0,1,x1+x2∈0,1,dist1=DTW,dist2=SPDTW,dist3=dED.Thus, a new weighted distance measurement is obtained as follows:(15)newdistX1,X2=x1DTWX1,X2+x2SPDTWX1,X2+1−x1−x2dEDX1,X2,s.t.x1∈0,1,x2∈0,1,x1+x2∈0,1.It can be seen from equations (14) and (15) that the selection of distance directly affects the selection of membership matrix and clustering center, and from equation (15), we can see that the selection of parameter sum determines the value of distance. The Cross-Validation method is used here for the parameters’ tune. Therefore, let x=x1,x2, so the value of x would directly affect the quality of the clustering result. To select the appropriate value of x, the particle swarm optimization algorithm of x is used in this paper for optimization so as to obtain the optimal clustering effect.In particle swarm optimization (PSO), each optimization problem’s solution is regarded as a particle in the search space. The initial population is first generated, and the objective function determines a fitness value. Each particle will travel in solution space, and its velocity will determine its direction and distance. In each iteration, the particle updates itself by tracking two “extremes”: the one found by the particle itself, known as the individual best (pbest), and the one so far found by the entire population, known as the global best (gbest).In the particle swarm algorithm, particle velocity and position updating formulas are, respectively,(16)vnk+1=ωvnk+c1r1pnk−xnk+c2r2g−xnk,xnk+1=xnk+vnk+1,where vnk=vn,1k,vn,2k,vn,3k,…,vn,mk is the particle velocity of the particle n in the iteration k, ω is the inertia weight, pnk is the best position of the particle n in the first k iteration, g is the best position in the iteration population k, c1,c2 are the acceleration constants, and r1,r2 are the random numbers between 0 and 1.In this paper, the particle swarm optimization algorithm is used to find the optimal value of particles, to obtain the optimal fitness value, namely, the optimal clustering effect. PSO algorithm retains the global search strategy based on population and adopts the speed-displacement model, which is easy to operate and can find the optimal solution in fewer iterations.


### 3.3. Mixed Fuzzy Clustering

With the continuous development and progress of the data information age, traditional FCM clustering technology can no longer meet people’s demand for data processing. In this section, we present a hybrid technique that takes advantage of the FCM and FCMdd techniques.In this method, for the data sequence ofn×m, the FCMdd method firstly clusters the data into rr≥c classes, where c is the number of final clustering, and then obtains the cluster center Vr×1 and partition matrix Ur×n with r rows and n columns. In fact, the FCMdd technique is used here to transform the data, and usually r≤n, the transformed dataset is located in a smaller search space, and Ur×n is treated as a new dataset with r features and n objects. In the next step of this algorithm, the new weighted distance proposed in this paper is used as the distance function in the FCM algorithm to cluster the dataset U into class c, so as to obtain the final membership matrix U0 and clustering center V0, and analyze the clustering results to complete the clustering analysis of multiple sequences.To quantify the clustering methods in cluster analysis, precision is considered as an appropriate evaluation standard. In this paper, the method in Izakian et al. [10] is adopted to determine the clustering accuracy, and the calculation formula of the accuracy is(17)P=∑j=1kCjN×maxi=1,2,…,cpKi,Cj,pKi,Cj=Ki∩CjCj,where c is the number of clustering clusters, k is the number of known classes, N is the number of dataset sequences, Ki is the data sequence belonging to class I (known sequences), Cj is the data sequence belonging to class j, and ⋅ represents the number of elements in the set. To sum up, the overall scheme of the hybrid fuzzy clustering method proposed in this paper is as follows:Step 1. For the sequence to be clustered, we determine the initial clustering center based on the grey relational degree, divide the data into rc≤r≤n classes by FCMdd algorithm and DTW distance, determine the membership matrix and clustering center, and then transform the dataset into a smaller search space.Step 2. The FCMdd algorithm needs to determine the membership degree matrix clustering as a new dataset for the secondary clustering by the FCM algorithm. It requires the presented weighted distance as the FCM algorithm’s function through the weight of the particle swarm optimization algorithm to optimize the weighted distance. It obtains the final membership degree matrix and cluster centers. The optimal weight is obtained as the best clustering accuracy.Figure1 shows the flow chart of the above process.Figure 1
Flow chart of the fuzzy clustering method.


## 3.1. Selection of Initial Cluster Centers

In general fuzzy clustering algorithms, the selection of the initial clustering center is usually randomly generated. However, since FCM and FCMdd clustering algorithms are susceptible to selecting the initial clustering center, the randomly generated clustering center may not have a good clustering effect. Therefore, this paper proposes an initial cluster center selection method based on the highest density and grey relational degree principle to reduce the dependence of the algorithm on the initial center point.In the clustering analysis of datasets, the clustering center must be in the area with a high distribution density of sample points. If the region centered on a sequence contains the most samples, the sample is the densest sequence. Therefore, we can first find the first initial clustering center in the region with the densest data distribution, and the distance between sample points located in the region with dense data distribution is small, and the mean distance of sample points in the dense region is also small. If an appropriate distance mean threshold is given, the distance and the mean distance between the initial cluster center in the dense region and other sample points in the region are generally smaller than the threshold. In this paper, the distance threshold used is determined by the average distance of all data samples and expressed as follows:(12)davg=1Cn2∑i=1n−1∑j=i+1ndxi,xj,where dxi,xj represents the distance between data xi and xj and n represents the number of all sample points to be clustered.The clustering center selection algorithm based on the principle of highest density is as follows:Step 1. Calculate the average distance value of all sample sequences through formula (12) and use it as the threshold value in the above analysis;Step 2. Draw a circle with the radius of davg and the sample i1≤i≤n as the center. Calculate the Euclidean distance between the first sample and other samples. If d<davg, then the sample is placed in the circle with the center of the sample i. Calculate the number of samples contained in the circle with the center of the sample i, and write it as ni;Step 3. The corresponding sequence maxni,1≤i≤n is obtained as the sequence i with the highest density, which denoted C1 as the first initial clustering center.In the clustering analysis, we need to determineC clustering centers. The above algorithm has given the first initial clustering center, and the selection of the remaining initial centers is given based on the grey relational degree method. The more similar the geometric shapes of the curve formed by the comparison sequence and the curve formed by the reference sequence are, the greater the correlation degree will be; otherwise, the smaller the correlation degree will be. The clustering center selection algorithm based on the grey relational degree is as follows:Step 1. Take the first determined initial clustering center C1 as the reference sequence and remove the sequence C1 from the dataset sequence of the clustering as the evaluation matrix.Step 2. According to the grey relational degree calculation formula (1), the correlation coefficient ζij of corresponding elements between the index sequence of each evaluated object (comparison sequence) and the reference sequence is calculated, and the correlation degree of each evaluation index sequence is y0i=1/m∑jζijj, in which the corresponding sequence with the lowest correlation degree is denoted as the second cluster center, denoted as C2.Step 3. Take the second cluster center C2 as the reference sequence, remove the dataset C1, C2 of the cluster, and repeat Step 2 as the new evaluation matrix C3. Repeat the above steps and get C as the initial cluster center.


## 3.2. Determination of Weighted Distance

In the process of clustering, different distance functions often have a great influence on the clustering results. Euclidean distance and DTW distance are widely used distance functions for data series clustering.The Euclidean distance has translation and rotation invariance. The use of the Euclidean distance as the objective function has intuitive significance and is easy to calculate. However, the Euclidean distance only considers the direct geographical distance between data and ignores the other valuable information, and it cannot solve the problem of linear drift.Dynamic time structuring distance (DTW) can well support time axis bending by stretching and compressing sequences. It can measure nonisometric sequences, flexibly match time series data, and determine the similarity between any two sequences by stretching or compressing data segments. However, traditional DTW algorithms are often limited by their high time and space complexity and are affected to some extent in practical applications.SPDTW is the DTW distance after differentiating the data sequence. Pure SPDTW is not very useful as a general distance metric. For example, a classification algorithm uses the nearest neighbor method, which tends to be less effective than DTW on a large database of time series. However, SPDTW can attenuate sequence fluctuations in many datasets and provide good results. This case is often used in conjunction with other distances.To overcome the disadvantages of different distance measurements, we combine the three kinds of distance measurement advantages. There may be a larger dataset dependent on a certain distance or a different degree depending on the distance measure problem (see Section4). This paper proposes a new method of weighted distance measurement, and it can be expressed as a linear combination of the form:(13)distX1,X2=a⋅dist1X1,X2+b⋅dist2X1,X2+c⋅dist3X1,X2,where a,b,c∈0,1, a+b+c=1.Based on the measurement method introduced in this article, we make the following transformation:(14)a=x1,b=x2,c=1−x1+x2,x1∈0,1,x2∈0,1,x1+x2∈0,1,dist1=DTW,dist2=SPDTW,dist3=dED.Thus, a new weighted distance measurement is obtained as follows:(15)newdistX1,X2=x1DTWX1,X2+x2SPDTWX1,X2+1−x1−x2dEDX1,X2,s.t.x1∈0,1,x2∈0,1,x1+x2∈0,1.It can be seen from equations (14) and (15) that the selection of distance directly affects the selection of membership matrix and clustering center, and from equation (15), we can see that the selection of parameter sum determines the value of distance. The Cross-Validation method is used here for the parameters’ tune. Therefore, let x=x1,x2, so the value of x would directly affect the quality of the clustering result. To select the appropriate value of x, the particle swarm optimization algorithm of x is used in this paper for optimization so as to obtain the optimal clustering effect.In particle swarm optimization (PSO), each optimization problem’s solution is regarded as a particle in the search space. The initial population is first generated, and the objective function determines a fitness value. Each particle will travel in solution space, and its velocity will determine its direction and distance. In each iteration, the particle updates itself by tracking two “extremes”: the one found by the particle itself, known as the individual best (pbest), and the one so far found by the entire population, known as the global best (gbest).In the particle swarm algorithm, particle velocity and position updating formulas are, respectively,(16)vnk+1=ωvnk+c1r1pnk−xnk+c2r2g−xnk,xnk+1=xnk+vnk+1,where vnk=vn,1k,vn,2k,vn,3k,…,vn,mk is the particle velocity of the particle n in the iteration k, ω is the inertia weight, pnk is the best position of the particle n in the first k iteration, g is the best position in the iteration population k, c1,c2 are the acceleration constants, and r1,r2 are the random numbers between 0 and 1.In this paper, the particle swarm optimization algorithm is used to find the optimal value of particles, to obtain the optimal fitness value, namely, the optimal clustering effect. PSO algorithm retains the global search strategy based on population and adopts the speed-displacement model, which is easy to operate and can find the optimal solution in fewer iterations.


## 3.3. Mixed Fuzzy Clustering

With the continuous development and progress of the data information age, traditional FCM clustering technology can no longer meet people’s demand for data processing. In this section, we present a hybrid technique that takes advantage of the FCM and FCMdd techniques.In this method, for the data sequence ofn×m, the FCMdd method firstly clusters the data into rr≥c classes, where c is the number of final clustering, and then obtains the cluster center Vr×1 and partition matrix Ur×n with r rows and n columns. In fact, the FCMdd technique is used here to transform the data, and usually r≤n, the transformed dataset is located in a smaller search space, and Ur×n is treated as a new dataset with r features and n objects. In the next step of this algorithm, the new weighted distance proposed in this paper is used as the distance function in the FCM algorithm to cluster the dataset U into class c, so as to obtain the final membership matrix U0 and clustering center V0, and analyze the clustering results to complete the clustering analysis of multiple sequences.To quantify the clustering methods in cluster analysis, precision is considered as an appropriate evaluation standard. In this paper, the method in Izakian et al. [10] is adopted to determine the clustering accuracy, and the calculation formula of the accuracy is(17)P=∑j=1kCjN×maxi=1,2,…,cpKi,Cj,pKi,Cj=Ki∩CjCj,where c is the number of clustering clusters, k is the number of known classes, N is the number of dataset sequences, Ki is the data sequence belonging to class I (known sequences), Cj is the data sequence belonging to class j, and ⋅ represents the number of elements in the set. To sum up, the overall scheme of the hybrid fuzzy clustering method proposed in this paper is as follows:Step 1. For the sequence to be clustered, we determine the initial clustering center based on the grey relational degree, divide the data into rc≤r≤n classes by FCMdd algorithm and DTW distance, determine the membership matrix and clustering center, and then transform the dataset into a smaller search space.Step 2. The FCMdd algorithm needs to determine the membership degree matrix clustering as a new dataset for the secondary clustering by the FCM algorithm. It requires the presented weighted distance as the FCM algorithm’s function through the weight of the particle swarm optimization algorithm to optimize the weighted distance. It obtains the final membership degree matrix and cluster centers. The optimal weight is obtained as the best clustering accuracy.Figure1 shows the flow chart of the above process.Figure 1
Flow chart of the fuzzy clustering method.


## 4. Experimental Analysis

To evaluate the performance of the algorithm, datasets from the UCI machine learning database are used in this paper for experiments. Datasets with different numbers, different sequence lengths, and categories were selected for the experiment. Table1 shows each experimental dataset’s overall characteristic distribution information, including the dimension and number of data samples in each dataset, the number of clusters, and other indicators.Table 1
The summary of the characteristics of the datasets.
DatasetSample sizeDimensionCategoriesSonyAIBORobotSurface621702SonyAIBORobotSurfaceII980652OliveOil605704CBF9301283ECG200200962Synthetic600606Lighting21216372Yoga33004262Beef604705Gisette1350050002Arcene900100002The main parameter settings of the algorithm are listed as follows:(1)
In particle swarm optimization, the acceleration constantsc1,c2 are both 1.5(2)
The initial inertia weightω is 1(3)
The population size is 10In both the FCM and the FCMdd algorithms, the fuzzy coefficientm is set as 2, the iteration termination condition is Piter+1−Piter<1.0e−5, and the maximum iteration number is set as 100. For hybrid technology, the number of clusters considered in the first step of the algorithm may substantially impact the performance of the algorithm. The optimal value of this parameter is determined by the internal structure of the clustered dataset. To simplify the calculation, take r=n (n is the number of datasets to be clustered).To eliminate the contingency of the experimental results and improve the accuracy of the results, this paper conducted 10 experiments for each dataset, and the final result was the average value of the data recorded in the 10 experiments.Table2 shows the comparison between the clustering accuracy obtained by using the Euclidean distance only (with weights), DTW distance only, SPDTW distance only, and the accuracy obtained by using the weighted distance proposed in this paper. Besides, the comparison results of clustering accuracy in the existing literature are also given. We see that the clustering method described in this paper determined by weighted distance has higher clustering accuracy and better clustering effect.Table 2
Comparison of clustering results.
DatasetWEDDTWSPDTWLiteratureNewdistSonyAIBORobotSurface0.60550.94520.96620.5620 [13]0.9452SonyAIBORobotSurfaceII0.61680.61730.61730.6320 [13]0.8071OliveOil0.53130.68330.51670.7764 [15]0.8833CBF0.33680.33330.35430.5810 [14]0.6441ECG2000.67500.69500.67000.5952 [15]0.7850Synthetic0.21720.25000.20940.6670 [13]0.7117Lighting20.61160.61160.60330.4993 [15]0.6033Yoga0.53660.53670.53640.5100 [16]0.5433Beef0.37500.46920.48330.3170 [13]0.5000Gisette0.33220.34010.3918∗0.4392Arcene0.40210.48810.4701∗0.5801Luczak [16] adopts the double-layer fuzzy clustering method and uses the weighted distance of DTW and differential form DTW as distance measurement to cluster the data. Huang et al. [17] developed a new objective function based on the k-means algorithm to cluster time series data by extracting the hidden smooth subspace. In Yu et al. [18], based on the best U-Shapelet method, combined with I index evaluation and multiple top-k query technology, the subsequence of the best dataset, namely, the U-Shapelets set, was selected, and the distance between each U-Shapelet in the U-Shapelets set and all sequences in the dataset was calculated to form the distance matrix Dist. The traditional K-MESNS clustering method is used to cluster the distance matrix to obtain the final clustering result. Ferreira and Zhao [19] establish a network in which each sequence is represented by a vertex and each vertex is connected to the most similar vertex by DTW. A hierarchical clustering is proposed, which uses DTW based functions to measure the similarity between clusters and iteratively calculates the most similar clustering.Table3 shows the weighted distance obtained when different data cluster classes have the highest accuracy, namely, the optimal weight. It can be seen from the table that different datasets have different degrees of dependence on different distances. Some datasets are more dependent on a certain distance, such as the Yoga dataset, which is more dependent on Euclidean distance. Some datasets are dependent on the three distances to varying degrees. For example, synthetic datasets are subject to similar dependence on the three distances. Combined with the data in Tables 2 and 3, the effectiveness and accuracy of the weighted distance method proposed in Section 3 of this paper are verified through multiple experiments. We believe that the weighted distance method proposed in this paper can get better clustering results when dealing with clustering problems of different data.Table 3
The optimal weights.
Datasets weightsSonyAIBORobotSurfaceSonyAIBORoboSurfaceIIOliveOilCBFECG200SyntheticLighting2YogaBeefGisetteArceneX10.2830.3670.3440.4070.0630.4600.3720.0730.4980.3770.405X20.1350.3320.1750.4530.1500.3100.1960.0120.0390.0260.031Figure2 shows the cluster center scatter diagram determined after secondary clustering of CBF, ECG200, OliveOil, and Yoga. Points with different colors in the figure represent clustering centers of different categories, where the x-coordinate represents the feature n of the dataset, and the y-coordinate represents the value corresponding to its feature. It can be seen from the figure that the determined cluster centers are of great difference and produce good clustering results. Therefore, the cluster center selection method based on the combination of maximum density and grey relational degree proposed in this paper has a good effect.Figure 2
The trend of the clustering center. (a) CBF. (b) ECG200. (c) Olive oil. (d) Yoga.
(a)(b)(c)(d)To further verify the feasibility of the clustering algorithm in this paper, cluster analysis was carried out for the MUSIC INTO EMOTIONS problem, the MUSIC INTO EMOTIONS standard dataset [20]. Experiments are conducted on 593 songs with 6 clusters of music emotions based on the Tellegen-Watson-Clark model (six classes: Classical, Reggae, Rock, Pop, Hip-Hop, Techno, and Jazz).Results of the MUSIC INTO EMOTIONS problem are presented in Table4, where the clustering of the FCM is using a classical fuzzy clustering algorithm to get the clustering accuracy, Hybrid-ED, Hybrid DTW, and Hybrid SPDTW, respectively, the Euclidean distance, and DTW distance, and only SPDTW distance is applied to present the FCMdd and FCM clustering technology in precision, using the proposed Hybrid-Newdist weighted distance metrics as Hybrid clustering technology to measure the distance of the results obtained.Table 4
Comparison of MUSIC into EMOTIONS data accuracy.
FCM0.8112Hybrid-ED0.6523Hybrid-DTW0.7051Hybrid-SPDTW0.6774Hybrid-newdist0.9027As can be seen from the comparison results in Table4, the hybrid fuzzy clustering technique based on weighted distance proposed in this paper also achieves good results when dealing with practical problems, thus verifying the effectiveness of the algorithm.To enhance the advantages of our proposed model, another real data YEAST is applied [21], which is a mixed distributed dataset. The Yeast dataset is formed by microarray expression data and phylogenetic profiles with 1500 genes in the learning set and 917 in the test set. The input dimension is 103. Each gene is associated with a set of functional classes whose maximum size can be potentially more than 190. The same experiments are repeated, and the results are listed in Table 5, which provides another convincing support for our model. Hybrid-Newdist provides significantly better results than other traditional algorithms.Table 5
Comparison of YEAST data accuracy.
FCM0.9044Hybrid-ED0.8791Hybrid-DTW0.8827Hybrid-SPDTW0.8518Hybrid-newdist0.9360


## 5. Conclusion and Discussion

Based on the research content and numerical analysis in this paper, the conclusions are as follows:(1)
The initial clustering center determined by the method based on the principle of maximum density and the grey relational degree proposed in this paper can reduce the dependence of the algorithm on the initial center point and avoid falling into the problem of an optimal local solution.(2)
In this paper, double-layer fuzzy clustering is adopted to realize data transformation, which improves the algorithm’s running speed to a certain extent.(3)
The weighted distance measurement proposed in this paper combines the advantages of Euclidean distance, DTW distance, and SPDTW distance. We use particle swarm optimization to improve clustering accuracy and make the clustering results more accurate.(4)
Through numerical experiments on the part of UCR datasets, the clustering accuracy obtained is improved to different degrees than the existing literature.By analyzing the data of the two real problems, the comparison results show that the clustering accuracy of the algorithm proposed in this paper is almost 7.1% higher than that of the classical FCM algorithm, which indicates that the algorithm proposed in this paper can also achieve a better clustering effect when dealing with practical problems.The most significant limitation of our study is that the multiclass problem cannot be solved well. We see that all the binary-class datasets obtain convincing results with our proposed algorithms from the numeric research. However, the multiclass datasets perform poorly. In the future, a further study on the multiclass datasets is needed. Also, the computational complexity of our proposed algorithm is larger than the traditional ones. It needs longer computational time and requires us to run a more complex programming code. A more efficient algorithm is another goal of our future research.



---

*Source: 6687202-2021-03-08.xml*