A comparative analysis of granular computing clustering from the view of set

2.1 Related work and motivation

Due to the vast and rapid increase in data, data mining has become an increasingly important tool for the purpose of knowledge discovery in order to prevent the presence of rich data but poor knowledge. Data mining tasks can be undertaken in two ways, namely, manual walkthrough of data and use of machine learning approaches [9]. The purpose of machine learning is to find the clustering results corresponding to the manual walkthrough.

As a clustering method, GrC has been proposed and studied in many fields, including machine learning and data analysis [10–15].

Witold Pedrycz proposes a new concept of granular rule-based models whose rules assume a format, such as if G (A _i ) then G (f _i ), where G (.) s are granular generalizations of the numeric conditions and conclusions of the rules [10]. Granular computing with multiple granular layers is proposed as an emerging computing paradigm of information processing, which simulates the multi-granular intelligent thinking model of human brain [11]. Witold Pedrycz and his colleague elaborated on the fundamental hierarchically organized layers of processing supporting the development and interpretation of granular time series [12].

A framework is proposed for studying a particular class of set-theoretic approaches to granular computing. A granule is a subset of a universal set, a granular structure is a family of subsets of the universal set, and relationship between granules is given by the standard set-inclusion relation [13]. Vassilis G. Kaburlasos and his colleague analyzed the representation method of granule, the inclusion measure between two granules, and the operations between two granules from set theory and lattice computing [14]. They proposed an effective synergy of the Intervals’ Number k-nearest neighbor (INknn) classifier, that is a granular extension of the conventional knn classifier in the metric lattice of Intervals’ Numbers (INs), with the gravitational search algorithm (GSA) for stochastic search and optimization. Their proposed techniques are demonstrated, comparatively, by computer simulation experiments regarding an industrial dispensing application and the benchmark classification datasets [15, 16].

Inspired by people’s cognitive structure, we analyze the granular clustering algorithm based on distance from the view of set, and the granule is represented as the subset for the training set S. The operation and distance between two granules are formed to design GrCC.

In general, for two subsets of training set S, distance between two non-empty sets is the minimum of the distances between any two elements belonging two different subsets, i.e. d ( A , B ) = min x ∈ A , y ∈ B d ( x , y )(1) where d (x,  y) is Euclidean distance between two points and has the properties, such as nonnegativity, symmetry, and triangular inequality. For aforementioned distance formula (1), it is suitable that intersection of set A and set B is empty set. In Fig. 1, sets A = {x₁,  x₂,  x₃,  x₄,  x₅} and B = {y₁,  y₂,  y₃,  y₄,  y₅ y₆} are denoted by ball A and B. In Fig. 1(a) distance between A and B is the distance between point x₅ and y₆, obviously, d (A,  B) is greater than 0. In Fig. 1(b), distance between set A and B also is the distance between x₅ and y₆. If the distance between x₅ and y₆ in Fig. 1(a) is equal to the distance between x₅ and y₆ in Fig. 1(b), the distance d (A,  B) in Fig. 1(a) is equal to the distance d (A,  B) in Fig. 1(b). Obviously, the distance d (A,  B) in Fig. 1(b) is less than Fig. 1(a), but d (A,  B) in Fig. 1(b) is equal to Fig. 1(b) according to the distance formula (1). The above distance formula (1) does not reflect the real distance between two sets, and we define the distance between two sets, where sets are represented as the form of hyperdiamond, hypersphere, and hypercube. Granular computing clustering is formed based the defined distance measure.

Considering the limitation of Euclidean distance between two subsets, we propose the granular computing clustering based on the novel distance which violates the properties of non-negativity, symmetry, and triangular inequality from the view of set. We analyze the proposed GrCC from Global Consistency Error (GCE), Normal Variation of Information (NVI), and Rand Index (RI).

In reality, the subset of data set S is regarded as a granule which has an irregular shape. In order to study granular computing, the granule is represented as regular shape, such as hyperdiamond, hypersphere, hypercube in N-dimensional space. These three shape granules can be represented as the following normal form.

Where C is the center of granule, r is the radius of granule which is generally induced by the distance between two points in N-dimensional space. Different distance form means the different shape of granule. Granularity is the size of granule, such as the radius of granule.

In Fig. 2, the normal form granule G = (0.1,  0.2,  0.5) is hyperdiamond granule shown in Fig. 2(a) in R² space, whose center is (0.1, 0.2) and granularity is 0.5 induced by the L₁-norm distance. G = (0.1,  0.2,  0.5) is hypershpere granule shown in Fig. 2(b) with center (0.1, 0.2) and granularity 0.5 induced by L₂-norm distance. G = (0.1,  0.2,  0.5) is hypercube granule shown in Fig. 2(c) with center (0.1, 0.2) and granularity 0.5 induced by L_∞-norm. From the Fig. 2, we can see different granules have different shapes even if they have the same forms of representations, such hyperdiamond granules, hypersphere granules, and hypercube granules in N-dimensional space.

2.3 Distance measure between granules

The distance between granules refers to the minimal distance between two points which belong to different granules.

