icssearchalgorithm.java

MacroWeka扩展了著名数据挖掘工具weka

		for (int iNode1 = 0; iNode1 < maxn() - 1; iNode1++) {
			for (int iNode2 = iNode1 + 1; iNode2 < maxn(); iNode2++) {
				if (!edges[iNode1][iNode2]) { /*i nonadj j*/
					for (int iNode3 = 0; iNode3 < maxn(); iNode3++) {
						if ((iNode3 != iNode1
							&& iNode3 != iNode2
							&& edges[iNode1][iNode3]
							&& edges[iNode2][iNode3])
							& (!sepsets[iNode1][iNode2].contains(iNode3))) {
							arrows[iNode1][iNode3] = true; /*add arc i->k*/
							arrows[iNode2][iNode3] = true; /*add arc j->k*/
						}
					}
				}
			}
		}
	} // CalcVeeNodes


	/** CalcArcDirections assigns directions to edges that remain after V-nodes have
	 * been identified. The arcs are directed using the following rules:
	   Rule 1: i->j--k & i-/-k => j->k
	   Rule 2: i->j->k & i--k => i->k
	   Rule 3  m
			 /|\
			i | k  => m->j
	i->j<-k  \|/
			  j
	
	   Rule 4  m
			 / \
			i---k  => i->m & k->m
	  i->j   \ /
			  j
	   Rule 5: if no edges are directed then take a random one (first we can find)
	 * @param edges : skeleton
	 * @param arrows : resulting fully directed DAG
	 */
	void calcArcDirections(boolean[][] edges, boolean[][] arrows) {
		/*give direction to remaining arcs*/
		int i, j, k, m;
		boolean bFound;

		do {
			bFound = false;

			/*Rule 1: i->j--k & i-/-k => j->k*/

			for (i = 0; i < maxn(); i++) {
				for (j = 0; j < maxn(); j++) {
					if (i != j && arrows[i][j]) {
						for (k = 0; k < maxn(); k++) {
							if (i != k
								&& j != k
								&& edges[j][k]
								&& !edges[i][k]
								&& !arrows[j][k]
								&& !arrows[k][j]) {
								arrows[j][k] = true;
								bFound = true;
							}
						}
					}
				}
			}

			/*Rule 2: i->j->k & i--k => i->k*/

			for (i = 0; i < maxn(); i++) {
				for (j = 0; j < maxn(); j++) {
					if (i != j && arrows[i][j]) {
						for (k = 0; k < maxn(); k++) {
							if (i != k
								&& j != k
								&& edges[i][k]
								&& arrows[j][k]
								&& !arrows[i][k]
								&& !arrows[k][i]) {
								arrows[i][k] = true;
								bFound = true;
							}
						}
					}
				}
			}

			/* Rule 3  m
			         /|\
			        i | k  => m->j
			i->j<-k  \|/
			          j
			*/
			for (i = 0; i < maxn(); i++) {
				for (j = 0; j < maxn(); j++) {
					if (i != j && arrows[i][j]) {
						for (k = 0; k < maxn(); k++) {
							if (k != i
								&& k != j
								&& arrows[k][j]
								&& !edges[k][i]) {
								for (m = 0; m < maxn(); m++) {
									if (m != i
										&& m != j
										&& m != k
										&& edges[m][i]
										&& !arrows[m][i]
										&& !arrows[i][m]
										&& edges[m][j]
										&& !arrows[m][j]
										&& !arrows[j][m]
										&& edges[m][k]
										&& !arrows[m][k]
										&& !arrows[k][m]) {
										arrows[m][j] = true;
										bFound = true;
									}
								}
							}
						}
					}
				}
			}

			/* Rule 4  m
			         / \
			        i---k  => i->m & k->m
			  i->j   \ /
			          j
			*/
			for (i = 0; i < maxn(); i++) {
				for (j = 0; j < maxn(); j++) {
					if (i != j && arrows[j][i]) {
						for (k = 0; k < maxn(); k++) {
							if (k != i
								&& k != j
								&& edges[k][j]
								&& !arrows[k][j]
								&& !arrows[j][k]
								&& edges[k][i]
								&& !arrows[k][i]
								&& !arrows[i][k]) {
								for (m = 0; m < maxn(); m++) {
									if (m != i
										&& m != j
										&& m != k
										&& edges[m][i]
										&& !arrows[m][i]
										&& !arrows[i][m]
										&& edges[m][k]
										&& !arrows[m][k]
										&& !arrows[k][m]) {
										arrows[i][m] = true;
										arrows[k][m] = true;
										bFound = true;
									}
								}
							}
						}
					}
				}
			}

			/*Rule 5: if no edges are directed then take a random one (first we can find)*/

			if (!bFound) {
				i = 0;
				while (!bFound && i < maxn()) {
					j = 0;
					while (!bFound && j < maxn()) {
						if (edges[i][j]
							&& !arrows[i][j]
							&& !arrows[j][i]) {
							arrows[i][j] = true;
							bFound = true;
						}
						j++;
					}
					i++;
				}
			}

		}
		while (bFound);

	} // CalcArcDirections

	/**
	 * Returns an enumeration describing the available options.
	 *
	 * @return an enumeration of all the available options.
	 */
	public Enumeration listOptions() {
	  Vector result = new Vector();
	  
	  result.addElement(new Option(
                "\tWhen determining whether an edge exists a search is performed "
              + "\tfor a set Z that separates the nodes. MaxCardinality determines "
              + "\tthe maximum size of the set Z. This greatly influences the "
              + "\tlength of the search. (default  2)",
	      "cardinality", 1, "-cardinality <num>"));
	  
	  Enumeration en = super.listOptions();
	  while (en.hasMoreElements())
	    result.addElement(en.nextElement());
	  
	  return result.elements();
	} // listOption
	
	/**
	 * Parses a given list of options. Valid options are:<p>
	 * @param options the list of options as an array of strings
	 * @exception Exception if an option is not supported
	 */
	public void setOptions(String[] options) throws Exception {
	  String        tmpStr;
	  
	  tmpStr = Utils.getOption("cardinality", options);
	  if (tmpStr.length() != 0)
	    setMaxCardinality(Integer.parseInt(tmpStr));
	  else
            setMaxCardinality(2);
            
          super.setOptions(options);
	} // setOptions
	
	/**
	 * Gets the current settings of the Classifier.
	 *
	 * @return an array of strings suitable for passing to setOptions
	 */
	public String[] getOptions() {
	  Vector        result;
	  String[]      options;
	  int           i;
	  
	  result  = new Vector();
	  options = super.getOptions();
	  for (i = 0; i < options.length; i++)
	    result.add(options[i]);
	  
	  result.add("-cardinality");
	  result.add("" + getMaxCardinality());
	  
	  return (String[]) result.toArray(new String[result.size()]);
	} // getOptions


	/**
	 * @return a string to describe the MaxCardinality option.
	 */
	public String maxCardinalityTipText() {
	  return "When determining whether an edge exists a search is performed for a set Z "+
	  "that separates the nodes. MaxCardinality determines the maximum size of the set Z. " +
	  "This greatly influences the length of the search. Default value is 2.";
	} // maxCardinalityTipText

	/**
	 * This will return a string describing the search algorithm.
	 * @return The string.
	 */
	public String globalInfo() {
	  return "This Bayes Network learning algorithm uses conditional independence tests " +
	  "to find a skeleton, finds V-nodes and applies a set of rules to find the directions " +
	  "of the remaining arrows.";
	}

	static public void main(String [] argv) {
		try {
			BayesNet b = new BayesNet();
			b.setSearchAlgorithm( new ICSSearchAlgorithm());
			Instances instances = new Instances(new FileReader("C:\\eclipse\\workspace\\weka\\data\\contact-lenses.arff"));
			instances.setClassIndex(instances.numAttributes() - 1);
			b.buildClassifier(instances);
			System.out.println(b.toString());
		} catch (Exception e) {
			e.printStackTrace();
		}
	} // main

} // class ICSSearchAlgorithm