HierarchicalClustering< PointRef > Class Template Reference

Generic 2-dimensional hierarchical clustering with geometric hashing. More...

#include <OpenMS/COMPARISON/CLUSTERING/HierarchicalClustering.h>

List of all members.

Classes
class	BoundingBox
	Bounding box of cluster. More...
class	Cluster
	Set of points. Describes a cluster on the grid. A point consists of a PointCoordinate and a PointRef. More...
class	TreeDistance
	Wrapper class for two trees and the corresponding distance. More...
class	TreeNode
	Tree node used for clustering. More...
Public Types
typedef DPosition< 2, DoubleReal >	PointCoordinate
	Coordinate of a point to be clustered.
typedef HashGrid< Cluster >	Grid
	The hash grid data type.
Public Member Functions
	HierarchicalClustering (const PointCoordinate &cluster_dimension)
	Constructor.
Grid::cell_iterator	insertPoint (const PointCoordinate &d, const PointRef &ref)
	Insert new PointCoordinate into grid.
void	cluster ()
	Perform clustering of all existing points.
Public Attributes
Grid	grid
	The hash grid.
Protected Types
typedef std::map< typename Grid::CellIndex, std::pair < typename Grid::CellContent *, bool > >	ClusterCells
typedef boost::unordered_set < TreeNode * >	ClusterTrees
typedef std::priority_queue < TreeDistance, std::vector < TreeDistance >, std::greater < TreeDistance > >	TreeDistanceQueue
	Priority queue queue used to find minimum distances.
Protected Member Functions
template<class P >
Grid::cell_iterator	insertCluster_ (const P &p)
	Insert new Cluster into grid.
void	clusterIndex_ (const typename Grid::CellIndex &p)
	Perform clustering at given cell index.
void	gridCells5x5_ (typename Grid::CellIndex cur, ClusterCells &cells)
	Collect all cells used to cluster at given cell index.
void	gridCell_ (const typename Grid::CellIndex &cur, ClusterCells &cells, bool center=false, bool ignore_missing=true)
	Collect one cell.
void	addTreeDistance_ (TreeNode *tree, ClusterTrees &trees, TreeDistanceQueue &dists)
	Add a new tree to the set of trees and distance queue.
DoubleReal	treeDistance_ (TreeNode *left, TreeNode *right)
	Returns distance of two tree nodes Returns the euclidean distance of the coordinates of the two trees. It checks the size of the bounding box and returns INFINITY if it gets to large.
void	tree2Cluster_ (const TreeNode *tree, Cluster &cluster)
	Recursively add the points of a finished cluster into the hash grid. All points are saved in the leafs of the tree.
void	tree2Points_ (const TreeNode *tree)
	Recursively add the points of an unfinished cluster back to the grid. All points are saved in the leafs of the tree.
Static Protected Member Functions
static PointCoordinate	coordScalarDiv_ (const PointCoordinate &lhs, const DoubleReal &rhs)
static PointCoordinate	coordElemDiv_ (const PointCoordinate &lhs, const PointCoordinate &rhs)
static bool	coordElemGreater_ (const PointCoordinate &lhs, const PointCoordinate &rhs)
static DoubleReal	coordDist_ (const PointCoordinate &lhs, const PointCoordinate &rhs)

---

Detailed Description

template<typename PointRef>
class OpenMS::HierarchicalClustering< PointRef >

Generic 2-dimensional hierarchical clustering with geometric hashing.

The input data is saved into a hash grid. The dimension of the hash cells is also the maximum cluster dimension.

The clustering is performed on a 5x5 subsets of the hash grid. Only clusters with all points in the inner 3x3 subset are accepted into the output; all others are discarded. This makes sure that all clusters are maximal and can't get larger with points not visible.

This clustering only supports centroid linkage. It uses a priority queue to save minimum distances between two subsets (proto-cluster?). No full distance matrix is required.

Template Parameters:

PointRef

Reference associated with every point. Must have a default constructor.

---

Member Typedef Documentation

typedef std::map<typename Grid::CellIndex, std::pair<typename Grid::CellContent *, bool> > ClusterCells [protected]

typedef boost::unordered_set<TreeNode *> ClusterTrees [protected]

typedef HashGrid<Cluster> Grid

The hash grid data type.

typedef DPosition<2, DoubleReal> PointCoordinate

Coordinate of a point to be clustered.

Attention:

To be replaced by a OpenMS coordinate type.

typedef std::priority_queue<TreeDistance, std::vector<TreeDistance>, std::greater<TreeDistance> > TreeDistanceQueue [protected]

Priority queue queue used to find minimum distances.

---

Constructor & Destructor Documentation

HierarchicalClustering

(

const PointCoordinate &

cluster_dimension

)

[inline]

Constructor.

Parameters:

cluster_dimension

Max dimension of cluster

---

Member Function Documentation

void addTreeDistance_	(	TreeNode *	tree,
		ClusterTrees &	trees,
		TreeDistanceQueue &	dists
	)			[inline, protected]

Add a new tree to the set of trees and distance queue.

Referenced by HierarchicalClustering< PointRef >::clusterIndex_().

