Clustering structured data: Assessing the similarity of documents that appear in tree structure

Question

Usually when performing text document clustering, similarities across documents are assessed based on the lexical content of documents. But, in my problem, I wish to consider both the lexical content and the ontology of documents while assessing similarities. I'll explain this with an example.

I have documents arranged in a tree structure as in the figure below. . Here, lets say, documents admod and customevent (leaf nodes) have a lexical similarity X (X is a real number). It could be noticed that these documents lie close to each other in the tree. Lets say, their distance in the tree is Y. Hence, while assessing similarity between these 2 documents, I wish to have

Similarity (admod, customevent) = f(X,Y), where f is an appropriate function (mapping)

Extending this example further, say the documents admob and Task Manager (root node) bear the same lexical similarity X. It could be observed that these 2 documents lie far apart in the tree. Say, they are Z units apart (where Z > Y), then, I require the similarity function to satisfy the following constraint,

Similarity (admod, customevent) > Similarity (admod, Task Manager)

as admob & customevent lie closer in the tree.

Please suggest on how to combine (include) the tree structure while assessing the similarities.

NOTE: The tree structure is inferred through domain expertise.

Answer 1

Disclaimer: This is not a statistical answer but in my opinion is more relevant to your question.

The tree structure can be regarded as an 'ontology', with the boxes in your figure forming 'classes'. You can have a read about it here.

Now, what you want to achieve is to find how relevant/distant two classes in the ontology are. This is also termed forming an ontology-based semantic similarity measure. This paper is a good introduction. Note that these people use the Web Ontology Language (OWL) to encode their ontologies. If you are interested, OWL is definitely the best language to go for.

On the topic of mixing lexical similarity and semantic similarity (ontological distance), these people have developed an ontological mapping tool which uses these two criteria. However, if you are not familiar with ontologies at all, it may be a hard read.

Finally, after re-reading your quesiton you mention domain expertise, inference, etc. So I guess you may be familir with ontologies. In that case, as a practical tip: there are semantic reasoners for OWL that can give you the distance between two classes.