# A Three-step Method for Three-way Clustering by Similarity-based Sample’s Stability

Authors: Jin Zhu; Dongqin Jiang; Pingxin Wang
Journal: Mathematical Problems in Engineering
 (2022)

---

## Abstract

Clustering is an important research field in machine learning. Traditional clustering approaches are not very effective in dealing with clusters having overlapping regions. To better capture the three types of relationships between a cluster and a sample, namely, belong-to fully, belong-to partially and not belong-to fully, we propose a theory of similarity-based sample’s stability and develop a three-step method for three-way clustering by integrating similarity-based sample’s stability into the idea of three-way clustering in this paper. In the proposed theory, the similarity of two samples is used to define the frequencies of two samples and the samples stability is calculated based on the defined frequencies and determinacy function. With this stability, the universe is divided into stable set and unstable set. The samples in the stable set are assigned into the core region of each cluster by using traditional clustering algorithm. The samples in the unstable set are assigned into the fringe region of corresponding cluster according to distances between the elements and the centers of the cluster core regions. Therefore, a three-way clustering is naturally formed. Experimental results on datasets show that this method can improve the structure of the clustering results.


---

## Body

## 1. Introduction

Data clustering is one of the most fundamental topics for data exploration in machine learning and plays has an important role in many fields such as information granulation, image analysis, network structure analysis and others [1–4]. The purpose of clustering is to discover the underlying structure of a data set by organizing the samples in the data set into several clusters such that the objects within a cluster are highly similar but remarkably dissimilar with objects in other clusters [5]. many researchers have done a series of research on clustering problem in the past decades and various kinds of clustering algorithms have been developed in the literature, including partitional, hierarchical, density-based and grid-based clustering and so on. A comprehensive review of clustering algorithms can be found in [6].According to the relation between the samples and the clusters, the existing algorithms for clustering can be divided into two categories: hard clustering and soft clustering. Hard clustering methods, such as k-means [7], spectral clustering [8], represent a cluster by a set with a crisp boundary, where the objects in the set belong to this cluster definitely and the objects not in the set do not belong to this cluster definitely. Only two relations between the samples and the clusters are considered in the process of clustering, i.e, belong-to and not belong to. We use an example V with 6 samples to illustrate this phenomenon in Figure 1. The samples in data set V are grouped into disjoint cluster C1 and cluster C2. C1 divides the universe into two sets, i.e., the set inside C1 and the set outside C1. The samples inside C1 belong to the cluster and the samples outside C1 do not belong to the cluster. The same is true about C2.Figure 1
An example of hard clustering results.Hard clustering methods ignore the possibility that a sample can belong to more than one cluster and lead to some exhaustive and exclusive clusters representing the data. Although the requirement that each cluster must be represented by a set with clear boundary leads to easy analytical results, assigning uncertain elements into a cluster may increase decision risk. In order to relax the constraint, many soft clustering methods were proposed for different application backgrounds [9–12]. As one of the effective tools to deal with uncertainty, three-way decision [13] trisects a universe and represents the uncertainty in the form of non-commitment. The main idea of three-way decision is thinking in threes, which is consistent with human’s cognitions to solve the problem in the real world [14]. Many soft computing models for learning uncertain concepts, such as rough sets [15], fuzzy sets [16] and shadowed sets [17], can be reinvestigated within the framework of three-way decision [14].By incorporating three-way decision with clustering analysis, Yu [18–20] proposes another model of soft clustering, i.e., three-way clustering. Different from the crisp representation of a cluster, three-way clustering uses the core region (Co), the fringe region (Fr), and the trivial region (Tr) to represent a cluster, which Tr can be expressed as the complement of the union of Co and Fr. The samples that belong to the cluster definitely are assigned to the Co and the samples that do not belong to the cluster definitely are assigned to the Tr. For the samples with uncertainty or information insufficient, we assign them into the Fr to give the further decision after obtaining more information. The above process reflects the three types of relationship between an object and a cluster, namely, belong-to definitely, uncertain and not belong-to definitely. Figure 2 shows one possible cluster obtained by three-way clustering method.Figure 2
A demonstration of three-way cluster.Three-way clustering uses the core region and the fringe to represent a cluster. How to develop different strategies to construct the core region and the fringe region has become the key problem of three-way clustering. In recent years, three-way clustering has attracted a lot of research, and many three-way clustering algorithm were obtained [21–27]. Recently, by observing that the samples can change between clusters in different clustering results, Li et al. [28] introduced the concept of sample’s stability based on the co-association frequencies in a clustering ensemble problem and presented a clustering ensemble algorithm based on sample’s stability. Sample’s stability is to quantify the contributions to detection of the clustering structure. The samples with higher stabilities can be used to discover the core region of three-way cluster, while the samples with lower stabilities are assigned into the fringe regions of corresponding clusters. The idea gives a new method for three-way clustering.There are many different methods to define the sample’s stability. In this paper, we develop a new three-way clustering algorithm by similarity-based sample’s stability. In the proposed method, we use the similarity of two samples to define the co-association frequency and compute the sample’s stability based on the defined frequencies. All samples are divided into stable set and unstable set based on sample’s stability. The stable set can be used to find the pre-structure of the universe, which provides instructive information to the assignments of the samples in the unstable set. Concretely, the samples in the stable set are assigned into the core region of each cluster by using traditional clustering algorithm. The samples in the unstable set are assigned into the fringe region of corresponding cluster according to distances between the elements and the centers of the cluster core region. Therefore, a three-way clustering is naturally formed.In comparison with the existing research, the main contributions of our work are as follows:• Base on the similarity of two samples, a new definition of co-association frequencies is proposed and the relation between the sample’s stability is discussed.• A novel three-way clustering algorithm by similarity-based sample’s stability is proposed. The samples with higher stabilities are assigned into the core region of each cluster by k-means and the samples with lower stabilities are assigned into the fringe region of corresponding cluster according to distances between the elements and the centers of the cluster core region.• The similarity-based sample’s stability that is measured by the proposed method is verified by experiments on UCI data sets. Six UCI data sets are used to show the effectiveness of the proposed three-way clustering algorithm.The rest of this paper is organized as follows. In Section2, we review the concept of sample’s stability and propose the theory of similarity-based sample’s stability . A new three-way clustering algorithm by using similarity-based sample’s stability is proposed in Section 3. Section 4 shows experimental results based on a bunch of public standard data sets.


