CMAR代码学习2 计算卡方值并利用CR-tree剪枝

CMAR代码学习2 计算卡方值并利用CR-tree剪枝,第1张

CMAR代码学习1 生成FP-tree挖掘规则https://blog.csdn.net/woshiwu6666/article/details/124717377

有一个java语法的知识点,通过赋值给属性会自动调用toString方法 

要特别注意的是,下面这个例子当中,要写成return "Animal [i=" + this.i + ", o=" + this.o +",kafang=" +(this.kafang=(NUMBER_INSTANCES/3))+"]";有this指针toString()方法自动被调用并且有值更新的时候toString()里的值也会默认更新。如果写成,return "Animal [i=" + i + ", o=" + o +",kafang=" +(kafang=(NUMBER_INSTANCES/3))+"]";则toString()方法不能被自动调用,要使用System.out.println();才能被调用

public class Animal {
	
	int i=1;
	String o="hello";
	double kafang=0;
	static double NUMBER_INSTANCES=0;
	public void printType() {
		System.out.println("Cat");
		}
	
	@Override
	public String toString() {
		return "Animal [i=" + this.i + ", o=" + this.o +",kafang=" +(this.kafang=(NUMBER_INSTANCES/3))+"]";
	}
	
	public static void main(String[] args) {
		Animal dog=new Animal();
		//通过赋值,会调用toString方法
		dog.i=2;
		System.out.println(dog);
		//更新值,toString方法也会更新
//		dog.NUMBER_INSTANCES=9;
		//通过赋值,会调用toString方法,自动计算了卡方值
		Animal.NUMBER_INSTANCES=9;
//		dog.i=2;
		System.out.println("kafang="+dog.kafang);
		System.out.println(dog);
	}

}

卡方值的计算

AlgoCMAR.java

生成这个类,new ClassifierCMAR(rules, dataset, delta);,利用该类计算卡方值并利用CR-tree剪枝

/**
     * Train a classifier
     * @param dataset a training dataset
     * @return a rule classifier
     * @throws Exception if an error occurs
     */
    @Override
    public ClassifierCMAR train(Dataset dataset){
    	// Apply a modified FPGrowth algorithm to obtain the rules
        FPGrowthForCMAR fpgrowth = new FPGrowthForCMAR(dataset, minSup, minConf);
        List rules = fpgrowth.run();
        
        // Return a classifier that is created using these rules
        return new ClassifierCMAR(rules, dataset, delta);
    }

ClassifierCMAR.java

NUMBER_INSTANCES表示数据的总条数

	/**
     * Constructor
     * 
     * @param rules    forming the current classifier
     * @param training dataset used while training classifier
     * @param delta  delta
     * 
     * @throws Exception
     */
    public ClassifierCMAR(List rules, Dataset training, int delta) {
        super("CMAR");
        //传了一个数进去,就可以计算卡方值
       RuleCMAR.NUMBER_INSTANCES = training.getInstances().size();
 
//        System.out.println(1);
       //一共有多少个属性值
        CRTree.NUMBER_SINGLETONS = training.getDistinctItemsCount();
        CRTree crTree = new CRTree(training, delta);
        for (Rule rule : rules) {
            crTree.insert(rule);
        }
        //它为什么把那些size并且优先级高的都去掉了
        crTree.pruneUsingCover();
        this.rules = crTree.getRules();
//        System.out.println(1);
    }

Rule.java

属性有更新,会自动调用toString()方法

/*
	 * (non-Javadoc)
	 * 
	 * @see java.lang.Object#toString()
	 */
	public String toString() {
//		System.out.println(1);
		return this.antecedent.toString() + " -> " + this.getKlass() + getMeasuresToString();
	}
	
	public abstract String getMeasuresToString();

RuleCMAR.java

	@Override
	public String getMeasuresToString() {
		return " #SUP: " + getSupportRule() + " #CONF: " + getConfidence() + " #CHISQUARE: " + this.getChiSquare();
	}

计算卡方值

假设有这么一条规则,计算它的卡方值

 

  1. 生成实际表格与期望表格

   2.利用公式计算,得到结果

 