void cluster

(

)

[inline]

Perform clustering of all existing points.

Reimplemented in SILACClustering.

Referenced by HierarchicalClustering< PointRef >::clusterIndex_().

void clusterIndex_

(

const typename Grid::CellIndex &

p

)

[protected]

Perform clustering at given cell index.

Parameters:

p

Cell index.

References HierarchicalClustering< PointRef >::addTreeDistance_(), HierarchicalClustering< PointRef >::TreeNode::bbox, HierarchicalClustering< PointRef >::cluster(), HierarchicalClustering< PointRef >::TreeNode::coord, HierarchicalClustering< PointRef >::coordScalarDiv_(), HierarchicalClustering< PointRef >::gridCells5x5_(), HierarchicalClustering< PointRef >::insertCluster_(), HierarchicalClustering< PointRef >::TreeNode::points, HierarchicalClustering< PointRef >::tree2Cluster_(), and HierarchicalClustering< PointRef >::tree2Points_().

Referenced by HierarchicalClustering< SILACPattern * >::cluster().

static DoubleReal coordDist_	(	const PointCoordinate &	lhs,
		const PointCoordinate &	rhs
	)			[inline, static, protected]

Referenced by HierarchicalClustering< SILACPattern * >::treeDistance_().

static PointCoordinate coordElemDiv_	(	const PointCoordinate &	lhs,
		const PointCoordinate &	rhs
	)			[inline, static, protected]

Referenced by HierarchicalClustering< SILACPattern * >::treeDistance_().

static bool coordElemGreater_	(	const PointCoordinate &	lhs,
		const PointCoordinate &	rhs
	)			[inline, static, protected]

Referenced by HierarchicalClustering< SILACPattern * >::treeDistance_().

static PointCoordinate coordScalarDiv_	(	const PointCoordinate &	lhs,
		const DoubleReal &	rhs
	)			[inline, static, protected]

Referenced by HierarchicalClustering< PointRef >::clusterIndex_(), and HierarchicalClustering< PointRef >::BoundingBox::operator PointCoordinate().

void gridCell_	(	const typename Grid::CellIndex &	cur,
		ClusterCells &	cells,
		bool	center = false,
		bool	ignore_missing = true
	)			[inline, protected]

Collect one cell.

Parameters:

	cur	Cell index.
	cells	List of cells.
	center	Is the given cell in the center.
	ignore_missing	Defines if non-existent errors should be ignored.

Referenced by HierarchicalClustering< PointRef >::gridCells5x5_().

void gridCells5x5_	(	typename Grid::CellIndex	cur,
		ClusterCells &	cells
	)			[protected]

Collect all cells used to cluster at given cell index.

This function collects all cells in a 5x5 array.

Parameters:

	cur	Cell index.
	cells	List of cells to be used.

References HierarchicalClustering< PointRef >::gridCell_().

Referenced by HierarchicalClustering< PointRef >::clusterIndex_().

Grid::cell_iterator insertCluster_

(

const P &

p

)

[inline, protected]

Insert new Cluster into grid.

Parameters:

p

Point to insert.

Returns:

iterator to inserted cluster.

Referenced by HierarchicalClustering< PointRef >::clusterIndex_(), and HierarchicalClustering< SILACPattern * >::insertPoint().

Grid::cell_iterator insertPoint	(	const PointCoordinate &	d,
		const PointRef &	ref
	)			[inline]

Insert new PointCoordinate into grid.

Parameters:

	d	PointCoordinate to insert.
	ref	Associated caller specified info.

Returns:

iterator to inserted cluster.

Referenced by HierarchicalClustering< SILACPattern * >::tree2Points_().

void tree2Cluster_	(	const TreeNode *	tree,
		Cluster &	cluster
	)			[inline, protected]

Recursively add the points of a finished cluster into the hash grid. All points are saved in the leafs of the tree.

Parameters:

	tree	The tree
	cluster	The cluster

Referenced by HierarchicalClustering< PointRef >::clusterIndex_(), and HierarchicalClustering< SILACPattern * >::tree2Cluster_().

void tree2Points_

(

const TreeNode *

tree

)

[inline, protected]

Recursively add the points of an unfinished cluster back to the grid. All points are saved in the leafs of the tree.

Parameters:

tree

The tree

Referenced by HierarchicalClustering< PointRef >::clusterIndex_(), and HierarchicalClustering< SILACPattern * >::tree2Points_().

DoubleReal treeDistance_	(	TreeNode *	left,
		TreeNode *	right
	)			[inline, protected]

Returns distance of two tree nodes Returns the euclidean distance of the coordinates of the two trees. It checks the size of the bounding box and returns INFINITY if it gets to large.

Referenced by HierarchicalClustering< SILACPattern * >::addTreeDistance_().

---

Member Data Documentation

Grid grid

The hash grid.

It contains clusters.

Referenced by HierarchicalClustering< SILACPattern * >::cluster(), HierarchicalClustering< SILACPattern * >::gridCell_(), HierarchicalClustering< SILACPattern * >::insertCluster_(), and HierarchicalClustering< SILACPattern * >::treeDistance_().