2 Background

2.1 The silhouette coefficient

In realistic document clustering problems, information about categories and correctly categorized documents is not provided beforehand. An important consequence of this lack of information is that results cannot usually be evaluated with typical external measures like the F-Measure (FM) (van Rijsbergen Reference van Rijsbergen1979) or the entropy (Shannon Reference Shannon1948; Zhao and Karypis Reference Zhao and Karypis2004), because ‘correct’ categorizations specified by a human expert are not available. Therefore, the quality of the resulting groups is evaluated with respect to structural properties expressed in different Internal Clustering Validity Measures (ICVMs). Classical ICVMs used as cluster validity measures include the Dunn (Dunn Reference Dunn1974; Bezdek and Pal Reference Bezdek and Pal1995) and Davies–Bouldin (Davies and Bouldin Reference Davies and Bouldin1979) indexes, the Global Silhouette (GS) coefficient (Rousseeuw Reference Rousseeuw1987; Kaufman and Rousseeuw Reference Kaufman and Rousseeuw1990) and new graph-based measures such as the Expected Density Measure and the λ-Measure (Stein, Meyer zu Eissen and Wißbrock Reference Stein, Eissen and Wißbrock2003).

Most of researchers working on clustering problems are familiar with the use of these unsupervised measures of cluster validity as cluster validation tools. However, some recent works have proposed other uses of this kind of measures that include the hardness estimation of corpora for document clustering problems (Pinto and Rosso Reference Pinto and Rosso2007; Errecalde, Ingaramo and Rosso Reference Errecalde, Ingaramo and Rosso2008) and its use as objective functions in optimization-based clustering methods (Selim and Alsultan Reference Selim and Alsultan1991; Zhao and Karypis Reference Zhao and Karypis2004; Cagnina et al. Reference Cagnina, Errecalde, Ingaramo and Rosso2008; Ingaramo et al. Reference Ingaramo, Errecalde, Cagnina and Rosso2009).

Among the considerable number of ICVMs proposed up to now, the GS coefficient has shown good results as cluster validation method with respect to other well-known validity measures (Brun et al. Reference Brun, Sima, Hua, Lowey, Carroll, Suh and Dougherty2007). Furthermore, the silhouette coefficient has also shown its potential for determining the optimal number of groups in a clustering problem (Rousseeuw Reference Rousseeuw1987; Tan et al. Reference Tan, Steinbach and Kumar2005; Choi et al. Reference Choi, Tan, Anandkumar and Willsky2011), estimating how difficult a corpus is for an arbitrary clustering algorithm (Errecalde et al. Reference Errecalde, Ingaramo and Rosso2008), computing a target function to be optimized (Cagnina et al. Reference Cagnina, Errecalde, Ingaramo and Rosso2008; Ingaramo et al. Reference Ingaramo, Errecalde, Cagnina and Rosso2009), automatically determining a threshold for a similarity function (Bonato dos Santos et al. Reference Bonato dos Santos, Heuser, Pereira Moreira and Krug Wives2011) and as a key component in other internal process of clustering algorithms (Aranganayagi and Thangavel Reference Aranganayagi and Thangavel2007; Errecalde et al. Reference Errecalde, Ingaramo and Rosso2010; Ingaramo et al. Reference Ingaramo, Errecalde and Rosso2010a).

The GS coefficient combines two key aspects to determine the quality of a given clustering: cohesion and separation. Cohesion measures how closely related are objects in a cluster whereas separation quantifies how distinct (well-separated) a cluster from other clusters is. The GS coefficient of a clustering is the average cluster silhouette of all the obtained groups. The cluster silhouette of a cluster C also is an average silhouette coefficient but, in this case, of all objects belonging to C. Therefore, the fundamental component of this measure is the formula used to determine the silhouette coefficient value of any arbitrary object i, that will be referred as s(i) and it is defined in (1).

(1) \begin{equation} s(i)= \frac{b(i)-a(i)}{max(a(i),b(i))} \end{equation}

with − 1 ⩽ s(i) ⩽ 1. The a(i) value denotes the average dissimilarity of the object i to the remaining objects in its own cluster, and b(i) is the average dissimilarity of the object i to all objects in the nearest cluster. From this formula, it can be observed that negative values for this measure are undesirable and that we want for this coefficient values as close to 1 as possible. Thus, for example, in Figure 1, two silhouette graphics representing clusterings of very different quality are shown. The graphic on the left shows that most of s(i) values are near to 1, indicating an adequate membership level of nearly all elements to their assigned groups (high-quality clustering); on the other hand, the graphic on the right clearly shows a low quality clustering with a significant number of elements with low and negative values of s(i).

Fig. 1.

Silhouette graphics. Examples of good and bad clusterings.

In Section 3, it will be shown that silhouette coefficient information of a grouping not only is an appealing device to clearly visualize aspects related to the quality of groups; it can also be a fundamental tool to determine the order in which the documents of a grouping should be considered in the Sil–Att method proposed in this work.Footnote ¹

2.2 An attraction-based comparison

Iterative clustering approaches like AntTree (Azzag et al. Reference Azzag, Monmarche, Slimane, Venturini and Guinot2003), K-means (MacQueen Reference MacQueen1967) and K-medoids (Kaufman and Rousseeuw Reference Kaufman and Rousseeuw1990) progressively add documents in different groups until all the documents have been considered (as Sil–Att does). These approaches have a prototype-based view of how this group should be selected in order to add a document. In this view, each cluster has associated an object (prototype) which will be used as a representative for the group being built. Thus, if p_j denotes the prototype of the cluster j, the document d will be incorporated in the group m whose prototype p_m is the most similar to d. It is important to notice that this prototype-based comparison has been used in classical clustering algorithms like K-means and K-medoids which take a ‘center-based’ view of prototypes, considering as representative of the cluster the centroid (K-means) and the medoid (K-medoid). It is also present in new ‘biological’ clustering approaches in which the role of prototypes (or representatives) are accomplished by ‘creatures’ with some particular characteristics like the ants connected to a support in the AntTree (Azzag et al. Reference Azzag, Monmarche, Slimane, Venturini and Guinot2003) algorithm.

An alternative view to this prototype-based approach, and the one used in Sil–Att, is to estimate the similarity between the document d being processed and the potential clusters where this document can be added, taking into account all the documents that have already been incorporated in the cluster instead of a prototype of this cluster. In that way, each group can be considered as exerting some kind of ‘attraction’ on the documents to be clustered. This idea of ‘attraction’ was already posed in Stein and Meyer zu Eissen (Reference Stein and Meyer zu Eissen2002), where it was used as an efficient way of obtaining ‘dense’ groups. In the present work, we will give a more general sense to the concept of attraction by considering that the ‘attraction level’ that a group $\mathscr {G}$ exerts on an arbitrary document d, can be computed by any plausible estimation of the quality of the group that would result if d were incorporated to $\mathscr {G}$ . This intuitive idea of ‘attraction’ is formalized in the following definition.

2.2.1 Attraction of a group

