package flare.analytics.cluster
{
import flare.util.Arrays;
import flare.util.Property;
import flare.util.Sort;
import flare.vis.data.Data;
import flare.vis.data.DataList;
import flare.vis.data.EdgeSprite;
import flare.vis.data.NodeSprite;
import flare.vis.data.Tree;
import flare.vis.operator.Operator;
/**
* Base class for clustering operators that construct a hierarchical
* clustering tree. Provides methods for taking a sequence of
* merge operations by a clustering algorithm and constructing a
* resulting cluster tree.
*
* <p>Once a clustering has been computed, each node included in the
* analysis will be annotated with both its cluster membership
* using the name indicated by the <code>clusterField</code> property.
* By default, this class will attempt to pick an optimal level of the
* cluster tree at which to break up items into discrete clusters.
* However, clients can invoke the <code>labelNodes</code> method with
* a specific merge number which indicates the point at which to "cut"
* the cluster tree into discrete sub-clusters. This class also annotates
* nodes with a sequence number using the name indicated by the
* <code>sequenceField</code> property. The sequence number allows items
* to be sorted in a way that attempts to preserve the clustered structure.
* Additionally, the <code>clusterTree</code> property will return a
* <code>flare.vis.data.Tree</code> instance that can be used to
* visualize the structure of the cluster tree.</p>
*/
public class HierarchicalCluster extends Operator
{
/** @private */
protected var _idx:Property = Property.$("props.sequence");
/** @private */
protected var _com:Property = Property.$("props.cluster");
/** @private */
protected var _qvals:Array;
/** @private */
protected var _merges:MergeEdge;
/** @private */
protected var _size:int;
/** @private */
protected var _tree:Tree;
/** @private */
protected var _group:String = Data.NODES;
/** The data group to cluster. */
public function get group():String { return _group; }
public function set group(g:String):void { _group = g; }
/** The property in which to store cluster indices. This property
* is used to annotate nodes with the community they belong to
* (indicated as an integer index). The default value
* is "props.cluster". */
public function get clusterField():String { return _com.name; }
public function set clusterField(f:String):void { _com = Property.$(f); }
/** The property in which to store sequence indices. This property
* is used to annotate nodes with their sequence index along the
* computed cluster tree. This value can be used to sort the nodes
* in a way that best preserves community structure. The default value
* is "props.sequence". */
public function get sequenceField():String { return _idx.name; }
public function set sequenceField(f:String):void { _idx = Property.$(f); }
/** Computed criterion values for each merge in the cluster tree. */
public function get criteria():Array { return _qvals; }
/** The cluster tree of detected community structures. The leaf nodes
* correspond to each of the nodes in the input graph, and include the
* same <code>data</code> property. Non-leaf nodes indicate merges
* made by the clustering algorithm, and have <code>data</code>
* properties that include the <code>merge</code> number (1 for the
* first merger, 2 for the second, etc), the <code>criterion</code>
* value computed for that merge, and the <code>size</code> of the
* cluster rooted at that node (the number of descendants in the
* cluster tree).
*/
public function get clusterTree():Tree { return _tree; }
/**
* Creates a new HierarchicalCluster instance.
*/
public function HierarchicalCluster()
{
super();
}
/**
* Labels nodes with their cluster membership, determined by
* the given merge number. If the merge number is less than
* zero or unprovided, the merge number that maximizes the
* clustering criteria will be assumed.
* @param merge the merge number at which to compute the clusters
*/
public function labelNodes(merge:int=-1):void
{
if (merge < 0) merge = Arrays.maxIndex(_qvals);
var com:int, idx:int;
var helper:Function = function(n:NodeSprite):void
{
var nn:NodeSprite;
if (n.childDegree && n.data.merge > merge)
{
for (var i:int=0; i<n.childDegree; ++i)
helper(n.getChildNode(i));
}
else if (n.childDegree)
{
n.visitTreeDepthFirst(function(c:NodeSprite):void {
if (c.childDegree==0) {
nn = c.props.node;
_com.setValue(nn, com);
_idx.setValue(nn, idx++);
}
});
com++;
}
else
{
nn = n.props.node;
_com.setValue(nn, com++);
_idx.setValue(nn, idx++);
}
}
helper(_tree.root);
}
/**
* @private
* Constructs the cluster tree from the cluster results
*/
protected function buildTree(list:DataList):Tree
{
var tree:Tree = new Tree();
var e:MergeEdge, i:int, j:int, ii:int, map:Object = {};
var l:NodeSprite, r:NodeSprite, p:NodeSprite;
for (i=0; i<_size; ++i) {
map[i] = (p = new NodeSprite());
p.data = list[i].data;
p.props.node = list[i];
p.props.size = 0;
}
for (ii=0, e=_merges.next; e!=null; ++ii, e=e.next) {
i = e.i;
j = e.j;
l = map[i];
r = map[j];
map[i] = (p = new NodeSprite());
if (l.props.size >= r.props.size) {
p.addChildEdge(new EdgeSprite(p, l));
p.addChildEdge(new EdgeSprite(p, r));
} else {
p.addChildEdge(new EdgeSprite(p, r));
p.addChildEdge(new EdgeSprite(p, l));
}
p.data.merge = ii + 1;
p.data.criterion = _qvals[ii];
p.props.size = 2 + l.props.size + r.props.size;
delete map[j];
}
var roots:Array = [];
for each (var n:NodeSprite in map) roots.push(n);
roots.sort(Sort.$("-props.size"));
if (roots.length == 1) {
p = NodeSprite(roots[0]);
} else {
p = new NodeSprite();
p.data.merge = ii;
for each (n in roots) {
p.addChildEdge(new EdgeSprite(p, n));
}
}
tree.root = p;
return tree;
}
} }