## 2. Similarity-Based Sample’s Stability

Sample’s stability was first introduced by Li et al. [28] based on the co-association frequencies in a clustering ensemble problem. Giving a base clustering results of data set X=x1,x2,…xn , the relationship of any two samples has three cases. The first case is that they are assigned to the same cluster in all clustering results and the second case is that they are assigned to different clusters in all clustering results. The last case is that they are assigned to the same cluster in some clustering results. The frequency of two samples appeared in the same cluster are defined as the co-association frequency of two samples. For the first case and the second case, the co-association frequency of two samples equals 1 and 0, respectively. Regardless of the first case or the second case, the relationship between two samples is certain. For the case 3, the co-association frequency of two samples is in 0,1 and the relationship between them is unstable. Based on the distribution of the co-association frequencies, we can obtain a threshold t to by Otsu algorithm [29] to represent the most unstable frequency.The co-association frequency of two samples describes the probability of assigning into the same cluster. There are different methods to define the co-association frequency of two samples. In this paper, we adopt the similarity in spectral clustering [30] to represent the co-association frequency. As we know, there are three kinds of methods to define the similarity in spectral clustering. Here, we use the following one.(1)pij=0,ifxi∉KNNxjorxj∉KNNxi,exp−d2xi,xj2σ2,ifxi∈KNNxjandxj∈KNNxi,where, KNNxi represents the K nearest neighbor of xi, i.e., KNNxi satisfies,•KNNxi⊂X;•∣KNNxi∣=K;•∀xj∈KNNxi,xk∉KNNxi∣=K, then, distxi,xj≤distxi,xk.Because a higher vale and a lower value of the co-association frequency mean a more stable relation between two samplesxi and xj, we can not use the co-association frequency to represent the stable level directly. We should design a function in 0,1, which have high values at both ends of 0,1 but low value at the most unstable frequency. This kind of function is named as the determinacy function, which is defined as follows:Definition 1.
(Determinacy function) [28]: f is a determinacy function if for arguments p∈0,1 and with a parameter t∈0,1 it satisfies:(1)
Ifp<t,fp<0; ifp>t,f′p>0.(2)
Ifpi<t<pj, andt−pi/pj−t=t/1−t,fpi=fpj.
From the definition, we can find that the determinacy function is monotonically decreasing function whenp<t and monotonically decreasing function when p>t. The function obtains the minimum value on t. Another properties is that the determinacy function is unbiased on both sides of t. From the first condition of Definition 1, we can obtain that for any two point pi and pj are located on the same side of t, the farther possibility point will have a higher determinacy value. From the second condition of Definition 1, we can conclude that for any two point pi and pj are located on the different sides of t, fpi>fpj if pi and pj satisfy pi<t<pj and 1−tt−pi>tpj−t.
From Definition1, there are many different mathematical functions satisfying the conditions of determinacy function. Here, we give two examples as following.(2)flpij=|pij−tt|,pij<t|pij−t1−t|,pij≥t;,(3)fqpij=pij−tt2,pij<tpij−t1−t2,pij≥t.
flpij is called as a linear determinacy function and fqpij is called as a quadratic determinacy function, respectively. In Equation (2) and (3), the threshold t is learned by using Otsu algorithm [29]. The idea of Otsu algorithm is to solve a linear discriminant problem. Suppose D=d1,d2,…,dm is a vector with m elements and D is divided into two groups g0 and g1 as following,(4)g0=di,di<t0,1⩽i⩽m.g1=di,di⩾t0,1⩽i⩽m..
The goal of Ostu algorithm is to search the thresholdt∗ to maximize the following between-class variance σt,(5)σt=w0μ0−μ2+w1μ1−μ2,where(6)w0=g0D,w1=g1D,μ0=∑di∈g0dig0,μ1=∑di∈g1dig1,μ=∑di∈DdiD.
The following Algorithm1 is the process of Otsu [29].
Determinacy function projects the co-association frequency into a relationship stability space. We can use the values of determinacy function to quantify the stability of a sample. Giving a determinacy functionf , we can define the stability of a sample xi as following.Algorithm 1: Otsu
Input: a vector D=d1,d2,…,dmOutput:threshold t∗1.
fort∈0,12.
calculateσt based on Formula (6)3.
end for4.
ti=argmaxσt5.
t∗=tiDefinition 2.
(Sample’s stability) [28]: Suppose f is a determinacy function. The stability of xi,sxi, is calculated by:(7)sxi=1n∑j=1nfpij.
Next, we use an example to address the process of computing sample’s stability. Suppose thatX=x1,x2,x3,x4,x5,x6 is a data set with 6 samples. The distances of xi and xj are listed as Table 1.
In order to compute the co-association frequency by equation (1), we set the size of neighbor K=3 and parameter σ=1. From Table 1, we have KNNx1=x1,x2,x3,KNNx2=x1,x2,x3 and KNNx3=x2,x3,x4. Because x1∈KNNx2 and x2∈KNNx1, we get the co-association frequency p12=e−1/2. Similarly, p13=0 because x1∉KNNx3. Repeating the above process for other samples, we can obtain all the co-association frequencies. All the pairwise frequencies will form a 6×6 matrix as Table 2.
Based on the co-association matrix of, the most unstable frequency can be learnedt=0.4647 by Otsu algorithm. According to the Definition 2, we get the sample’s stabilities of X by using linear determinacy function flpij,(8)sx1=0.8775;sx2=0.7611;sx3=0.7611;sx4=0.7064;sx5=0.7611;sx6=0.8350.Table 1
The sample’s distances ofX
distancex1x2x3x4x5x6x1012345x2101.52.53.54.5x321.5012.53x432.51012x543.52.5101.5x654.5321.50Table 2
The co-association matrix ofX
frequencyx1x2x3x4x5x6x11e−1/20000x2e−1/21e−9/8000x30e−9/81e−1/200x400e−1/21e−1/2e−2x5000e−1/21e−9/8x6000e−2e−9/81