Let $\mathscr {G}$ be a group (set) of documents and d be an arbitrary document. Let $\mathscr {D}$ be the universe of possible documents to be considered. The attraction of a group $\mathscr {G}$ on the document d, denoted as att( $\mathscr {G}$ , d) is a mapping att: $2^{\mathscr {D}} \times \mathscr {D} \rightarrow \mathbb{R}$ such that if att( $\mathscr {G}$ , d)= a, $a \in \mathbb{R}$ is an estimation of the quality of the group $\mathscr {G} \cup \lbrace$ d}.

To compute att( $\mathscr {G}$ , d), any ICVM that allows to estimate the quality of individual clusters can be applied to $\mathscr {G} \cup \lbrace$ d}. An effective attraction measure (and the one used in this work) is the average similarity Sim between d and all the documents in $\mathscr {G}$ as shown in (2).

(2) \begin{equation} att({\mathscr {G}}, d) = \frac{\sum _{d_i \in \mathscr {G}} Sim(d,d_i)}{|\mathscr {G}|} \end{equation}

The next section shows how the silhouette coefficient and the idea of attraction can be combined in a simple and effective method for text clustering.

3 The Sil–Att method

The Sil–Att is a simple and effective technique for text clustering that could also be used in more general clustering scenarios. The main idea behind this method is the combined use of silhouette coefficient information of a given clustering, with the incremental generation of groups based on the attraction that each group exerts on the document being clustered.

Figure 2 gives a concise description of the main steps involved in the Sil–Att algorithm. It starts considering an initial clustering $\mathscr {C}$ , which can be given by the user or some previous clustering process (Sil–Att as a boosting method) or automatically generated by a random clustering process (random_initial_cluster()) when no clustering is provided as input ( $\mathscr {C}$ =NULL). In the first case, Sil–Att will attempt to improve the quality of the clustering supplied by the user (or other clustering algorithm). In the second one, Sil–Att will act as an independent clustering algorithm which will only require the initial grouping generated by random_initial_cluster(). Currently, this procedure is only intended to generate random (uniformly distributed) clusterings based on the set of documents and the number of groups (k) specified by the user.Footnote ² However, other more elaborated approaches that also allow to specify non-uniform probability distributions for the different groups would be valid alternatives.

Fig. 2.

The Sil–Att algorithm.

Once the initial clustering ${\mathscr {C}}$ is determined, three main processes take place in Sil–Att: (1) the generation of initial singletons, (2) the generation of the ${\mathscr {L}}$ list and (3) the incremental clustering process.

In the first process, the documents in each group $C_i \in {\mathscr {C}}$ are sorted according to their silhouette coefficient values, from highest to lowest. Then, the document d_i with the highest silhouette coefficient value of each group is selected as the initial representative of the C_i group, and a singleton ${\mathscr {G}}_i = \lbrace d_i\rbrace$ is generated for each $C_i \in {\mathscr {C}}$ . After that, the ${\mathscr {L}}$ list with the remaining documents is generated considering again the silhouette coefficient information previously computed. The idea in this process is to take one document from each ordered queue in ${\mathscr {Q}}^{\prime \prime }$ following a round-robin policy, until all the queues are empty. Since the documents of each ordered queue are taken from head to tail, we can assure that the order that two documents had in an ordered queue $q \in {\mathscr {Q}}^{\prime \prime }$ will be preserved in the resulting combined ${\mathscr {L}}$ list. However, the silhouette coefficients of two documents taken from two different groups will not necessarily be in decreasing order in ${\mathscr {L}}$ . As it was observed in some previous works related to our proposal (Azzag et al. Reference Azzag, Monmarche, Slimane, Venturini and Guinot2003; Ingaramo et al. Reference Ingaramo, Errecalde and Rosso2010b), the order in which these documents are later considered (determined by the ${\mathscr {L}}$ list) can directly affect the resulting clusters. For instance, in Sil–Att, the way the ${\mathscr {L}}$ list is generated favors a good ‘mixture’ of good representatives of each group in the first positions of ${\mathscr {L}}$ and a balanced number of documents in each group in the initial iterations of Step 3. In that way, when the ‘difficult’ documents (the ones with a low silhouette coefficient) need to be assigned to a particular group, this decision is made taking into account an acceptable and balanced number of the ‘best’ documents of each group (according to the silhouette coefficient).

Finally, the third process generates the new groups of the clustering by iteratively considering each document in ${\mathscr {L}}$ and placing this document in the most appropriate group. The decision of which of all the available groups will be considered as the most appropriated to include a current document $\hat{d}$ is based on the attraction level that each group exerts on $\hat{d}$ . More formally, $\hat{d}$ will be incorporated in the group ${\mathscr {G}}^+$ , such that

(3) \begin{equation} {\mathscr {G}}^+ = \arg \max _{{\mathscr {G}}_i} att({\mathscr {G}}_i,\hat{d}). \end{equation}

Once the previous process has finished, the last step in the algorithm consists in determining whether the resulting group will be returned as final result of Sil–Att or it will be used as input clustering for a new execution of Sil–Att. The boolean stop_condition() function performs this decision considering for that task the initial clustering ( ${\mathscr {C}}$ ) and the recently generated one ( ${\mathscr {C}}^\star$ ).

As can be seen in Figure 2, two main aspects need to be specified by the user of Sil–Att: (i) the type of use of Sil–Att (as boosting method or as independent clustering method); and (ii) the criterion to be used in the stop_condition() function.

With respect to the first point, this is simply determined by providing a NULL argument to Sil–Att when it must operate as a clustering method. From now on, this case will be denoted as Sil–Att(NULL). On the other hand, if Sil–Att is intended to improve a clustering ${\mathscr {C}}_{Alg}$ obtained with some arbitrary clustering algorithm Alg, this usage of Sil–Att as boosting method will be denoted as $Sil\mbox{--}Att({\mathscr {C}}_{Alg})$ .

The criterion used in the stop_condition() function to determine whether Sil–Att must continue iterating or not is another relevant aspect. The most simple alternative consists in making this function always return a constant True value. In that case, Sil–Att will execute only one improvement processing step on an initial clustering ${\mathscr {C}}$ . This use of Sil–Att will be denoted from now on as $Sil\mbox{--}Att({\mathscr {C}})^1$ . Another alternative implementation for stop_condition() consists in using a general stop criterion that will be usually based on the recently generated clustering ( ${\mathscr {C}}^\star$ ) and the previous one ( ${\mathscr {C}}$ ). In this case, the usual criterion, and the one used in the present work, will consist in stopping the process when no change of elements among different groups is observed. However, other more general criteria could also be used; a simple alternative, for example, would consist in executing the process a maximum number of iterations m specified by the user. When stop_condition() is implemented in that way, Sil–Att will iteratively perform an arbitrary number of improvement processing steps on an arbitrary initial clustering ${\mathscr {C}}$ , until stop_condition() returns True. This iterative operating mode of Sil–Att will be denoted as $Sil\mbox{--}Att({\mathscr {C}})^\star$ .

From the above discussion, it is clear that Sil–Att can operate in four distinct operation modes, which result from the combination of both aspects:

1. (1) Sil–Att(NULL)¹: Sil–Att operates as an independent clustering algorithm that only performs one improvement step.

