Clustering is one of most important methods of data mining. It is used to identify unknown yet interesting and useful patterns or trends in datasets. There are different types of clustering algorithms such as partitioning, hierarchical, grid and density-based. In general, clustering methods are considered unsupervised, however, in recent years the new branch of clustering algorithms has emerged, namely constrained clustering algorithms. By means of socalled constraints, it is possible to incorporate background knowledge into clustering algorithms which usually leads to better performance and accuracy of clustering results. Through the last years, a number of clustering algorithms employing different types of constraints have been proposed and most of them extend existing partitioning and hierarchical approaches. Among density-based methods using constraints algorithms such as C-DBSCAN, DBCCOM, DBCluC were proposed. In this paper we offer a new C-NBC algorithm which combines known neighborhood-based algorithm (NBC) and instance-level constraints.
Clustering is one of well-known and often used data mining methods. Its goal is to
assign data objects (or points) to different clusters so that objects that were assigned
to the same clusters are more similar to each other than to objects assigned to another
clusters [
Constraint-based clustering algorithms employ the fact, that in many applications,
the domain knowledge in the form of labeled objects is already known or could be
easily specified by domain experts. Moreover, in some cases such knowledge can be
automatically detected. Initially, researchers focused on algorithms that incorporated
pairwise constraints on cluster membership or learned distance metrics. Subsequent
research was related to algorithms that used many different kinds of domain
knowledge [
The major contribution of this work is the offering of a constrained
neighborhoodbased clustering algorithm called C-NBC which combines the known NBC
algorithm [
This paper is divided into five sections. In Section 1 we have given a brief introduction to clustering with constraints. Next, in Section 2, we shortly describe most known types of constraints and focus on instance-level constraints such as must-link and cannot-link constraints. In Section 3, the Neighborhood-Based Clustering (NBC) is reminded. Further, in Section 4 we present the proposed C-NBC algorithm. Conclusions are drawn and further research is briefly discussed in Section 5. 2
In constrained clustering background knowledge can be incorporated into algorithms
by means of different types of constraints. Through the years, different methods of
using constraints in clustering algorithms have been developed [
Several types of constraints are known, but the hard instance-level constraints seem
to be most useful since the incorporation of just few constraints of this type can
increase clustering accuracy as well as decrease runtime. In [
In the next part of the paper, when referring to must-link and cannot-link constraints, we will use the notations presented in Table 1. 3
The Neighborhood-Based Clustering (NBC) algorithm [
( ) is the set of all points in dataset ; that is, ) ε-neighborhood of point that are distant from by no more than , where is a distance function.
( ) is a set of ( (), in brief) -neighborhood of point ) points satisfying the following conditions: ().
of point ( ) is equal to , where .
brief) Reversed punctured k+-neighborhood of a point ( ) is the set of all points in dataset such that ; that is: .
density factor of a point ( ) is defined as
. (Points having the value of the NDF factor equal to or greater than 1, are considered as dense.)
In order to find clusters, NBC starts with calculating values of factors for each point in a database , . Next, for each , a value of is checked. If it is greater than or equal to , then is assigned to the currently created cluster (identified by the value of ). Next, the temporary variable for storing references to points, is cleared and each point, say , belonging to is assigned to . If is greater than or equal to , then is also added to . Otherwise, is omitted and a next point from is analyzed. Further, for each point from , say , is computed. All unclassified ) -neighborhood points belonging to are assigned to and points having values of greater than or equal to 1 are added to . Next, is removed from . When is empty, is incremented and a next point from , namely , is analyzed. Finally, if there are no more points in having values of factor greater than or equal to 1, then all unclassified points in are marked as NOISE. 4
In this section we offer our new neighborhood-based constrained clustering algorithm
called C-NBC. The algorithm is based on the NBC algorithm [
The C-NBC algorithm employs the same definitions as NBC which are used in a process of clustering to assign points to appropriate clusters or mark them as noise. In NBC three kinds of points can be distinguished: unclassified, classified and noise points. In our proposal, we introduced another kind of points, namely deferred points (Definition 6).
Definition 6. (deferred point) A point is called deferred if it is involved in a cannotlink relationship with any other point or it belongs to a -punctured neighborhood , where is any point involved in a cannot-link relationship.
C-NBC (Figure 1) can be divided into two main steps. In the first step the algorithms works very similarly to NBC. It calculates NDF factors and performs clustering. The difference between C-NBC and NBC is that the former additionally determines deferred points and has to deal with must-link constraints when building clusters. In spite of the fact that in the first step the deferred points are not assigned to any cluster, these points are normally used to calculate NDF factors. In the second step C-NBC works so that it allocates deferred points to appropriate clusters. This is done by means of the AssignDeferredPointsToClusters function (Figure 2) which assigns points to clusters after checking if such an assignment if feasible. The detailed description of C-NBC is provided beneath. The key variables and notations related to C-NBC are explained in Table 2. ,
Description The auxiliary integer variable used for storing currentlycreated cluster’s identifier.
By using such a notation we refer to a related to point .
Such a notation is used to refer to a value of the NDF factor associated with point .
Algorithm C-NBC( , , , ) Input: the input not clustered dataset
the parameter of the C-NBC , the sets of pairs of points connected by must-link or cannot-link constraints Output: The clustered set with clusters satisfying cannot-link and must-link constraints.
; = 0; // initialization of a set of deferred points and label all points in as UNCLASSIFIED; // = UNCLASSIFIED CalcNDF( , ); // calculate values of NDF factor for every point in ┌ for each point involved in any constraint from or do │ label and points in as DEFERRED // label points as DEFERRED │ add to ; // add DEFERRED points to └ endfor // expanding a currently created cluster
The C-NBC algorithm starts with the CalcNDF function. After calculating the NDF factors for each point from D, the deferred points are determined by scanning pairs of cannot-link connected points. Such a points are added to an auxiliary set .
Then, the clustering process is performed in the following way: for each point which was not marked as DEFERRED, it is checked if is less than . If , then is omitted and a next from is checked. If , then as a dense point is assigned to the currently-created cluster identified by the current value of .
Next, the temporary variable is cleared and each not deferred point, say , belonging to is assigned to the currently-created cluster identified by the current value of the variable. Additionally, if , then it is assigned to as well as all dense points which are in a must-link relation with . Function AssignDeferredPointsToClusters( , , , ) Input: the input not clustered dataset the set of points marked as deferred the parameter of the C-NBC algorithm the set of cannot-link constraints Output: The clustered set with clusters satisfying cannot-link and must-link constraints // saving contents of in a temporary set
Next, for each unclassified point from , say , its punctured -neighborhood is determined. Each point, say , which belongs to this neighborhood and has not been labeled as deferred yet is assigned to the currently created cluster and if its value of NDF is equal to or greater than 1, is added to . Moreover, all dense points which are in a must-link relation with are added to as well. Later, s is removed from and next point from is processed. When is emptied, then is incremented.
After all points from are processed, unclassified points are marked as noise by setting the values of their attribute to NOISE. However, in order to process the deferred points, the AssignDeferredPointsToCluster function is invoked. The function performs so that for each deferred point it finds the nearest point assigned to any cluster and checks whether it is possible (in accordance with cannot-link constraints) to assign to the same cluster as . Additionally, the function checks if the assignment of to a specific cluster will not violate previous assignments of deferred points.
In order to test the efficiency of the proposed C-NBC algorithm we performed a
number of basic experiments using the following datasets: a manually created dataset
containing 2800 data points, the known four dimensional iris dataset [
In recent years a number of algorithms employing different kinds of constraints have
been proposed. Most commonly used constraints are instance constraints which are
widely employed in enriching clustering algorithms to utilize additional background
knowledge. However, among density based clustering algorithms, so far only the
DBSCAN algorithm [
In this paper we have offered C-NBC, the density based algorithm for clustering under instance constraints which was based on the known NBC algorithm. Our preliminary experiments, confirm that the algorithm performs in line with the assumptions. In other words, it works so that must-link connected points are assigned to the same clusters and cannot-link connected points are assigned to different clusters. Moreover, for datasets tested, it turns out that constraints have a little effect on the efficiency of the algorithm. In spite of this, in our future research we would like to still focus on performance of constrained based clustering and on proposing other methods of ensuring constraints during clustering process for larger and high dimensional datasets.