libtbx.cluster
index
/net/chevy/raid1/nat/src/cctbx_project/libtbx/cluster.py

http://pypi.python.org/pypi/cluster/1.1.1b3

 
Classes
       
exceptions.Exception(exceptions.BaseException)
ClusteringError
BaseClusterMethod
HierarchicalClustering
Cluster
KMeansClustering

 
class BaseClusterMethod
    The base class of all clustering methods.
 
  Methods defined here:
__init__(self, input, distance_function)
Constructs the object and starts clustering
 
PARAMETERS
   input             - a list of objects
   distance_function - a function returning the distance - or opposite of
                       similarity ( distance = -similarity ) - of two
                       items from the input. In other words, the closer
                       the two items are related, the smaller this value
                       needs to be. With 0 meaning they are exactly the
                       same.
 
NOTES
   The distance function should always return the absolute distance
   between two given items of the list. Say,
 
   distance(input[1], input[4]) = distance(input[4], input[1])
 
   This is very important for the clustering algorithm to work!
   Naturally, the data returned by the distance function MUST be a
   comparable datatype, so you can perform arithmetic comparisons on
   them (< or >)! The simplest examples would be floats or ints. But as
   long as they are comparable, it's ok.
topo(self)
Returns the structure (topology) of the cluster.
 
See Cluster.topology() for information.

Data descriptors defined here:
data
Returns the data that is currently in process.
raw_data
Returns the raw data (data without being clustered).

 
class Cluster
    A collection of items. This is internally used to detect clustered items in
the data so we could distinguish other collection types (lists, dicts, ...)
from the actual clusters. This means that you could also create clusters of
lists with this class.
 
  Methods defined here:
__init__(self, level, *args)
Constructor
 
PARAMETERS
   level - The level of this cluster. This is used in hierarchical
           clustering to retrieve a specific set of clusters. The higher
           the level, the smaller the count of clusters returned. The
           level depends on the difference function used.
   *args - every additional argument passed following the level value
           will get added as item to the cluster. You could also pass a
           list as second parameter to initialise the cluster with that
           list as content
__repr__(self)
__str__(self)
append(self, item)
Appends a new item to the cluster
 
PARAMETERS
   item  -  The item that is to be appended
display(self, depth=0)
Pretty-prints this cluster. Useful for debuging
fullyflatten(self, *args)
Completely flattens out this cluster and returns a one-dimensional list
containing the cluster's items. This is useful in cases where some items
of the cluster are clusters in their own right and you only want the
items.
 
PARAMETERS
   *args - only used for recursion.
getlevel(self, threshold)
Retrieve all clusters up to a specific level threshold. This
level-threshold represents the maximum distance between two clusters. So
the lower you set this threshold, the more clusters you will receive and
the higher you set it, you will receive less but bigger clusters.
 
PARAMETERS
   threshold - The level threshold
 
NOTE
   It is debatable whether the value passed into this method should
   really be as strongly linked to the real cluster-levels as it is right
   now. The end-user will not know the range of this value unless s/he
   first inspects the top-level cluster. So instead you might argue that
   a value ranging from 0 to 1 might be a more useful approach.
items(self, newItems=None)
Sets or gets the items of the cluster
 
PARAMETERS
   newItems (optional) - if set, the items of the cluster will be
                         replaced with that argument.
level(self)
Returns the level associated with this cluster
topology(self)
Returns the structure (topology) of the cluster as tuples.
 
Output from cl.data:
    [<Cluster@0.833333333333(['CVS', <Cluster@0.818181818182(['34.xls',
    <Cluster@0.789473684211([<Cluster@0.555555555556(['0.txt',
    <Cluster@0.181818181818(['ChangeLog', 'ChangeLog.txt'])>])>,
    <Cluster@0.684210526316(['20060730.py',
    <Cluster@0.684210526316(['.cvsignore',
    <Cluster@0.647058823529(['About.py',
    <Cluster@0.625(['.idlerc', '.pylint.d'])>])>])>])>])>])>])>]
 
