Technical reports are an invaluable resource of information. They represent the work that is carried on by students or researchers in short periods of time. In order to maintain the organization of collections, this paper discusses how the structure and the terms of the collection can be used to select the best cluster for a new technical report. The collection is represented as a lightweight ontology which is a hierarchical structure that clusters similar documents in such a way that the documents of a k -level cluster share the k -terms of the cluster label. The ontology is used to get syntactic and semantic measures.
Technical reports are an invaluable resource of information. Some common criteria to organize these documents are by number, date, department or author. An organization based on the content is less frequent.
For small collections, the organization of documents by content could be done manually by domain experts, but for large collections, document clustering techniques are commonly used. These techniques depend of diverse factors as the domain, the format and the representation of documents. Some collections have privacy politics that avoid the free access to documents but they allow users to query the titles, the abstracts and maybe the list of references or cites.
At the Universidad Polit¶ecnica de Puebla, teachers and students maintain a collection of technical reports called CORTUPP (Colecci¶on de Reportes T¶ecnicos de la Universidad Polit¶ecnica de Puebla 3). Technical reports show the work of students and teachers in short periods of time (approximately eight months).
CORTUPP collection is represented as a lightweight ontology. The term
lightweight indicates that the construction of the ontology requires minimum human
3 CORTUPP collection is available at http://server3.uppuebla.edu.mx/cortupp/index.html
participation, it is often limited to the assignment of values for input parameters
of an ontology learning method [
In the ¯eld of digital libraries, ontologies have been used in tasks such
integration of information, interoperability on metadata and communication level,
search and browsing of digital collections, or description of resources [
An ontology creates a machine-accessible data model. The method used to
construct the ontology (called the OntOAIr method) has previously described
in [
The ontology is a hierarchical structure of disjoint clusters of similar documents. Although the construction time of the ontology is linear with respect to the number of documents, when this number is large, the construction can become a time consuming task. This paper discusses how the structure, the terms of a collection and the ontology can be used to select the best cluster for a new technical report. We propose the best cluster algorithm (BC algorithm) for this purpose and the CORTUPP collection as a test bed. The algorithm allows users to insert new technical reports to avoid the reconstruction of the ontology. In general, the algorithm can also be perceived as a simple strategy to maintain the organization of any collection of documents that is represented as a lightweight ontology.
The remainder of the document is organized as follows. Section 2 presents the related work. Section 3 summarizes the ontology learning method called OntOAIr, which is used to construct the ontology that represents the collection of technical reports. Section 2 and Section 3 correspond to previous work of the ¯rst two authors. The following sections describe new contributions. Section 4 presents the algorithm to ¯nd the best cluster for a new technical report. Section 5 discusses preliminary results. Finally, Section 6 includes conclusions and suggests future directions of our work. 2
There are relevant works that formally have analyzed the similarity between
abstracts and documents such as [
OntoLearn is an ontology learning method that applies a hierarchical
algorithm to a set of documents from dedicated web sites and document warehouses
[
The authors of [
Another group [
The authors of [
We have developed an ontology learning method called OntOAIr. It uses
simpli¯ed representations of documents, an adaptation of the Frequent Itemset-based
Hierarchical Clustering algorithm (FIHC)[
The OntOAIr method is universal in the sense that it can be used for di®erent domains, languages and applications. The four main tasks of this method are the following: (1) harvesting, (2) representation, (3) clustering and (4) formalization. These tasks are brie°y described as follows: 3.1
The harvesting task obtains the documents from collections. Collections typically have hundreds or thousands of abstracts that would need to be transmitted through the network. For this reason, we assume that harvesting is an asynchronous task. 3.2
The representation task constructs a vectorial representation called feature vector
for each harvested document. The name is adopted from [
The clustering task applies the Frequent Itemset-based Hierarchical Clustering
algorithm (FIHC) to produce a tree of clusters. FIHC is an agglomerative
clustering algorithm proposed by [
The formalization task transforms the tree of clusters into a lightweight
ontology. We have explored the use of XML, RDF and OWL languages to represent
the ontologies constructed by the OntOAIr method. We have analyzed the use
of these languages in [
The ontologies constructed by the OntOAIr method are hierarchical structures that cluster similar documents in such a way that the documents of a k -level cluster share the k -terms of the cluster label. As a way of illustration, Figure 1 shows a small ontology produced by the OntOAIr method. The boxes contain a term of the cluster labels. At the ¯rst level, the ontology has three main clusters and three labels, processing, robotics and simulation, respectively. At the following levels, the clusters represent more specialized topics. For example, the processing cluster is divided into two clusters, each one with the following labels: images processing and language processing. The language processing cluster includes the natural language processing cluster which belongs to the third level, and so on. Note that the boxes only contains a term of the label, however, the terms of its ancestors are also part of the cluster label.
The ontology is a hierarchical structure, therefore common operations such as insertion, elimination or search of an element can be implemented. The next section describes how this structure can be used to select the best cluster for a new document. 4
The BC algorithm uses the ontology constructed by the OntOAIr method to select the best cluster for a new technical report. We believe that the terms of cluster labels de¯ne a vocabulary that describes the topics.
The algorithm assumes that the ontology has been constructed previously. Before processing, stop words and any case sensitivity are removed from the new document. The algorithm uses the following notation. 4.1
{ A technical report tr of m terms is represented as a tuple tr (t1; t2; :::tm) where m is the number of terms. { The length of tr denoted by length(tr ) is m, the number of terms of tr { An ontology of records is represented as O { l(c) indicates that l is the label of the cluster C { S(tr,l) denotes the similarity function between a technical report tr and a cluster label l { CL(l) denotes the level of the cluster with label l in the ontology { Lc is a list of clusters 4.2
The BC algorithm input: tr : a new technical report, O : an ontology of records output: bc, the best cluster for tr begin 1. Determine the set C of clusters c of level 1 such that ti == l(c), 8 1 · i · m // select the clusters at the ¯rst level such that their label coincide with a term of the new technical report 2. For each c 2 C do { Add the label l of each descendent of c (concatenating the labels of ancestor clusters) to the list of labels Lc 3. For each label l 2 Lc do
{ Apply S(tr, l) 4. Find the cluster in Lc with the highest S(tr, l), bc 5. Return bc
The function to measure the similarity between a label l of the cluster c and a technical report tr(t1; t2; :::; tm) is the following:
S(tr; l(c)) =
X w(ti) ti if ti == l(c), 8 1 · i · m where w(ti) represents the weight of the i -term of tr de¯ned as follows: w(ti) = 8 1:5 if ti appears in the title and abstract of tr ><> 1:0 if ti only appears in the title of tr
0:5 if ti only appears in the abstract of tr > >: 0:0 if ti do not appear in the title neither in the abstract of tr Two notes about the BC algorithm are the following: { There is not a formal criteria that explains the assigned values to the weights of the terms of a technical report. We propose these values experimentally assuming that a term in the title is more representative than a term in the abstract. { The BC algorithm applies the similarity function S(tr; l) only to cluster labels because in the construction process of the ontology, the terms of the labels are the most representative terms of the collection. 4.3
The BC cluster can be used to estimate the similarity between a new technical report (ntr ) and the elements of the BC cluster (tr's). The purpose of this task is to identify duplicated documents. If all the terms of a document are also included in the new technical report and their weight is the same, then the new technical report should not be inserted into the collection.
We assume that each element tr of BC and the new technical report (ntr ) are represented as tuple of terms: tr (t1; t2; :::tm) and ntr (n1; n2; :::nk), respectively. The function to measure the similarity between a tr and ntr hS(tr, ntr) is the following: hS(tr, ntr) = length(tr) ¤ 100 length(ctr) ; where length(ctr) is the number of terms in ntr that are also in tr. The hS(tr, ntr) function assumes that the terms of a tr in the BC cluster are more representative than the terms in the new technical report, thus, new terms of ntr are discarded.
This section presents an algorithm to ¯nd similar technical reports called FSTR algorithm.
input: ntr : a new technical report, BC cluster output: Astr, an array with the titles, identi¯es and a value that represents the similarity between ntr and the technical reports of the BC cluster begin 1. For each tr 2 BC do { Apply hS(tr, ntr) { Construct an object str formed by the title of tr, its identi¯er and the value or hS(tr, ntr) { Insert str to the array of str objects Astr 2. Find in Astr the tr with the highest value of hS(tr, ntr)
5
The OntOAIr method is used to construct an ontology for the CORTUPP
collection with the following input parameters: minimum support 20%, cluster support
25% and global support 5%. The values of these parameters were experimentally
determined in [
The constructed ontology has the following characteristics: { Number of nodes at the ¯rst level: 9 { Number of levels: 4 { Number of clusters: 17 { Total number of documents: 32
We propose two experiments to validate the BC algorithm:
We randomly select 10 of 32 documents of di®erent clusters. Each selected document was manually removed from the ontology and then it was considered a new technical report. The best cluster was found in seven cases correctly (70%), however there were three cases (30%) where the best cluster identi¯ed was an ancestor of the original cluster.
We propose a human validation for the identi¯cation of the best cluster using
the cluster labels of the ontology. We required the participation of four persons,
each one read the title and the abstract of 4 di®erent technical reports. We
requested to these persons to select the most appropriate label related with the
title and abstract that they had read. We use the categories proposed by [
The results of experiment 2 are the following: 40% answers were correct, 30%
were identi¯ed as somehow related, 10% as incorrect and 20% as cannot tell. The
performance of BC algorithm is estimated using the following formula [
A test bed system called (Best Cluster system (BCS)) has been implemented to provide users with an environment to carry on the following tasks: (1)
6
In this paper, we proposed an algorithm to select the best cluster in a collection represented as an ontology. We have described the ontology learning method that constructs the ontology and we have presented the ontology structure using XML language.
The BC algorithm applies a similarity function only to cluster labels. It is appropriate for collections where the number of clusters is ¯xed or when the organization of clusters has been validated. However, for a large number of new documents, the reconstruction of the ontology would be recommended.
The output of the BC algorithm can be used to estimate the similarity between a new technical report and the documents of the best cluster. This task can be interpreted as a simple plagiarism mechanism.
We have constructed a prototypical system that implements the BC algorithm and we have presented preliminary results using the CORTUPP collection as the data set.
The BC algorithm can be applied to any collection that can be represented as an ontology constructed by the OntOAIr method. We expect that the algorithm supports e±ciently the maintenance of collections.