In this paper we describe a solution for incorporating background knowledge into the OntoGen system for semi-automatic ontology construction. This makes it easier for different users to construct different and more personalized ontologies for the same domain. To achieve this we introduce a word weighting schema to be used in the document representation. The weighting schema is learned based on the background knowledge provided by user. It is than used by OntoGen's machine learning and text mining algorithms.
When using ontology-based techniques for knowledge management it is important for the ontology to capture the domain knowledge in a proper way. Very often different tasks and users require the knowledge to be encoded into ontology in different ways, depending on the task. For instance, the same document-database in a company may be viewed differently by marketing, management, and technical staff. Therefore it is crucial to develop techniques for incorporating user’s background knowledge into ontologies.
In [
In this paper we propose a method which extends OntoGen system so that the user can supervise the methods for concept discovery by providing background knowledge - his specific view on the data used by the text mining algorithms in the system.
To encode the background knowledge we require from the user to
group documents into categories. These categories do not need to
describe the data in details, the important thing is that they show to the
system the user’s view of the data - which documents are similar and
which are different from the user’s perspective. The process of
manually marking the documents with categories is time consuming but
can be significantly speeded up by the use of active learning [
This paper is organized as follows. In Section 2 we introduce OntoGen system and in Section 3 we derive the algorithm for calculating word weights. We conclude the paper with some preliminary results in Section 4.
OntoGen [
OntoGen discovers concepts using Latent Semantic Indexing
(LSI) [
Both methods heavily rely on the representation of the documents. Namely, the document representation provides the vectors of the documents which LSI tries to approximate and, the basis for clustering algorithm is the similarity of document which also depends on the document representation.
By incorporating background knowledge directly into the document representation via word weighting, reflecting similarity between the documents, we enable our methods to discover concepts which resemble the view that the user has on the data. 3.1
Most commonly used representation of the documents in text mining is bag-of-words representation. Let V = w1, . . . , wn be vocabulary of words. Let T Fk be the number of occurrences of the word wk in the document. In the bag-of-words representation a single document is encoded as a vector x with elements corresponding to the words from a vocabulary, eg. xk = T Fk. These vectors are in general very sparse since the number of different words that appear in the whole collection is usually much larger than the number of different words that appear inside one specific document.
Measure usually used to compare text documents is the cosine similarity and is defined to be the cosine of the angle between two documents’ bag-of-words vectors, sim(xi, xj ) =
Pkn=1 xikxjk pPn k=1 xikxik k=1 xikxikpPn .
(1) Performance of both bag-of-words representation and cosine similarity can be significantly improved by introducing word weights. Each word from vocabulary V is assigned a weight and elements of vectors xi are multiplied by the corresponding weights.
As we already mentioned, our approach is based on the word weights being the key to viewing the same data from different angels. We can use the weights to store the background knowledge since the weights define which words are important. 3.2
Most of the research on word weighting schemas was traditionally done in the information retrieval community. A typical goal in information retrieval is to find the most relevant document from the document collection for a given query. Many popular methods from information retrieval are based on measuring cosine similarity between the documents and a query and their performance can be significantly improved by appropriate weighting of the words.
Most of the popular methods for this task developed in last decades
do not involve learning. Word weights are calculated by predefined
formulas from some basic statistics of the word frequencies inside
the document and inside the whole document collection [
The most widely used is the TFIDF weighting schema [
The intuition behind this weighting schema is that the words which occur very often are not so important for determining if a pair of documents is similar while a not so frequent words occurring in the both documents is a strong sign of similarity. The TFIDF weighting can be easily modified to include category information by replacing IDF and number of documents with ICF and number of categories.
There are many extensions of this schema most famous being
Okapi weighting schema [
As we will see in the next chapter a different approach can also be
taken for generating word weights based on feature selection
methods. Feature selection methods based on Support Vector Machine
(SVM) [
The method proceeds as follow. First linear SVM classifier is trained using all the features. Classification of a document is done by multiplying the document’s bag-of-words vector with the normal vector computed by SVM, xT w = x1w1 + x2w2 + . . . + xnwn, (3) and if the result is above some threshold b then the document is considered positive. This process can also be seen as voting where each word is assigned a vote weight wi and when document is being clasi i as its vote. All the sified each word from the document issues x w votes are summed together to obtain the classification. A vote can be positive (document should belong to the category) or negative (the document should not belong to the category).
A simple and naive way of selecting the most important words for the given category would be to select the words with the highest vote values wi for the category. It turns out that it is more stable to select the words with the highest vote xiwi averaged over all the positive documents.
The votes wi could also be interpreted as word weights since they are higher for the words which better separate the documents according to the given categories. 3.4
The algorithm we developed for assigning weights using SVM feature selection method is the following: 1. Calculate a classifier for each category from the document collection (one-vs-all method for multi-class classification). TFIDF weighting schema can be used at this stage. Result is a set of SVM normal vectors W = {wj ; j = 1, . . . , m}, one for each category. 2. Calculate weighting for each of the categories from its classifier i i weight vector. Weights are calculated by averaging votes x w across all the documents from the category. Only weights with positive average are kept while the negative ones are set to zero. This results in a separate set of word weights for each category.
By μjk we denote weight for the k-th word and j-th category. 3. Weighted bag-of-words vectors are calculated for each document.
Let C(di) be a set of categories of a document di. Elements of vector xi are calculated in the following way:
xik =
X j∈C(di) j μk · T Fk .
(4)
This approach has another strong point. Weights are not only selected so that similarities correspond to the categories given by the user but they also depend on the context. Let us illustrate this on a sample document which contains words ”machine learning”. If the document would belong to category ”learning” then the word ”learning” would have high weight and the word ”machine” low weight. However, if the same document would belong to category ”machine learning”, then most probably both words would be found important by SVM. 4 4.1
As a document collection for testing our method we chose Reuters
RCV1 [
A List with the 10 most frequent categories from the used subset of RCV1 dataset is shown in Table 1. The statistics are for the subset used in the experiments. 4.2
In the Figure 2 are the top 3 concepts discovered with k-means algorithm for both word weighting schemas. Documents are placed also in different concepts. For example, having two documents talking about the stock prices, one at the New York stock-exchange and the other at the UK stock-exchange. The New York document was placed in (1) Market concept (the same as the UK document) and in (2) USA concept (while the UK document was placed in (2) Europe concept).
In this paper we have presented a method for learning document similarity measure trough selecting appropriate word weights for bag-ofwords document representation model. We selected the word weights by training the SVM linear classifier for given categories and than extracting the word weights from the hyper plane normal vector. The learned word weighting schema was used to adjust the concept discovery methods in the OntoGen system to the user’s domain knowledge.
As part of the future work we plan to extend this method to the text categorization task where category information is known only for the documents from training set.
This work was supported by the Slovenian Research Agency and the IST Programme of the European Community under SEKT Semantically Enabled Knowledge Technologies (IST-1-506826-IP), NeOn Networked Ontologies (IST-2004- 27595) and PASCAL Network of Excellence (IST-2002-506778). This publication only reflects the authors’ views.