For two hyperdiamond granules G₁ = (C₁,  r₁) and G₁ = (C₂,  r₂), the distance between two granules is defined as follows. d ( G 1 , G 2 ) = ∥ C 1 - C 2 ∥ 1 - r 1 - r 2(2) where C₁ and C₂ are two vectors which represent the centers of hyperdiamond granules G₁ and G₂, r₁ and r₂ are granularities of hyperdiamond granules G₁ and G₂. The distance between C₁ and C₂ is defined as the following L₁-norm. ∥ C 1 - C 2 ∥ 1 = | x 1 - y 1 | + | x 2 - y 2 | + … + | x N - y N |

For two hypersphere granule G₁ = (C₁,  r₁) and G₂ = (C₂,  r₂), the distance between two hypersphere granules is defined as follows. d ( G 1 , G 2 ) = ∥ C 1 - C 2 ∥ 2 - r 1 - r 2(3) where C₁ and C₂ are two vectors which represent the centers of hypersphere granules G₁ and G₂, r₁ and r₂ are granularities of hypersphere granules G₁ and G₂. The distance between C₁ and C₂ is defined as the following L₂-norm. ∥ C 1 - C 2 ∥ 2 = ( x 1 - y 1 ) 2 + ( x 2 - y 2 ) 2 + … + ( x N - y N ) 2

For hypercube granules G₁ = (C₁,  r₁) and G₁ = (C₂,  r₂), the distance between two hypercube granules is defined as follows. d ( G 1 , G 2 ) = ∥ C 1 - C 2 ∥ ∞ - r 1 - r 2(4)

Where C₁ and C₂ are two vectors which represent the centers of hypercube granules G₁ and G₂, r₁ and r₂ are granularities of hypercube granules G₁ and G₂. The distance between C₁ and C₂ is defined as the following L_∞-norm. ∥ C 1 - C 2 ∥ ∞ = max { | x 1 - y 1 | , | x 2 - y 2 | , … , | x N - y N | }

According to the distance between two granules mentioned above, the distance between two granules is the arbitrary real number. There is margin between two granules when d > 0, there is an only common point between two granules when d = 0, and there is an overlap between two granules when d < 0. When d > 0, the greater d means the greater margin between two granules, and when d < 0, the greater d means the smaller overlap. Figure 3 shows the distance between two granules, including d < 0, d = 0, and d < 0.

The operations between two granules reflect the transformation between macroscopic and microcosmic of human cognitions. When a person want to observe the object more carefully, the object is partitioned into some suitable sub-objects, namely the universe is transformed into some parts in order to study the object in detail in the view of microscopic. Conversely, there is the same attributes of some objects, we regard the objects as a universe to simple the process in the view of macroscopic. The operations between two granules are designed to realize the transformation between macroscopic and microscopic. Set-based models of granular structures are special cases of lattice-based models, where the lattice join operation ∨ coincides with set union operation ∪ and lattice meet operation ∧ coincides with set intersection operation ∩.

Join operation ∨ and meet operation ∧ are used to realize the transformation between macroscopic and microcosmic. Operation ∨ unites the granules with small granularities to the granules with the large granularities. Inversely, Operation ∧ divides the granules with large granularities into the granules with small granularities. Join operation ∨ is designed as follows.

Any points are regarded as atomic granules which are indivisible, the join process is the key to obtain the larger granules compared with atomic granules. Likewise, the whole space is a granule with the maximal granularity, the meet process produces the smaller granules compared with original granules.

For two hyperdiamond granules G₁ = (C₁,  R₁) and G₁ = (C₂,  R₂) in the N-dimensional space, the join hyperdiamond granule is G = G 1 ∨ G 2 = ( C , R )

The center C and the granularity R of G are computed as follows.

Firstly, the vector from C₁ to C₂ and vector from C₂ to C₁ are computed.

If C₁ = C₂, then C₁₂ = 0 and C₂₁ = 0.

If C₁ ≠ C₂, then C₁₂ = (C₂ - C₁)/d (C₁ - C₂) and C₂₁ = (C₁ - C₂)/d (C₂ - C₁).

Secondly, the crosspoints of G and G₁ are P₁ = C₁ - C₁₂R₁ and P₂ = C₁ + C₁₂R₁. The crosspoints of G and G₂ are Q₁ = C₂ - R₂C₂₁ and Q₂ = C₂ + R₂C₂₁.

Thirdly, the center C and granularity R of the join hyperdiamond granule G are computed by the centers and granularities of G₁ and G₂, and Algorithm 1 is designed to realise the computing process, in which the distance is computed by the formula (2). In algorithm 1, if we design the hypersphere granular computing, the distance is computed by the formula (3), if we design the hypercube granular computing, the distance is computed by the formula (4).