## 3. Three-Step Method for Three-Way Clustering by Similarity-Based Sample’s Stability

According to the discussion in previous section, we can calculate the stability of each sample in a data set. With these stability values, the universe can be divided into two sets through a threshold, i.e., the set with higher stability values and the set with lower stability values. For the samples with higher stability values, they have robust relationships with other samples and can be assigned to certain cluster in the process of clustering. For the samples with lower stability values, they do not have a clear relationships with other samples and assigning them into a certain cluster will increase decision risk.Three-way clustering was proposed by Yu et al. [18–20], which uses the coreregion (Co), the fringe region (Fr), and the trivial region (Tr) to represent a cluster, which Tr can be expressed as the complement of the union of Co and Fr. Since Tr is the complement of the union of Co and Fr, three-way clustering represents a three-way cluster Ci as(9)Ci=CoCi,FrCi.The result of three-way clustering can be represented as(10)ℂ=CoC1,FrC1,CoC2,FrC2,…,CoCk,FrCk,where subsets CoCi,FrCi have the following properties.(11)TrCi∪CoCi∪FrCi=U,∗CoCi∩FrCi=ϕ,∗CoCi∩TrCi=ϕ,∗FrCi∩TrCi=ϕ.Motivated by three-way clustering, this paper presents a new three-way clustering algorithm by similarity-based sample’s stability (3WC-SSS for short). The main idea of 3WC-SSS is dividing the universe into stable set and unstable set according to the similarity-based sample’s stability and handling the samples in stable set and unstable set differently.


