Clustering Uncertain Data via Representative Possible Worlds with Consistency Learning
Han Liu Xianchao Zhang Xiaotong Zhang Qimai Li Xiao-Ming Wu


Non-Hermitian Linear Response Theory
    Hui Zhai
    Received: date / Accepted: date
====================================




Clustering uncertain data is an essential task in data mining for the internet of things. Possible world based algorithms seem promising for clustering uncertain data. However, there are two issues in existing possible world based algorithms: (1) They rely on all the possible worlds and treat them equally, but some marginal possible worlds may cause negative effects. (2) They do not well utilize the consistency among possible worlds, since they conduct clustering or construct the affinity matrix on each possible world independently. In this paper, we propose a representative possible world based consistent clustering (RPC) algorithm for uncertain data. First, by introducing representative loss and using Jensen-Shannon divergence as the distribution measure, we design a heuristic strategy for the selection of representative possible worlds, thus avoiding the negative effects caused by marginal possible worlds. Second, we integrate a consistency learning procedure into spectral clustering to deal with the representative possible worlds synergistically, thus utilizing the consistency to achieve better performance. Experimental results show that our proposed algorithm performs better than the state-of-the-art algorithms.




§ INTRODUCTION

Most existing clustering algorithms focus on certain data. However, due to various reasons like randomness in data generation and collection, imprecision in physical measurement, privacy concern and data staling <cit.>, uncertain data is ubiquitous in many real applications, such as sensor networks, biomedical measurement, location tracking, meteorological forecasting and so on <cit.>. Uncertain data has posed a serious challenge to existing clustering algorithms.

Several algorithms have been proposed for clustering uncertain data. Partition-based algorithms, e.g., UK-means <cit.> and UK-medoids <cit.>, use expected distance or uncertain distance to extend traditional k-means or k-medoids to deal with uncertain data. However, they reduce complex probability distributions to a single probability distribution or a determinate value, thus cannot handle the uncertain information well <cit.>. Density-based algorithms, e.g., FDBSCAN <cit.> and FOPTICS <cit.>, extend traditional DBSCAN <cit.> or OPTICS <cit.> for clustering uncertain data by use of probabilistic definitions. However, they suffer from the unreasonable independent distance assumption <cit.>, thus are difficult to obtain satisfactory performance.

Different from partition-based and density-based algorithms, possible world based algorithms, e.g., SC <cit.> and REP <cit.>, employ multiple independent and identically distributed realizations of an uncertain dataset to deal with data uncertainty, thus reducing the loss of uncertain information and avoiding the independent distance assumption. However, they have two unaddressed issues: (1) They rely on all the possible worlds and treat them equally, but some marginal possible worlds may cause negative effects on the clustering result. (2) They do not well utilize the consistency among possible worlds, since they conduct clustering or construct the affinity matrix on each possible world independently. Nevertheless, the consistency is important since different possible worlds can utilize it to transfer useful information for improving the performance.

In this paper, we propose a representative possible world based consistent clustering (RPC) algorithm for uncertain data, which improves existing algorithms from the following two aspects: (1) To alleviate the negative effects caused by marginal possible worlds, we introduce the definition of representative loss, use Jensen-Shannon divergence as the distribution measure, and then design a heuristic strategy for the selection of representative possible worlds. This strategy can be used by any possible world based algorithm to improve the performance. (2) To utilize the consistency to achieve better performance, we integrate a consistency learning procedure into spectral clustering to deal with the representative possible worlds synergistically. Extensive experimental results demonstrate the superiority of the proposed algorithm over the existing ones.



§ RELATED WORK