2. (2) Sil–Att(NULL)*: Sil–Att operates as an independent clustering algorithm which iteratively improves the clustering generated in the previous iteration until stop_condition() holds.

3. (3) $Sil\mbox{--}Att({\mathscr {C}}_{Alg})^1$ : Sil–Att improves a clustering ${\mathscr {C}}_{Alg}$ , previously obtained with some arbitrary clustering algorithm Alg, performing only one improvement step.

4. (4) $Sil\mbox{--}Att({\mathscr {C}}_{Alg})^\star$ : Sil–Att takes a clustering ${\mathscr {C}}_{Alg}$ obtained with some arbitrary clustering algorithm Alg, and iteratively improves the clustering generated in the previous iteration until stop_condition() holds.

It is interesting to note that Sil–Att (and particularly the Sil–Att()* variants) has some similarities with classical iterative clustering approaches such as K-means (MacQueen Reference MacQueen1967), or K-medoids (Kaufman and Rousseeuw Reference Kaufman and Rousseeuw1990; Ng and Han Reference Ng and Han1994). These algorithms start with some initial points representing the K different groups and strive to successively improve the existing set of clusters by changing these ‘representative’ objects (or prototypes). Classical prototypes are those most centrally located within their clusters such as the centroids (in K-means) or the medoids (in K-medoids). In that way, the task of finding K clusters in these iterative prototype-based approaches can be simply understood as the task of determining an appropriate representative object for each cluster (Ng and Han Reference Ng and Han1994).

Sil–Att also tries to improve the clustering obtained in a previous iteration but its manner of operating is completely different with respect to the way these algorithms work. First of all, Sil–Att is an iterative method but it cannot be considered a prototype-based approach. Algorithms like K-means or K-medoids decide which cluster a document should be added to, by only considering the distance of the document to the nearest prototype of each cluster. The Sil–Att method instead, considers the attraction that the whole current groups exert on the object being considered. This implies that, unlike prototype-based approaches which keep the prototypes fixed while the objects are being compared, the attraction of the different groups in Sil–Att changes as new documents are added to these clusters. This means that the order in which the objects are considered in the step 3 of Figure 2 (determined by the $\mathscr {L}$ list) can directly affect the resulting clustering of each iteration of the algorithm.

The above comment shows a key difference between Sil–Att and the iterative prototype-based approaches. Our proposal based on the silhouette coefficient not only determines which will be the first elements that the initial groups will have, it also determines the order in which the remaining documents will be considered and hence the resulting clustering in each iteration. This aspect is not usually considered in prototype-based approaches which only focus on methods to obtain good initial prototypes (or ‘seeds’) (Hasan et al. Reference Hasan, Chaoji, Salem and Zaki2009; Paterlini, Nascimento and Traina Jr. Reference Paterlini, Nascimento and Traina2011) and only consider how to update the prototypes in each iteration.

The computational complexity of the Sil–Att algorithm can be analyzed in terms of the number of documents n to be clustered and the number of iterations required for the convergence I.Footnote ³ The main steps involved in the process carried out by Sil–Att algorithm are detailed as follows:

Step 1: The creation of the similarity matrix takes $\frac{(n) * (n - 1)}{2}$ . Then, this step uses $T_{Step1}: \frac{(n^2 - n)}{2}$ .

Step 2: Computation of the silhouette coefficients takes $\frac{(n) * (n - 1)}{2}$ . Then, this step takes $T_{Step2}: \frac{(n^2 - n)}{2}$ .

Step 3: Sorting of documents takes n*logn. Then, step 3 uses T _Step3 : n*logn.

Step 4: Merging process to generate the $\mathscr {L}$ list takes n. Then, T _Step4 : n.

Step 5: The cluster determination takes $\frac{(n) * (n - 1)}{2}$ . Then, this step uses $T_{Step5}: \frac{(n^2 - n)}{2}$ .

The similarity matrix is generated only once by computing the similarity for each pair of documents in the collection. This is possible for static corpus clustering tasks although for dynamic text collections, a different and more efficient (lower computational cost) implementation should be used. See Conclusions section for more details. Steps 2 to 5 are repeated I times, then the total computational complexity of Sil–Att is $T_{Sil-Att}: T_{Step1} + I * (T_{Step2}+T_{Step3}+T_{Step4}+T_{Step5}) = \frac{n^2-n}{2} + I*n^2 + I*n*\log n$ which is $\mathscr {O}$ (n ²).

4 Experimental setting and analysis of results

For the experimental work, fourteen corpora with different levels of complexity with respect to the size, length of documents and vocabulary overlapping were selected: Micro4News, EasyAbstracts, SEPLN-CICLing, CICLing-2002-A, CICLing-2002-F, R4, R6, R8-, R8+, R8B, JRC6, R8-Test, JRC-Full and R8-Train. Table 1 shows some general features of these corpora: corpus size expressed in Kbytes, number of categories and documents ( $|\mathscr {C}|$ and $|\mathscr {D}|$ respectively), total number of term occurrences in the collection ( $|\mathscr {T}|$ ), vocabulary size ( $|\mathscr {V}|$ ) and average number of term occurrences per document ( $\overline{\mathscr {T}}_{d}$ ). RH, which stands for Relative Hardness (Pinto and Rosso Reference Pinto and Rosso2007), is a specific measure which aims at estimating how related the topics corresponding to the different categories of the grouping are, that is, how difficult a corpus would be for a general clustering task. An alternative to estimate this aspect consists in using a simple vocabulary overlapping calculation among the vocabularies of the distinct categories of the corpus. Different set overlapping measures could be used for this purpose and, in the present work, the Jaccard coefficient among the vocabularies of the categories was used, resulting in the following definition: let $\mathscr {C}$ a corpus with n categories Cat ₁, . . ., Cat_n . The Relative Hardness of $\mathscr {C}$ , $RH(\mathscr {C})$ , is defined in (4).

(4) \begin{equation} RH({\mathscr {C}}) = \frac{1}{n*(n-1)/2} * \sum _{j,k = 1;j<k}^n sim(Cat_j,Cat_k) \end{equation}

where each category Cat_j is considered as the ‘document’ obtained by concatenating all the documents in Cat_j and the similarity (sim) between two categories Cat_j, Cat_k , is calculated as (5) shows.

(5) \begin{equation} sim(Cat_j,Cat_k)=\frac{|Cat_j \bigcap Cat_k|}{|Cat_j \bigcup Cat_k|} \end{equation}