### 3.1. Step 1: Dividing the Universe into a Stable Set and an Unstable Set

In the proposed algorithm, the stability of each sample is first computed by using definition of similarity-based sample’s stability in the previous section and the universe is divided into two sets through a threshold, i.e., the set with higher stability values and the set with lower stability values. The group with higher stability is defined as the stable set while the group with lower stability is defined as the unstable set. For the samples in the stable set, they have robust relationships with other samples, which can be assigned into the core region of each cluster by using k-means. After obtaining the core region of each clusterCoC1,CoC2,…,CoCk, the next problem is to assign the samples in the unstable set to the fringe region of each cluster. We compute its local co-association coefficient corresponding to CoC1,CoC2,…,CoCk, respectively, and assign the sample to FrCi according to its local stability. The workflow of the proposed 3WC-SSS algorithm can be depicted by Fig 3.Figure 3
The workflow of 3WC-SSS algorithm.Three-way clustering uses the core region (Co), the fringe region (Fr), and the trivial region (Tr) to represent a cluster. Since Tr can be expressed as the complement of the union of Co and Fr, we can represent a three-way cluster by a pair of the set of core objects and the set of boundary or fringe objects. The representation of three-way clustering by using three regions or, equivalently, a pair of sets to represent a cluster chapters the three types of relationships between an element and a cluster, namely, belong-to definitely, not belong-to definitely, and uncertain. One of the main tasks of three-way clustering is to construct the core region and the fringe region of each cluster. The strategy of 3WC-SSS algorithm is dividing the universe into universe core and universe fringe by using similarity-based sample’s stability and assigning the samples in universe core and the universe fringe to the core region and the fringe region of each cluster, respectively. So, the first step of 3WC-SSS algorithm is to obtain the sample’s stability based on Definition2. Suppose X=x1,…,xn is a data set with n samples. Firstly , we use equation (1) to get co-association frequency pij of xi and xj, where the size K of neighbour is an important parameter. Too large and too small value of K are not appropriate. Too large K will increase the costs of computation and too small K will lead to local problem. In this paper, we set K=n/2k, k is the number of the clusters.In this paper, we use the linear determinacy functionflx to compute the sample’s stability. After we get the co-association matrix, the stabilities of all samples S=sx1,sx2,…,sxn can be obtained by Definition 2. Similarly, taking S=sx1,sx2,…,sxn as an input, we can use Otsu algorithm to obtain a threshold s and the data set X is divided into two crisp sets according to threshold. We name these two groups as the stable set and the unstable set, respectively, which are given by:(12)STX=xi|sxi>s.and(13)USX=xi|sxi≤s.


### 3.2. Step 2: Finding the Core Region of Each Cluster

