Hierarchical clustering algorithms create groups of objects in a data set based on their similarity. This similarity is commonly measured by a distance function, which makes the resulting groups dependent on the distance function used and also the technique employed to merge the clusters. In this work, we propose to transform the objects to a representation where each variable is defined by an interval. Using this representation, we define a new method that measures the similarity of the objects variable by variable based on the overlapping of their intervals, instead of using a distance function. The results obtained for each variable are later passed to an aggregation function, which allows comparing the similarity between the pairs of clusters. An example of algorithm is proposed in this work using a binary function to check the overlapping and aggregating its results with the average function. Finally, the method is compared with other approaches by means of two examples.
Clustering methods define how to create groups of objects (also known as clusters) in a data
set. The aim is that the groups contain the most similar objects and, at the same time, they
are as diferent as possible from the objects in other groups [
In the process of creating the groups, classical approaches treat the clusters as points and
measure their similarity by using point-based distances such as the Euclidean distance. In this
work, we propose to transform the data in order to represent the clusters as intervals. In the
literature, some methods based on intervals can be found. For instance, Galdino and Maciel [
This paper is organized as follows. Section 2 gives an overview of the clustering problem and the transformation we apply for an interval-based approach. Section 3 details the two key points introduced into the hierarchical clustering algorithm for creating the clusters using intervals and also presents the proposed algorithm. A comparison with other approaches is presented in Section 4 by means of two examples. Conclusions of this work can be found in the final section.
Let us consider a data set X where each object ∈ X is defined by variables such that = {1 , ..., } with ∈ R, 1 ≤ ≤ . The aim of any clustering algorithm is to group these objects into diferent clusters such that each object belongs uniquely to one cluster and 1 ∪ · · · ∪ = X. As the number of clusters is usually unknown beforehand, hierarchical clustering algorithms use a binary tree structure of levels that groups the objects in X from the bottom of the tree to the top. Therefore, the algorithm defines for each level ℓ of the tree, with 1 ≤ ℓ ≤ , a set of clusters Cℓ = {ℓ1, . . . , ℓℓ}. Following this, the root of the generated tree C1 (which is the last level reached by the algorithm) contains one single cluster with all the elements in X. On the other hand, the bottom level (where the algorithm starts) contains the leaves of the tree, this is, a set of clusters that has as many clusters as objects in the data set, since each of the clusters contains a single object of X. As the tree is built from the bottom (i.e. ℓ equal to the number of objects in X) to the top (i.e. ℓ = 1), in each iteration the clusters in level ℓ are almost the same than the clusters in level ℓ + 1, varying only in the two clusters of ℓ + 1 that are substituted by one in ℓ, corresponding to the cluster generated after merging two most similar clusters in ℓ + 1 into one single cluster in ℓ. The process is repeated iteratively until the root of the tree is reached. After the tree is obtained, the clusters for any number of diferent clusters can be determined by cutting the tree at the corresponding level.
Taking into account that the clustering algorithm seeks for creating groups of similar objects,
it is necessary to define how the similarity between the objects is measured. This is usually
done by means of a distance function and many variations have been proposed in the literature
[
• Distance between two clusters (ℓ, ℓ ) : ℓ, ℓ ∈ Cℓ.
However, as hierarchical clustering algorithms consider that each object belongs to its own
cluster in the first iteration (i.e. the bottom of the tree), all three types of distances could
be generalized as (ℓ, ℓ ). How the distance between two clusters is computed is usually
referred to as linkage method. Depending on the linkage method chosen, the algorithm will
result in diferent sets of clusters [
To sum up, this means that each linkage method represents the cluster by choosing a diferent object of the cluster. Then, using this object as a representation of the cluster, the distance is computed pairwisely and the closest ones are merged together.
In this work, we propose to identify the clusters using intervals instead of one single point. For defining a measure of similarity, we keep in mind the original methods and how the distance between two objects is a particular case of the distance between two clusters. Then, we propose a new hierarchical clustering method based on intervals that substitutes the linkage method by an interval-based function and an aggregation function. By using this method, the distance involving clusters of intervals can be computed by components applying a function to each variable and then using an aggregation function in order to obtain a single value that allows comparing the clusters pairwisely. This comparison is necessary in order to establish which two of the clusters are the most similar and consequently should be merged together into a single cluster.
In order to identify the objects of the data set with an interval-based representation, each object ∈ X is turned into an object ∈ Y such that each component of the object is transformed into a degenerated interval = [, ], where = = . Notice that this is a particular case of a cluster, therefore any cluster can be defined as ℓ = {ℓ1, . . . , ℓ} where ℓ = [ℓ, ℓ] with 1 ≤ ≤ . The data set Y with the transformed representation of all the objects in X is given as input to the clustering algorithm.
Whenever two clusters are merged together, and therefore contain more than one object of the data set, the new cluster is created taking from the two clusters merged the lowest and the greatest endpoints for the interval that represents each variable. Formally, given two clusters ℓ and ℓ , the resulting cluster ℓ− 1ℎ = {ℓ− 1ℎ1, . . . , ℓ− 1ℎ} is built such that ℓ− 1ℎ = [min{ℓ, ℓ}, max{ℓ, ℓ}], 1 ≤ ≤ .
The first step in order to obtain an algorithm based on this interval approach is to define the function used to measure the similarity between two intervals [, ], [, ] ⊆ this function could be defined in multiple forms, here we consider a binary basic approach so R. Although the following function is used to determine whether there is overlapping between the two intervals: ([, ], [, ]) = ︂{ 1 0 otherwise. if [, ] ∩ [, ] ̸= ∅ is possible to obtain the vector ⃗ℓ
The algorithm starts by applying the function (ℓ, ℓ) to each component of the clusters ℓ, ℓ ∈ Cℓ such that ℓ is equal to the number of objects in X and 1 ≤ ≤ . By doing this, it ,ℓ = (ℓ1 ,ℓ , . . . , ℓ ,ℓ ). This vector gives an intuition about what we call the degree of coincidence between the two objects. a single value that eases this pairwise comparison, the elements of ⃗ℓ
After ⃗ℓ ,ℓ has been calculated for all pairs of objects, these must be compared. To obtain ,ℓ are aggregated by means of an aggregation function (⃗ℓ ). For this work, as a first approach, we define simply as the average of the elements in ⃗, such that:
,ℓ (⃗ℓ ,ℓ ) = 1 ∑︁ ℓ =1 ,ℓ .
The two clusters ℓ, ℓ with the greatest value of (⃗ℓ ,ℓ ) are merged together into a cluster. interval ℓ is transformed into:
Notice that, using this basic function, in case that none of the elements of the objects are equal, the overlapping between the initial vectors will be 0 so none of the objects could be grouped together. To solve this, the neighborhood of the interval in each component will be considered taking into account the range of each variable in the original data set. Formally, we can define the vector ⃗ of elements, which associates each value with the -th variable of the data set using the range of the variable in the initial data set X. Prior to the execution of the clustering the algorithm, the percentage of the variable that will be considered for this update is set using , which determines the amount that the interval will be extended in case that there is no overlapping, such that = (max∈X() − min∈X()) × .
Using the coeficient , when there is no overlapping between any of the intervals, the
ℓ = [ℓ − , ℓ + ].
The resulting algorithm obtained from the considerations explained is shown in Algorithm 3.
In order to illustrate the method, an example for a toy data set is presented below. Example 4.1. Let us consider the one-dimensional data set of five objects X = {5, 7, 46, 81, 92}.
In order to apply the proposed method, first of all, it is necessary to transform the data set X
into an interval data set Y by using degenerated intervals. Therefore, the transformed data set
Y = {[
0 0 0 0
2 = [
4 = [81, 81] 0
C5 = {51 = {[
As there are no overlapping between any of the objects, the extremes of the intervals must be updated using 1. The new intervals obtained after subtracting 1 to the left extreme of the interval and adding 1 to the right extreme of the interval are shown below:
After this update, there is an overlapping between the clusters 51 and 52. Therefore, these two clusters are merged together in the next iteration, creating in the upper level of the tree ℓ = 4 the cluster 41. The interval takes the lowest value of the left limit and the greatest value of the right limit of the two clusters that are merged, therefore, 41 = {[3.26, 8.74]}.
The representation of the clusters in the next iteration is given by the set of intervals C4, which contains all the previous intervals and the new cluster created. This set can be defined as: C4 = {41 = {[3.26, 8.74]}, 42 = {[44.26, 47.74]}, 43 = {[79.26, 82.74]}, 44 = {[90.26, 93.74]}}.
After the creation of this new cluster, it is again necessary to update the intervals to increase their extremes until they overlap and a new cluster can be created. As shown in the comparison below, in the first iteration there is no overlap: 41 = [3.26, 8.74] Therefore, 1 must be iteratively applied and after five times, the following clusters are obtained: 41 = [− 1.09, 13.09] 12 3 4 5
According to the values obtained at this point, it is necessary to merge the clusters 43 and 44, which contains the objects 4 and 5 respectively, obtaining the following clusters for the next iteration, must be merged, which corresponds with the following situation in ℓ = 3: 12 3 4 5
Following this procedure and increasing the range of the intervals iteratively using 1, the following overlapping is obtained:
12 3 4 5 Meaning that these are merged together making the two following clusters in ℓ = 2: 12 3 4 5
The last iteration will conclude the method by merging the two remaining clusters together in the root of the tree representation, with one single cluster that contains all the objects in the data set.
On the other hand, for creating the groups using the classical linkage methods, it is necessary to perform a pairwise comparison of the objects in X to compute their distance. The results obtained from this comparison are shown below:
Using this, when the single linkage method is employed, the clusters obtained are the same as the ones with our method (left dendrogram). However, when the complete, average or centroid linkage methods are considered the results are diferent (right dendrogram).
1 2 3 4 5 1 2 3 4 5
The one-dimensional version of the algorithm yields the same results that the single linkage method using Euclidean distance. Intuitively, it is natural that in one dimension the results are the same than using this binary function as, the closer the objects are, the sooner they will overlap. However, the single method is only equivalent to our method in the case of objects with one dimension. A counterexample showing that this is not the case when the number of variables increases is shown below.
Example 4.2. Here we present a counterexample using a data set where the objects are defined with two variables: age and height. This shows that our method is diferent from single linkage using Euclidean distance in the case when the number of the variables is greater than one. Let us consider the following data set (left) and the corresponding pairwise distance between the objects of the data set (right): 1 2 3
According to the Euclidean distance, the most similar objects in the bottom level of the tree (i.e. ℓ = 3) are 1 and 2. This means that these two objects are merged into one single cluster 21 in the upper level ℓ = 2. Then, the third object 3 will be merged with this cluster in an upper level of the tree, creating the single cluster in the root 11 that contains all the objects. On the other hand, with our method, we obtain a diferent result. First of all, let us transform the data set into a data set Y of degenerated intervals (shown below on the table). The individual results of each pairwise comparison of the objects after applying the function to each variable are shown in the tables below. Then, the aggregation function is applied to each pairwise comparison, such that the table Average is obtained. The objects 1 and 3 are the most similar according to the first approach so these would be merged together first.
So using this method, on the contrary to what happened using the single linkage method with the Euclidean distance, the objects 1 and 3, (which represent the original 1 and 3) form 21. This makes the clusters in ℓ = 2 be diferent than the ones obtained before.
As illustrated in the previous examples, classical methods based on distances require comparing all the pairs of objects in the cluster. On the contrary, with the proposed method, this matrix is reduced in each step which benefits the implementation of the algorithm as well as its suitability to be applied in practice to large problems. Furthermore, using the basic function that we are considering in this work, the Boolean matrix used is more eficient and less memory space is needed to store the comparison.
1 2 3
Age [10,10] [11,11] [10,10]
Height [140,140] [150,150] [170,170] 1 1
1 Age 2 3 0 2 1 0
Height 2 3 0 2 0 0
Average 2 0 2 3 1/2 0
In this work, a new hierarchical clustering method based on grouping intervals has been proposed. This method provides an approach that uses a coincidence function as well as an aggregation function, which means that can be extended by changing these parts in order to explore diferent properties of the created groups. Future work will include the exploration of diferent aggregation functions in order to create the groups.
This research has been partially supported by Spanish MINECO projects TIN2017-87600-P (Noelia Rico and Irene Díz) and PGC2018-098623-B-I00 (Pedro Huidobro and Susana Montes). Pedro Huidobro and Noelia Rico are alspp supported by the Severo Ochoa predoctoral grant program by the Principality of Asturias (PA-20-PF-BP19-169 and PA-20-PF-BP19-167, respectively).