corefclusteradv.java

来自「mallet是自然语言处理、机器学习领域的一个开源项目。」· Java 代码 · 共 1,911 行 · 第 1/5 页

					//WeightedEdge chosenEdge = chooseEdge(sortedEdges, minVal,
					//totalVal, rand);
					//WeightedEdge chosenEdge = chooseEdge2(sortedEdges, minVal,
					//totalVal, rand);
					WeightedEdge chosenEdge = chooseEdge2(sortedEdges, minVal, totalVal, rand);

					if (chosenEdge != null) {
						VertexImpl v1 = (VertexImpl)chosenEdge.getVertexA();
						VertexImpl v2 = (VertexImpl)chosenEdge.getVertexB();

						/*
							System.out.println("Best edge val: " + chosenEdge.getWeight());
							System.out.println("Merging vertices: " + v1.getObject()
							+ " and " + v2.getObject()); */
						mergeVertices(graph, v1, v2);
					}
				} else // edges has size zero
					break;
				if ((evalFreq > 0) && ((iter % evalFreq) == 0)) {
					curPartitioning = getCollectionOfOriginalObjects ((Collection)graph.getVertexSet());
					cost = evaluatePartitioning(curPartitioning, origGraph);

					if (keyPartitioning != null && curPartitioning != null) {
						PairEvaluate pairEval = new PairEvaluate (keyPartitioning, curPartitioning);
						pairEval.evaluate();
						treeCost = 0.0;
						if (treeModel != null)
							treeCost = treeModel.computeTreeObjFn (curPartitioning);

						System.out.println(cost + "," + evaluateAgainstKey (curPartitioning)
															 + "," + pairEval.getF1() + "," + treeCost + "," +
															 curPartitioning.size());
					} else {
						if (keyPartitioning == null)
							System.out.println(" keyPart is NULL!!");
						if (curPartitioning == null)
							System.out.println(" curPart is NULL!!");
					}
					
					//System.out.println("Cost at iteration " + iter + " is: " + cost);
					// in this case, we've gone too far and have lowered the FN value
					if (!trueNumStop && cost <= bCost) {
						//System.out.println("Graph val reduced to " + cost + " from " + prevCost);
						//System.out.println("Due to merging on edge with weight: " +
						//chosenEdge.getWeight());
						graph = graph1; // set graph to what is was before the merge
						numReductions++; // increment the number of reductions

						//reset the evaluation frequency
						evalFreq = (int)Math.ceil(evalFreq/2);
					}
					else {
						numReductions = 0;
						localBestPartitioning = curPartitioning;
						bCost = cost; // let prevCost now equal the new higher cost
					}
					// only copy graph if we allow back-tracking in search
					if (!trueNumStop)
						graph1 = copyGraph(graph);  // make a copy of the graph
				}

				iter++;
				// we stop when we've tried to increase the obj fn value
				// MAX_REDUCTIONS times
				if (!trueNumStop && (numReductions > MAX_REDUCTIONS))
					break;

				if (trueNumStop && (graph.getVertexSet().size() <= keyPartitioning.size())) {
					localBestPartitioning = curPartitioning;
					break;
				}
	    }
	    curPartitioning = getCollectionOfOriginalObjects ((Collection)graph.getVertexSet());			
	    if (localBestPartitioning == null)
				localBestPartitioning = curPartitioning;

	    //System.out.println("best cost was: " + bCost);
	    curCost = evaluatePartitioning(localBestPartitioning, origGraph);
	    //System.out.println("curCost is: " + curCost);
	    //double curAgree = evaluatePartitioningAgree(localBestPartitioning, origGraph);
	    //double curDisAgree = evaluatePartitioningDisAgree(localBestPartitioning, origGraph);
	    PairEvaluate pairEval = new PairEvaluate (keyPartitioning, localBestPartitioning);
	    pairEval.evaluate();
			
	    if (treeModel != null)
				treeCost = treeModel.computeTreeObjFn (curPartitioning);

	    if (curCost > bestCost) {
				bestCost = curCost;
				bestPartitioning = localBestPartitioning;

	    }

	    System.out.println(curCost + "," + evaluateAgainstKey (localBestPartitioning)
												 + "," + pairEval.getF1() + "," + treeCost + "," + keyPartitioning.size());

		}
		return bestPartitioning;

	}

	public double evaluateAgainstKey (Collection col) {
		if (keyPartitioning != null) {

	    ClusterEvaluate cl = new ClusterEvaluate(keyPartitioning, col);
	    cl.evaluate();
	    //cl.printResults();
	    //cl.printVerbose();
	    return cl.getRecall();
		}
		return 0.0;

	}
 
	public class EdgeComparator implements Comparator {

		public EdgeComparator () {}

		public int compare (Object e1, Object e2) {
	    // note that this is backwards because we want it to sort in
	    // descending order
	    if (e1 == e2)
				return 0;
	    double val = ((WeightedEdge)e2).getWeight()-((WeightedEdge)e1).getWeight();
	    if (val > 0)
				return 1;
	    else
				return -1;
			
		}
		
		public boolean equals (Object e1, Object e2) {
	    return e1 == e2;
		}

	}

	public class PseudoEdgeComparator implements Comparator {

		public PseudoEdgeComparator () {}

		public int compare (Object e1, Object e2) {
	    // note that this is backwards because we want it to sort in
	    // descending order
	    if (e1 == e2)
				return 0;
	    double val = ((PseudoEdge)e2).getWeight()-((PseudoEdge)e1).getWeight();
	    if (val > 0)
				return 1;
	    else
				return -1;
		}
		public boolean equals (Object e1, Object e2) {
	    return e1 == e2;
		}
	}

	/**
	 * Construct a Collection of Collections where the objects in the
	 * collections are the original objects (i.e. the object of the vertices)
	 */
	public Collection getCollectionOfOriginalObjects (Collection vertices) {
		Collection collection = new LinkedHashSet();
		Iterator i1 = vertices.iterator();
		while (i1.hasNext()) {
	    VertexImpl v = (VertexImpl)i1.next();
	    Object o = v.getObject(); // underlying object
	    if (o != null) {
				Collection c1 = new LinkedHashSet();
				if (o instanceof Collection) {
					Iterator i2 = ((Collection)o).iterator();
					while (i2.hasNext()) {
						c1.add(i2.next());   // add the underlying object
					}
				} else {
					// in this case, the vertex is a singleton, but we wrap it in a
					// Collection so that we always have a collection of collections
					c1.add(o);
				}
				collection.add(c1); // add the cluster to the collection of clusters
	    }
		}
		return collection;
	}

	/**
	 * The graph may not be fully connected.  If an edge does not exist,
	 * that corresponds to an edge weight of negative inifinite.  So,
	 * before merging two vertices, one must add in any negative weights.
	 * For example, if v1 has an edge to v3 but v2 does not, then the
	 * merged v1-v2 should have a negative weighted edge to v3.
	 * @param g
	 * @param v1
	 * @param v2
	 */
	private void addNegativeWeights(WeightedGraph g, Vertex v1, Vertex v2) {
		List adjacentToV1;
		List adjacentToV2;

		adjacentToV1 = g.getAdjacentVertices(v1);
		adjacentToV2 = g.getAdjacentVertices(v2);

		// Check that v1 is connected to all of v2's adjacent vertices
		for (int i=0; i < adjacentToV2.size(); i++) {
	    Vertex v = (Vertex)adjacentToV2.get(i);
	    //System.out.println("v1: " + v1 + " v: " + v);
	    if (v == v1) {
				continue;
	    }
	    if (!adjacentToV1.contains(v)) {
				try {
					g.addEdge(v, v1, NegativeInfinite);
				} catch (Exception e) { e.printStackTrace(); }
	    }
		}
		// Check that v2 is connected to all of v1's adjacent vertices
		for (int i=0; i < adjacentToV1.size(); i++) {
	    Vertex v = (Vertex)adjacentToV1.get(i);
	    //System.out.println("v2: " + v2 + " v " + v + " " + g.isConnected(v, v2));
	    if (v == v2) {
				continue;
	    }
	    if (!adjacentToV2.contains(v)) {
				try {
					System.out.println("Adding negative infinite edge: " + v2 + " to " + v);
					g.addEdge(v, v2, NegativeInfinite);
				} catch (Exception e) { e.printStackTrace(); }
	    }
		}
	}

	private void printVObj (Object o1) {
		if (o1 instanceof List) {
	    List l10 = (List)o1;
	    for (int k=0; k < l10.size(); k++) {
				System.out.print(" " + ((Citation)l10.get(k)).getIndex());
	    }
		} else 
	    System.out.print(" " + ((Citation)o1).getIndex());
	}

	public void mergeVertices (WeightedGraph g, VertexImpl v1, VertexImpl v2) {
		// Change: mhay 1/10/04
		//addNegativeWeights(g, v1, v2);

		Object o1 = v1.getObject();
		Object o2 = v2.getObject();
		List l1 = new ArrayList();

		//System.out.println("Merging o1 = " + toString(o1) + " and o2 = " +
		//toString(o2));
		if (o1 instanceof List)
			l1.addAll ((List)o1);
		else l1.add (o1);
		if (o2 instanceof List)
			l1.addAll ((List)o2);
		else l1.add (o2);

		
/*		if ((o1 instanceof List) && (o2 instanceof List)) {
	    l1.addAll((List)o1);
	    l1.addAll((List)o2);
		} else if (o1 instanceof List) {
	    l1.addAll((List)o1);
	    l1.add(o2);
		} else if (o2 instanceof List) {
	    l1.addAll((List)o2);
	    l1.add(o1);
		} else {
	    l1.add(o1);
	    l1.add(o2);
		}
*/		

		VertexImpl newVertex = new VertexImpl(l1);
		try {
	    g.add(newVertex);
		} catch (Exception e) {
	    e.printStackTrace();
		}
		List edges1 = (List) g.getEdges(v1);
		Iterator i1 = edges1.iterator();

		HashMap hm = new HashMap();
		while (i1.hasNext()) {
	    WeightedEdge e = (WeightedEdge) i1.next();
	    if ((e.getVertexA() == v1) && (e.getVertexB() != v2))
				hm.put((Object) e.getVertexB(), new Double(e.getWeight()));
	    else if (e.getVertexA() != v2)
				hm.put((Object) e.getVertexA(), new Double(e.getWeight()));
		}
		try {
	    g.remove(v1); // this also removes all edges incident with this vertex
		} catch (Exception ex) {
	    ex.printStackTrace();
		}

		//		System.out.println("Hashmap for vertex: " + v1 + " is: " + hm);
		List edges2 = (List)g.getEdges(v2);
		Iterator i2 = edges2.iterator();
		Vertex cv = null;
		
		
		if (edges2.size() > 0) {
	    while (i2.hasNext()) {
				WeightedEdge e = (WeightedEdge)i2.next();
				if (e.getVertexA() == v2)
					cv = e.getVertexB();
				else
					cv = e.getVertexA();

				double w2 = ((Double)hm.get(cv)).doubleValue();
				double w1 = e.getWeight();
				//double weight = (w1 > w2) ? w1 : w2;   // max
				double weight = (w1 + w2)/2;   // avg
				if (w1 == NegativeInfinite || w2 == NegativeInfinite) {
					weight = NegativeInfinite; // precaution: avoid creeping away from Infinite
				}
				WeightedEdge ne = new WeightedEdgeImpl(newVertex, cv, weight);
				try {
					g.addEdge(ne);
				} catch (Exception ex) { ex.printStackTrace(); }
	    }
		} else { // in this case, no edges are left, just add new Vertex
	    try {
				g.add(newVertex);
	    }	catch (Exception ex) { ex.printStackTrace(); }
		}
		try {
	    g.remove(v2);
		}	catch (Exception ex) { ex.printStackTrace(); }
		
		//		System.out.println("After adding new edges: " + g);
	}

	public void printGraph (WeightedGraph g) {
		Set vs = g.getVertexSet();
		Iterator i = vs.iterator();
		System.out.println("Vertices: " + vs);
		while (i.hasNext()) {
	    VertexImpl v = (VertexImpl)i.next();
	    printVObj(v.getObject());
	    System.out.println(" ");
		}
		Set es = g.getEdgeSet();
		Iterator i2 = es.iterator();
		System.out.println("Edges: ");
		while (i2.hasNext()) {
	    WeightedEdge e = (WeightedEdge)i2.next();
	    VertexImpl v1 = (VertexImpl)e.getVertexA();
	    VertexImpl v2 = (VertexImpl)e.getVertexB();
	    printVObj(v1.getObject());
	    System.out.print(" <----> (" + e.getWeight() + ") ");
	    printVObj(v2.getObject());
	    System.out.println("");
		}

	}

	private double computeScore_NBest (MaxEnt classifier, Instance origInstPair, int ind1, int ind2) {
		NodePair origNodePair = (NodePair)origInstPair.getSource();
		Citation citation1 = (Citation)origNodePair.getObject1();
		Citation citation2 = (Citation)origNodePair.getObject2();
		Citation nBest1 = citation1.getNthBest(ind1);
		Citation nBest2 = citation2.getNthBest(ind2);
		NodePair newPair = new NodePair (nBest1, nBest2);
		Pipe pipe = origInstPair.getPipe();
		return computeScore(classifier, new Instance(newPair, "yes", null, newPair, pipe));
	}


	/**
	 * This method assumes that the instance is a pair of Citation and that the
	 * Citation objects have an N-best list for the n-best segmentations. The
	 * edge value returned is simply the MAX score of any pair of citations.
	 *
	 * @param classifier
	 * @param origInstPair
	 * @return
	 */
	private double computeScore_NBest(MaxEnt classifier, Instance origInstPair) {
		NodePair origNodePair = (NodePair)origInstPair.getSource();