The samples in the stable set have higher stability, which means that the samples have robust relationships with other samples. Because the samples in the core region belong to the cluster definitely, they should have robust relationships with other samples. So, we assign the the samples of the stable set into the core region of each cluster in our proposed 3WC-SSS. All the hard clustering algorithm can be used to divide the stable set intok clusters. This paper adopts k-means [7] algorithm to realize this result. The main idea of k-means is to randomly select k initial centers, then, cluster the samples k groups according to the shortest distance to the center points, update the centers by means of the data in the cluster until the center no longer changes. K-means algorithm aims at minimizing the following objective function,(14)J=min∑j=1k∑xi∈Cj‖vi−μj‖2,where ‖xi−μj‖ represents the distance between xi and the centre μj of j-th cluster.Based on the above discussions, we get the core region of each cluster by assigning the samples with higher stability into several clusters through k-means. The procedure of obtaining core region of each cluster can be described as Algorithm2.Algorithm 2: Finding the core region of each cluster
Input:X=x1,…,xn, the size of neighbour K, the number of cluster k, parameter σ.Output: the core region of each cluster CoCi,i=1,2…,k;1.
Calculate the co-association matrixMn×n by (1).2.
fori=1 to n3.
Obtainsxi based on Definition 24.
end for5.
S=sx1,sx2,…,sxn6.
s← Algorithm 1S7.
STX=xi|sxi>s8.
Randomly selectk initial group centers μ1,μ2,…,μk∈STX .9.
Assign each samples to the group according to the shortest distance to the centersCoCi=xj|dvj,μi≤dxj,μl,l≠i,j=1,2,…,∣STX∣10.
When all objects have been assigned, update the centers as,μi=1/CoCi∑j∈CoCiVj,i=1,2,…,k.11.
Repeat Steps 9 and 10 until the centers no longer change.12.
ReturnC=CoC1,CoC2,…,CoCk.


### 3.3. Step 3: Finding the Fringe Region of Each Cluster

Another task of 3WC-SSS is to get the fringe region of each cluster. For the samples in the unstable set, it is reasonable to assign them into the fringe region of the corresponding cluster because they do not have a clear relationships with other samples. Since the core regions have been obtained by stable set, the relationship between the samples of unstable set and the discovered core regions can be used to decide the fringe region of each cluster. In this paper, we introduce the definition of local co-association coefficient and use this definition to get the fringe region. The definition of local co-association coefficient is as following.Definition 3.
SupposeX is a date set, X1 is subset of X, pij is the co-association frequency between two samples xi and xj. The local co-association coefficient Alxi between a sample xi and subset X1 is defined as following,(15)Alxi=∑xj∈X1pij.
The local co-association coefficient reflects the affiliation between the sample and the subset. The higher the value, the closer the relationship. It is reasonable to use the local co-association coefficient between the samples in unstable set and the discovered core regions to obtain the fringe region of each cluster. For each samplex∈USV, we calculate the local co-association coefficient Alix between the sample and the core regions CoCi,i=1,2,…,k and search the minimum value of the local co-association coefficient Alix,i=1,2,…,k. In order to reduce the decision risk, we use the following method to get the fringe region of each cluster.
Suppose(16)Alj∗=min1≤i≤kAlix.
and(17)T=j:Aljx−Alj∗≤ε,j≠j∗,where ε is a given parameter.1
IfT≠ϕ, then x∈FrCj and x∈FrCj∗.2
IfT=ϕ, then x∈FrCj∗.Algorithm 3 is the process of finding the fringe region of each cluster.
According to the above strategy, a three-way clustering is naturally formed. Unlike existing algorithms that treat every sample equally in the construction of the underlying structure, 3WC-SSS uses the similarity in spectral clustering to represent the co-association frequency and get the stability of each sample by using the determinacy function. With this stability, the universe is divided into stable set and unstable set. These samples in the stable set represent a clear structure which is easy to be discovered. We use k-means algorithm to obtain the core region of each cluster. The samples in the unstable set are assigned to the fringe region of each cluster by local co-association coefficient corresponding to the discovered core regions. The whole process can be shown as Algorithm4.Algorithm 3: Find the fringe region of each cluster
Input:USV and CoC1,CoC2,…,CoCk, parameter εOutput:FrC1,FrC2,…,FrCk1
for a sample x∈USV.2.
fori=1 to k3.
computeAlix=∑xj∈CoVipij4.
end for5.
Alj∗=min1≤i≤kAlix6.
T=j:Aljx−Alj∗≤ε,j≠j∗7.
if8.
T≠ϕ9.
assignx∈FrCj and x∈FrCj∗10.
else11.
x∈FrCj∗12.
end for13.
ReturnC=FrC1,FrC2,…,FrCkAlgorithm 4: 3WC-SSS algorithm
Input:X=x1,…,xn, the size of neighbour K, the number of cluster k, parameters σ and ε .Output: three-way clustering ℂ=CoC1,FrC1,CoC2,FrC2,…,CoCk,FrCk1.
CoC1,CoC2,…,CoCk← Algorithm 22.
FrC1,FrC2,…,FrCk← Algorithm 33.
Returnℂ=CoC1,FrC1,CoC2,FrC2,…,CoCk,FrCk


