Experiment and evaluation

In order to test our system, we used a text collection of 28 sentences. The test set contains four groups of sentences talking respectively about “foxes”, “fruits”, and “cars”. The last set, called rag bag, is composed of topically unrelated sentences. It is used only for control purposes.

Table 7.6. Our test sentences

The system’s task is now to integrate as many messages as possible. This will yield a tree containing as many branches as there are topics, in our case four. At the next cycle, the system will try to create subcategories, i.e. branches are further divided, or, viewed in the opposite direction, messages are clustered in more specific categories (habits, living places, etc., in the fox group). Whether this is feasible depends, of course, on the message elements. Since the function of the control group (the set of topically unrelated sentences) is only to check the system’s accuracy, none of its sentences should appear in any other group than the “control group”.

Once this clustering is done, we can determine the system’s performance by counting the number of sentences assigned properly in the tree. For the evaluation, we used the classical metrics, defining precision, recall and F- measure in the following way:

recall (Number of sentences correctly assigned to the valid cluster/Total number of sentences);

precision (Number of sentences correctly assigned to the valid cluster/ Number of sentences clustered);

f-measure (2/ [(1/precision) + (1/recall)]).

We obtained the following results: 22 out of the 28 sentences are placed in the correct cluster, six occur in the wrong place. For example, the sentences 25 and 27 are both placed in the fruit cluster (topic 2), while they should not. This is due to the fact that our method does not take into account the semantics of the string “apple”, which can refer both to the fruit and to the computer manufacturing company located at Cupertino. The same holds for “wine”, which can be both an alcoholic drink and a fruit.

We have also evaluated our system by further clustering the sentences within each topic based on their similarity. All the sentences of topic 1 are clustered correctly, with sentences 1-4, 2-6 and 5-7 forming three clusters. Sentence 3 is more closely related to the clusters containing 5 and 7 than to any other cluster. All the sentences in group 2 are clustered and two of them (10 and 14) are grouped in a more specific category. However, we do have some problems as some items appear in the wrong place. Sentences 25 and 27 are intruders, dealing with a different topic. Hence, they should not be in this category. The same holds for sentence 9, which is put in the (sub)group of sentences 10 and 14. This is clearly wrong, since it is about the computer company and not about “apple”, the fruit. On the other hand, sentence 11 should be there, i.e. in the same cluster as 10 and 14. Yet it is not. It is placed elsewhere, standing like a loner, which, of course, is a mistake. In topic 3 (cars), all the sentences are clustered correctly, and two sentences (15, 16) are placed in a more specific category. However, the system failed to cluster 19 and 21 together.

Given the above described results, the system has a recall, precision and f-measure of 78.6%, if we consider only the sentences placed in the correct position in the tree. It is interesting to note that some of the sentences placed in the wrong category have a similarity value fairly close to the one of the correct cluster. Actually, most of them have the second highest similarity value. Note also that, at this point, the clusters, i.e. the nodes of the tree, are not labeled. Whether this could be achieved via topic signatures [LIN 00] remains to be shown and is clearly a work for the future.