Traditional algorithms. (1) Partition-based algorithms: UK-means <cit.> is the first partition-based algorithm for clustering uncertain data. It extends the traditional k-means by using expected distance. To improve the efficiency of UK-means, <cit.> use various pruning techniques to avoid the computation of redundant expected distances. CK-means <cit.> optimizes UK-means by resorting to the moment of inertia of rigid bodies. DUK-means <cit.> is an improved version of UK-means, which is specifically designed for distributed network environment. UK-medoids <cit.> employs uncertain distance to extend the traditional k-medoids. MMVar <cit.> uses a novel objective function which aims to minimize the variance of cluster mixture models. UCPC <cit.> introduces the notion of uncertain centroid and it is a local search based heuristic algorithm. All these algorithms can deal with uncertain data to some extent. However, they reduce complex probability distributions to a single probability distribution or a determinate value, thus cannot handle the uncertain information well <cit.>. (2) Density-based algorithms: FDBSCAN <cit.> and FOPTICS <cit.> are the first density-based and hierarchical density-based algorithms for clustering uncertain data respectively. They introduce a series of probabilistic definitions to extend the traditional DBSCAN or OPTICS. Zhang et al. <cit.> analyze the limitations in FDBSCAN and FOPTICS, and propose a novel density-based algorithm PDBSCAN for clustering uncertain data. However, these algorithms rely on the unreasonable independent distance assumption <cit.>, thus are difficult to obtain satisfactory clustering results.

Possible world based algorithms. SC <cit.> is the first possible world based algorithm for clustering uncertain data. It conducts clustering on each possible world independently and integrates the clustering results into one final result. REP <cit.> also conducts clustering on each possible world independently, but it selects the representative clustering result as the final result. Recently, <cit.> tries to leverage the consistency principle for clustering uncertain data. It constructs the affinity matrix for each possible world independently and then learns a consensus affinity matrix for clustering uncertain data. However, the consistency learning method introduced in <cit.> lacks the procedure of updating the affinity matrix of each possible world, thus reducing the ability of consistency learning. Possible world based algorithms avoid the issues in traditional algorithms and seem more promising for clustering uncertain data. However, as we point out hereinafter, there are some unaddressed issues in existing possible world based algorithms.



§ PRELIMINARIES



 §.§ Consistency Principle

Consistency principle is a common assumption, which has been widely used in many machine learning methods <cit.>. Its definition is as follows <cit.>.

(Consistency principle). Given a dataset which has multiple representations, consistency principle refers to an assumption that the class labels and cluster structures of the multiple representations are consistent.


By using consistency principle to minimize the disagreement of different representations, we can improve the algorithm performance greatly. The detailed proof can refer to <cit.>.



 §.§ Uncertain Data and Possible World

Uncertain data can be considered at table, tuple or attribute level <cit.>. For uncertain data clustering, we mainly focus on attribute level uncertainty. That is to say, each uncertain object is represented as a random variable with a probability distribution, which is associated with the probability that the object appears at any position in a multidimensional space.

Possible world is an effective tool to model uncertain data <cit.>. Its definition is as follows <cit.>.

(Possible world). Let UD = {O_1,O_2,...,O_n} be an uncertain dataset. A possible world pw = {o_1,o_2,...,o_n} (o_i∈ O_i) is a set of instances such that each instance is taken from each corresponding uncertain object. Let PW be the set of all the possible worlds, P(pw) be the existence probability of pw, then ∑_pw∈ PW P(pw)=1.


Possible world can be generated through the inversion method. Due to space limitation, more information and proofs can refer to <cit.>.



  §.§.§ Consistency Principle for Possible World




According to the definition of possible world, different possible worlds come from the same uncertain dataset and they are a number of independent and identically distributed realizations of an uncertain dataset <cit.>. Therefore, if we treat each possible world as one representation of the uncertain dataset, by the concept of consistency principle, we can have the following consistency principle for possible world: the class labels and cluster structures of different possible worlds are consistent.

In general, the consistency principle for possible world conforms to the reality well, i.e., in most cases the class labels and cluster structures of different possible worlds are consistent. For example, in Figure 1, O_1, O_2, O_3 are uncertain objects, and o^i_1, o^i_2, o^i_3, o^i_4 are the possible instances of O_i (i ∈{1,2,3}). If we divide O_1, O_2, O_3 into two clusters, based on the geometric information, O_1 should belong to one cluster, O_2 and O_3 should belong to the other cluster. For the possible worlds pw_1, pw_2, pw_3 with their components shown in Figure 1, it is easy to find that their class labels and cluster structures are consistent.

However, the consistency principle for possible world is not absolute. In some cases, abnormal possible worlds violate the principle, and we call this kind of possible worlds as the marginal ones. Formally, the definition of marginal possible world is as follows.

(Marginal possible world). Let PW be the set of all the possible worlds, marginal possible world refers to the possible world whose class label and cluster structure have large differences with most possible worlds in PW.