## 3.1. Step 1: Dividing the Universe into a Stable Set and an Unstable Set

In the proposed algorithm, the stability of each sample is first computed by using definition of similarity-based sample’s stability in the previous section and the universe is divided into two sets through a threshold, i.e., the set with higher stability values and the set with lower stability values. The group with higher stability is defined as the stable set while the group with lower stability is defined as the unstable set. For the samples in the stable set, they have robust relationships with other samples, which can be assigned into the core region of each cluster by using k-means. After obtaining the core region of each clusterCoC1,CoC2,…,CoCk, the next problem is to assign the samples in the unstable set to the fringe region of each cluster. We compute its local co-association coefficient corresponding to CoC1,CoC2,…,CoCk, respectively, and assign the sample to FrCi according to its local stability. The workflow of the proposed 3WC-SSS algorithm can be depicted by Fig 3.Figure 3
The workflow of 3WC-SSS algorithm.Three-way clustering uses the core region (Co), the fringe region (Fr), and the trivial region (Tr) to represent a cluster. Since Tr can be expressed as the complement of the union of Co and Fr, we can represent a three-way cluster by a pair of the set of core objects and the set of boundary or fringe objects. The representation of three-way clustering by using three regions or, equivalently, a pair of sets to represent a cluster chapters the three types of relationships between an element and a cluster, namely, belong-to definitely, not belong-to definitely, and uncertain. One of the main tasks of three-way clustering is to construct the core region and the fringe region of each cluster. The strategy of 3WC-SSS algorithm is dividing the universe into universe core and universe fringe by using similarity-based sample’s stability and assigning the samples in universe core and the universe fringe to the core region and the fringe region of each cluster, respectively. So, the first step of 3WC-SSS algorithm is to obtain the sample’s stability based on Definition2. Suppose X=x1,…,xn is a data set with n samples. Firstly , we use equation (1) to get co-association frequency pij of xi and xj, where the size K of neighbour is an important parameter. Too large and too small value of K are not appropriate. Too large K will increase the costs of computation and too small K will lead to local problem. In this paper, we set K=n/2k, k is the number of the clusters.In this paper, we use the linear determinacy functionflx to compute the sample’s stability. After we get the co-association matrix, the stabilities of all samples S=sx1,sx2,…,sxn can be obtained by Definition 2. Similarly, taking S=sx1,sx2,…,sxn as an input, we can use Otsu algorithm to obtain a threshold s and the data set X is divided into two crisp sets according to threshold. We name these two groups as the stable set and the unstable set, respectively, which are given by:(12)STX=xi|sxi>s.and(13)USX=xi|sxi≤s.


## 3.2. Step 2: Finding the Core Region of Each Cluster

The samples in the stable set have higher stability, which means that the samples have robust relationships with other samples. Because the samples in the core region belong to the cluster definitely, they should have robust relationships with other samples. So, we assign the the samples of the stable set into the core region of each cluster in our proposed 3WC-SSS. All the hard clustering algorithm can be used to divide the stable set intok clusters. This paper adopts k-means [7] algorithm to realize this result. The main idea of k-means is to randomly select k initial centers, then, cluster the samples k groups according to the shortest distance to the center points, update the centers by means of the data in the cluster until the center no longer changes. K-means algorithm aims at minimizing the following objective function,(14)J=min∑j=1k∑xi∈Cj‖vi−μj‖2,where ‖xi−μj‖ represents the distance between xi and the centre μj of j-th cluster.Based on the above discussions, we get the core region of each cluster by assigning the samples with higher stability into several clusters through k-means. The procedure of obtaining core region of each cluster can be described as Algorithm2.Algorithm 2: Finding the core region of each cluster
Input:X=x1,…,xn, the size of neighbour K, the number of cluster k, parameter σ.Output: the core region of each cluster CoCi,i=1,2…,k;1.
Calculate the co-association matrixMn×n by (1).2.
fori=1 to n3.
Obtainsxi based on Definition 24.
end for5.
S=sx1,sx2,…,sxn6.
s← Algorithm 1S7.
STX=xi|sxi>s8.
Randomly selectk initial group centers μ1,μ2,…,μk∈STX .9.
Assign each samples to the group according to the shortest distance to the centersCoCi=xj|dvj,μi≤dxj,μl,l≠i,j=1,2,…,∣STX∣10.
When all objects have been assigned, update the centers as,μi=1/CoCi∑j∈CoCiVj,i=1,2,…,k.11.
Repeat Steps 9 and 10 until the centers no longer change.12.
ReturnC=CoC1,CoC2,…,CoCk.


