One of most commonly used methods of data mining is clustering. Its goal is to identify unknown yet interesting and useful patters in datasets. Clustering is considered as unsupervised, however recent years have shown a tendency toward incorporation external knowledge into clustering methods making them semi-supervised methods. Generally, all known types of clustering methods such as partitioning, hierarchical, grid and density-based, have been adapted to use so-called constraints. By means constraints, the background knowledge can be easily used with clustering algorithms which usually leads to better performance and accuracy of clustering results. In spite of growing interest in constraint based clustering this domain still needs attention. For example, a promising relative constraints have not been widely investigated and seem to be very promising since they can be easily represent domain knowledge. Our work is another step in the research on relative constraints. We have used and simplified the approach presented in [1] so that we created a mechanism of using relative constraints as features.
Normally, clustering proceeds in an unsupervised manner. However, in some cases, it is desirable to incorporate external knowledge into a clustering algorihtm. Let us consider the following example. A system designed for analysing customers’ data of a GSM company is going to be built. The purpose of this system is to give managers the ability to detect new groups of customers for which new and customised individual plans could be offered. The number of customers is large and each of them can be described by the great number (thousands) of attributes. In order to analyse and cluster the dataset any clustering algorithm that is capable of dealing with large and high dimensional datasets can be applied. However, the company employs a number of experinced analysts which know the market and can give invaluable insights into the system. The question is how to easily incorporate analysts’ knowledge into clusteiring algorithms so that it could enrich the clustering results.
One of the ways of incorporating external knowledge into clustering
algorithms is to use so-called constraints [
Incorporation of of just few constraints of above type can increase clustering
accuracy as well as decrease runtime [
In [
Dei;j = Dbi;j +
∑
c=1:::N
αDi(;cj),
where Dbi;j is the matrix created by adding must-link constraints to the original
distance matrix Di;j , α is used to scale distance space from ( 1, 1) interval to
( α, α) (α is the longest distance in Di;j ), Dei;j is the matrix constructed by
adding Di(;cj) matrices to it, where c = 1, ..., N (N is a number of cannot-link
constraints) and each Di(;cj) matrix represents one cannot-link constraint. Di(;cj)
is called the diffusion distance matrix [
Di(;cj) = jvi
vj j, vi = φ(i, c2) φ(i, c1) , φ(i, c2) + φ(i, c1) where c1 and c2 are cannot-link objects in a cannot-link relationship and i is the index of the object in the dataset. φ is the function given by the following formula: φ(x, y) = jΨt(x)
Ψt(y)j, where
Ψt(x) = (λt1ψ1(x), λt2ψ2(x), . . . , λt1ψn(x))T ,
where λit are the eigen values and ψi are the eigen vectors of the input dataset’s
Diffusion Map, n is the number of objects in a dataset and t is a time parameter
which can be determined experimentally [
Diffusion maps are based on the observation that when walking from one
point to another in a dataset, it is more probable to traverse points that are
located nearby than far away. This observation leads to defining the probability of
traversing from point a to b. As described above, in order to use a Diffusion Map,
several computation has to be done. First, the distance matrix needs to be built.
Then, the computed distance matrix has to be normalized by using the sums of
its rows. Next, the spectral decomposition is performed to using eigenvalues and
eigenvectors of the previously normalized matrix. The dimensionality reduction
is performed by omitting the smallest eigenvalues. For this reason diffusion maps
can be used to deal with high dimensional datasets by discovering an underlying
manifold from data and to give a simpler global description of the dataset [
In recent studies relative constraints gain more and more attention due to the
fact that they can easily represent domain knowledge [
Our proposal of using relative constraints comprises the ideas presented by [
Dei;j = Di;j +
∑ r=1:::N αDi(;rj), where r is a set of relative constarints (a set of objects triples).
Further, in our method in order to compute the diffusion distance matrix Di(;rj) of diffusion distances between objects, the following formulas are used: where
Di(;rj) = jvi
vj j, vi = min(φ(i, a) + φ(i, b)) φ(i, c) min(φ(i, a) + φ(i, b)) + φ(i, c) where a, b and c are points which are in a relative relationship abjc. 3
In order to test our method we implemented a framework for performing data
clustering experiments. We have implemented appropriate functions for
computing diffusion distance matrices which were later used in a neighborhood-based
clustering algorithm (NBC) [
In the nearest future we are going to focus to make our method more efficient. Moreover we want to focus on examination of the influence of the t parameter on the quality and efficiency of our method. Additionally we would like to test different core functions used for when determining the Diffusion Map ane check their influence on the results of the clustering.