Author: scooter
Date: 2011-08-14 19:12:47 -0700 (Sun, 14 Aug 2011)
New Revision: 26551
Added:
csplugins/trunk/ucsf/scooter/clusterMaker/src/clusterMaker/algorithms/Hopach/
csplugins/trunk/ucsf/scooter/clusterMaker/src/clusterMaker/algorithms/Hopach/HopachCluster.java
csplugins/trunk/ucsf/scooter/clusterMaker/src/clusterMaker/algorithms/silhouette/
csplugins/trunk/ucsf/scooter/clusterMaker/src/clusterMaker/algorithms/silhouette/SilhouetteResult.java
csplugins/trunk/ucsf/scooter/clusterMaker/src/clusterMaker/algorithms/silhouette/SilhouetteUtil.java
Modified:
csplugins/trunk/ucsf/scooter/clusterMaker/src/clusterMaker/algorithms/DistanceMatrix.java
csplugins/trunk/ucsf/scooter/clusterMaker/src/clusterMaker/algorithms/autosome/AutoSOMECluster.java
csplugins/trunk/ucsf/scooter/clusterMaker/src/clusterMaker/algorithms/hierarchical/Matrix.java
Log:
Adding the silhouette algorithm. Not really integrated, yet...
Modified:
csplugins/trunk/ucsf/scooter/clusterMaker/src/clusterMaker/algorithms/DistanceMatrix.java
===================================================================
---
csplugins/trunk/ucsf/scooter/clusterMaker/src/clusterMaker/algorithms/DistanceMatrix.java
2011-08-15 02:06:10 UTC (rev 26550)
+++
csplugins/trunk/ucsf/scooter/clusterMaker/src/clusterMaker/algorithms/DistanceMatrix.java
2011-08-15 02:12:47 UTC (rev 26551)
@@ -54,7 +54,6 @@
edges = network.getConnectingEdges(nodes);
}
- // double[][] graph = new
double[this.nodes.size()][this.nodes.size()];
CyAttributes edgeAttributes = Cytoscape.getEdgeAttributes();
edgeWeights = new double[edges.size()];
@@ -176,6 +175,7 @@
return getDistanceMatrix();
}
+ // TODO: relax symmetrical constraint?
public DoubleMatrix2D getDistanceMatrix() {
if (matrix != null)
return matrix;
Added:
csplugins/trunk/ucsf/scooter/clusterMaker/src/clusterMaker/algorithms/Hopach/HopachCluster.java
===================================================================
---
csplugins/trunk/ucsf/scooter/clusterMaker/src/clusterMaker/algorithms/Hopach/HopachCluster.java
(rev 0)
+++
csplugins/trunk/ucsf/scooter/clusterMaker/src/clusterMaker/algorithms/Hopach/HopachCluster.java
2011-08-15 02:12:47 UTC (rev 26551)
@@ -0,0 +1,130 @@
+/* vim: set ts=2: */
+/**
+ * Copyright (c) 2011 The Regents of the University of California.
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions, and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above
+ * copyright notice, this list of conditions, and the following
+ * disclaimer in the documentation and/or other materials provided
+ * with the distribution.
+ * 3. Redistributions must acknowledge that this software was
+ * originally developed by the UCSF Computer Graphics Laboratory
+ * under support by the NIH National Center for Research Resources,
+ * grant P41-RR01081.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDER "AS IS" AND ANY
+ * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS BE LIABLE
+ * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
+ * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT
+ * OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR
+ * BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
+ * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE
+ * OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE,
+ * EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ *
+ */
+package clusterMaker.algorithms.Hopach;
+
+import java.awt.GridLayout;
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.Comparator;
+import java.util.List;
+import javax.swing.JPanel;
+
+// Cytoscape imports
+import cytoscape.Cytoscape;
+import cytoscape.data.CyAttributes;
+import cytoscape.layout.Tunable;
+import cytoscape.logger.CyLogger;
+import cytoscape.task.TaskMonitor;
+
+import clusterMaker.algorithms.ClusterAlgorithm;
+import clusterMaker.algorithms.AbstractClusterAlgorithm;
+import clusterMaker.algorithms.hierarchical.DistanceMetric;
+import clusterMaker.algorithms.hierarchical.EisenCluster;
+import clusterMaker.ui.ClusterViz;
+import clusterMaker.ui.KnnView;
+
+
+/**
+ * HopachCluster implements the HOPACH algorithm of van der Laan
+ * and Pollard. The algorithm can be basically outlined as:
+ * while (minClusterSize > 3)
+ * foreach (level)
+ * k = averageSilhouette(K); // Get the average
silhouette for k=2,...,K
+ * partitionClusters(k); // Partition the clusters with
PAM
+ * orderClusters(); // Order the
new clusters
+ * collapseClusters(); // Collapse clusters
+ * level++;
+ *
+ * where partitionClusters() uses PAM (Partition About Medoids)
+ * algorithm (we actually use our k-medoid implementation)
+ *
+ * User inputs:
+ * K - the maximum number of clusters
+ * attributeList - the names of the features to cluster on
+ * metric - the distance metric (Euclidean distance is used in HOPACH)
+ * maxDepth - the maximum number of times to descend
+ * minSize - the minimum size of a cluster
+ *
+ * Output:
+ * Ordered cluster tree
+ *
+ * TODO: Get R source code to figure out exact algorithm
+ */
+public class HopachCluster extends AbstractClusterAlgorithm {
+
+ String[] attributeArray = new String[1];
+
+ TaskMonitor monitor = null;
+ CyLogger logger = null;
+
+ public HopachCluster() {
+ super();
+ logger = CyLogger.getLogger(HopachCluster.class);
+ initializeProperties();
+ }
+
+ public String getShortName() {return "hopach";};
+ public String getName() {return "HOPACH cluster";};
+
+ public JPanel getSettingsPanel() {
+ return null;
+ }
+
+ public ClusterViz getVisualizer() {
+ return null;
+ }
+
+ public void initializeProperties() {
+ super.initializeProperties();
+ updateSettings(true);
+ }
+
+ public void updateSettings() {
+ updateSettings(false);
+ }
+
+ public void updateSettings(boolean force) {
+ clusterProperties.updateValues();
+ super.updateSettings(force);
+
+ }
+
+ public void doCluster(TaskMonitor monitor) {
+ this.monitor = monitor;
+ }
+
+ public boolean isAvailable() {
+ return true;
+ }
+
+}
Modified:
csplugins/trunk/ucsf/scooter/clusterMaker/src/clusterMaker/algorithms/autosome/AutoSOMECluster.java
===================================================================
---
csplugins/trunk/ucsf/scooter/clusterMaker/src/clusterMaker/algorithms/autosome/AutoSOMECluster.java
2011-08-15 02:06:10 UTC (rev 26550)
+++
csplugins/trunk/ucsf/scooter/clusterMaker/src/clusterMaker/algorithms/autosome/AutoSOMECluster.java
2011-08-15 02:12:47 UTC (rev 26551)
@@ -168,6 +168,22 @@
/**
* Tuning values
*/
+ //data input tunables
+ clusterProperties.add(new Tunable("tunables_panel3",
+ "Data Input",
+ Tunable.GROUP, new
Integer(3)));
+ attributeArray = getAllAttributes();
+ clusterProperties.add(new Tunable("attributeList",
+ "Array Sources (Node
Attributes)",
+ Tunable.LIST, "",
+ (Object)attributeArray,
(Object)null, Tunable.MULTISELECT));
+
+ clusterProperties.add(new Tunable("selectedOnly", "Only use
selected nodes for clustering",
+ Tunable.BOOLEAN, new
Boolean(false)));
+
+ clusterProperties.add(new Tunable("ignoreMissing", "Ignore
nodes/edges with no data",
+ Tunable.BOOLEAN, new
Boolean(true)));
+
clusterProperties.add(new Tunable("tunables_panel",
"AutoSOME Basic Tuning",
Tunable.GROUP, new
Integer(4)));
@@ -197,8 +213,6 @@
Tunable.INTEGER, new
Integer(Runtime.getRuntime().availableProcessors()),
new Integer(1), (Object)null,
0));
-
-
//normalization tunables
clusterProperties.add(new Tunable("tunables_panel2",
"Data Normalization",
@@ -238,8 +252,9 @@
clusterProperties.add(new Tunable("fuzzyclustering", "Fuzzy
Cluster Network Settings",
Tunable.GROUP, new Integer(4),
new Boolean(false), null,
Tunable.COLLAPSABLE));
+
Tunable fcn = new Tunable("enableFCN", "Perform Fuzzy
Clustering",
- Tunable.BOOLEAN, new
Boolean(false));
+ Tunable.BOOLEAN, new
Boolean(true));
fcn.addTunableValueListener(this);
clusterProperties.add(fcn);
@@ -267,9 +282,9 @@
clusterProperties.add(mxedges);
//advanced settings
- clusterProperties.add(new Tunable("advancedAut", "Additional
Settings",
- Tunable.GROUP, new Integer(1),
- new Boolean(true), null,
Tunable.COLLAPSABLE));
+ // clusterProperties.add(new Tunable("advancedAut", "Additional
Settings",
+ // Tunable.GROUP, new Integer(1),
+ // new Boolean(false), null,
Tunable.COLLAPSABLE));
/*
@@ -280,27 +295,11 @@
*/
- //data input tunables
- clusterProperties.add(new Tunable("tunables_panel3",
- "Data Input",
- Tunable.GROUP, new
Integer(3)));
- attributeArray = getAllAttributes();
- clusterProperties.add(new Tunable("attributeList",
- "Array Sources (Node
Attributes)",
- Tunable.LIST, "",
- (Object)attributeArray,
(Object)null, Tunable.MULTISELECT));
-
- clusterProperties.add(new Tunable("selectedOnly", "Only use
selected nodes for clustering",
- Tunable.BOOLEAN, new
Boolean(false)));
-
- clusterProperties.add(new Tunable("ignoreMissing", "Ignore
nodes/edges with no data",
- Tunable.BOOLEAN, new
Boolean(true)));
-
- //output tunables
- clusterProperties.add(new Tunable("tunables_panel4",
- "Data Output",
- Tunable.GROUP, new
Integer(2)));
+ //output tunables
+ clusterProperties.add(new Tunable("tunables_panel4",
+ "Data Output",
+ Tunable.GROUP, new Integer(2)));
Tunable data_output = new Tunable("cluster_output",
"Choose Visualization",
Modified:
csplugins/trunk/ucsf/scooter/clusterMaker/src/clusterMaker/algorithms/hierarchical/Matrix.java
===================================================================
---
csplugins/trunk/ucsf/scooter/clusterMaker/src/clusterMaker/algorithms/hierarchical/Matrix.java
2011-08-15 02:06:10 UTC (rev 26550)
+++
csplugins/trunk/ucsf/scooter/clusterMaker/src/clusterMaker/algorithms/hierarchical/Matrix.java
2011-08-15 02:12:47 UTC (rev 26551)
@@ -52,6 +52,7 @@
private int nRows;
private int nColumns;
private Double matrix[][];
+ // private DoubleMatrix2D matrix = null;
private double colWeights[];
private double rowWeights[];
private double maxAttribute;
@@ -326,6 +327,8 @@
for (int row = 0; row < nRows; row++) {
System.out.print(rowLabels[row]+"\t");
for (int col = 0; col < nColumns; col++) {
+ // Double val = matrix.get(row, column);
+ // if (val != null)
if (matrix[row][col] != null)
System.out.print(matrix[row][col]+"\t");
else
@@ -370,6 +373,7 @@
}
}
+ // XXX Isn't this the same as clusterMaker.algorithms.DistanceMatrix?
private void buildSymmetricalMatrix(CyNetwork network, String weight,
boolean ignoreMissing, boolean
selectedOnly) {
@@ -383,6 +387,7 @@
this.nRows = nodeList.size();
this.nColumns = this.nRows;
this.matrix = new Double[nRows][nColumns];
+ // this.matrix = DoubleFactory2D.sparse.make(nRows,nColumns);
this.rowLabels = new String[nRows];
this.columnLabels = new String[nColumns];
this.rowNodes = new CyNode[nRows];
@@ -420,15 +425,16 @@
if (val != null) {
found = true;
maxAttribute = Math.max(maxAttribute,
val);
+ if (edge.getSource() == node) {
+ column =
nodeList.indexOf(edge.getTarget());
+ matrix[index][column] = val;
+ //matrix.set(index,column,val);
+ } else {
+ column =
nodeList.indexOf(edge.getSource());
+ matrix[index][column] = val;
+ // matrix.set(index,column,val);
+ }
}
-
- if (edge.getSource() == node) {
- column =
nodeList.indexOf(edge.getTarget());
- matrix[index][column] = val;
- } else {
- column =
nodeList.indexOf(edge.getSource());
- matrix[index][column] = val;
- }
}
if ((!ignoreMissing || found) && (!selectedOnly ||
hasSelectedEdge))
index++;
@@ -442,19 +448,20 @@
}
}
+ // XXX Do we need a new constructor to
clusterMaker.algorithms.DistanceMatrix?
private void buildGeneArrayMatrix(CyNetwork network, String[]
weightAttributes,
boolean transpose, boolean
ignoreMissing,
boolean selectedOnly) {
// Get the list of nodes
List<CyNode>nodeList = network.nodesList();
- if (selectedOnly) nodeList = new
ArrayList(network.getSelectedNodes());
+ if (selectedOnly) nodeList = new
ArrayList<CyNode>(network.getSelectedNodes());
// For debugging purposes, sort the node list by identifier
nodeList = sortNodeList(nodeList);
// Make a map of the conditions, indexed by CyNode
- HashMap<CyNode,HashMap<String,Double>>nodeCondMap = new
HashMap();
+ HashMap<CyNode,HashMap<String,Double>>nodeCondMap = new
HashMap<CyNode,HashMap<String,Double>>();
// Make a map of the conditions, by name
List<String>condList = Arrays.asList(weightAttributes);
@@ -465,7 +472,7 @@
// Iterate over all of our nodes, getting the conditions
attributes
for (CyNode node: nodeList) {
// Create the map for this node
- HashMap<String,Double>thisCondMap = new HashMap();
+ HashMap<String,Double>thisCondMap = new
HashMap<String,Double>();
for (int attrIndex = 0; attrIndex <
weightAttributes.length; attrIndex++) {
String attr = weightAttributes[attrIndex];
@@ -495,6 +502,7 @@
this.nRows = condList.size();
this.nColumns = nodeCondMap.size();
this.matrix = new Double[nRows][nColumns];
+ // this.matrix =
DoubleFactory2D.sparse.make(nRows,nColumns);
this.rowLabels = new String[nRows];
this.columnLabels = new String[nColumns];
this.columnNodes = new CyNode[nColumns];
@@ -512,6 +520,7 @@
String rowLabel = this.rowLabels[row];
if (thisCondMap.containsKey(rowLabel)) {
matrix[row][column] =
thisCondMap.get(rowLabel);
+ //
matrix.set(row,column,thisCondMap.get(rowLabel));
}
}
column++;
@@ -523,6 +532,7 @@
this.rowNodes = new CyNode[nRows];
this.columnLabels = new String[nColumns];
this.matrix = new Double[nRows][nColumns];
+ // this.matrix =
DoubleFactory2D.sparse.make(nRows,nColumns);
assignColumnLabels(condList);
int row = 0;
@@ -537,6 +547,7 @@
if
(thisCondMap.containsKey(columnLabel)) {
// System.out.println("Setting
matrix["+rowLabels[row]+"]["+columnLabel+"] to "+thisCondMap.get(columnLabel));
matrix[row][column] =
thisCondMap.get(columnLabel);
+ //
matrix.set(row,column,thisCondMap.get(columnLabel));
}
}
row++;
@@ -560,7 +571,7 @@
// sortNodeList does an alphabetical sort on the names of the nodes.
private List<CyNode>sortNodeList(List<CyNode>nodeList) {
- HashMap<String,CyNode>nodeMap = new HashMap();
+ HashMap<String,CyNode>nodeMap = new HashMap<String, CyNode>();
// First build a string array
String nodeNames[] = new String[nodeList.size()];
int index = 0;
@@ -571,7 +582,7 @@
// Sort it
Arrays.sort(nodeNames);
// Build the node list again
- ArrayList<CyNode>newList = new ArrayList(nodeList.size());
+ ArrayList<CyNode>newList = new
ArrayList<CyNode>(nodeList.size());
for (index = 0; index < nodeNames.length; index++) {
newList.add(nodeMap.get(nodeNames[index]));
}
Added:
csplugins/trunk/ucsf/scooter/clusterMaker/src/clusterMaker/algorithms/silhouette/SilhouetteResult.java
===================================================================
---
csplugins/trunk/ucsf/scooter/clusterMaker/src/clusterMaker/algorithms/silhouette/SilhouetteResult.java
(rev 0)
+++
csplugins/trunk/ucsf/scooter/clusterMaker/src/clusterMaker/algorithms/silhouette/SilhouetteResult.java
2011-08-15 02:12:47 UTC (rev 26551)
@@ -0,0 +1,81 @@
+/*
+ * To change this template, choose Tools | Templates
+ * and open the template in the editor.
+ */
+package clusterMaker.algorithms.silhouette;
+import java.util.ArrayList;
+
+/**
+ *
+ * @author lucasyao
+ *
+ * TODO: Package documentation
+ */
+public class SilhouetteResult {
+
+ int samplenumber;
+ ArrayList<Double> silhouetteValues;
+ ArrayList<Integer> neighborLabels;
+
+ /**
+ * !DOCUMENT ME!
+ */
+ public SilhouetteResult()
+ {
+ samplenumber = 0;
+ silhouetteValues = new ArrayList<Double>();
+ neighborLabels = new ArrayList<Integer>();
+ }
+
+ /**
+ * !DOCUMENT ME!
+ */
+ public void addSilhouettevalue(double value, Integer label)
+ {
+ samplenumber++;
+ silhouetteValues.add(value);
+ neighborLabels.add(label);
+ }
+
+ /**
+ * !DOCUMENT ME!
+ */
+ public void deleteSilhouettevalue(int index)
+ {
+ samplenumber--;
+ silhouetteValues.remove(index);
+ neighborLabels.remove(index);
+ }
+
+ /**
+ * !DOCUMENT ME!
+ */
+ public double getSilhouettevalue(int index)
+ {
+
+ return silhouetteValues.get(index).doubleValue();
+ }
+
+ /**
+ * !DOCUMENT ME!
+ */
+ public Integer getSilhouetteneighborlabel(int index)
+ {
+ return neighborLabels.get(index);
+ }
+
+ /**
+ * Return the average silhouette for this clustering.
+ *
+ * @return the average silhouette
+ */
+ public double getAverageSilhouette()
+ {
+ double avgS = 0;
+ for (Double v: silhouetteValues) {
+ avgS = avgS+v.doubleValue();
+ }
+ return avgS/(double)silhouetteValues.size();
+ }
+
+}
Added:
csplugins/trunk/ucsf/scooter/clusterMaker/src/clusterMaker/algorithms/silhouette/SilhouetteUtil.java
===================================================================
---
csplugins/trunk/ucsf/scooter/clusterMaker/src/clusterMaker/algorithms/silhouette/SilhouetteUtil.java
(rev 0)
+++
csplugins/trunk/ucsf/scooter/clusterMaker/src/clusterMaker/algorithms/silhouette/SilhouetteUtil.java
2011-08-15 02:12:47 UTC (rev 26551)
@@ -0,0 +1,129 @@
+/*
+ * To change this template, choose Tools | Templates
+ * and open the template in the editor.
+ */
+package clusterMaker.algorithms.silhouette;
+
+import clusterMaker.algorithms.hierarchical.DistanceMetric;
+import clusterMaker.algorithms.hierarchical.Matrix;
+
+import java.util.ArrayList;
+import java.util.HashMap;
+import java.util.Set;
+import java.util.Iterator;
+
+
+/**
+ *
+ * @author lucasyao
+ *
+ * TODO: Package documentation
+ */
+public class SilhouetteUtil {
+
+ /**
+ * This method calculates the silhouette for a given data matrix using a
metric as it's string. The current
+ * cluster is provided.
+ *
+ * @param matrix the data matrix
+ * @param metric the distrance metric we're using
+ * @param labels the labels for each of clusters
+ * @return the resulting silhouette
+ */
+ public static SilhouetteResult SilhouetteCalculator(Matrix matrix,
DistanceMetric metric, Integer[] labels)
+ {
+ double[][] distanceMatrix = matrix.getDistanceMatrix(metric);
+ return SilhouetteCalculator(distanceMatrix, labels);
+ }
+
+ /**
+ * !DOCUMENT ME!
+ */
+ public static SilhouetteResult SilhouetteCalculator(double[][]
distancematrix, Integer[] labels)
+ {
+
+ SilhouetteResult silresult = new SilhouetteResult();
+ HashMap<Integer, Integer> classlabels = new HashMap<Integer,
Integer>();
+ int samplenum = labels.length;
+
+ // Get the size of each cluster
+ for(int i=0; i<samplenum; i++)
+ {
+ Integer currentlabel = labels[i];
+ if(classlabels.containsKey(currentlabel))
+ {
+ int count = classlabels.get(currentlabel).intValue()+1;
+ classlabels.put(currentlabel, Integer.valueOf(count));
+ } else {
+ classlabels.put(currentlabel, 1);
+ }
+ }
+
+ // OK, now calculate the silhouete
+ for(int i=0;i<labels.length;i++)
+ {
+ double silhouettevalue=0;
+ double a=0;
+ double b=0;
+ int classnum = classlabels.size();
+ Integer classlabel = labels[i];
+
+ //initializing
+ HashMap<Integer, Double> bvalues = new HashMap<Integer, Double>();
+ for(int k=0; k<classnum; k++)
+ {
+ Set<Integer> labelset = classlabels.keySet();
+ for (Integer label: labelset)
+ {
+ bvalues.put(label, Double.valueOf(0));
+ }
+ }
+
+ //calculate distance by differnt classes
+ for(int j=0;j<samplenum;j++)
+ {
+ if (i == j) continue;
+ Integer currentclasslabel = labels[j];
+ double distancevalue =
bvalues.get(currentclasslabel).doubleValue();
+ distancevalue = distancevalue + distancematrix[i][j];
+ bvalues.put(currentclasslabel, Double.valueOf(distancevalue));
+ }
+
+ //calculate a b and silhouette
+ for(int k=0;k<classnum;k++)
+ {
+ double mindis = Double.MAX_VALUE;
+ Integer minlabel = null;
+ Set<Integer> labelset = classlabels.keySet();
+ for (Integer label: labelset)
+ {
+ int count = classlabels.get(label).intValue();
+ double value = bvalues.get(label).doubleValue();
+
+ if(label.equals(classlabel))
+ a = value/count;
+ else {
+ b = value/count;
+ if(b<mindis)
+ {
+ mindis = b;
+ minlabel = label;
+ }
+ }
+ }
+
+ if(a>b) {
+ silhouettevalue = (b-a)/a;
+ } else {
+ silhouettevalue = (b-a)/b;
+ }
+
+ silresult.addSilhouettevalue(silhouettevalue, minlabel);
+
+ }
+ }
+
+ return silresult;
+ }
+
+}
--
You received this message because you are subscribed to the Google Groups
"cytoscape-cvs" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/cytoscape-cvs?hl=en.
