icssearchalgorithm.java

数据挖掘聚类算法：bayes源代码,使用JAVA语言实现

	 * a->c<-b and a-/-b. These nodes are identified by finding nodes
	 * a,b,c in the skeleton such that a--c, c--b and a-/-b and furthermore
	 * c is not in the set Z that separates a and b
	 * @param edges skeleton
	 * @param arrows resulting partially directed skeleton after all V-nodes 
	 * have been identified
	 * @param sepsets separating sets
	 */
	void calcVeeNodes(
		boolean[][] edges,
		boolean[][] arrows,
		SeparationSet[][] sepsets) {

		// start with complete empty graph
		for (int iNode1 = 0; iNode1 < maxn(); iNode1++) {
			for (int iNode2 = 0; iNode2 < maxn(); iNode2++) {
				arrows[iNode1][iNode2] = false;
			}
		}

		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 \n"
              + "\tfor a set Z that separates the nodes. MaxCardinality determines \n"
              + "\tthe maximum size of the set Z. This greatly influences the \n"
              + "\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. <p/>
	 *
	 <!-- options-start -->
	 * Valid options are: <p/>
	 * 
	 * <pre> -cardinality &lt;num&gt;
	 *  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 2)</pre>
	 * 
	 * <pre> -mbc
	 *  Applies a Markov Blanket correction to the network structure, 
	 *  after a network structure is learned. This ensures that all 
	 *  nodes in the network are part of the Markov blanket of the 
	 *  classifier node.</pre>
	 * 
	 * <pre> -S [BAYES|MDL|ENTROPY|AIC|CROSS_CLASSIC|CROSS_BAYES]
	 *  Score type (BAYES, BDeu, MDL, ENTROPY and AIC)</pre>
	 * 
	 <!-- options-end -->
	 * 
	 * @param options the list of options as an array of strings
	 * @throws 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.";
	}

	/**
	 * Returns the revision string.
	 * 
	 * @return		the revision
	 */
	public String getRevision() {
	  return RevisionUtils.extract("$Revision: 1.8 $");
	}

	/**
	 * for testing the class
	 * 
	 * @param argv the commandline parameters
	 */
	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