Axiomatic Analysis of Co-occurrence Similarity Functions
Un-Gu Kang, Mikhail Bilenko, Dengyong Zhou, Christos Faloutsos · 2012
this document are those of the authors and should not be interpreted as representing the official policies, either expressed or implied, of the Army Research Laboratory, the U.S. Government, or other funding parties. The U.S. Government is authorized to reproduce Finding similar items based on co-occurrence data is an important data mining task with applications ranging from recommender systems to keyword based advertising. A number of co-occurrence similarity functions have been proposed based on graph-theoretic, geometric, and statistical abstractions. Despite the variety of existing algorithms, however, there exists no formal methodology for analyzing their properties and comparing their benefits and limitations. At the same time, the wide range of applications and domains where co-occurrence-based similarity functions are deployed limits the conclusiveness of experimental evaluations beyond the narrow task typically considered by each method. This paper proposes an axiomatic approach to analyzing co-occurrence similarity functions. The approach is based on formulating general, domain-independent constraints that well-behaved methods must satisfy to avoid producing degenerate results. Such constraints are derived based on the impact that continuous aggregation of the co-occurrence data is expected to have on absolute or relative similarity estimates. Proposed constraint-based analysis is applied to several representative, popular similarity functions and reveals