Similarity to a Single Set
Lee Naish
Identifying similarities in data is fundamental to discovery in
science. Measuring or ranking similarity is a key way of reducing
the dimensionality of data, is at the heart of many data intensive
algorithms and can also be used directly for some applications. This
paper extends our understanding of a relatively simple similarity problem.
Our
primary application is spectral based fault localisation (SBFL), in
which a computer program is run with a large number of test cases and
data is collected on which statements are executed in each test case.
For each statement, the set of test cases in which it is executed is
compared to the set of test cases that failed and this is used to rank
the statements to help locate bugs, an instance of what we call the
similarity to a single set (STASS) problem. This paper is primarily
theoretical but some contributions are validated with SBFL experiments.
Set similarity is equivalent to similarity
of binary vectors or two by two contingency tables. The problem is also
equivalent to converting two-dimensional data with a "partial order",
such as points on a rectangular grid, to a one-dimensional total order.
Even when the raw data is not binary we are often interested in
comparing binary classifiers for the data, such as diagnostic tests,
and comparing binary classifiers is an instance of the STASS problem.
More than a hundred set similarity measures have been proposed in the
literature and hundreds of thousands have been evaluated for SBFL but
there is very little understanding of how best to choose a similarity
measure for a given domain. This work discusses numerous properties
and forms of symmetry that similarity measures can have. It refines
previously identified properties so they are no longer incompatible,
identifies new forms of symmetry, defines ordering relations over
similarity measures and proposes a new statistic that can be used to
help choose a good similarity measure for a given domain.
Keywords:
binary similarity measure, set similarity, STASS, data mining,
clustering, classification, diagnostic test
Lee