调用getChiSquare()函数进行计算

以下面的两条规则为例,解释SupportKlass,SupportAntecedent,SupportRule以及CONF

SupportKlass: 分类为class=12的数量

SupportAntecedent:条件部分的出现次数

SupportRule: 这些条件判断为12的次数

CONF: SupportRule/SupportAntecedent

[5] -> 12 #SupportRule: 1#SupportAntecedent: 1#SupportKlass: 6 #CONF: 1.0

[5, 8] -> 12 #SupportRule: 1#SupportAntecedent: 1#SupportKlass: 6 #CONF: 1.0

/**
	 * Get the chi square of this rule
	 * 
	 * @return chi square of this rule
	 */
	public double getChiSquare() {
		double[] observedValues = new double[4];
		double[] expectedValues = new double[4];
		// Calculate observed and expected values
		observedValues[0] = this.supportRule;
		observedValues[1] = this.supportAntecedent - this.supportRule;
		observedValues[2] = this.supportKlass - this.supportRule;
		observedValues[3] = NUMBER_INSTANCES - this.supportAntecedent - this.supportKlass + this.supportRule;

		// Calculate additional support values
		double supNotAntecedent = NUMBER_INSTANCES - this.supportAntecedent;
		double supNotConsequent = NUMBER_INSTANCES - this.supportKlass;

		// Expected values
		expectedValues[0] = (this.supportKlass * this.supportAntecedent) / NUMBER_INSTANCES;
		expectedValues[1] = (supNotConsequent * this.supportAntecedent) / NUMBER_INSTANCES;
		expectedValues[2] = (this.supportKlass * supNotAntecedent) / NUMBER_INSTANCES;
		expectedValues[3] = (supNotConsequent * supNotAntecedent) / NUMBER_INSTANCES;

		double sumChiSquaredValues = 0.0;

		for (int index = 0; index < observedValues.length; index++) {
			double chiValue = Math.pow((observedValues[index] - expectedValues[index]), 2.0) / expectedValues[index];
			sumChiSquaredValues = sumChiSquaredValues + chiValue;
		}

		return sumChiSquaredValues;
	}

下面展示计算的输出

[5] -> 12 #SupportRule: 1#SupportAntecedent: 1#SupportKlass: 6 #CONF: 1.0
observedValues[0]1.0
observedValues[1]0.0
observedValues[2]5.0
observedValues[3]3.0
supNotAntecedent8.0
supNotConsequent3.0
expectedValues[0]0.6666666666666666
expectedValues[1]0.3333333333333333
expectedValues[2]5.333333333333333
expectedValues[3]2.6666666666666665
chiValue0.1666666666666667
chiValue0.3333333333333333
chiValue0.020833333333333297
chiValue0.041666666666666706
sumChiSquaredValues0.5625
[5, 8] -> 12 #SupportRule: 1#SupportAntecedent: 1#SupportKlass: 6 #CONF: 1.0
observedValues[0]1.0
observedValues[1]0.0
observedValues[2]5.0
observedValues[3]3.0
supNotAntecedent8.0
supNotConsequent3.0
expectedValues[0]0.6666666666666666
expectedValues[1]0.3333333333333333
expectedValues[2]5.333333333333333
expectedValues[3]2.6666666666666665
chiValue0.1666666666666667
chiValue0.3333333333333333
chiValue0.020833333333333297
chiValue0.041666666666666706
sumChiSquaredValues0.5625

Yes表示是5,No表示非

判断为12判断为11total
[5]Yes10=1-01
[5]No5=6-13=9-5-18
total639
判断为12判断为11total
[5, 8]Yes10=1-01
[5, 8]No5=6-13=9-5-18
total639

 下一 步是创建CR-Tree

  1. 为CR-Tree赋值
  2. 调用 crTree.insert( )方法插入规则
  3. 调用crTree.pruneUsingCover( )过滤掉不符合规则的方法
  4. 得到过滤后的规则crTree.getRules( )

minCover:是database coverage的参数

第一步为CR-tree赋值

CRTree(Dataset dataset, int delta) {
		minCover = delta;
		this.dataset = dataset;
	}