Corresponding output from cl.topo():
    ('CVS', ('34.xls', (('0.txt', ('ChangeLog', 'ChangeLog.txt')),
    ('20060730.py', ('.cvsignore', ('About.py',
    ('.idlerc', '.pylint.d')))))))

 
class ClusteringError(exceptions.Exception)
    
Method resolution order:
ClusteringError
exceptions.Exception
exceptions.BaseException
__builtin__.object

Data descriptors defined here:
__weakref__
list of weak references to the object (if defined)

Methods inherited from exceptions.Exception:
__init__(...)
x.__init__(...) initializes x; see help(type(x)) for signature

Data and other attributes inherited from exceptions.Exception:
__new__ = <built-in method __new__ of type object>
T.__new__(S, ...) -> a new object with type S, a subtype of T

Methods inherited from exceptions.BaseException:
__delattr__(...)
x.__delattr__('name') <==> del x.name
__getattribute__(...)
x.__getattribute__('name') <==> x.name
__getitem__(...)
x.__getitem__(y) <==> x[y]
__getslice__(...)
x.__getslice__(i, j) <==> x[i:j]
 
Use of negative indices is not supported.
__reduce__(...)
__repr__(...)
x.__repr__() <==> repr(x)
__setattr__(...)
x.__setattr__('name', value) <==> x.name = value
__setstate__(...)
__str__(...)
x.__str__() <==> str(x)
__unicode__(...)

Data descriptors inherited from exceptions.BaseException:
__dict__
args
message

 
class HierarchicalClustering(BaseClusterMethod)
    Implementation of the hierarchical clustering method as explained in
http://www.elet.polimi.it/upload/matteucc/Clustering/tutorial_html/hierarchical.html
 
USAGE
   >>> from cluster import HierarchicalClustering
   >>> # or: from cluster import *
   >>> cl = HierarchicalClustering([123,334,345,242,234,1,3], lambda x,y: float(abs(x-y)))
   >>> cl.getlevel(90)
   [[345, 334], [234, 242], [123], [3, 1]]
 
   Note that all of the returned clusters are more that 90 apart
 
  Methods defined here:
__init__(self, data, distance_function, linkage='single')
Constructor
 
See BaseClusterMethod.__init__ for more details.
averageLinkageDistance(self, x, y)
The method to determine the distance between one cluster an another
item/cluster. The distance equals to the *average* (mean) distance from
any member of one cluster to any member of the other cluster.
 
PARAMETERS
   x  -  first cluster/item
   y  -  second cluster/item
cluster(self, matrix=None, level=None, sequence=None)
Perform hierarchical clustering. This method is automatically called by
the constructor so you should not need to call it explicitly.
 
PARAMETERS
   matrix   -  The 2D list that is currently under processing. The matrix
               contains the distances of each item with each other
   level    -  The current level of clustering
   sequence -  The sequence number of the clustering
completeLinkageDistance(self, x, y)
The method to determine the distance between one cluster an another
item/cluster. The distance equals to the *longest* distance from any
member of one cluster to any member of the other cluster.
 
PARAMETERS
   x  -  first cluster/item
   y  -  second cluster/item
getlevel(self, threshold)
Returns all clusters with a maximum distance of <threshold> in between
each other
 
PARAMETERS
   threshold - the maximum distance between clusters
 
SEE-ALSO
   Cluster.getlevel(threshold)
setLinkageMethod(self, method)
Sets the method to determine the distance between two clusters.
 
PARAMETERS:
   method - The name of the method to use. It must be one of 'single',
            'complete', 'average' or 'uclus'
singleLinkageDistance(self, x, y)
The method to determine the distance between one cluster an another
item/cluster. The distance equals to the *shortest* distance from any
member of one cluster to any member of the other cluster.
 
PARAMETERS
   x  -  first cluster/item
   y  -  second cluster/item
