We deploy a recently proposed framework for mining subjectively interesting patterns from data [3] to the problem of clustering, where patterns are clusters in the data. This framework outlines how subjective interestingness of patterns (here, clusters) can be quantified using sound information theoretic concepts. We demonstrate how it motivates a new objective function quantifying the interestingness of (a set of) clusters, automatically accounting for a user's prior beliefs and for redundancies between the clusters. Directly searching for the optimal set of clusters defined in this way is hard. However, the optimization problem can be solved to a provably good approximation if clusters are generated iteratively, paralleling the iterative data mining setting discussed in [3]. In this iterative scheme, each subsequent cluster is maximally interesting given the previously generated ones, automatically trading off interestingness with non-redundancy. Thus, this implementation of the clustering approach can be regarded as a method for alternative clustering. Although generating each cluster in an iterative fashion is computationally hard as well, we develop an approximation technique similar to spectral clustering algorithms. We end with a few visual demonstrations of the alternative clustering approach to artificial datasets.
A main challenge in research on clustering methods and theory is that clustering is (in a way intentionally) ill-defined as a task. As a result, numerous types of syntaxes for cluster patterns have been suggested (e.g. clusters as hyperrectangles, hyperspheres, ellipsoids, decision trees; clusterings as partitions, hierarchical partitionings, etc). Additionally, even when the syntax is fixed, there are often various alternative choices for the objective function (e.g. the K-means cost function, the likelihood of a mixture of Gaussians, etc).
Despite this variety in approaches, the goal of clustering is almost always to provide a user with insight in the structure of the data, allowing the user to conceptualize it as coming from a number of broad areas in the data space. The knowledge of such a structure can be more or less elucidating to the user, also depending on the prior beliefs the user held about the data.
Here, we take the perspective that a clustering is more useful if it conveys
more novel information. We make a specicfi choice for a cluster syntax, and we
deploy ideas from [
Our approach attempts to quantify subjective interestingness of clusters, in that it takes prior beliefs held by the user into account. As a result, different clusters might be deemed interesting to different users. One particular example is the situation where a user has already been informed about previously discovered clusters in the data, which is the alternative clustering setting. In that case, clusters that are individually informative while non-redundant will be the most interesting ones. Our approach naturally deals with alternative clustering, by regarding already communicated clusters as prior beliefs.
Throughout this paper x ∈ Rd denotes a d-dimensional data point, and X = x1 x2 · · · xn denotes the data matrix containing n data points as its rows. The space the data matrix belongs to is denoted as X = Rn×d. 2
For completeness, we here provide a short overview of a framework for data
mining that was introduced in [
The framework aims to formalize data mining as a process of information exchange between the data and the data miner (the user). The goal of the data miner is to get as good an understanding about the data as possible, i.e. to reduce his uncertainty as much as possible. To be able to do this, the degree of uncertainty must be quantiefid, and to this end we use probability distribution P (referred to as the background distribution) to model the prior beliefs of the user about the data X, in combination with ideas from information theory.
More specifically, the framework deals wi th the setting where the prior beliefs specify that the background distribution belongs to one of a set P of possible distributions. The more prior beliefs, the smaller this set will be. For example, the data miner may have a set of prior beliefs that can be formalized in the form of constraints the background distribution P satisfies:
X∈ Rn×d
fi(X)P (X) = ci, ∀i.
Such constraints represent the fact that the expected value of certain statistics (the functions fi) are equal to a given number. The set P is defined as the set of distributions satisfying these constraints. (Note that the framework is not limited to such prior beliefs, although they are convenient from a practical viewpoint.)
We argued in [
In the framework, a pattern is defined as any piece of knowledge about the data that reduces the set of possible values it may take from the original data space X = Rn×d to a subset X . We then argued that the subjective interestingness of such a pattern can be adequately formalized as the self-information of the pattern, i.e. the negative logarithm of the probability that the pattern is present in the data, i.e. by − log (P (X ∈ X )). Thus, patterns are deemed more interesting if their probability is smaller under the background model, and thus if the user is more surprised by their observation.
After observing a pattern, a user instinctively adapts his beliefs. In [
In [
Thus, the alternative clustering method we will detail below generates clusters in an iterative manner, in such a way that at any time the clusters generated so far are approximately the most informative set of clusters of that size. 3 3.1
Here we consider two types of initial prior beliefs, expressed as constraints on the rfist and second order cumulants of the data points. It is conceptually easy to extend the results from this paper to other types of prior beliefs, although the computational cost will vary. The background distribution incorporating these constraints is the maximum entropy distribution that has the prescribed rfist and second order cumulants. It is well known that for data with unbounded domain, this distribution is the multivariate Gaussian distribution with mean and covariance matrix equal to the prescribed cumulants:
P (X) =
1 exp
1 − 2 trace (X − eμ )Σ −1(X − eμ ) .
(1)
We note that the prescribed cumulants may be computed from the actual data at the request of the data miner, such that they are indeed part of the prior knowledge. However, they may also be beliefs, in the sense that they may be based on external information or assumptions that may be right or wrong. 3.2
The framework from [
In this paper we restrict our attention to one specific type of cluster pattern. The pattern type we consider is parameterized by a set of indices to the data points and a vector in the data space. The pattern is then the fact that the mean of the data points for these indices is equal to the specified vector.
More formally, let eI ∈ Rd be defined as an indicator vector containing zeros at positions i ∈ I and ones at positions i ∈ I, and let nI = |I| = eI eI denote the number of elements in I. Then, our patterns are constraints of the form: 1 nI i∈ I
eI ⇔ X eI eI xi = μI , = μI .
Such a constraint restricts the possible values of the data set X, in that the mean of a subset of the data points is required to have a prescribed value μI . 3.3
The following theorem shows how to assess the self-information of a pattern. Theorem 1. Given a background distribution of the form in Eq. (1), the probability of a pattern of the form X eIeIeI = μI is given by: P
X eI eI eI = μI =
1 (2π )d|Σ | exp
1 − 2|I| eI · (X − eμ )Σ −1(X − eμ ) · eI .
Thus the self-information of the pattern for a cluster specified by the set I, defined as the negative log probability of the cluster pattern and denoted as SelfInformationI , is equal to:
1 1 SelfInformationI = log (2π )d|Σ | + QI , 2 2 1 where QI = eI · (X − eμ )Σ −1(X − eμ ) · eI .
|I| Note that the self-information depends on I only through QI , so we may choose to use QI as a quality metric for a cluster, as we will do in this paper.
This theorem can be used to quantify the self-information of any cluster given the background model based on the prior beliefs of the data miner. Note however that it cannot be used to assess the self-information of a cluster after other clusters have already been found, as each new cluster will affect the user’s prior beliefs. How this can be accounted for will be discussed in Sec. 3.4, based on a generalization of Theorem 1. As Theorem 1 directly follows from Theorem 2, we will only provide a proof for the latter in Sec. 3.4. 3.4
of the i’th cluster as their i’th columns.
Let us discuss the more general case, where the patterns are constraints of the form X E = M with E ∈ Rn×k and M ∈ Rd×k. Clearly, the type of patterns we wish to consider are a special case of this, with E = eIeIeI and M = μI . Furthermore, it allows us to consider a composite pattern, a pattern defined as the union of a set of k patterns. Indeed, if we have k different cluster patterns specified by the sets from I = {Ii}, we can write down this set of constraints concisely as X E = M where E and M contain eIeiIeiIi and the mean vector μi Theorem 2. Let the columns of the matrix E be the indicator vectors of the sets in I = {Ii}, and let PE = E(E E)−1E , the projection matrix onto the column space of E. Then, the probability of the composite pattern X E = M is given by: P (X E = M) =
1 exp
1 − 2 trace PE · (X − eμ )Σ −1(X − eμ ) .
Thus the self-information of the set of patterns defined by the columns of E, defined as its negative log probability and denoted as SelfInformationI , is equal to:
SelfInformationI = k 1 2 log (2π )d|Σ | + 2 QI , where QI = trace PE · (X − eμ )Σ −1(X − eμ ) .
Again, since the self-information depends on I only through QI , we choose to use QI as a quality metric for a cluster further below.
Proof. A constraint X E = M constrains the data X to an (n − k) × d dimensional affine subspace in the following way. Let us write the singular value decomposition for E as:
E =
U U0
V V0 where Z = Λ−1V M is a constant xfied by E and M, and Z0 ∈ R(n−k)×d is a variable. In general, writing X = UZ + U0Z0, we can write the probability density for X as: P (X) = P (Z,Z0),
1 = = ·
1 − 2 trace (UZ + U0Z0 − eμ )Σ −1(UZ + U0Z0 − eμ ) exp
1 − 2 trace (Z0 − U0eμ )Σ −1(Z0 − U0eμ ) exp
1 − 2 trace (Z − U eμ )Σ −1(Z − U eμ ) We can now compute the marginal probability density for Z by integrating over Z0, yielding:
P (Z) =
1 exp
1 − 2 trace (Z − U eμ )Σ −1(Z − U eμ ) .
The probability density value for the pattern’s presence, i.e. for X E = M or equivalently Z = Λ−1V M , is thus: = =
P (Z = Λ−1V M ) 1 1 exp exp
1 − 2 trace (Λ−1V M − U eμ )Σ −1(Λ−1V M − U eμ ) , 1 − 2 trace PE · (X − eμ )Σ −1(X − eμ ) , where PE = E(E E)−1E is a projection matrix projecting onto the k-dimensional column space of E.
Note that Theorem 1 is indeed a special case of Theorem 2 as can be seen by substituting E = eI and PE = eIIeI .
| |
According to the framework, a (composite) pattern specified by matrices E and M in this way is thus more informative if trace PE · (X − eμ )Σ −1(X − eμ ) is larger. Thus, we could search for the most informative set of clusters by maximizing this quality measure with respect to a set I = {Ii} of clusters. This is a hard problem though, even in the case where only one cluster is sought. Thus, we developed an approximation algorithm.
Our approach is approximate in two ways. First, the search for a set of clusters
is approximated using a greedy algorithm, searching clusters one by one, thus
operating like an alternative clustering algoritm. From [
The framework from [
In the current context, describing a pattern amounts to describing the subset I and the mean vector μI . For simplicity, we assume the description length is constant for all patterns, independent of I and μI . However, note that different costs could be used if patterns with smaller sets I are more easy to understand (i.e. have a smaller cost), or vice versa.
Here we discuss an iterative approach to optimizing the quality measure QI from Theorem 2. There are two reasons for choosing an iterative approach.
Firstly, directly optimizing the quality measure is equivalent to a set covering
type problem (see [
Secondly, usually it is not a priori clear how many clusters are required for the data miner to be sufficiently satisefid with his new understanding of the data. The idea of alternative clustering, as we view it, is to provide the user the opportunity to request new clusters (or clusterings) as long as more are desired. Optimizing the quality measure over a growing set of clusters by iteratively optimizing over a newly added column of E is thus a type of alternative clustering.
Hence, the iterative approach can be regarded as an approximation, but one with usability benetfis over a global optimizing approach. 4.1
To search for the rfist cluster, we attempt to optimize the quality function from Theorem 1. This is itself a hard problem, but we explain how we approximately solve it in Sec. 4.2.
In the subsequent iterations, let us say that we have already found k − 1 ≥ 1 clusters, and the matrices E and M respectively contain the normalized indicator vectors and cluster means as their columns. We are interested in finding the k’th cluster so as to optimize the quality measure from Theorem 2 but keeping the first k − 1 cluster patterns as they are.
To do this, it is convenient to write the quality measure as a function of the k’th cluster with indicator vector ek. Let QE = I − PE, the projection matrix on the null column space of E. Furthermore, let us denote E∗ = E ek . Then, using the denfiition of a projection matrix and the matrix inversion lemma: Q{Ii|i=1:k} = trace PE∗ · (X − eμ )Σ −1(X − eμ ) , = trace PE · (X − eμ )Σ −1(X − eμ ) +trace
QEekekQE
ekQEek = Q{Ii|i=1:k−1} +
· (X − eμ )Σ −1(X − eμ ) ,
Note that if we denfie Q∅ = 0 and with QE = I the quality measure from Theorem 1 is retrieved. We can thus interpret the above reformulation of the quality metric for the k’th cluster conditioned on the rfist k − 1 clusters as being the quality metric for a first cluster on data that is projected onto the space orthogonal to the k − 1 columns of E, i.e. the k − 1 previously selected indicator vectors. It is as if the data was deflated to take account of the knowledge of the previously found cluster patterns, thus automatically accounting for redundancy. 4.2
Each of the iterative steps thus reduces to the maximization of the following increase of the quality measure: ΔQk = If we relax the vector ek to be real-valued instead of containing only 0’s and 1’s, this Rayleigh quotient is maximized by the dominant eigenvector of the matrix QE · (X − eμ )Σ −1(X − eμ ) QE. Thus, as an approximation technique we will use this dominant eigenvector, and threshold it to obtain a crisp 0/1 vector ek. To determine a suitable threshold, we simply do an exhaustive search over n + 1 threshold values that generate a different set I of indices i ∈ I for which ek(i) = 1, selecting the threshold that maximizes the quantity in Eq. (2). Note that for Σ = I, the quality metrics depend on X only through the inner product matrix XX . This means that a kernel-variant is readily derived, by substituting this inner product matrix with any suitable kernel matrix. In this way nonlinearly shaped clusters can be obtained, similar to spectral clustering methods and kernel K-Means. 5
There appear to be strong relations between spectral clustering and our
spectral relaxation of the problem [
We conducted 3 experiments, each time reporting the result of 6 iterations of the alternative clustering scheme. Initial prior beliefs are always μ = 0 and Σ = I. – A plain application to a synthetic dataset of 100 points and 2 dimensions in 4 clusters. See Fig. 1. – An application to the same data but now with a Radial Basis Function (RBF) kernel used for the inner products. See Fig. 2. – An application with an RBF kernel to a different synthetic dataset, with one central cluster and two half-moon shaped clusters around this central cluster. See Fig. 3. 948.3664 923.4161
0 55.4025 5 5 5 5 0 −5 10 5 0 −5 10 5 0 −5 27.9164
0 18.9836
0 2.5518 5 5 5 5 0 −5 10 5 0 −5 10 5 0 −5 11.324
0 10.192
0 8.1599 1 1 1 2 2 2 10.2221
0 Fig. 3. A synthetic dataset with a central set of 20 data points surrounded by two half moons of 40 data points each. The plots show the first 6 consecutive alternative clusters when an RBF kernel with kernel width 0.3 is used. The numbers above the plots are the values of ΔQk from Eq. (2) for the cluster shown. Note that the second cluster generated contains all data points. This is possible and sensible from the perspective of our approach if the mean of the entire data set is significantly different from the expected mean in the initial background model. This may well be the case when working in a Hilbert space induced by the RBF kernel, where all data points lie in one orthant such that their mean cannot be in the origin.
In [
In further work, we will investigate the quality of the spectral relaxation, and consider the development of tighter relaxations (e.g. to semi-denfiite programs). We will also further develop links with spectral clustering and other existing clustering approaches, to provide alternative justifications and insights or to improve on these approaches. We will also investigate the use of other pattern syntaxes for cluster(ing)s, and the use of more complex types of prior beliefs. Lastly, we plan to demonstrate the power of the framework by also applying these ideas to other types of data and corresponding types of prior beliefs, such as positive real-valued, integer, binary, and more structured types of data.
Due to space constraints, in this workshop paper we could not situate the contributions within the wider literature on alternative clustering. We will rectify this important shortcoming in a later version of this workshop paper.
This work is supported by the EPSRC grant EP/G056447/1.