Short-texts clustering is currently an important research area because of its applicability to web information retrieval, text summarization and text mining. These texts are often available in different languages and parallel multilingual corpora. Some previous works have demonstrated the effectiveness of a discrete Particle Swarm Optimizer algorithm, named CLUDIPSO, for clustering monolingual corpora containing very short documents. In all the considered cases, CLUDIPSO outperformed different algorithms representative of the state-of-the-art in the area. This paper presents a preliminary study showing the performance of CLUDIPSO on parallel Spanish-English corpora. The idea is to analyze how this bilingual information can be incorporated in the CLUDIPSO algorithm and to what extent this information can improve the clustering results. In order to adapt CLUDIPSO to a bilingual environment, some alternatives are proposed and evaluated. The results were compared considering CLUDIPSO in both environments, bilingual and monolingual. The experimental work shows that bilingual information allows to obtain just comparable results to those obtained with monolingual corpora. More work is required to make an effective use of this kind of information.
1
Vast amounts of information are actually available on internet in documents such as news, academic works, web-repositories, etc. many of which are in a short-text format. Document clustering groups automatically a large set of documents into different clusters. In this context, the clustering of short-text corpora, is one of the most difficult tasks in natural language processing due to the low frequencies of terms in the documents.
In document clustering, the information
about categories and correctly categorized
documents is not provided in advance. An
important consequence of this lack of
information is that in realistic document
clustering problems, results can not usually be
evaluated with typical external measures like F
Measure and Entropy, because the 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
and Davies-Bouldin indexes, the Global
Silhouette (GS) coefficient and, new
graphbased measures such as the Expected Density
Measure and the λ-Measure (see
The use of ICVMs has not been limited
to the cluster evaluation stage. Different
ICVMs have also been used as explicit
objective functions that the clustering algorithm
attempts to optimize during the grouping
process. This approach has been adopted,
for example, in CLUDIPSO, a discrete
Particle Swarm Optimizer (PSO) which obtained
in previous work
CLUDIPSO, and other techniques to
∗ This work has been done in the framework of the
VLC/CAMPUS Microcluster on Multimodal
Interaction in Intelligent Systems and it has been partially
funded by the European Commission as part of the
WIQEI IRSES project (grant no. 269180) within the
FP 7 Marie Curie People Framework, by MICINN
as part of the Text-Enterprise 2.0 project
In this work, information from parallel Spanish-English corpora is used in short-text clustering and two main research questions are addressed: 1) how this bilingual information can be incorporated in the CLUDIPSO algorithm, and 2) to what extent this information can improve the clustering results. The first aspect is addressed in Section 2.1, where some modifications are introduced in CLUDIPSO to incorporate information from parallel Spanish-English short-text corpora. The second one is analyzed in Section 3 which includes results of CLUDIPSO with Spanish and English documents (taken separately) and results with approaches that simultaneously consider documents written in both languages.
The remainder of the paper is organized as follows. Section 2 describes CLUDIPSO, the PSO-based algorithm under study and the proposed alternatives to bilingual document clustering. Section 3 describes some general features of the corpora used in the experiments, the experimental setup and the analysis of the results obtained from the empirical study. Finally, some general conclusions are drawn and present and future work is discussed in Section 4. 2
CLUDIPSO (CLUstering with a DIscrete
Particle Swarm Optimization), is based on
a PSO
In the discrete version CLUDIPSO, each valid clustering is represented with a particle. The particles are n-dimensional integer vectors, where n is the number of documents in the corpus. Since the task was modeled with a discrete approach, a new formula was developed for updating the positions (shown in Equation (3)).
parid = pbid (3) where parid is the value of the particle i at the dimension d and pbid is the best position reached by the particle i until that moment. This equation was introduced with the objective of accelerate the convergence velocity of the algorithm (principal incoming of discrete PSO models). It is important to note that in this approach the process of updating particles is not as direct as in the continuous case (basic PSO algorithm). In CLUDIPSO, the updating process is not carried out on all dimensions at each iteration. In order to determine which dimensions of a particle will be updated the following steps are performed: 1) all dimensions of the velocity vector are normalized in the [0, 1] range, according to the process proposed by
Hu et al.
A Dynamic mutation operator
max cycle
Where max pm and min pm are the
maximum and minimum values that pm can take,
max cycle is the total number of cycles and
the current cycle in the iterative process is
current cycle. The mutation operation is
applied if the particle is the same that its
own pbest, as was suggest by
Global Silhouette (GS) Coefficient was used as an objective function f (pi), because gives a reasonable estimation of the quality of the obtained groups. The optimization of GS drives the entire CLUDIPSO process. The GS measure combines two key aspects to determine the quality of a given clustering: cohesion and separation. Cohesion measures how closely related are the objects in a same 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 for determining the silhouette coefficient of any arbitrary object i, that we will refer as s(i) and that is defined as follows: s(i) =
b(i) − a(i) max(a(i), b(i)) (4) 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 for this coefficient values as close to 1 as possible are desirable. 2.1
CLUDIPSO adaptations to
bilingual contexts
The idea of using bilingual information in
a clustering algorithm is motivated by
similar reasons to those giving origin to
ensemble methods
CLUDIPSO allows to combine this kind of information in a relatively direct way: using the values that the evaluation function obtains with the documents in each language, and combining these values using different criteria. For example, the minimum (MIN), maximum (MAX) or average (AVG) value between the evaluation function’s values obtained with the documents in each language could be used. Or simply taking the value that the evaluation function returns with documents in both languages, but alternating in each iteration the language used to evaluate this function. More formally: Let D be a bilingual environment (parallel corpus) with Spanish-English documents. Then, each document di ∈ D will be represented by an English text, diEN and the corresponding representation of di in Spanish language, diES . Let DEN and DES be the documents in D in its English and Spanish representation respectively.
We will denote as CLU DIP SOMULT I the CLUDIPSO version that incorporates DEN and DES information in the clustering process. CLU DIP SOMULT I uses the available bilingual information by adapting the CLUDIPSO evaluation function step (see section 2). The four alternatives that were considered to incorporate the bilingual information in the evaluation function are described below.
Let p be a particle representing a possible solution (clustering) and let f (pen) and f (pes) be the fitness values of p with respect to DEN and DES respectively. Then, the fitness value for: 1. CLU DIP SOMULT I−MAX is defined as: f (p) = max(f (pen), f (pes)). 2. CLU DIP SOMULT I−MIN is defined as: f (p) = min(f (pen), f (pes)). 3. CLU DIP SOMULT I−AV G is defined as: f (p) = f(pen)+f(pes) .
2 4. CLU DIP SOMULT I−ALT in the iteration i is f (pen) if i is odd and f (pes) in other case.
Thus, for example, if the Silhouette Coefficient is used as evaluation function, CLU DIP SOMULT I−AV G will use as fitness value the average value obtained from the Silhouette value for the clustering pi using the English documents in D and the Silhouette value for the same clustering, but using in this case the Spanish documents. 3
For the experimental work, two collections with different levels of complexity with respect to the size, length of documents and vocabulary overlapping were selected: SEPLNCICLing and JRC-Acquis. Table 1 shows some general features of these corpora: corpus size (CS), number of categories and documents (|C| and |D| respectively), total number of terms in the collection (|T |), vocabulary size (|V|) and average number of terms per document (T d).
The first one, SEPLN-CICLing, is a small
collection based on CICLing-20021 scientific
abstract corpus which has been intensively
used in different works
The SEPLN-CICLingEN corpus was composed by the English abstracts of CICLing2002 and SEPLN. The SEPLN-CICLingES was obtained adding to the Spanish version of SEPLN abstracts the manual translation of the CICLing abstracts.
1http://www.cicling.org/2002/ 2http://www.sepln.org/
JRC-Acquis refers to a sub-collection of the
Acquis
Corpora SEPLN-CICLingEN SEPLN-CICLingES JRC-AcquisEN JRC-AcquisES Corpora SEPLN-CICLingEN SEPLN-CICLingES JRC-AcquisEN JRC-AcquisES
Due to the fact the gold standard is known for each of the two sub-collections, the quality of the results was evaluated by using the classical (external) F -measure. Each algorithm generated 50 independent runs per collection after performing 10,000 iterations (stopping condition). The reported results in Table 2, correspond to the minimum (Fmin), maximum (Fmax) and average (Favg ) F -measure values obtained by the different the algorithm of CLUDIPSO. The values highlighted in bold, indicate the best obtained results. it is observed that the version CLU DIP SO− EN obtained the best Favg value and CLU DIP SOMULT I the best Fmax value. Similar results can be observed with the Fmin values in both cases. It should be noted that CLU DIP SOMULT I slightly overcomes the algorithm CLU DIP SO − ES but not the CLU DIP SO − EN although both algorithms have a similar performance no matter the language used.
With respect to the obtained results with the larger collection JRC-Acquis, CLU DIP SOMULT I gets similar values to CLU DIP SO−EN and a minimum improvement compared to CLU DIP SO − ES (like in SEPLN-CICLing). It should be noted that CLU DIP SOMULT I improves Fmin in all the cases, excluding CLU DIP SOMULT I−ALT . Experiments carried out show an improvement related to CLU DIP SO − ES but results are similar to CLU DIP SO − EN . However, in JRC-Acquis results needs to be improved for both languages. 4
This work presents a preliminary study of performance of different versions of CLU DIP SOMULT I , a novel bilingual PSObased clustering algorithm. The results obtained by CLU DIP SOMULT I on SpanishEnglish corpora indicate that the approach is an alternative to solve bilingual clustering of small short-text corpora, although no significant improvement was obtained so far with respect to the monolingual PSO-based version CLUDIPSO. CLU DIP SOMULT I was also tested with a larger size collection and the performance was comparable to its predecessor monolingual CLUDIPSO, possibly the lack of improvement it is due to the limitations derived by a wide search space in large document collection.
Future works include text-enrichment of documents, combining both documents representations by using a term selection technique and also, including bilingual information into a novel on going version named CLU DIP SO⋆ considering newer mechanisms to incorporate the bilingual knowledge.
The proposed algorithm was tested with Spanish-English corpora although other bilingual corpora could be used in a future.
In order to tackle the problem of the size of the particle that CLU DIP SOMULT I suffers with collection such as JRC-Acquis, we aim at investigating the possibility of dividing the particle in two: a part of the particle would deal with the representation in English and the other one with the Spanish representation.