minimizedisagreementsclustering.java

这是一个matlab的java实现。里面有许多内容。请大家慢慢捉摸。

		while (i.hasNext()) {
	    tSet.add(i.next());
		}
		return tSet;  // sorted using comparator
	}

	private double getVWeight (Vertex v, Graph g)
	{
		double posWeight = 0.0;
		Iterator i = g.getEdges(v).iterator();
		while (i.hasNext()) {
	    double w = ((WeightedEdgeImpl)i.next()).getWeight();
	    if (w > 0.0)
				posWeight += w;
		}
		return posWeight;
	}
    
	// XXX OPTIMIZE
	private Vertex selectRandomVertex(Graph g)
	{
		Set vs = g.getVertexSet();
		Object []o = vs.toArray();
		int rval = randGen.nextInt(g.getVerticesCount());
		return (Vertex)o[rval]; // for speed
	}
    
	// set of neighbors with positive edge value AND this vertex
	private Set getNPlus (Graph curGraph, Vertex v)
	{
		LinkedHashSet nplus = new LinkedHashSet();		
		List edges = curGraph.getEdges(v);
		WeightedEdge curEdge = null;
	
		Iterator iter = edges.iterator();
		while (iter.hasNext())
		{
			curEdge = (WeightedEdge)iter.next();
			if (curEdge.getWeight() > 0) {
		    nplus.add(curEdge.getVertexA());
		    nplus.add(curEdge.getVertexB());
			}
		}
		nplus.remove(v);  // ensure v is not in there
		return nplus;
	}

	private Cluster findOptimalCluster (Graph curGraph, Set curCluster, double threshold)
	{
		Vertex curWorst = null;  // the current worst vertex
		boolean stillBads = true;
		double worst = 0.0;  // keeps track of the value of the worst vertex
		Cluster copyCluster = new Cluster();
		Iterator i = curCluster.iterator();
		while (i.hasNext()) {
	    copyCluster.add(i.next());
		}

		while (stillBads) {
	    stillBads = false;
	    Iterator iter = copyCluster.iterator();
	    while (iter.hasNext()) {
				Vertex v = (Vertex)iter.next();
				double w = howGood(curGraph, v, copyCluster);
				if (w < threshold) {
					curWorst = v;
					worst = w;
					stillBads = true;
				}
	    }
	    copyCluster.remove(curWorst);
		}
		return copyCluster;
	}

	/*
	// old one
	private Set findOptimalCluster (Graph curGraph, Set curCluster)
	{
	SortedSet allVertices = sortSet(curGraph.getVertexSet(),comparator);
	System.out.println("AllVertices: ");
	Set c1 = removeDeltaBads (curGraph, curCluster); // actual reduced set
	System.out.println("Reduced set: " + c1);
	Set c2 = addDeltaGoods (allVertices, c1, curGraph); // set to add to reduced one
	System.out.println("goods to add back: " + c2);
	Set c3 = setAdd (c1, c2);
	return c3;
	}
	*/    
	private Set removeDeltaBads (Graph curGraph, Set curCluster)
	{
		boolean allClear = false;
		while (!allClear)
		{
			boolean iterate = true;
			Iterator i = curCluster.iterator();
			Vertex v = null;
			while (iterate && i.hasNext()) {
		    v = (Vertex)i.next();
		    if (!(deltaGood (curGraph, v, curCluster, removeDelta))) {
					removesCnt++;
					System.out.println("Removing " + v + " from " + curCluster + " via" + curGraph.getVertexSet());
					iterate = false; // stop iterating
		    }
			}
			if (iterate && !i.hasNext())
		    allClear = true;
			if (v != null)
		    curCluster.remove(v);
		}
		return curCluster;
	}
    
	private Set addDeltaGoods (Set allVertices, Set curCluster, Graph curGraph)
	{
		Set goods = new LinkedHashSet ();
		Iterator i = allVertices.iterator();
		while (i.hasNext())
		{
			Vertex v = (Vertex)i.next();
			if (deltaGood (curGraph, v, curCluster, addDelta)) {
		    goods.add(v);
			}
		}
		return goods;
	}
    
	// New version of delta good takes into account edge weights
	// XXXX NOTE: we may have recalibrate delta value because of lower values
	/*
    private boolean deltaGood (Graph curGraph, Vertex v, Set cluster, double curDelta)
    {
		System.out.println("Checking d-good on: " + v + " wrt " + cluster + " in " +curGraph.getVertexSet());
		int clusterSize = cluster.size();
		Set nplus = getNPlus (curGraph, v);
		Set i1 = setIntersection (nplus, cluster);
		double sumOfEdgeWeights1 = getSumOfEdgeWeights (i1, v, curGraph);
		System.out.println(" -- intersection: " + i1);
		if ((sumOfEdgeWeights1 + (1 - curDelta)) < ((1 - curDelta) * clusterSize)) {
		System.out.println("false: " + (sumOfEdgeWeights1 + delta));
		return false;
		}
		Set diff = setSubtract (curGraph.getVertexSet(), cluster);
		Set i2 = setIntersection (nplus, diff);
		double sumOfEdgeWeights2 = getSumOfEdgeWeights (i2, v, curGraph);
		if ((sumOfEdgeWeights2 + curDelta) > (curDelta * clusterSize)) {
		System.out.println("False: " + (sumOfEdgeWeights2 + curDelta) + " and " + (curDelta * clusterSize));
		return false;
		}
		else {
		goodsCnt++;
		System.out.println(v + " is d-good wrt " + cluster + " in " + curGraph);
		return true;
		}
    }
	*/
	private double getSumOfEdgeWeights (Set s1, Vertex v, Graph curGraph)
	{
		List allEdges = curGraph.getEdges(v);
		Iterator allIter = allEdges.iterator();
		double curSum = 0.0;

		while (allIter.hasNext()) {
	    WeightedEdgeImpl e = (WeightedEdgeImpl)allIter.next();
	    if (((e.getVertexA() == v) && s1.contains(e.getVertexB())) ||
					((e.getVertexB() == v) && s1.contains(e.getVertexA())))
				curSum += e.getWeight();
		}
		return curSum;
	}


	private boolean deltaGood (Graph curGraph, Vertex v, Set cluster, double curDelta)
	{
		int clusterSize = cluster.size();
		Set nplus = getNPlus (curGraph, v);
		nplus.add(v);
		Set i1 = setIntersection (nplus, cluster);
		System.out.println(" -- intersection: " + i1);
		if (i1.size() < ((1 - curDelta) * clusterSize)) {
	    System.out.println ("BAD 1");
	    return false;
		}
		Set diff = setSubtract (curGraph.getVertexSet(), cluster);
		System.out.println("DIFF: " + diff);
		Set i2 = setIntersection (nplus, diff);
		System.out.println("i2 = " + i2);
		if (i2.size() > (curDelta * clusterSize)) {
	    System.out.println("BAD 2");
	    return false;
		}
		else {
	    goodsCnt++;
	    return true;
		}
	}
    

	private double howGood (Graph curGraph, Vertex v, Set cluster)
	{
		// val = sum of all edge weights within cluster +
		//       inverse sum of all edge weights of GraphVertices - Cluster
		// Idea is to remove the worst vertices *first* in the removeDeltaBads phase
		//   this should provide a better clustering . . . .
		//    -- but chance for big clusters to dominate
		double val = 0.0;
		List edges = curGraph.getEdges(v);
		Iterator i = edges.iterator();
		while (i.hasNext()) {
	    WeightedEdge e = (WeightedEdgeImpl)i.next();
	    if (((e.getVertexA() == v)&& (cluster.contains(e.getVertexB()))) ||
					((e.getVertexB() == v)&& (cluster.contains(e.getVertexA()))))
				val += e.getWeight();
	    else
				val -= e.getWeight();
		}
		return val;
	}
    
	private Set setAdd (Set s1, Set s2)
	{
		LinkedHashSet s = new LinkedHashSet ();
		Iterator i1 = s1.iterator();
		Iterator i2 = s2.iterator();
	
		while (i1.hasNext())
		{
			s.add(i1.next());
		}
		while (i2.hasNext())
		{
			s.add(i2.next());
		}
		return s;
	}
    
	private Set setIntersection (Set s1, Set s2)
	{
		LinkedHashSet s = new LinkedHashSet ();
		Iterator i1 = s1.iterator();
	
		while (i1.hasNext())
		{
			Object el = i1.next();
			if (s2.contains(el))
		    s.add(el);
		}
		return s;
	}
    
	private Set setSubtract (Set s1, Set s2)
	{
		LinkedHashSet s = new LinkedHashSet ();
		Iterator i1 = s1.iterator();
	
		while (i1.hasNext())
		{
			Object el  = i1.next();
			if (!s2.contains(el))
		    s.add(el);
		}
		return s;
	}
    
	public static MappedGraph generateRandomMappedGraph (int size, double posRand)
	{
		int i;
		MappedGraph g = new MappedGraph();
		Vector vertices = new Vector(); // gross
		double val = 0.0;
		Random statRandGen = new Random();
		// add vertices first
		for (i = 0; i < size; i++)
		{
			Integer v = new Integer (i); 
			try {
		    g.addVertexMap (v);
			} catch (Exception e) {e.printStackTrace();}
			vertices.add(v);
		}
	
		for (i = 0; i < size; i++) {
	    for (int j = 0; j < i; j++)
			{
		    if (statRandGen.nextFloat() < posRand)
					val = 1.0;
		    else
					val = -1.0;
		    try {
					g.addEdgeMap ((Object)vertices.elementAt(j),
												(Object)vertices.elementAt(i), val);
		    } catch (Exception f) {f.printStackTrace();}
			}
		}
		return g;
	}

	public static WeightedGraph generateRandomWeightedGraph (int size, double posRand)
	{
		int i;
		WeightedGraph g = new WeightedGraphImpl();
		Vector vertices = new Vector(); // gross
		double val = 0.0;
		Random statRandGen = new Random();
		// add vertices first
		for (i = 0; i < size; i++)
		{
			Vertex v = new VertexImpl (new Integer (i)); 
			try {
		    g.add (v);
			} catch (Exception e) {e.printStackTrace();}
			vertices.add(v);
		}
	
		for (i = 0; i < size; i++) {
	    for (int j = 0; j < i; j++)
			{
		    if (statRandGen.nextFloat() < posRand)
					val = 1.0;
		    else
					val = -1.0;
		    try {
					g.addEdge ((Vertex)vertices.elementAt(j),
										 (Vertex)vertices.elementAt(i), val);
		    } catch (Exception f) {f.printStackTrace();}
			}
		}
		return g;
	}
    
    
	public static void main (String[] args)
	{

		int SIZE = 5;

		MappedGraph tg =
	    new MappedGraph();
	
		Set s1 = new LinkedHashSet();
		Set s2 = new LinkedHashSet();
		Set s3 = new LinkedHashSet();
		s1.add(new String ("foo"));
		s2.add(new String ("bar"));
		s3.add(new String ("baz"));

		try {
	    tg.addEdgeMap (s1,s2, -0.25);
	    tg.addEdgeMap (s2,s3, 0.5);
	    tg.addEdgeMap (s1,s3, 0.5);
	    //tg.addEdge (v1,v4, -0.5);
	    //tg.addEdge (v2,v4, -0.5);
	    //tg.addEdge (v3,v4, -0.1);
		} catch (Exception e) {e.printStackTrace();}
		System.out.println(tg.toString());
		MinimizeDisagreementsClustering cl1 = new
																					MinimizeDisagreementsClustering(tg,(double)1/44);
		Set clusters1 = cl1.getClustering(null);
		System.out.println("clusters: " + clusters1);
	
		MappedGraph g =
	    MinimizeDisagreementsClustering.generateRandomMappedGraph (10, 0.1);
	
		System.out.println (g.toString());

		Set clusterSets[] = new Set[SIZE];
	
		for (int i=0; i < SIZE; i++) {
	    MinimizeDisagreementsClustering cl = new
																					 MinimizeDisagreementsClustering(g,(double)1/44);
	    System.out.println(cl);
	    Set clusters = cl.getClustering(null, -5.0); 
	    System.out.println("There are " + clusters.size() + " clusters in this graph.\n");
	    System.out.println("Clusters: " + clusters);
	    clusterSets[i] = clusters;
		}

		for (int i=0; i < SIZE; i++) {
	    for (int j=i; j < SIZE; j++) {
				ClusterEvaluate eval = new ClusterEvaluate (clusterSets[i], clusterSets[j]);
				eval.evaluate();
				System.out.println("Score " + i + "-" + j + " " + eval.getF1());
	    }
		}

		//System.out.println("There are " + clusters.size() + " clusters in this graph.");
	}
}