The first five corpora (Micro4News, EasyAbstracts, SEPLN-CICLing, CICLing-2002-A, CICLing-2002-F) are small corpora with the same number of documents (48) and categories (4). These data sets were intensively used in different works (Alexandrov, Gelbukh and Rosso 2005; Errecalde et al. Reference Errecalde, Ingaramo and Rosso2008; Ingaramo et al. Reference Ingaramo, Errecalde, Cagnina and Rosso2009; Popova and Khodyrev Reference Popova and Khodyrev2011) that focused on specific characteristics of the corpora such as document lengths and its closeness respect to the topics considered in these documents. However, other features such as the number of groups and number of documents per group were maintained the same for all corpora in order to obtain comparable results. Although these studies were limited in general to small size corpora, this decision allowed a meticulous analysis of the features of each collection used in the experiments and a detailed understanding of the results obtained in each case that would be difficult to achieve otherwise with larger standard corpora. Three of these corpora (EasyAbstracts, SEPLN-CICLing and CICLing-2002-A) correspond to short-length documents (scientific abstracts) that mainly differ in the closeness among the topics of their categories. Thus, the EasyAbstracts corpus with scientific abstracts on well-differentiated topics can be considered a medium complexity corpus, whereas the CICling-2002-A corpus with narrow domain abstracts is a relatively high complexity corpus. This corpus, generated with abstracts of articles presented at the CICLing 2002 conference is a well-known short-text corpus that has been recognized in different works (Makagonov, Alexandrov and Gelbukh 2004; Alexandrov et al. Reference Alexandrov, Gelbukh, Rosso, Montoyo, Muñoz and Métais2005; Pinto, Benedí and Rosso 2007; Cagnina et al. Reference Cagnina, Errecalde, Ingaramo and Rosso2008; Errecalde et al. Reference Errecalde, Ingaramo and Rosso2008; Ingaramo et al. Reference Ingaramo, Pinto, Rosso and Errecalde2008, Reference Ingaramo, Errecalde, Cagnina and Rosso2009; Popova and Khodyrev Reference Popova and Khodyrev2011) as a very difficult corpus. The remaining two small corpora, Micro4News and CICLing-2002-F, have longer documents than the previous ones, but Micro4News contains documents about well-differentiated topics (low complexity) whereas CICLing-2002-F and CICLing-2002-A have very related categories (high complexity).

Table 1.

Features of the corpora used in the experimental work: corpus size (CS) in Kb, number of categories ( $|\mathscr {C}|$ ), number of documents ( $|\mathscr {D}|$ ), total number of term occurrences ( $|\mathscr {T}|$ ), vocabulary size ( $|\mathscr {V}|$ ), average number of term occurrences per document ( $\overline{\mathscr {T}}_{d}$ ) and Relative Hardness (RH)

The next five corpora (R4, R6, R8-, R8+, R8B) are subsets of the well-known R8-Test corpus, a subcollection of the Reuters-21578 dataset. These corpora were artificially generated in order to consider corpora with a different number of groups: four groups for R4, six groups for R6 and eight groups for R8B, R8- and R8+. R8B maintains the same groups as R8-Test but the number of documents per group does not significantly differ and it is more balanced. The last two eight-groups corpora differ in the lengths of their documents: R8- contains the shortest documents of R8-Test (approximately a twenty per cent of the documents in each group) whereas R8+ contains the largest documents of the same collection.

JRC6 refers to a sub-collection of JRC-Acquis (Steinberger et al. Reference Steinberger, Pouliquen, Widiger, Ignat, Erjavec, Tufis and Varga2006), a popular corpus with legal documents and laws corresponding to different countries of the European Union. JRC6 consists of six groups of the original JRC-Acquis’s about well-differentiated topics.

Finally, the last three corpora were used to test the performance of the algorithms in order to study their capabilities when dealing with larger amount of documents. The complete versions of R8-Test and R8-Train corpora were considered in this work. Also, a larger version of JRC6 corpus named JRC-Full containing a larger amount of short documents (in fact, all the short texts of six categories) was considered.Footnote ⁴

As it can be observed from the previous description, most of the corpora used in the experimental work correspond to corpora with short documents. In fact, we are particularly interested in this kind of corpora because they constitute the most challenging scenario for text clustering as it has been recognized in different works (Makagonov et al. Reference Makagonov, Alexandrov and Gelbukh2004; Alexandrov et al. Reference Alexandrov, Gelbukh, Rosso, Montoyo, Muñoz and Métais2005; Banerjee, Ramanathan and Gupta Reference Banerjee, Ramanathan and Gupta2007; He et al. Reference He, Chen, Xu and Guo2007; Pinto et al. Reference Pinto, Benedí and Rosso2007; Carullo, Binaghi and Gallo Reference Carullo, Binaghi and Gallo2009; Hu et al. Reference Hu, Sun, Zhang and Chua2009; Cagnina et al. Reference Cagnina, Errecalde, Ingaramo and Rosso2008; Errecalde et al. Reference Errecalde, Ingaramo and Rosso2008; Ingaramo et al. Reference Ingaramo, Pinto, Rosso and Errecalde2008, Reference Ingaramo, Errecalde, Cagnina and Rosso2009). However, in order to study if the results obtained with Sil–Att can be generalized to other more traditional corpora (with longer documents), other corpora such as Micro4News, CICLing-2002-F and JRC6 with lengths between 1,600 and 2,600 terms per document (in average) were also considered.

The documents were represented with the standard (normalized) tf-idf codification after a stop-word removing process. The popular cosine measure was used to estimate the similarity between two documents.

The results of Sil–Att were compared with those obtained by other five clustering algorithms: K-means (MacQueen Reference MacQueen1967), K-MajorClust (Stein and Meyer zu Eissen Reference Stein and Meyer zu Eissen2002; Ingaramo et al. Reference Ingaramo, Errecalde and Rosso2010a), Chameleon (Karypis, Han and Kumar Reference Karypis, Han and Kumar1999), CLUDIPSO (Cagnina et al. Reference Cagnina, Errecalde, Ingaramo and Rosso2008) and sIB (Slonim, Friedman and Tishby Reference Slonim, Friedman and Tishby2002). These algorithms have been used in similar studies and are representative of different algorithmic principles of clustering. K-means, is a classical exemplar-based iterative algorithm and is probably one of the most popular clustering algorithms. MajorClust can be classified as a density-based algorithm with a cumulative attraction approach (Stein and Meyer zu Eissen Reference Stein and Meyer zu Eissen2002; Stein and Busch Reference Stein and Busch2005). K-MajorClust (Ingaramo et al. Reference Ingaramo, Errecalde and Rosso2010a), the variant used in this work, is based on the MajorClust algorithm but it was modified to generate exactly K groups. This modification allowed to make its results comparable to those obtained by the other algorithms which always generate clusterings with K groups. Chameleon is a graph-based clustering algorithm that is considered a good alternative when the clusters have different shapes, sizes and density (Tan et al. Reference Tan, Steinbach and Kumar2005). CLUDIPSO, a discrete Particle Swarm Optimization algorithm, is a meta-search algorithm which explicitly attempts to optimize a global criterion (objective function) that estimates the quality of clusterings. Previous works (Ingaramo et al. Reference Ingaramo, Errecalde, Cagnina and Rosso2009; Cagnina et al. Reference Cagnina, Errecalde, Ingaramo and Rosso2014) have showed the potential of CLUDIPSO when the GS coefficient was used as function to optimize, obtaining the best results in experiments with the four small size short-text corpora described at the beginning of this section: Micro4News, EasyAbstracts, SEPLN-CICLing and CICling-2002-A. The parameter settings for CLUDIPSO and the algorithms previously cited used in the comparisons correspond to the parameters empirically derived in Ingaramo et al. (Reference Ingaramo, Errecalde, Cagnina and Rosso2009). The sequential clustering algorithm sIB (Slonim et al. Reference Slonim, Friedman and Tishby2002) is based on the Information Bottleneck method. This popular approach finds clusters such that the mutual information between documents and clusters is maximized in a sequential update process as K-means does. The parameter setting for sIB corresponds to that proposed in Slonim et al. (Reference Slonim, Friedman and Tishby2002) and selecting the adequate k value depending on the amount of the groups of each collection. Regarding the computational complexity of the algorithms evaluated in the experimental study, K-means is lineal in the amount of documents, that is $\mathscr {O}$ (n) (Manning, Raghavan and Schutze Reference Manning, Raghavan and Schutze2008) and $\mathscr {O}$ (n ²) for CHAMELEON (Karypis et al. Reference Karypis, Han and Kumar1999), CLUDIPSO (Cagnina et al. Reference Cagnina, Errecalde, Ingaramo and Rosso2014) and Sil–Att. K-MajorClust is based on MajorClust algorithm but uses exactly K clusters. As the computational complexity of MajorClust (Karthikeyan, Peter and Chidambaranathan Reference Karthikeyan, Peter and Chidambaranathan2011) does not depend on the number of the groups, we conclude that the latter two have similar computational complexity, that is, $\mathscr {O}$ (n ²). Comparing all computational complexities, we conclude that all algorithms excepts K-means (the lowest) have similar computational complexity.

