Compression-based distance between string data and its application to literary work classification based on authorship

There are many well-known document classification/clustering algorithms. In this paper, compression-based distances between documents are focused on, in particular, the normalized compression distance (NCD). The NCD is a popular and powerful metric between strings. A new distance $$D_\alpha $$ with one parameter $$\alpha $$ between strings is designed on the basis of the NCD, and several properties of $$D_\alpha $$ are studied. It is also proved that every pair of strings $$(x,y)$$ can be plotted on the contour graphs of NCD and $$D_\alpha $$ (and some other compression-based distances) in a 2-dimensional plane. The distance $$D_\alpha (x,y)$$ is defined to take a relatively small value if a string $$x$$ is a portion of a string $$y.$$ Literary works $$x$$ and $$y$$ are usually assumed to be written by the same author(s) if $$x$$ is a portion of $$y.$$ Therefore, it may be appropriate to consider the performance of $$D_\alpha $$ for literary work classification based on authorship, as a benchmark. An algorithm to determine an appropriate value of $$\alpha $$ is presented using the contour graphs, and this algorithm does not require the knowledge of the names of the authors of each work. According to experimental results of the area under receiver operating characteristics curves and clustering, $$D_\alpha $$ with such an appropriate value of $$\alpha $$ performs somewhat better in literary work classification based on authorship. Copyright Springer-Verlag 2013