uclusDistance(self, x, y)
The method to determine the distance between one cluster an another
item/cluster. The distance equals to the *average* (median) distance from
any member of one cluster to any member of the other cluster.
 
PARAMETERS
   x  -  first cluster/item
   y  -  second cluster/item

Methods inherited from BaseClusterMethod:
topo(self)
Returns the structure (topology) of the cluster.
 
See Cluster.topology() for information.

Data descriptors inherited from BaseClusterMethod:
data
Returns the data that is currently in process.
raw_data
Returns the raw data (data without being clustered).

 
class KMeansClustering
    Implementation of the kmeans clustering method as explained in
http://www.elet.polimi.it/upload/matteucc/Clustering/tutorial_html/kmeans.html
 
USAGE
=====
 
  >>> from cluster import KMeansClustering
  >>> cl = KMeansClustering([(1,1), (2,1), (5,3), ...])
  >>> clusters = cl.getclusters(2)
 
  Methods defined here:
__init__(self, data, distance=None)
Constructor
 
PARAMETERS
   data     - A list of tuples or integers.
   distance - A function determining the distance between two items.
              Default: It assumes the tuples contain numeric values and
                       appiles a generalised form of the
                       euclidian-distance algorithm on them.
assign_item(self, item, origin)
Assigns an item from a given cluster to the closest located cluster
 
PARAMETERS
   item   - the item to be moved
   origin - the originating cluster
getclusters(self, n)
Generates <n> clusters
 
PARAMETERS
   n - The amount of clusters that should be generated.
       n must be greater than 1
initialiseClusters(self, input, clustercount)
Initialises the clusters by distributing the items from the data evenly
across n clusters
 
PARAMETERS
   input        - the data set (a list of tuples)
   clustercount - the amount of clusters (n)
move_item(self, item, origin, destination)
Moves an item from one cluster to anoter cluster
 
PARAMETERS
 
   item        - the item to be moved
   origin      - the originating cluster
   destination - the target cluster

 
Functions
       
centroid(list, method=<function median>)
returns the central vector of a list of vectors
dotproduct(a, b)
Calculates the dotproduct between two vecors
flatten(L)
Flattens a list.
Example:
flatten([a,b,[c,d,[e,f]]]) = [a,b,c,d,e,f]
genmatrix(list, combinfunc, symmetric=False, diagonal=None)
Takes a list and generates a 2D-matrix using the supplied combination
function to calculate the values.
 
PARAMETERS
   list        - the list of items
   combinfunc  - the function that is used to calculate teh value in a cell.
                 It has to cope with two arguments.
   symmetric   - Whether it will be a symmetric matrix along the diagonal.
                 For example, it the list contains integers, and the
                 combination function is abs(x-y), then the matrix will be
                 symmetric.
                 Default: False
   diagonal    - The value to be put into the diagonal. For some functions,
                 the diagonal will stay constant. An example could be the
                 function "x-y". Then each diagonal cell will be "0".
                 If this value is set to None, then the diagonal will be
                 calculated.
                 Default: None
magnitude(a)
calculates the magnitude of a vecor
mean(numbers)
Returns the arithmetic mean of a numeric list.
 
found at: http://mail.python.org/pipermail/python-list/2004-December/253517.html
median(numbers)
Return the median of the list of numbers.
 
found at: http://mail.python.org/pipermail/python-list/2004-December/253517.html
minkowski_distance(x, y, p=2)
Calculates the minkowski distance between two points.
 
PARAMETERS
   x - the first point
   y - the second point
   p - the order of the minkowski algorithm.
       Default = 2. This is equal to the euclidian distance.
                    If the order is 1, it is equal to the manhatten
                    distance.
                    The higher the order, the closer it converges to the
                    Chebyshev distance, which has p=infinity
printmatrix(list)
Prints out a 2-dimensional list cleanly.
This is useful for debugging.
 
PARAMETERS
   list  -  the 2D-list to display

 
Data
        division = _Feature((2, 2, 0, 'alpha', 2), (3, 0, 0, 'alpha', 0), 8192)