CLUSTERING OF WEB DOCUMENTS USING A GRAPH MODEL
Adam Schenker, Mark Last, Horst Bunke, Abraham Kandel · Series in machine perception and artificial intelligence · 2003
In this chapter we enhance the representation of web documents by utilizing graphs instead of vectors. In typical content-based representations of web documents based on the popular vector model, the structural (term adjacency and term location) information cannot be used for clustering. We have created a new framework for extending traditional numerical vector-based clustering algorithms to work with graphs. This approach is demonstrated by an extended version of the classical k-means clustering algorithm which uses the maximum common subgraph distance measure and the concept of median graphs in the place of the usual distance and centroid calculations, respectively. An interesting feature of our approach is that the determination of the maximum common subgraph for measuring graph similarity, which is an NP-Complete problem, becomes polynomial time with our graph representation. By applying this graph-based kmeans algorithm to the graph model we demonstrate a superior performance when clustering a collection of web documents.