Distributed proximity-based granular clustering: towards a development of global structural relationships in data

Clustering is about revealing a structure in a single data set. Distributed clustering is concerned with the same problem present in situations where there is a family of data sets for which clustering is carried out separately. The term distributed clustering is quite often encountered in the literature. Furthermore, this type of clustering quite often comes with a remarkable variety of terminology, methods, evaluation measures, extensions (Corsini et al. 2005; Pedrycz and Rai 2008; Pedrycz 2005) and applications (Coppi et al. 2010; Graves et al. 2012; Peters 2011). The results of clustering are conveniently interpreted as information granules in the sequel benefiting from a wealth of conceptual developments of Granular Computing (Apolloni et al. 2006; Pedrycz 2013, 2007). Likewise the distributed nature of the data may imply cases when objects (patterns) are described in different feature spaces or all data sets are in the same feature space (Mali and Mitra 2003; Pedrycz and Rai 2008). There are also combinations of these two alternatives (Pedrycz and Rai 2008).

There are two essential aspects that have to be raised with regard to distributed clustering:In this study, we are concerned with a category of objective function-based clustering in which the results of clustering come in the form of partition matrices and prototypes (or other numeric representatives). K-Means and Fuzzy C-Means (FCM) (Bezdek 1981) are highly visible alternatives of the clustering methods falling under this category. To facilitate a sound comparison of local structures, one has to look at them from a more general and abstract point of view than the one being conveyed by partition matrices. Proximity matrices (Bezdek 1981; Pedrycz 2005) come here as a viable alternative as they are abstracted from the number of clusters. Their dimensionality is N\(\times \)N meaning that all locally formed proximity matrices can be compared (matched) as their dimensionality does not depend explicitly upon the number of clusters. The usage of proximity matrices in clustering problems has been reported in so-called proximity-based clustering, see (Graves et al. 2012; Pedrycz et al. 2004; Pedrycz 2004).

The main objective of this study is to develop a general concept of distributed clustering based on the principles of Granular Computing (Pedrycz et al. 1998) and their constructs (Apolloni et al. 2006; Pedrycz et al. 2004). Here our focus is on the data described in different feature spaces, which implies that a communication vehicle is established in terms of proximity matrices. Based on this form of interaction, we discuss three main conceptual settings. The one is of a passive nature, which concentrates on a granular characterization of proximity-based structure with the invocation of granular proximity matrices of a global character. The two other active-like alternatives invoke some structural feedback to refine local structures on a basis of the global result (viz. a granular proximity matrix).

Our investigations come with several well-articulated aspects of originality. The formulation of the problem is original: although some facets of collaborative clustering have been investigated in the literature, those approaches focus on the passive mode meaning that the results of clustering are aggregated, however, an active facet is not considered at all meaning that no mechanisms adjusting local clustering findings were developed given some global findings. Let us recall that a passive mode implies that the locally available clustering results are provided and some aggregation mechanism is invoked, which gives rise to a general (global) view of the results. In this process, irrespectively of the result obtained at the global level, the local structures (clusters) are not modified (affected). In contrast, when talking about an active mode, a feedback loop is being formed so that in an iterative fashion the local results give rise to some global results. In the sequel, those are contrasted with the results available at the lower level and as a result the local results are modified following a certain adjustment strategy so that in the next iteration there is some improvement observed at the level of the global results.

It is worth noting that there have been some interesting earlier studies on interval-valued clustering, cf. (Souza and Carvalho 2004; Gacek and Pedrycz 2013; Hathaway et al. 1996; Pedrycz et al. 1998; Hwang and Rhee 2007; Mali and Mitra 2003; Wong and Hu 2013; Zhang et al. 2014). There is, however, an important difference between the undertaken research and the previous line of investigation. Here we are concerned with numeric data whereas information granules come as a result of reconciliation of results and are reflective of the diversity of the local findings. The previous studies were focused on granular clustering, more specifically, interval-valued data

The paper is structured as follows. In Sect. 2, we highlight an essence of the problem and identify a role of information granularity being played in this setting. In the sequel, we briefly outline the essence of the main classes of problems (Sect. 3). In Sect. 4, all associated optimization problems are formulated and solved. More specifically, we discuss a way of forming granular proximity matrices through the use of the principle of justifiable granularity (Pedrycz 2013), and look at the techniques of refining local partition matrices based on the gradient-based optimization and particle swarm optimization (PSO) as well as a hybrid of these two techniques. Two ways of characterization of granular proximity matrices are discussed. Numeric studies are covered in Sect. 5.

In the study, we adhere to the standard notation encountered in pattern recognition, clustering and system modeling. To emphasize the origin of the locally available data and the resulting constructs, we use indexes placed in square brackets, say \(c\)[ii], \(U\)[ii], \(u_{ik}\)[ii], etc.