For example, in Figure 1, pw_4 is a possible world which consists of some abnormal instances. As the class label and cluster structure of pw_4 are very different from most possible worlds, pw_4 is a marginal possible world.



 §.§ Unaddressed Issues


(1) Negative effects caused by marginal possible worlds. Existing possible world based algorithms rely on all the possible worlds and treat them equally. However, marginal possible worlds belong to the abnormal ones, their class labels and cluster structures have large differences with most possible worlds, which may disturb the integrating or selecting procedure of existing possible world based algorithms and cause negative effects on the clustering result. To solve this issue, we propose to select some representative possible worlds to filter out marginal possible worlds. By representative possible worlds we mean a subset of all the possible worlds which has a strong ability to represent all the possible worlds. As marginal possible worlds are abnormal and their representative ability is weak, we can filter out marginal possible worlds and avoid the negative effects by selecting representative possible worlds.

(2) Utilizing the consistency principle for possible world not well. The consistency principle makes it possible to transfer useful information among different possible worlds, which can potentially improve the clustering quality. However, existing possible world based algorithms conduct clustering or construct the affinity matrix on each possible world independently, thus cannot well utilize the consistency among possible worlds. To tackle this issue, we propose a consistent spectral clustering method which can update the eigenvector matrix of each possible world iteratively and minimize the disagreement of different possible worlds, thus better achieving the consistency learning and improving the performance.



§ THE PROPOSED ALGORITHM

The proposed algorithm consists of two parts: selecting representative possible worlds and consistent spectral clustering.

Given an uncertain dataset UD={O_1,O_2,...,O_n} in a d-dimensional independent space, PW={pw_i|i=1,2,...,M}, PWR={pwr_j|j=1,2,...,R}, PWU={pwu_k|k=1,2,...,M-R} respectively denote the set of all the possible worlds, the representative possible world set and the unrepresentative possible world set. M, R and M-R respectively denote the number of possible worlds in PW, PWR and PWU. Here PW=PWR∪ PWU.



 §.§ Selecting Representative Possible Worlds

By selecting representative possible worlds, we can filter out marginal possible worlds and avoid the waste of time caused by redundant possible worlds. In order to select representative possible worlds, we introduce the definition of representative loss, use Jensen-Shannon divergence as the distribution measure, and then design a heuristic strategy for the selection of representative possible worlds.



  §.§.§ Representative Loss

Intuitively, given any two possible worlds pw and pw', if we want to use pw to represent pw', then the smaller the difference between pw and pw', the less the loss that pw represents pw'. We aim to select PWR from PW to represent PW. As PW=PWR∪ PWU and the loss that PWR represents PWR is equal to 0, then the loss that PWR represents PW is equal to the loss that PWR represents PWU. Based on these observations, we have the following definition.

(Representative loss). Let PWR be the representative possible world set and pwr_j ∈ PWR, PWU be the unrepresentative possible world set and pwu_k ∈ PWU. If using PWR to represent PWU, then the representative loss, denoted by L(PWR→ PWU), can be defined as:

    L(PWR→ PWU)= ∑_k=1^M-Rmin_pwr_jΦ(pwr_j,pwu_k),


where Φ(pwr_j,pwu_k) is the difference between pwr_j and pwu_k, M-R is the number of possible worlds in PWU.

From this definition, it can be seen that if we know how to compute the difference between possible worlds, we can get the representative loss that PWR represents PWU, i.e., the representative loss that PWR represents PW.



  §.§.§ Jensen-Shannon Divergence between Possible Worlds

As a possible world can be regarded as a probability distribution, we can compute the difference between possible worlds by Jensen-Shannon divergence <cit.>. Compared with KL divergence <cit.>, Jensen-Shannon divergence is symmetric and finite, therefore it is more suitable as the representative loss measure.

Given any two possible worlds pw and pw', the Jensen-Shannon divergence between them can be defined as:

    JSD(pw||pw')=1/2D(P_pw||H)+1/2D(P_pw'||H),