## 3.3. Step 3: Finding the Fringe Region of Each Cluster

Another task of 3WC-SSS is to get the fringe region of each cluster. For the samples in the unstable set, it is reasonable to assign them into the fringe region of the corresponding cluster because they do not have a clear relationships with other samples. Since the core regions have been obtained by stable set, the relationship between the samples of unstable set and the discovered core regions can be used to decide the fringe region of each cluster. In this paper, we introduce the definition of local co-association coefficient and use this definition to get the fringe region. The definition of local co-association coefficient is as following.Definition 3.
SupposeX is a date set, X1 is subset of X, pij is the co-association frequency between two samples xi and xj. The local co-association coefficient Alxi between a sample xi and subset X1 is defined as following,(15)Alxi=∑xj∈X1pij.
The local co-association coefficient reflects the affiliation between the sample and the subset. The higher the value, the closer the relationship. It is reasonable to use the local co-association coefficient between the samples in unstable set and the discovered core regions to obtain the fringe region of each cluster. For each samplex∈USV, we calculate the local co-association coefficient Alix between the sample and the core regions CoCi,i=1,2,…,k and search the minimum value of the local co-association coefficient Alix,i=1,2,…,k. In order to reduce the decision risk, we use the following method to get the fringe region of each cluster.
Suppose(16)Alj∗=min1≤i≤kAlix.
and(17)T=j:Aljx−Alj∗≤ε,j≠j∗,where ε is a given parameter.1
IfT≠ϕ, then x∈FrCj and x∈FrCj∗.2
IfT=ϕ, then x∈FrCj∗.Algorithm 3 is the process of finding the fringe region of each cluster.
According to the above strategy, a three-way clustering is naturally formed. Unlike existing algorithms that treat every sample equally in the construction of the underlying structure, 3WC-SSS uses the similarity in spectral clustering to represent the co-association frequency and get the stability of each sample by using the determinacy function. With this stability, the universe is divided into stable set and unstable set. These samples in the stable set represent a clear structure which is easy to be discovered. We use k-means algorithm to obtain the core region of each cluster. The samples in the unstable set are assigned to the fringe region of each cluster by local co-association coefficient corresponding to the discovered core regions. The whole process can be shown as Algorithm4.Algorithm 3: Find the fringe region of each cluster
Input:USV and CoC1,CoC2,…,CoCk, parameter εOutput:FrC1,FrC2,…,FrCk1
for a sample x∈USV.2.
fori=1 to k3.
computeAlix=∑xj∈CoVipij4.
end for5.
Alj∗=min1≤i≤kAlix6.
T=j:Aljx−Alj∗≤ε,j≠j∗7.
if8.
T≠ϕ9.
assignx∈FrCj and x∈FrCj∗10.
else11.
x∈FrCj∗12.
end for13.
ReturnC=FrC1,FrC2,…,FrCkAlgorithm 4: 3WC-SSS algorithm
Input:X=x1,…,xn, the size of neighbour K, the number of cluster k, parameters σ and ε .Output: three-way clustering ℂ=CoC1,FrC1,CoC2,FrC2,…,CoCk,FrCk1.
CoC1,CoC2,…,CoCk← Algorithm 22.
FrC1,FrC2,…,FrCk← Algorithm 33.
Returnℂ=CoC1,FrC1,CoC2,FrC2,…,CoCk,FrCk


## 4. Experimental Results