The quality of the results was evaluated by using the classical (external) F-measure on the clusterings that each algorithm generated in fifty independent runs per collection.Footnote ⁵ The reported results correspond to the minimum (F_min ), maximum (F_max ) and average (F_avg ) FM values. All the comparisons between Sil–Att and the other algorithms used in the experiments were carried out on the basis of statistical significance criteria. We first analyze in Section 4.1 the performance of Sil–Att as boosting method. Then, in Section 4.2, the results obtained by Sil–Att as an independent clustering algorithm are analyzed.

4.1 Sil–Att as a boosting method

In the experimental work, the first analyzed aspect was the Sil–Att’s performance as boosting method. Considering the Sil–Att() algorithm shown in Figure 2, that means to compare the result (clustering) ${\mathscr {C}}_{Alg}$ obtained with some arbitrary clustering algorithm Alg, and the result ${\mathscr {C}}_{Sil\mbox{--}Att({\mathscr {C}}_{Alg})}$ obtained with Sil–Att() when ${\mathscr {C}}_{Alg}$ was used as input clustering. Two instances of the Sil–Att() algorithm were considered in the experiments with respect to the stop_condition() function: (i) $Sil\mbox{--}Att({\mathscr {C}}_{Alg})^1$ , where stop_condition() always returns True and, in consequence, Sil–Att() executes only one boosting processing step on the clustering ${\mathscr {C}}_{Alg}$ received from Alg; and (ii) $Sil\mbox{--}Att({\mathscr {C}}_{Alg})^\star$ which iteratively performs an arbitrary number of boosting processing steps, until stop_condition() returns True; in this work, it occurs when no difference is observed between the clustering obtained in the current iteration and the obtained in the previous one ( ${\mathscr {C}}^\star$ and ${\mathscr {C}}$ of Figure 2).

In order to keep notation as simple as possible when comparing an arbitrary method Alg and the improvements obtained by Sil–Att(), the results of $Sil\mbox{--}Att({\mathscr {C}}_{Alg})^1$ will be directly referred as Alg ¹, and those obtained with $Sil\mbox{--}Att({\mathscr {C}}_{Alg})^\star$ as Alg*. Thus, for example, when K-means is the method to be compared, the results obtained with $Sil\mbox{--}Att({\mathscr {C}}_{K-\mbox{means}})^1$ will be denoted as K-means¹, and those obtained with $Sil\mbox{--}Att({\mathscr {C}}_{K-\mbox{means}})^\star$ as K-means*.

Tables 2–5 show the F_min, F_max and F_avg values that K-means, K-MajorClust, Chameleon and CLUDIPSO obtained with the first eleven corpora.Footnote ⁶ These tables also include the results obtained with Sil–Att()¹ and Sil–Att()* taking as input the groupings generated by these algorithms. The values highlighted in bold indicate the best obtained results.

Table 2.

Sil–Att()¹ and Sil–Att()* as boosting method: F-measure values for Micro4News, EasyAbstracts and SEPLN-CICLing corpora

Table 3.

Sil–Att()¹ and Sil–Att()* as boosting method: F-measure values for CICLing2002-F, CICLing2002-A and JRC6 corpora

Table 4.

Sil–Att()¹ and Sil–Att()* as boosting method: F-measure values for R8B, R8- and R8+ corpora

Table 5.

Sil–Att()¹ and Sil–Att()* as boosting method: F-measure values for R4 and R6 corpora

These results show the good performance that Sil–Att can obtain with text collections with very different characteristics. With the exception of the F_avg and F_min values obtained with CICling2002-F and the F_max value of JRC6, it achieves the highest F_min, F_avg and F_max values for all the corpora considered in our study, by improving the clusterings obtained with different algorithms. Thus, for instance, Sil–Att()* obtains the highest F_avg value for R8+ by improving the clusterings obtained by CLUDIPSO and the highest F_max value for EasyAbstracts by improving the clusterings obtained by K-means and K-MajorClust. It can also be appreciated in these tables that both versions of the boosting algorithm, Sil–Att()¹ and Sil–Att()*, obtain in most of the cases considerable improvements on the original clusterings. Thus, for example, the F_avg value corresponding to the clusterings generated by K-means with the Micro4News collection (F_avg = 0.67), is considerably improved by Sil–Att()¹ (F_avg = 0.84) and Sil–Att()* (F_avg = 0.9).

Another important aspect that can be analyzed in the previous results is the performance comparison between the iterative approach of Sil–Att (Sil–Att()*) and the approach with only one execution of the algorithm (Sil–Att()¹). Here, the benefits of using the iterative approach seem to be evident, with a better performance of Sil–Att()* on Sil–Att()¹ in most of the considered experimental instances. As an example, when Sil–Att()* took as input the clusterings generated by K-means, its results were in most of the cases consistently better than those obtained by Sil–Att()¹ with the same clusterings, on the eleven considered corpora. The only exception is the F_max value of Sil–Att()* with JRC6 (0.59) which is worse than the F_max value obtained by Sil–Att()¹ (0.6) and even than the one obtained by K-means (0.64). However, it is worth noting that, despite the fact that Sil–Att()¹’s results are in general not as good as those obtained by Sil–Att()*, the differences between both algorithms are very small and Sil–Att()¹ also shows a competitive performance with respect to the other four algorithms. In fact, if Sil–Att()* were kept out of our analysis, Sil–Att()¹ would become the algorithm with the highest F_min, F_avg and F_max values in all the experimental instances, except in the same three cases previously mentioned where neither Sil–Att()* nor Sil–Att()¹ can outperform the remaining algorithms.