Figure 4 shows the join process between the hyperdiamond granule G₁ = [0.2 0.15 0.1] and the hyperdiamond granule G₂ = [0.1 0.2 0.1]. The crosspoints of hyperdiamond granule G₁ and the line crossing vector C₁₂ = [-0.6667, 0.3333] are P₁ = [0.2667,  0.1167] and P₂ = [0.1333,  0.1833]. The crosspoints of hyperdiamond granule G₂ and the line crossing vector C₂₁ = [0.333  - 0.6667] are Q₁ = [0.0333,  0.23333] and Q₂ = [0.1667,  0.1667]. According to algorithm1, the central vector and granularity of the join hyperdiamond granule G are C = [0.15,  0.175] and R = 0.175, namely G = [0.15 0.175 0.175].

4.1 Global consistency error

D. Martin proposed several error measures to quantify the consistency between partitions of the same set [17, 18]. Let π and π′ be two partitions of data set S = {x₁,  x₂, …,  x _n } consisting of n objects with N features. For a given datum x _i , consider the classes that contain x _i in π and π′, C (π,  x _i ) and C (π′,  x _i ) are denoted as the subsets contain x _i in π and π′, respectively. Local Refinement Error (LRE) is then defined at point x _i as: LRE ( π , π ′ , x i ) = | C ( π , x i ) - C ( π ′ , x i ) | / | C ( π , x i ) | where C (π,  x _i ) - C (π′,  x _i ) denotes the set differencing operat or between sets C (π,  x _i ) and C (π′,  x _i ). This error measure is not symmetric and encodes a measure of refinement in one direction only. There are two natural ways to combine the LRE at each point into a measure for the entire data set. Global Consistency Error (GCE) forces all local refinements to be in the same direction and is defined as: GCE ( π , π ′ ) = min { LRE ( π , π ′ , x 1 ) + … + LRE ( π , π ′ , x n ) , LRE ( π ′ , π , x 1 ) + … + LRE ( π ′ , π , x n ) } / n

Property 1. For all S _i  ∈ π, there is an only S j ′ ⊆ π ′ satisfying S i ⊆ S j ′, then GCE (π,  π′) =0.

Proof. For all x ∈ S, there is an only subset S _i of S in π satisfying x ∈ S _i , S _i  ∈ π, there is an only S j ′ ∈ π ′, S _i  ⊆ S _j , namely C (π,  x) - C (π′,  x) =∅. So GCE (π,  π′) =0.

4.2 Normalized variation of information

Work in [19] computes a measure of information content in each of the partitions. The proposed measure, termed the Variation of Information (VI), is a metric and is related to the conditional entropies between the class label distribution of the partitions. The VI is computed by the following steps.

Firstly, computing the entropies En (π) and En (π′) associated with partitions π and π′.

For π = {S₁,  S₂, …,  S _S }

En (π) = - (P (1) log ₁₀P (1) + … + P (s) log ₁₀P (s))

where P (i) = |S _i |/n, and for π ′ = { S 1 ′ , S 2 ′ , … , S t ′ }

En (π′) = - (P′ (1) log ₁₀P′ (1) + … + P′ (t) log ₁₀P′ (t))

Where P ′ ( i ) = | S i ′ | / n, log ₁₀0 = 0.

Secondly, computing the mutual information between π and π′ I ( π , π ′ ) = ∑ i = 1 s ∑ j = 1 t P ( i , j ) log 10 P ( i , j ) P ( i ) P ′ ( j )

Thirdly, computing the VI VI ( π , π ′ ) = En ( π ) + En ( π ′ ) - 2 I ( π , π ′ )

The VI can be normalized by the following formula [20]. NVI ( π , π ′ ) = VI / log 10 ( s )

Property 2. If π = π′, then NVI (π,  π′) =0.

Proof. If π = π′, then En (π) = En (π′), S i = S i ′,s = t.

For i ≠ j, S i ∩ S j ′ = S i ∩ S j = ∅, P (i, j) =0.

For i = j, S i ∩ S j ′ = S i ∩ S j = S i = S j, P (i) = P (j) ,  P (i, j) = P (i). I ( π , π ′ ) = ∑ i = 1 s ∑ j = 1 t P ( i , j ) log 10 P ( i , j ) P ( i ) P ′ ( j ) = ∑ j = 1 t P ( j ) log 2 1 P ( j ) = - ∑ j = 1 t P ( j ) log 2 P ( j ) = En ( π ′ )

So VI (π,  π′) =0, and NVI (π,  π′) =0.

4.3 Rand index

Rand Index (RI) was motivated by standard classification problems in which the result of a classification scheme has to be compared to a correct classification [21]. The most common performance measure for this problem calculates the fraction of correctly classified (respectively misclassified) elements to all elements. For RI, comparing two clusters is just a natural extension of this problem which has a corresponding extension of the performance measure, instead of counting single elements, The correct classified pairs are counted. Thus, RI is defined by RI ( π , π ′ ) = 2 ( n 11 + n 00 ) / ( n ( n - 1 ) ) where n₁₁ denotes the numbers of pairs that are in the same cluster under π and π′, n₀₀ denotes the number of pairs that are in different clusters under π and π′. RI depends on both the number of clusters and the number of elements, and ranges from 0 to 1. Obviously, we have the following property for RI.

Property 3. If π = π′, then RI (π,  π′) =1.