第二步调用insert()方法

/**
	 * Insert a rule in the tree
	 * 
	 * @param baseRule a rule to be inserted into the CRTree
	 */
	protected void insert(Rule baseRule) {

		RuleCMAR rule = (RuleCMAR) baseRule;

		// If the rule fails the Chi-Squared test
		if (rule.getChiSquare() <= THRESHOLD_CHI_SQUARE) {
			// We dont add the rule
			return;
		}

		// Otherwise, we create a new node for this rule
		CRNode newNode = new CRNode(rule);

		// If it is the first rule, it will be added as the root of the tree.
		//添加到树的rootnode当中
		if (rootNode == null) {
			rootNode = newNode;
			return;
		}

		// If more general rule with higher ranking exists, current rule will be
		// discarded
		//如果两项都满足就discarded,只要有一项不满足就可以添加
		if (isMoreGeneralNode(newNode)) {
			return;
		}

		// Add current node as the first node
		//和这颗树的首节点比较,如果比它优先级高就添加它到树的下一个节点当中然后返回
		//如果比这颗树的头节点大
		if (newNode.rule.isGreater(rootNode.rule)) {
			newNode.next = rootNode;
			rootNode = newNode;
			return;
		}

		// Search for the position where
		// the rule should be inserted in terms of rank
		//则要找到合适的位置的位置添加
		CRNode currentNode = rootNode;
		CRNode nextNode = rootNode.next;
		while (nextNode != null) {
			if (newNode.rule.isGreater(nextNode.rule)) {
				currentNode.next = newNode;
				newNode.next = nextNode;
				return;
			}
			currentNode = nextNode;
			nextNode = nextNode.next;
		}

		// Add new node at the very end
		//整棵树里都没有比它小的就添加到最后,最小的放到最后
		currentNode.next = newNode;
	}

首先,有一个THRESHOLD_CHI_SQUARE 的筛选,默认阈值1.6424。不满足阈值,则不放进这颗树中

/**
	 * Critical threshold for 25% "significance" level (assuming "degree of freedom"
	 * equivalent to 1).
	 */
	private static final double THRESHOLD_20 = 1.6424;

	/**
	 * Critical threshold value for CHI_SQUARE
	 */
	private static final double THRESHOLD_CHI_SQUARE = THRESHOLD_20; // Default

否则放进这颗树中,这一棵单路径的树,其数据结构如下所示

CRNode.java

/**
 * Class representing a CRTree node, as used by the CMAR algorithm.
 * 
 * @see AlgoCMAR
 */
public class CRNode {
    /**
     * Rule stored in the current node
     */
    RuleCMAR rule = null;

    /**
     * Link to the next node
     */
    CRNode next = null;

    /**
     * Constructor 
     * 
     * @param rule to be stored in the node
     */
    CRNode(RuleCMAR rule) {
        this.rule = rule;
    }
}

接着判断规则是不是general和high confidence的,用generalhigh confidence的去覆盖specific和low confidence的

	/**
	 * Checks whether there are a more general rule, with higher ranking in the
	 * current tree
	 * 
	 * @param ruleNode a node to be inserted
	 * @return true if more general rule exists in the tree
	 */
	private boolean isMoreGeneralNode(CRNode ruleNode) {
		
		CRNode currentNode = rootNode;

		// Search in tree by follwing the "next" links between nodes
		while (currentNode != null) {
			//如果这两个都满足就discard
			//如果size更小,并且优先级更高,就discard,不用放到树当中,因为都满足的不需要修剪
			//只满足一个的才需要修剪
			if (ruleNode.rule.isMoreGeneral(currentNode.rule) && ruleNode.rule.isGreater(currentNode.rule))
				{
//				System.out.println(1);
//				System.out.println(ruleNode.rule);
				return true;
				}
			currentNode = currentNode.next;
		}

		return false;
	}

 如何算是more generalisMoreGeneralNode(newNode),原文中是怎么描述的

 

欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/langs/942366.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-05-18
下一篇 2022-05-18

发表评论

登录后才能评论

评论列表(0条)

保存