The previous discussion about the very good performance of Sil–Att()¹ is not a secondary aspect. It offers evidence that the combination of the silhouette coefficient and the attraction concept can be a powerful tool that, in only one step, can achieve significant improvements on the original clusterings. Thus, it can be seen that it is possible to use Sil–Att as a relatively inexpensive mechanism that can obtain very competitive results in only one improvement step. However, if higher quality results are required, it can keep iterating with high chances of improving the obtained performance. In the rest of this sub-section, we will only focus on the results obtained with Sil–Att()* in the comparisons with the other algorithms. However, a similar study could also be carried out using Sil–Att()¹.

In the previously shown results it could be seen that, despite the excellent performance of Sil–Att in almost all experimental instances, there are some few cases where Sil–Att()* does not improve (and it can even slightly deteriorate) the results obtained with Sil–Att()¹ or the initial clusterings generated by the other algorithms. This suggests that, although Sil–Att()* can achieve significant improvements (on average) on all the considered algorithms, and the highest F_min and F_max value obtained on most of the corpora, a deeper analysis is required in order to also consider the particular improvements (or the deteriorations) that this algorithm makes on each clustering that it receives as input. In other words, it would be interesting to analyze how often (and in what extent) we can expect to observe an improvement in the quality of the clusterings provided to Sil–Att()*. Tables 6 and 7 give some insights on this issue, by presenting in Table 6 the improvement percentage (IP) and the improvement magnitude (IM) obtained with Sil–Att()*, whereas Table 7 gives the deterioration percentage (DP) and the deterioration magnitude (DM) that Sil–Att()* produced on the original clusterings. The percentage of cases where Sil–Att()* produced clusterings with the same quality as the clusterings received as input (SQP) can be directly derived from the two previous percentages. Thus, for example, in Table 6 it can be seen that Sil–Att()* produced an improvement in the ninety-two per cent of the cases when received the clusterings generated by Chameleon on the R4 collection, giving FM values which are (on average) a 0.17 higher than the FM values obtained with Chameleon. In this case, the values presented in Table 7 indicate that DP = 7% and DM = 0.02 meaning that in one per cent of the experiments with this algorithm and this collection, Sil–Att()* gave results of the same quality (SQP = 1%).

Table 6.

IP and IM values of Sil–Att()* with respect to the original algorithms

Table 7.

DP and DM values of Sil–Att()* with respect to the original algorithms

With the exception of the Chameleon-SEPLN-CICLing and CLUDIPSO-SEPLN-CICLing combinations, where Sil–Att()* does not obtain significant improvements, the remaining experimental instances show the advantages of using Sil–Att()* as a general boosting method. Thus, for example, on a total of forty-four experimental instances (algorithm-collection combinations), Sil–Att()* obtained over eighty-two per cent of improvements in thirty-eight experimental instances and hundred per cent of improvements in twenty-nine cases. This excellent performance of Sil–Att()* can be easily appreciated in Figure 3, where the IP (white bar), DP (black bar) and SQP (gray bar) values are compared but considering in this case the improvements/deteriorations obtained in each of the eleven corpora.

Fig. 3.

IP, DP and SQP values per collection of Sil–Att()* with respect to the original algorithms.

From the information shown in Tables 6 and 7 and, in Figure 3, it can be concluded that Sil–Att()* shows a remarkable performance in corpora such as Micro4News, R6 and R8B, where it obtains hundred per cent of improvements. However, in corpora such as SEPLN-CICLing, CICLing-2002-A, CICLing-2002-F and JRC6 the obtained DP values indicate that the performance of Sil–Att()* with respect to the other algorithms, although improved, needs to be further investigated. In both cases, a more rigorous analysis about the statistical significance of those results is required.

In this analytical study, the first considered aspect was assessing whether or not the distributional assumptions (independence of observations, normality of sampling distribution and equal variance) required by the analysis of variance ANOVA (Fisher Reference Fisher1925) were violated by the results obtained in the experiments. In this case, the (non-parametric) Levene’s test (Levene Reference Levene1960) showed that the variances obtained in each collection were significantly different and, therefore, the homogeneity of variance assumption was broken in each case.

An alternative approach when the ANOVA’s assumptions are violated, is to use a non-parametric approach analogue to ANOVA such as the Kruskal–Wallis test (Kruskal and Wallis Reference Kruskal and Wallis1952). The results obtained with this test allowed to assert that there were significant differences in the results obtained in the eleven considered corpora. Then, the next step was to apply multiple Tukey’s tests (Tukey Reference Tukey1953; Barnette and McLean Reference Barnette and McLean1998) to determine which were the specific experimental instances where there were significant differences between the results obtained with the original algorithms and those obtained with Sil–Att()*. However, before starting this analysis, it can be useful to analyze some side-by-side boxplots with the best (Figures 4 and 5) and the worst (Figures 6 and 7) results according to the results previously presented in Tables 6 and 7 and in Figure 3.Footnote ⁷ For each collection and arbitrary algorithm Alg considered in the experiments, the boxplots of Sil–Att()* obtained with the initial clusters generated by Alg are shown immediately to the right of the boxplots corresponding to Alg. This allows an easier comparison of Sil–Att()* with respect to the clustering algorithms used to generate its initial groupings.

Fig. 4.

Best results of Sil–Att()* as boosting method. (a) Micro4News. (b) R6.

Fig. 5.

Best results of Sil–Att()* as boosting method. (a) R8B. (b) R4.

Fig. 6.

Worst results of Sil–Att()* as boosting method. (a) SEPLN-CICLing. (b) CICLing-2002-A.

Fig. 7.

Worst results of Sil–Att()* as boosting method. (a) CICLing-2002-F. (b) JRC6.

Our first observation about the boxplots shown in Figures 4 and 5 is that the median values obtained with Sil–Att()* are, in all the corpora and algorithms considered, better than the median values of the original algorithms that provided to Sil–Att()* its initial clusterings. Moreover, the ‘notches’ of the boxplots corresponding to Sil–Att()* never overlap the notches of the boxplots obtained with the original algorithms. In comparisons of boxplot graphics, that is usually considered as a firm evidence of a significant difference between the data being compared. Another important aspect is related to the upper limits of the Sil–Att()*’s boxplots. They all achieve the highest values in all the corpora and algorithms considered showing that Sil–Att()* is able to obtain very high-quality results as boosting method, in corpora with very different characteristics. Finally, it is very interesting to note that in each of the four considered corpora, Sil–Att()* obtains very similar boxplots, independently of the cluster’s quality received as input. This is evident, for instance, in corpora such as R8B where Sil–Att()* obtains very similar boxplots with good quality clusters generated with K-means but also with very bad input clusterings generated with K-MajorClust.

With respect to the boxplots shown in Figures 6 and 7, it is interesting to note that the results which were considered as ‘the worst’ results obtained by Sil–Att()*, actually correspond to situations where Sil–Att()* does not show a significant difference with respect to the original clusterings. This is the case, for example, of the results obtained by CLUDIPSO with SEPLN-CICLing, CICLing-2002-A and CICLing-2002-F, and the K-means’ results with JRC6. In all these cases, it can be appreciated a slightly better (or similar) performance of Sil–Att()*, but it cannot be assured that it clearly outperforms the original algorithms. However, Sil–Att()* still shows significant differences in the remaining algorithm-collection combinations and, in some cases, such as the results obtained by CLUDIPSO with JRC6, the advantages of using Sil–Att()* are evident.