where P_pw and P_pw' are the probability distributions of pw and pw' respectively, and H=1/2(P_pw+P_pw'). D(P||Q) is the KL divergence between two probability distributions P and Q. For continuous probability distributions P and Q with a variable x in a domain 𝔻, D(P||Q) is defined as:

    D(P||Q)=∫_𝔻f(x)logf(x)/g(x)dx,

where f(x) and g(x) are the probability density functions of P and Q. D(P||Q) can also be expressed as:

    D(P||Q)=E(logf(x)/g(x)),

where E denotes the expectation. According to the law of large numbers and Eq.(<ref>), given a sample set S, D(P||Q) can be estimated by:

    D(P||Q)=1/|S|∑_x∈ S log f(x)/g(x),

where |S| denotes the number of objects in S.

We employ the kernel density estimation method <cit.> to obtain the probability density functions f_pw and f_pw' of the probability distributions P_pw and P_pw'. Specifically, f_pw can be estimated as:

    f_pw(x) = 1/ |pw| ∏_j = 1^d h_j ∑_o ∈ pw∏_j = 1^d K(x.D_j  - o.D_j /h_j ).


In Eq.(<ref>), o denotes an object in pw and it can be represented by (o.D_1, o.D_2, ..., o.D_d), d denotes the total dimensionality, and |pw| denotes the number of objects in pw. K denotes the kernel function, and we use the most common Gaussian kernel function. h_j denotes the bandwidth of the j-th dimension. For Gaussian kernel function, we set h_j=1.06×δ_j|pw|^-1/5 according to the Silverman's rule of thumb <cit.>, where δ_j is the standard deviation of the j-th dimension of the objects in pw.

By using Jensen-Shannon divergence as the distribution measure to compute the difference between possible worlds, i.e., replacing Φ(pwr_j,pwu_k) in Eq.(<ref>) with JSD(pwr_j||pwu_k), we can get the representative loss.



  §.§.§ Selection Strategy

Our goal is to select a given number of possible worlds as the representative possible worlds. In general, a good representative possible world set should have a strong representative ability, i.e., its corresponding representative loss should be small. Inspired by this observation, we propose the following selection strategy:

Let PWR be the representative possible world set, and PWU be the unrepresentative possible world set. Now select a possible world pwu^* from PWU and move pwu^* to PWR, if we want the new representative possible world set PWR∪ pwu^* to be the best, then the selection strategy should ensure the representative loss that PWR∪ pwu^* represents PWU\ pwu^* to be the minimum. Formally:

    pwu^*=min_pwu^*L(PWR∪ pwu^* → PWU\ pwu^*).


From Eq.(<ref>), it can be seen that pwu^* should have a strong representative ability. Marginal possible worlds are the abnormal ones and their representative ability is poor, therefore this selection strategy can filter out marginal possible worlds.

Based on the selection strategy, we design a heuristic method to select the representative possible worlds, which is shown in Algorithm 1 (Part 1).





 §.§ Consistent Spectral Clustering

We integrate a consistency learning procedure into spectral clustering to deal with the representative possible worlds synergistically.



  §.§.§ Spectral Clustering

Assume that pwr_j is a possible world from the representative possible world set PWR and PWR={pwr_j|j=1,2,...,R}, where R denotes the number of possible worlds in PWR. W^(j) is the similarity matrix of pwr_j, which is computed by the Gaussian kernel. L^(j) is the normalized Laplacian matrix of pwr_j and L^(j)=D^(j)^-1/2W^(j)D^(j)^-1/2. D^(j) is a diagonal matrix and D^(j)(i,i)=∑_l=1^n W^(j)(i,l), where n denotes the number of objects in pwr_j. For the representative possible world pwr_j, the objective function of spectral clustering is:

    max_U^(j) tr(U^(j)^TL^(j)U^(j)),   s.t.  U^(j)^TU^(j)=I,

where tr(·) denotes the trace of a matrix, and the solution of U^(j)∈ℝ^n× k is composed by k eigenvectors corresponding to the k largest eigenvalues of L^(j).



  §.§.§ Consistency Learning

The eigenvector matrix U^(j) can reflect the cluster structure of the representative possible world pwr_j. To meet the requirement of consistency, we assume that each eigenvector matrix U^(j)∈ℝ^n× k tends to a common eigenvector matrix U^* ∈ℝ^n× k. Then by minimizing the disagreement between each U^(j) and U^*, we can achieve the consistency learning among different possible worlds. For the disagreement between U^(j) and U^*, we use the squared Euclidean distance between the similarity matrices to measure it:

    Dis(U^(j), U^*)=||S_U^(j)-S_ U^*||^2_F, 
     s.t.   U^(j)^TU^(j)=I,  U^*^TU^*=I,

where S_U^(j) and S_ U^* denote the similarity matrices of U^(j) and U^*, and ||·||_F denotes the Frobenius norm of the matrix.

Considering the feasibility of optimization, we use the commonly adopted inner product to compute the similarity matrix, i.e., S_U^(j)=U^(j)U^(j)^T. Then with some manipulations, minimizing Eq.(<ref>) can be transformed as:

    max_U^(j), U^*tr(U^(j)U^(j)^TU^*U^*^T),     
     s.t.   U^(j)^TU^(j)=I,  U^*^TU^*=I.




  §.§.§ Overall Objective Function and Optimization

By integrating the objective functions of spectral clustering and consistency learning, we can get the overall objective function of consistent spectral clustering as follows:

    max_U^(j), U^*∑_j=1^R (tr(U^(j)^TL^(j)U^(j))+  tr(U^(j)U^(j)^TU^*U^*^T)),
      s.t.   U^(j)^TU^(j)=I,   1⩽ j⩽ R,   U^*^TU^*=I.


For Eq.(<ref>), we can employ the alternative iteration method to solve it.

(1) Optimizing Eq.(<ref>) with respect to U^*. Fix each U^(j), then Eq.(<ref>) becomes:

    max_U^*∑_j=1^R tr(U^(j)U^(j)^TU^*U^*^T),
      s.t.   U^*^TU^*=I.


Eq.(<ref>) can be written as:

    max_U^* tr (U^*^T(∑_j=1^R  U^(j)U^(j)^T)U^*),
     s.t.  U^*^TU^*=I.


It is easy to find that optimizing Eq.(<ref>) is equivalent to solve the standard spectral clustering with a modified Laplacian matrix ∑_j=1^R U^(j)U^(j)^T, i.e., the solution of U^* is composed by k eigenvectors corresponding to the k largest eigenvalues of ∑_j=1^R U^(j)U^(j)^T.

(2) Optimizing Eq.(<ref>) with respect to one of the U^(j)s. Fix the other U^(j)s and U^*, then Eq.(<ref>) becomes:

    max_U^(j) tr(U^(j)^TL^(j)U^(j))+ tr(U^(j)U^(j)^TU^*U^*^T),
    
    s.t.   U^(j)^TU^(j)=I.


Eq.(<ref>) can be written as:

    max_U^(j) tr(U^(j)^T(L^(j)+U^*U^*^T) U^(j)),
    
    s.t.   U^(j)^TU^(j)=I.


Optimizing Eq.(<ref>) is similar with optimizing Eq.(<ref>), therefore the solution of U^(j) is composed by k eigenvectors corresponding to the k largest eigenvalues of L^(j)+U^*U^*^T.

The overall procedure of consistent spectral clustering is shown in Algorithm 1 (Part 2).




§ EXPERIMENTS



 §.§ Datasets

Real benchmark datasets. We conduct experiments on 6 real benchmark datasets. The details of the datasets are shown in Table 1. These datasets are originally established as collections of data with determinate values, we follow the method in <cit.> to generate the uncertainty of Gaussian distribution for these datasets.




Real world uncertain datasets. We also use 3 real world uncertain datasets: Movement (http://archive.ics.uci.edu/ml/), NBA (http://espn.go.com/nba/) and Weather (http://bcc.ncc-cma.net/) to perform experiments.

(1) Movement: it consists of 13197 radio signal records about 314 temporal sequences from a wireless sensor network deployed in real-world office environments. Each record has four dimensions which are respectively corresponding to four sensor nodes. According to user movement path, the dataset is divided into six classes. Each temporal sequence is treated as an uncertain object and each record of the temporal sequence is treated as a possible value of the uncertain object.

(2) NBA: it consists of 2197 records about the top 300 players in ESPN 2015 rank. Each record has five dimensions: points, rebounds, assists, steals and blocks. According to season average performance, they are divided into three classes: star/key/role player. Each player is treated as an uncertain object and each season average performance of the player is treated as a possible value of the uncertain object.

(3) Weather: it consists of 18360 records about 153 weather stations around China. Each station contains the monthly average weather condition from 2006 to 2015. Each record has two dimensions: average temperature and average precipitation. Each station is labeled with a climate type. We have three types of climates: temperate continental climate, temperate monsoon climate and tropical/subtropical monsoon climate. The stations with the same label are considered to be in the same class. Each station is treated as an uncertain object and each monthly average weather condition of the station is treated as a possible value of the uncertain object.





 §.§ Experimental Setup

Baselines. We compare RPC with the state-of-the-art clustering algorithms for uncertain data, including UK-means (UKM), CK-means (CKM), UK-medoids (UKMD), MMVar (MMV), UCPC, FDBSCAN (FDB), FOPTICS (FOP), PDBSCAN (PDB), SC and REP. We also compare with the improved versions of SC and REP, which use our proposed selection strategy to select the representative possible worlds and then perform the original SC and REP on the representative possible worlds, and we call them RP-SC and RP-REP.

Settings. For UK-means, CK-means, UK-medoids, MMVar, UCPC and RPC, the sets of initial centroids or partitions are randomly selected. To avoid that the clustering results are affected by random chance, we average the results over 10 different runs. For FDBSCAN, FOPTICS, PDBSCAN, SC, REP, RP-SC and RP-REP, since these algorithms are sensitive to parameters, we adjust the parameters continuously until the performance of each method becomes the best and stable. The methods of determining the parameters can refer to <cit.>.

Evaluation metrics. We adopt two widely used evaluation metrics <cit.>: clustering accuracy (ACC) and normalized mutual information (NMI) to evaluate the clustering performance.



 §.§ Parameter Investigation for RPC




(1) For parameter k, we follow the common practice to set k to the true number of classes in the datasets. (2) For parameter M, the investigation results in previous possible world based methods show that setting M=100 is enough to obtain satisfactory results <cit.>, so we set M=100. (3) For parameter R, Figure 2 shows the performance of RPC with different R on real world uncertain datasets. From the results, it can be seen that when R is within 10∼70, the clustering performance is always good and stable. When the parameter R is larger than 70, the clustering performance will be affected seriously, which is because that the remaining 30 possible worlds contain many marginal ones. As selecting too many representative possible worlds will result in a waste of time to some extent, in this paper we set R=10 and report the corresponding results.



 §.§ Clustering Results


Effectiveness. From the effectiveness results in Table 2, it can be seen that RPC performs the best. RP-SC and RP-REP respectively perform better than SC and REP, but not as well as RPC. This is because that compared with SC and REP, RP-SC and RP-REP select the representative possible worlds, thus avoiding the negative effects caused by marginal possible worlds. However, compared with RPC, RP-SC and RP-REP do not make use of the consistency principle among different possible worlds. UK-means, CK-means, UK-medoids, MMVar and UCPC perform worse than RPC. The reason is that these algorithms reduce complex probability distributions to a single probability distribution or a determinate value, which may cause the loss of uncertain information. FDBSCAN, FOPTICS and PDBSCAN also perform worse than RPC. The reason is that they rely on the unreasonable independent distance assumption. All in all, in terms of effectiveness, RPC performs much better than the compared algorithms.

Efficiency. Due to space limit, we only report the efficiency results (in milliseconds) on real world uncertain datasets. Other datasets have the similar trend. From the results in Figure 3, it can be seen that UK-medoids is the slowest. RPC runs faster than FDBSCAN and FOPTICS, but slower than UK-means, CK-means, MMVar, UCPC and PDBSCAN. Among possible world based algorithms, RP-SC, RP-REP and RPC perform almost identically, and they are slower than SC and REP. The reason is that when selecting representative possible worlds, the computation process of Jensen-Shannon divergence is a little complex.





§ CONCLUSION

In this paper, we propose a representative possible world based consistent clustering algorithm for uncertain data. By selecting representative possible worlds, it avoids the negative effects caused by marginal possible worlds. By consistent spectral clustering, it makes use of the consistency principle to achieve better performance. Experimental results show that the proposed algorithm outperforms the state-of-the-art algorithms in effectiveness. For future work, we will extend the idea to uncertain data stream clustering and classification.



§ ACKNOWLEDGMENTS

This work was supported by National Science Foundation of China (No. 61876028) and the grants 1-ZVJJ and G-YBXV funded by the Hong Kong Polytechnic University.


named


