NAME
"Set::Partitions::Similarity" - Routines to measure similarity of
partitions.
SYNOPSIS
use Set::Partitions::Similarity qw(getAccuracyAndPrecision);
use Data::Dump qw(dump);
# set elements are Perl strings, sets are array references
# partitions are nested arrays.
dump getAccuracyAndPrecision ([[qw(a b)],[1,2]], [[qw(a b 1)],[2]]);
# dumps:
# ("0.5", "0.25")
# a partition is equivalent to itself, even the empty partition.
dump getAccuracyAndPrecision ([[1,2], [3,4]], [[2,1], [4,3]]);
dump getAccuracyAndPrecision ([], []);
# dumps:
# (1, 1)
# (1, 1)
# accuracy and precision are symmetric functions.
my ($p, $q) = ([[1,2,3], [4]], [[1], [2,3,4]]);
dump getAccuracyAndPrecision ($p, $q);
dump getAccuracyAndPrecision ($q, $p);
# dumps:
# ("0.333333333333333", "0.2")
# ("0.333333333333333", "0.2")
# checks partitions and throws an exception.
eval { getAccuracyAndPrecision ([[1]], [[1,2]], 1); };
warn $@ if $@;
# dumps:
# partitions are invalid, they have different set elements.
DESCRIPTION
A partition of a set is a collection of mutually disjoint subsets of the
set whose union is the set. "Set::Partitions::Similarity" provides
routines that measure the *accuracy* and *precision* between two
partitions of a set. The measures can assess the performance of a binary
clustering algorithm by comparing the clusters the algorithm creates
against the correct clusters of test data.
Accuracy and Precision
Let "S" be a set of "n" elements and let "P" be a partition of "S". Let
T(S) be the set of all sets of two distinct elements of "S"; so T(S) has
"n*(n-1)/2" sets. The partition "P" uniquely defines a partitioning of
T(S) into two sets, C(P) and D(P) where C(P) is the set of all pairs in
T(S) such that both elements of a pair occur in the same set in "P", and
define D(P) as "T(S)-C(P)", the complement.
Given two partitions "P" and "Q" of the set "S", the *accuracy* is
defined as "(|C(P) ^ C(Q)| + |D(P) ^ D(Q)|) / (n*(n-1)/2)", where | |
gives the size of a set and ^ represents the intersection operator. The
*precision* is defined as "|C(P) ^ C(Q)| / (|C(P) ^ C(Q)| + |C(P) ^
D(Q)| + |D(P) ^ C(Q)|)". The *accuracy* and *precision* return values
ranging from zero (no similarity) to one (equivalent partitions). The
*distance* between two partitions is defined as *1-accuracy*, and in
mathematics is a metric. The *distance* returns values ranging from zero
(equivalent partitions) to one (no similarity).
All the methods implemented that compute the *accuracy*, *precision*,
and *distance* run in time linear in the number of elements of the set
partitioned.
ROUTINES
"areSubsetsDisjoint ($Partition)"
The routine "areSubsetsDisjoint" returns true if the subsets of the
partition are disjoint, false otherwise. It can be used to check the
validity of a partition.
$Partition
The partition is stored as a nested array reference of the form
"[[],...[]]". For example, the set partition "{{a,b}, {1,2}}" of the
set "{a,b,1,2}" should be stored as the nested array reference
"[['a','b']],[1,2]]". Note the elements of a set are represented as
Perl strings.
An example:
use Set::Partitions::Similarity qw(areSubsetsDisjoint);
use Data::Dump qw(dump);
dump areSubsetsDisjoint ([[1,2,3], [4]]);
dump areSubsetsDisjoint ([[1,2,3], [4,1]]);
# dumps:
# "1"
# "0"
"getAccuracy ($PartitionP, $PartitionQ, $CheckValidity)"
The routine "getAccuracy" returns the *accuracy* of the two partitions.
"$PartitionP, $PartitionQ"
The partitions are stored as nested array references of the form
"[[],...[]]". For example, the set partition "{{a,b}, {1,2}}" of the
set "{a,b,1,2}" should be stored as the nested array references
"[['a','b']],[1,2]]". Note the elements of a set are represented as
Perl strings.
$CheckValidity
If $CheckValidity evaluates to true, then checks are performed to
ensure both partitions are valid and an exception is thrown if they
are not. The default is false.
An example:
use Set::Partitions::Similarity qw(getAccuracy);
use Data::Dump qw(dump);
dump getAccuracy ([[qw(a b)], [qw(c d)]], [[qw(a b c d)]]);
dump getAccuracy ([[qw(a b c d)]], [[qw(a b)], [qw(c d)]]);
# dumps:
# "0.333333333333333"
# "0.333333333333333"
"getAccuracyAndPrecision ($PartitionP, $PartitionQ, $CheckValidity)"
The routine "getAccuracyAndPrecision" returns the *accuracy* and
*precision* of the two partitions as an array "(accuracy, precision)".
"$PartitionP, $PartitionQ"
The partitions are stored as nested array references of the form
"[[],...[]]". For example, the set partition "{{a,b}, {1,2}}" of the
set "{a,b,1,2}" should be stored as the nested array references
"[['a','b']],[1,2]]". Note the elements of a set are represented as
Perl strings.
$CheckValidity
If $CheckValidity evaluates to true, then checks are performed to
ensure both partitions are valid and an exception is thrown if they
are not. The default is false.
An example:
use Set::Partitions::Similarity qw(getAccuracyAndPrecision);
use Data::Dump qw(dump);
dump getAccuracyAndPrecision ([[1,2], [3,4]], [[1], [2], [3], [4]]);
dump getAccuracyAndPrecision ([[1], [2], [3], [4]], [[1,2], [3,4]]);
# dumps:
# ("0.666666666666667", 0)
# ("0.666666666666667", 0)
"getDistance ($PartitionP, $PartitionQ, $CheckValidity)"
The routine "getDistance" returns *1-accuracy* of the two partitions, or
"1-getAccuracy($PartitionP, $PartitionQ, $CheckValidity)".
"$PartitionP, $PartitionQ"
The partitions are stored as nested array references of the form
"[[],...[]]". For example, the set partition "{{a,b}, {1,2}}" of the
set "{a,b,1,2}" should be stored as the nested array references
"[['a','b']],[1,2]]". Note the elements of a set are represented as
Perl strings.
$CheckValidity
If $CheckValidity evaluates to true, then checks are performed to
ensure both partitions are valid and an exception is thrown if they
are not. The default is false.
An example:
use Set::Partitions::Similarity qw(getDistance);
use Data::Dump qw(dump);
dump getDistance ([[1,2,3], [4]], [[1], [2,3,4]]);
# dumps:
# "0.666666666666667"
"getPrecision ($PartitionP, $PartitionQ, $CheckValidity)"
The routine "getPrecision" returns the *precision* of the two
partitions.
"$PartitionP, $PartitionQ"
The partitions are stored as nested array references of the form
"[[],...[]]". For example, the set partition "{{a,b}, {1,2}}" of the
set "{a,b,1,2}" should be stored as the nested array references
"[['a','b']],[1,2]]". Note the elements of a set are represented as
Perl strings.
$CheckValidity
If $CheckValidity evaluates to true, then checks are performed to
ensure both partitions are valid and an exception is thrown if they
are not. The default is false.
An example:
use Set::Partitions::Similarity qw(getPrecision);
use Data::Dump qw(dump);
dump getPrecision ([[1,2,3], [4]], [[1], [2,3,4]]);
# dumps:
# "0.2"
EXAMPLE
The code following measures the *distance* of a set of 512 elements
partitioned equally into subsets of size $s to the entire set.
use Set::Partitions::Similarity qw(getDistance);
my @p = ([0..511]);
for (my $s = 1; $s <= 512; $s += $s)
{
my @q = map { [$s*$_..($s*$_+$s-1)] } (0..(512/$s-1));
print join (', ', $s, getDistance (\@p, \@q, 1)) . "\n";
}
# dumps:
# 1, 1
# 2, 0.998043052837573
# 4, 0.99412915851272
# 8, 0.986301369863014
# 16, 0.970645792563601
# 32, 0.939334637964775
# 64, 0.876712328767123
# 128, 0.75146771037182
# 256, 0.500978473581213
# 512, 0
INSTALLATION
To install the module run the following commands:
perl Makefile.PL
make
make test
make install
If you are on a windows box you should use 'nmake' rather than 'make'.
BUGS
Please email bugs reports or feature requests to
"bug-set-partitions-similarities@rt.cpan.org", or through the web
interface at
. The author will be notified and you can be automatically notified of
progress on the bug fix or feature request.
AUTHOR
Jeff Kubina
COPYRIGHT
Copyright (c) 2009 Jeff Kubina. All rights reserved. This program is
free software; you can redistribute it and/or modify it under the same
terms as Perl itself.
The full text of the license can be found in the LICENSE file included
with this module.
KEYWORDS
accuracy, clustering, measure, metric, partitions, precision, set,
similarity
SEE ALSO