The above graphical results shown in Figures 4–7 were also confirmed by using the Tukey’s test of multiple comparisons which showed significant differences between the performance of Sil–Att()* and the original algorithms except for the CLUDIPSO’s results with the five small size corpora and the K-means’ results with JRC6. In order to analyze this aspect, in Table 8 we show only the cases for which there is not significant difference (that is, p > 0.05). This is not a minor aspect, if we consider that on a total of forty-four possible algorithm-collection combinations, Sil–Att()* outperformed the remaining algorithms with significant differences in thirty-eight cases and, in the remaining algorithms, it obtained better (or comparable) results but they cannot be considered as statistically significant.

Table 8.

Tukey’s tests: (Sil–Att()* versus CLUDIPSO) and (Sil–Att()* vs. K-means). Results with Micro4News, EasyAbstracts, SEPLN-CICLing, CICLing-2002-A,CICLing-2002-F, R4 and JRC6

4.2 Sil–Att as an independent clustering method

The two main concepts that support Sil–Att, the silhouette coefficient information and the idea of attraction, were firstly used in two bio-inspired approaches for improving the clusterings obtained by other algorithms in short-text clustering problems (Errecalde et al. Reference Errecalde, Ingaramo and Rosso2010). Those studies, as well as the results obtained in the previous section, showed some interesting aspects:

1. (1) The approach seems to obtain significant improvements in almost all the considered experimental instances, independently of the particular characteristics of the collection being processed. That behavior can be clearly appreciated in Figures 4–7, where Sil–Att()* consistently improves (or at least maintains) the quality of the input clusterings, and shows competitive results in all the considered corpora.

2. (2) Those previous results also seem to be independent of the clustering algorithms used for generating the input clusterings.

In order to gain a deeper understanding about these aspects, the first addressed issue was analyzing to what extent the quality of the clusterings generated by Sil–Att and the quality of the input clusterings are related. In other words, can we say that the performance of Sil–Att() directly depends on how bad/good the initial clusterings are?

A simple alternative to attempt answering this question consists in considering some correlation measure such as the Spearman Correlation (Spearman Reference Spearman1904) and use it for comparing the quality of the clusterings that Sil–Att receives as input and the quality of the clusterings that it generates as output. This was the study carried out in this work, taking as quality measures the GS coefficient and the popular FM. The correlation study considered all the possible combinations using both quality measures on the input/output clusterings. The Spearman correlation values indicate that we are not able to affirm that a correlation between the quality of the input and output clusterings exists (value < 0.75).

From the previous results, an obvious question that naturally arises is: can Sil–Att obtain acceptable quality results taking as input randomly generated clusterings? That is a crucial aspect because it would become Sil–Att a truly independent clustering algorithm which would not require of another clustering algorithm to generate the initial clusterings. This was the idea that gave origin to the Sil–Att(NULL)¹ and the Sil–Att(NULL)* versions of the Sil–Att() algorithm presented in Figure 2.

In order to analyze how robust Sil–Att is to random initial clusterings, fifty experimental instances of Sil–Att(NULL)¹ and Sil–Att(NULL)* were tested, using as random_initial_cluster() function, a simple process that randomly determines the group of each document (denoted Rand-Clust). The results obtained with Rand-Clust were compared with those of the algorithms considered in the previous section. Tables 9–13 show these results. In those, it is possible to appreciate that Sil–Att(NULL)* is robust despite the low quality of the initial clusterings. In fact, Sil–Att(NULL)* obtained in most of the considered corpora the best F_min, F_max or F_avg values and, in the remaining cases, it achieved results comparable to the best results obtained with the other algorithms. Thus, for example, in eleven corpora it obtained the best F_max value and, in the remaining three corpora, the second best value, with a minimal difference with respect to the best obtained value. In eleven corpora, it obtained the best F_avg value and, in nine of the fourteen corpora it obtained the best F_min value. This last result seems to be one weak aspect of Sil–Att as independent clustering method, due to the low quality clusterings obtained in some cases. However, as can be appreciated in Figures 8–13, the boxplots corresponding to Sil–Att(NULL)* (abbreviated as Sil–Att* for short) show a remarkable performance of this method in eleven of the considered corpora.

Table 9.

Sil–Att(NULL)¹ and Sil–Att(NULL)*’s results for Micro4News, EasyAbstracts and SEPLN-CICLing corpora

Table 10.

Sil–Att(NULL)¹ and Sil–Att(NULL)*’s results for CICLing2002-F, CICLing2002-A and JRC6 corpora

Table 11.

Sil–Att(NULL)¹ and Sil–Att(NULL)*’s results for R8B, R8- and R8+ corpora

Table 12.

Sil–Att(NULL)¹ and Sil–Att(NULL)*’s results for R4 and R6 corpora

Table 13.

Sil–Att(NULL)¹ and Sil–Att(NULL)*’s results for R8-Test, JRC-Full and R8-Train corpora

^a NA: Not Available result.

Fig. 8.

Sil–Att as independent clustering method. (a) Micro4News. (b) EasyAbstracts

Fig. 9.

Sil–Att as independent clustering method. (a) CICLing-2002-A. (b) SEPLN-CICLing.

Fig. 10.

Sil–Att as independent clustering method. (a) R4. (b) R6.

Fig. 11.

Sil–Att as independent clustering method. (a) R8B. (b) JRC6.

Fig. 12.

Sil–Att as independent clustering method. (a) R8-Test. (b) JRC-Full.

Fig. 13.

Sil–Att as independent clustering method.

Following the same procedure that in the previous section, the first considered aspect was assessing whether or not the distributional assumptions required by ANOVA were violated. The Levene’s test values obtained in this case also showed that in all the considered cases, these values were significant and, in consequence, the ANOVA’s assumptions were violated. Therefore, the Kruskal–Wallis test was newly used and the results showed that there were significant differences in the results obtained in the eleven considered corpora. Therefore, the next step was to apply multiple Tukey’s tests to determine which are the specific experimental instances where these differences hold.

The same as in the previous study, the differences between the results obtained with Sil–Att(NULL)* and the other algorithms were statistically significant in most of the considered corpora, clearly outperforming them in thirty-eight of the forty-four possible experimental instances. The values of the six cases where the Tukey’s test did not reveal significant differences are shown in Table 14. In this table, it can be seen that this occurs when Sil–Att(NULL)* is compared to CLUDIPSO in the four small corpora (Micro4News, EasyAbstracts, SEPLN-CICLing and CICLing-2002-A) and in two specific experimental instances where K-means obtains good results with the R4 and JRC6 corpora. Obviously, that do not mean that in these instances CLUDIPSO and K-means outperform Sil–Att(NULL)*, but not significant differences can be observed in these cases, as can also be seen in the boxplots presented in Figures 8–10.

Table 14.

Tukey’s tests: (Sil–Att(NULL)* vs. CLUDIPSO) and (Sil–Att(NULL)* vs. K-means). Results with Micro4News, EasyAbstracts, SEPLN-CICLing, CICLing-2002-A, R4 and JRC6

5 Related work