Let us consider a collection of \(p\) data sets \(\mathbf{D}_{1}, \mathbf{D}_{2}, {\ldots }, \mathbf{D}_{p}\) originating from a certain problem. For instance, those sets could be data describing a certain system for which formed are individual, local views associated with their local data. The data originated from different collections may be described in different feature spaces \(\mathbf{F}_{1}, \mathbf{F}_{2}, {\ldots ,} \mathbf{F}_{p}\). In general, we also assume that some data points are shared among the data sets meaning that an intersection of them is nonempty, namely \(\mathbf{D} = \mathbf{D}_{1} \cap \mathbf{D}_{2} \cap {\cdots }\cap \mathbf{D}_{p}\) card \((\mathbf{D}) =N\). Formally speaking, a selected object o\(_{k}\) belonging to the intersection of \(\mathbf{D}_{1}, \mathbf{D}_{2},{\ldots }\), and D \(_{p}\) comes with its own vectors of features x \(_{k}\)[1], x \(_{k}\)[2], ...,x \(_{k}\)[\(p\)] defined in the corresponding feature spaces. The data \({\{}\mathbf{x}_{k}[ii]{\}}\), \(k=\) 1, 2, ...\(N\) forming the data set D \(_{ii}\) are clustered in the corresponding feature space resulting in the corresponding partition matrix \(U\)[ii]. Clustering is completed for other data sets subsequently giving rise to partition matrices \(U\)[1], \(U\)[2],..., and \(U\)[\(p\)], respectively. In general, the number of clusters associated with these partition matrices, namely \(c\)[1], \(c\)[2],.., and \(c\)[\(p\)], could vary from one data set to another. The partition matrices formed in this way exhibit a local character, viz. they are concerned with the findings being confined to the given feature space and produced for the particular locally available data set. Our key objective of this study is to discover (or reconcile) a global structure in the data based on the reconciliation of the local views conveyed through the already constructed partition matrices.

There are two essential and general observations to be made here in the context of the problem under study:In the study, when developing a structure of a global nature, we rely on the fundamental concept of proximity matrices implied by partition matrices. Recall that for any partition matrix \(U\)[ii]= [\(u_{ik}\)[ii]], \(i=\) 1, 2,..., \(c\)[ii], \(k=\) 1, 2, ..., \(N\), the corresponding proximity matrix \(P\)[ii] \(=\) [\(p_{kl}\)[ii]] comes in the following form \(k\), \( l =\) 1, 2,..., \(N\).

It is instructive to provide a brief example to highlight the essence of the approach, motivate its origin, and shed light at the multistep processing dwelling on a formation of proximity matrices. The five two-dimensional data positioned in several feature subspaces are shown in Fig. 1.

It is apparent that the structures vary from one feature space to another. Assume that the partition matrices \(U\)[1], \(U\)[2], and \(U\)[3] have the following entries which reflect a distribution of the data. Likewise, by visualizing the structures of the data, the number of clusters varies from 2 to 3. In light of the varying dimensionality of these matrices, they cannot be compared directly. Instead, we have to consider some constructs built at the higher level of generality whose representation does not explicitly involve the number of clusters. Here, the corresponding proximity matrices are formed. These proximity matrices are determined following (1) and come in the form The proximity matrices exhibit different entries and as a result of their summarization produces the construct at the next level of generality, namely, a granular proximity matrix.

The granular proximity matrix visualizes an emergence of groups of data that are kept close to each other. One can observe a jump in the values of the entries pointing at the occurrence of the well-formed clusters.

We can distinguish three general categories of problems where the fundamental ideas outlined so far can be fully exploited. The essence of these problems is visualized through a series of figures that help contrast different tasks being studied here.

The three categories of problems outlined in the previous section call for a certain way of formulating the ensuing optimization problem, building its solution and finally characterizing the quality of the obtained solutions. We come up with some design procedures and show their arrangement when solving the three categories of problems formulated above.

In this section, a series of experiments involving both synthetic and real-world data are presented to illustrate how different schemes discussed above operate and a form of the results formed. In all experiments, we consider Fuzzy C-Means (FCM) algorithm (Bezdek 1981) run with the fuzzification coefficient set to 2, \(m=\) 2.

In this study, we have conceptualized, developed the algorithmic setting, and experimented with granular proximity matrices. It has been demonstrated that granularity of these matrices plays an important role in the realization of collaborative processes of forming views at the global structures not only facilitating this process, but also quantifying the diversity of locally available structures through the associated level of information granules of the granular proximity matrix. The guidance offered by global granular proximity matrices is an example of a realization of a structural feedback loop which augments the clustering processes by auxiliary sources of knowledge.

There are two open directions, which are worth further investigations:

Formation of structures exhibiting a higher type of granularity Higher level structures such as granular\(^{2}\) proximity matrices (if a hierarchy having three levels is present) can be discussed.