/usr/lib/python2.7/dist-packages/cluster/linkage.py is in python-cluster 1.3.3-1.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 | from __future__ import division
from functools import wraps
def cached(fun):
"""
memoizing decorator for linkage functions.
Parameters have been hardcoded (no ``*args``, ``**kwargs`` magic), because,
the way this is coded (interchangingly using sets and frozensets) is true
for this specific case. For other cases that is not necessarily guaranteed.
"""
_cache = {}
@wraps(fun)
def newfun(a, b, distance_function):
frozen_a = frozenset(a)
frozen_b = frozenset(b)
if (frozen_a, frozen_b) not in _cache:
result = fun(a, b, distance_function)
_cache[(frozen_a, frozen_b)] = result
return _cache[(frozen_a, frozen_b)]
return newfun
@cached
def single(a, b, distance_function):
"""
Given two collections ``a`` and ``b``, this will return the distance of the
points which are closest together. ``distance_function`` is used to
determine the distance between two elements.
Example::
>>> single([1, 2], [3, 4], lambda x, y: abs(x-y))
1 # (distance between 2 and 3)
"""
left_a, right_a = min(a), max(a)
left_b, right_b = min(b), max(b)
result = min(distance_function(left_a, right_b),
distance_function(left_b, right_a))
return result
@cached
def complete(a, b, distance_function):
"""
Given two collections ``a`` and ``b``, this will return the distance of the
points which are farthest apart. ``distance_function`` is used to determine
the distance between two elements.
Example::
>>> single([1, 2], [3, 4], lambda x, y: abs(x-y))
3 # (distance between 1 and 4)
"""
left_a, right_a = min(a), max(a)
left_b, right_b = min(b), max(b)
result = max(distance_function(left_a, right_b),
distance_function(left_b, right_a))
return result
@cached
def average(a, b, distance_function):
"""
Given two collections ``a`` and ``b``, this will return the mean of all
distances. ``distance_function`` is used to determine the distance between
two elements.
Example::
>>> single([1, 2], [3, 100], lambda x, y: abs(x-y))
26
"""
distances = [distance_function(x, y)
for x in a for y in b]
return sum(distances) / len(distances)
@cached
def uclus(a, b, distance_function):
"""
Given two collections ``a`` and ``b``, this will return the *median* of all
distances. ``distance_function`` is used to determine the distance between
two elements.
Example::
>>> single([1, 2], [3, 100], lambda x, y: abs(x-y))
2.5
"""
distances = sorted([distance_function(x, y)
for x in a for y in b])
midpoint, rest = len(distances) // 2, len(distances) % 2
if not rest:
return sum(distances[midpoint-1:midpoint+1]) / 2
else:
return distances[midpoint]
|