The use of silhouette coefficient information beyond its role as ICVM has several antecedents in clustering problems. In Errecalde et al. (Reference Errecalde, Ingaramo and Rosso2008) for instance, the evaluation of the GS coefficient and other ICVMs on the ‘gold standard’ of different short-text corpora is proposed as a method to estimate the hardness of those corpora. The GS coefficient has also been used as an explicit objective function that the clustering algorithms attempt to optimize. This idea has recently been used in short-text clustering by using discrete and continuous Particle Swarm Optimization algorithms as function optimizers (Cagnina et al. Reference Cagnina, Errecalde, Ingaramo and Rosso2008; Ingaramo et al. Reference Ingaramo, Errecalde, Cagnina and Rosso2009; Cagnina et al. Reference Cagnina, Errecalde, Ingaramo and Rosso2014). In these works, CLUDIPSO obtained the best results on different short-text corpora when the GS coefficient was used as objective function. This coefficient has also been recognized as a good measure to determine the correct number of clusters in arbitrary data sets (Rousseeuw Reference Rousseeuw1987; Tan et al. Reference Tan, Steinbach and Kumar2005; Choi et al. Reference Choi, Tan, Anandkumar and Willsky2011).

In Bonato dos Santos et al. (Reference Bonato dos Santos, Heuser, Pereira Moreira and Krug Wives2011), an estimation method to automatically determine a threshold for a similarity measure is proposed. It relies on a clustering phase and on the choice of a similarity threshold based on the silhouette coefficient. This work also includes some experimental studies that show that the silhouette coefficient is highly correlated with the (external) FM. The idea of closeness can be an alternative choice to the similarity measure. In Zhou, Cheng and Yu (Reference Zhou, Cheng and Yu2009), a closeness measure is used to perform the clustering of data in networks. The algorithm learns the weights of the edges connecting nodes in the network, during a random walks process and uses them in the clustering process. For the same problem, the algorithm proposed in Qi, Aggarwal and Huang (Reference Qi, Aggarwal and Huang2012) considers that text content is attached to the edges meanwhile in Yang et al. (Reference Yang, Jin, Chi and Zhu2009) the content is attached to the nodes of the network. The approach in Qi et al. (Reference Qi, Aggarwal and Huang2012) implements a matrix-factorization methodology for modeling the content and the structure of a network to be clustered then, by a K-means algorithm. The work proposed in Yang et al. (Reference Yang, Jin, Chi and Zhu2009) uses a two-stage optimization algorithm which combines conditional and discriminative content models for performing the clustering. In opposition to the idea of similarity, in Zhang, Wang and Si (Reference Zhang, Wang and Si2011) the authors proposed to use a universum of documents not belonging to any class, in order to guide the clustering process. The use of that universum as background information avoids mistakes in the selection of the adequate cluster. In Aranganayagi and Thangavel (Reference Aranganayagi and Thangavel2007), a novel algorithm is proposed to cluster categorical data. Objects are grouped into clusters taking into account minimum dissimilarity values. Then, these objects are relocated with a merging process by using the silhouette coefficient.

The idea of attraction can have different interpretations but in this work, it corresponds to the concept described in Stein and Meyer zu Eissen (Reference Stein and Meyer zu Eissen2002); Stein and Busch (Reference Stein and Busch2005), where it is used as a key component of an efficient density-based clustering algorithm (MajorClust). MajorClust derives its density information from the attraction a cluster C exerts on some object q. This attraction is computed as the sum of the similarity values among q and all the objects in C. MajorClust implements density propagation according to the principle ‘maximum attraction wins’.

Another work which combines the idea of attraction and density is proposed in Jiang, Pei and Zhang (Reference Jiang, Pei and Zhang2003). However, it differs from the previous approach (and the one used in Sil–Att) in the way the attraction is computed. Here, the attraction between two objects is based on the density that both objects have and the idea is that objects with high density attract some other objects with lower density.

In Tu and Chen (Reference Tu and Chen2009), D-Stream, a new density-based framework for clustering stream data is proposed. This framework aims at finding clusters of arbitrary shapes. A key component in D-Stream is an attraction-based mechanism which allows to accurately generate cluster boundaries. The algorithm maps each input data into a grid, computes the density of each grid and clusters the grids by using a density-based algorithm. Then, a new concept on the attraction between grids is used in order to improve the quality of density-based clustering.

Sil–Att initially sorts the documents to be clustered and then iteratively adds these documents into the most appropriate group. This idea was also used in two bio-inspired hierarchical clustering algorithms for clustering arbitrary objects (Azzag et al. Reference Azzag, Monmarche, Slimane, Venturini and Guinot2003; Ingaramo, Leguizamón and Errecalde Reference Ingaramo, Leguizamón and Errecalde2005). These works did not consider collections of documents in the experimental work and used a different approach to obtain the initial ordering of the objects to be clustered. Furthermore, the decision on which group an element should be added to, was not made following the attraction idea and only took into account a single ant (object) that played the role of representative of the group.

The first approach in which silhouette coefficient information and the idea of attraction were simultaneously integrated in the same clustering algorithm, is AntSA-CLU (Ingaramo et al. Reference Ingaramo, Errecalde and Rosso2010b). AntSA-CLU is a hierarchical AntTree-based algorithm whose main ideas were taken from Azzag et al. (Reference Azzag, Monmarche, Slimane, Venturini and Guinot2003) but it also incorporated silhouette coefficient information and the idea of attraction as key components in its functioning. AntSA-CLU heavily depended on the initial data partition generated by the CLUDIPSO algorithm. This idea was later generalized and served as antecedent for the approach of using Sil–Att as a general improvement method. In Ingaramo et al. (Reference Ingaramo, Errecalde and Rosso2010a), a simplified and more general version of AntSA-CLU is presented, named Partitional AntSA* (PAntSA*). PAntSA* is the partitional version of the hierarchical AntSA-CLU algorithm where, furthermore, it is not assumed as input the results of any particular clustering algorithm. In that way, PAntSA* takes the clusterings generated by arbitrary clustering algorithms and attempts to improve them by using techniques based on silhouette coefficient information and the idea of attraction.

Finally, ITSA* (ITerative PAntSA*), the iterative version of PAntSA*, is a bio-inspired method which recently obtained interesting results in short-text clustering problems (Errecalde et al. Reference Errecalde, Ingaramo and Rosso2010). ITSA* was also used to cluster documents whose representations were enriched with semantic information (concepts) obtained from knowledge-based disambiguation methods (Ingaramo et al. Reference Ingaramo, Rosas, Errecalde and Rosso2011). The experimental results offered strong evidence that ITSA* is a robust method which can handle different document representations, obtaining competitive results when semantic information was added to these representations. ITSA* is the direct predecessor of the proposal presented in this work, but Sil–Att does not consider any bio-inspired aspects in its functioning in order to keep the proposal as simple and clear as possible. In that way, the present work can be considered as an extension of the ideas proposed in Errecalde et al. (Reference Errecalde, Ingaramo and Rosso2010), presenting a simpler and more efficient algorithm, considering more general corpora and providing a more exhaustive analysis on the statistical significance of the results and the independence of Sil–Att on the quality of the initial clusterings.