In order to illustrate the effectiveness of our proposed 3WC-SSS algorithm, Two synthetic datasets and five UCI [31] data sets are employed in this section. The details of these data sets are shown in Table 3 and Table 4, respectively.Table 3
synthetic data sets
Data setsSamplesAttributesClassesA13000220S15000215Table 4
UCI data sets
Data setsSamplesAttributesClassesZoo101187Iris15043Wine178133Dermatology366336Segmentation2310197In this paper, we useACC,FMIARI [32] and AS [33] , four quantitative indices to evaluate the performances of clustering algorithms. The range of the ACC,FMI,AS,ARI is between 0 and 1. The higher value indicates a better clustering result. Because all the above evaluation indices are only adapted to hard clustering algorithm, for fair comparison on clustering results with two kinds of representation, we take core region of each cluster obtained by 3WC-SSS as the single set to compare with other algorithms. For comparing the clustering effect, the performance of 3WC-SSS is compared with the performances of kmeans and FCM [9]. All experiments are repeated 10 times and we adopt the average result for 10 times as the final valid resultsTable 5 in Table 6 this Table 7 paper. Tables 8 show the clustering evaluation on 7 datasets. The best performances for each dataset are highlighted in bold.Table 5
Performances ofACC
Data setskmeansFCM3WC-SSSA10.96560.97110.9772S10.96670.97180.9792Zoo0.88810.91990.9011Iris0.71830.74530.7801Wine0.95500.97890.9719Dermatology0.98990.99660.9991Segmentation0.65630.71340.6915Table 6
Performances ofFMI
Data setskmeansFCM3WC-SSSA10.92140.93210.9453S10.93330.95140.9605Zoo0.82210.85510.8556Iris0.81850.84560.8819Wine0.92530.93880.9435Dermatology0.88910.89210.9015Segmentation0.58640.63720.6589Table 7
Performances ofARI
Data setskmeansFCM3WC-SSSA10.91110.91230.9425S10.94370.94880.9577Zoo0.80000.81010.8127Iris0.81450.82220.8238Wine0.90050.91160.9149Dermatology0.84450.85630.8682Segmentation0.56680.58880.6006Table 8
Performances ofAS
Data setskmeansFCM3WC-SSSA10.81230.82240.8328S10.86670.86740.8677Zoo0.74420.75010.7663Iris0.68910.71320.7405Wine0.47630.50110.5121Dermatology0.51130.56120.5655Segmentation0.45890.51800.5421Following experimental performances in Tables6-8, it is not difficult to find that our proposed 3TW-SSS achieves the highest results of FMI,ARI,AS on all 7 datasets. The results show that the samples in core regions can improve the structure of the clustering results. This is because the samples in the core regions have higher stabilities than the samples in the fringe regions and we do not consider the samples in the fringe regions for computing FMI,ARI,AS.Through observing Tables5, we can find the performances of ACC that achieved by 3TW-SSS is a little lower than the results of other algorithm on some datesets. Such result indicates that though the samples in the core regions have higher stabilities, the results of accuracy may not be better because the denominator n become smaller when we compute ACC by deleting the samples in the fringe regions.According to the experimental performances, we can find the samples with higher stabilities can provide more instructive information for detecting the pre-structure of data set and our proposed method for finding the core region is effective.


## 5. Concluding Remarks

In this paper, we develop a new three-way clustering algorithm, namely, 3W-SSS, by integrating similarity-based sample’s stability into the idea of three-way clustering. In the proposed theory, the similarity of two samples is used to define the frequencies of two samples and the samples stability is calculated based on the defined frequencies and determinacy function. With this stability, the universe is divided into stable set and unstable set. The samples in the stable set are assigned into the core region of each cluster by using traditional clustering algorithm. The samples in the unstable set are assigned into the fringe region of corresponding cluster according to distances between the elements and the center of the cluster core regions. One contribution of 3W-SSS is that this algorithm can discovers a structure based on stable samples and then gradually assigns unstable samples to the pre-discovered structure. The experimental results on several datasets show that 3TW-SSS can significantly improve the structure of clustering results. The following problems may deserve further investigation.1
For the sake of simplicity, the number of clustersk is known in this paper. However, how to choose k and determine the number of clusters can be researched\enleadertwodots2
Some other strategies for co-association frequency and determinacy function can be considered.



---

*Source: 6555501-2022-02-27.xml*