HotSpot关联规则算法（1）-- 挖掘离散型数据

? ? ? 提到关联规则算法，一般会想到Apriori或者FP，一般很少有想到HotSpot的，这个算法不知道是应用少还是我查资料的手段太low了，在网上只找到很少的内容，这篇http://wiki.pentaho.com/display/DATAMINING/HotSpot+Segmentation-Profiling ，大概分析了一点，其他好像就没怎么看到了。比较好用的算法类软件，如weka，其里面已经包含了这个算法，在Associate--> HotSpot里面即可看到，运行算法界面一般如下：

其中，红色方框里面为设置的参数，如下：

-c last ，表示目标所在的目标所在的列，last表示最后一列，也是是数值，表示第几列；

-V first， 表示目标列的某个状态值下标值（这里可以看出目标列应该是离散型），first表示第0个，可以是数值型；

-S 0.13，最小支持度，里面会乘以样本总数得到一个数值型的支持度；

-M 2 ， 最大分指数；

-I 0.01 ， 在weka里面解释为Minimum improvement in target value，不知道是否传统的置信度一样；

相关说明：本篇相关代码参考weka里面的HotSpot算法的具体实现，本篇只分析离散型数据，代码可以在（http://download.csdn.net/detail/fansy1990/8488971）下载。

1.?数据：

@attribute age 			{young,pre-presbyopic,presbyopic}
@attribute spectacle-prescrip	{myope,hypermetrope}
@attribute astigmatism		{no,yes}
@attribute tear-prod-rate	{reduced,normal}
@attribute contact-lenses	{soft,hard,none}
young,myope,no,reduced,none
young,normal,soft
young,yes,none
。。。
presbyopic,hypermetrope,none

这个数据格式是参考weka里面的，加入最前面的5行是因为需要把各个属性进行编码，所以提前拿到属性的各个状态，方便后续操作；
2. 单个节点定义：

public class HSNode {
	private int splitAttrIndex; // 属性的下标
	private int attrStateIndex; // 属性state的下标
	private int allCount ; // 当前数据集的个数
	private int stateCount ; // 属性的state的个数
	private double support; // 属性的支持度
	private List<HSNode> chidren;
	
	public HSNode(){}}
	

splitAttrIndex 即对应属性astigmatism的下标（应该是第2个，从0开始）；attrStateIndex 则对应这个属性的下标，即no的下标（这里应该是0）；allCount即12，stateCount即5，support 对应41.57%（即5/12的值）；children即其孩子节点；（这里的下标即是从文件的前面几行编码得到的，比如属性age为第一个属性，编码为0，young为其第一个状态，编码为0）；

3. 算法伪代码，（文字描述，太不专业了，如果要看，就将就看？）

1. 创建根节点；
2. 创建孩子节点；
    
   2.1 针对所有数据，计算每列的每个属性的’支持度‘support，
       if support>= MINSUPPORT
          把该列的当前属性加入潜在的孩子节点列表；
	end
   2.2 针对潜在孩子节点列表遍历
       if (!当前节点产生的规则序in全局规则序列）
	  把当前节点加入孩子节点列表；
	  把当前节点产生的规则加入全局规则中；
       end

   2.3 遍历孩子节点列表
        针对当前节点，返回到2，进行递归；
   

4. 代码关键步骤具体实现：

4.1 数据读取及初始化：

1） 读取文件的前面几行，初始化两个变量，attributes和attributeStates,分别对应所有的属性和属性的各个状态；

 while ((tempString = reader.readLine()) != null) {
            	// 第一行数据是标题
            	if(tempString.indexOf(HSUtils.FILEFORMAT)==0){
            		String attr = tempString.substring(HSUtils.FILEFORMAT.length(),tempString.indexOf("{")).trim();
            		String[] attrStates =tempString.substring(tempString.indexOf("{")+1,tempString.indexOf("}")).split(",");
            		for(int i=0;i<attrStates.length;i++){
            			attrStates[i]=attrStates[i].trim();
            		}
            		attrList.add( attr);
            		line++;
            		this.attributeStates.put(attr,attrStates);
            		continue;
            	}
            	if(flag){
            		this.attributes= new String[line];
            		attrList.toArray(this.attributes);// 复制值到数组中		
            		flag=false;
            	}
            	String[] tempStrings = tempString.split(splitter);
            	lists.add(strArr2IntArr(tempStrings));
            }

2） 后面就是把下面的数据转为数值型数组了，strArr2IntArr 函数如下：

	/**
	 * String 数组转为int数组
	 * @param sArr
	 * @return
	 * @throws Exception 
	 */
	private int[] strArr2IntArr(String[] sArr) throws Exception{
		int[] iArr = new int[sArr.length];
		for(int i=0;i<sArr.length;i++){
			iArr[i]= getAttrCode(sArr[i],i);
		}
		return iArr;
	}
	/**
	 * 获得第attrIndex属性的attrState的编码
	 * @param attrState
	 * @param attrIndex
	 * @return
	 * @throws Exception 
	 */
	private int getAttrCode(String attrState,int attrIndex) throws Exception{
		String[] attrStates = attributeStates.get(attributes[attrIndex]);
		for(int i=0;i<attrStates.length;i++){
			if(attrState.equals(attrStates[i])){
				return i;
			}
		}
		throw new Exception("编码错误！");
//		return -1; // 如果运行到这里应该会报错
	}

这里数据读取主要是把离散型的字符串类型数据转换为数值型数据，编码规则如下：

属性age的状态：	[young-->0,pre-presbyopic-->1,presbyopic-->2,]
属性spectacle-prescrip的状态：	[myope-->0,hypermetrope-->1,]
属性astigmatism的状态：	[no-->0,yes-->1,]
属性tear-prod-rate的状态：	[reduced-->0,normal-->1,]
属性contact-lenses的状态：	[soft-->0,hard-->1,none-->2,]

4.2 初始化根节点

// 读取文件并赋值
		List<int[]> intData = readFileAndInitial(HSUtils.FILEPATH,HSUtils.SPLITTER);;
		
		int splitAttributeIndex = attributes.length-1;// 下标需减1
		int stateIndex = HSUtils.LABELSTATE;
		
		int numInstances = intData.size();// 数据总个数
		int[] labelStateCount = attrStateCount(intData,attributes.length-1);
		
		HSUtils.setMinSupportCount(numInstances);
		double targetValue=1.0*labelStateCount[HSUtils.LABELSTATE]/numInstances;
		// 创建根节点
		HSNode root = new HSNode(splitAttributeIndex,stateIndex,labelStateCount[stateIndex],numInstances);
		double[] splitVals=new double[attributes.length];
        byte[] tests = new byte[attributes.length];
		root.setChidren(constructChildrenNodes(intData,targetValue,splitVals,tests));

labelStateCount即目标属性的各个状态的个数，比如这里目标状态为soft，一共有5个值，一共有24个样本，所以其支持度为5/25=20.82%;

constructChildrenNodes函数为创建所有子节点，接收的参数有：intData：所有的数据（经过编码的）；targetValue：当前节点支持度；splitVals和tests数组主要用于针对节点产生规则；

4.3 创建孩子节点：

1） 计算潜在孩子节点：

private List<HSNode> constructChildrenNodes(List<int[]> intData,double targetValue,double[] splitVals,byte[] tests) {
		
		// 设置孩子节点
//		// 获取子数据集
//		
		// 针对每个属性的每个state值计算其支持度（需要符合置信度）
		PriorityQueue<AttrStateSup> pq = new PriorityQueue<AttrStateSup>();
		for(int i=0;i<attributes.length-1;i++){// 最后一个属性不用计算（为Label）
			evaluateAttr(pq,intData,i,targetValue);
		}

这里的evaluateAttr主要是判断每个属性的各个状态是否符合要求，是则加入pq

/**
	 * 是否把第attrIndex属性的state作为备选节点加入pq
	 * @param pq
	 * @param intData 
	 * @param attrIndex
	 * @param targetValue 
	 * @param stateIndex 
	 * @param labelStateCount 
	 */
	private void evaluateAttr(PriorityQueue<AttrStateSup> pq,List<int[]> intData,int attrIndex,double targetValue) {
		int[] counts = attrStateCount(intData,attrIndex);
		
		 boolean ok = false;
	      // only consider attribute values that result in subsets that meet/exceed min support
	      for (int i = 0; i < counts.length; i++) {
	        if (counts[i] >= HSUtils.getMinSupportCount()) {
	          ok = true;
	          break;
	        }
	      }
	    if(ok){
	    	double subsetMatrix =0.0;
			for(int stateIndex=0;stateIndex<counts.length;
					stateIndex++){
				subsetMatrix =attrStateCount(intData,attrIndex,attributes.length-1,HSUtils.LABELSTATE);
				if(counts[stateIndex]>=HSUtils.getMinSupportCount()&&subsetMatrix>=HSUtils.getMinSupportCount()){
					
					 double merit = 1.0*subsetMatrix / counts[stateIndex]; //
			         double delta = merit - targetValue;
			         if(delta/targetValue>=HSUtils.MINCONFIDENCE){
			        	 pq.add(new AttrStateSup(attrIndex,counts[stateIndex],(int)subsetMatrix));
			         }
					
				}
			}
	    }// ok
	}

这里首先针对当前数据集计算属性下标为attrIndex的各个状态的计数到counts[]数组中；如果各个状态的所有计数都小于最小支持度，则该属性都不作为备选加入pq中；否则继续判断：计算目标属性的设定状态（比如soft）和当前属性的状态（young）共同出现的次数（第一次应该是2），赋值给subsetMatrix（那么该值就是2）；判断subsetMatrix是否>=最小支持度，如果是在按照上面的代码进行计算，最后还有个判断是用到置信度的（暂译为置信度），如果满足则把其加入到pq中，即备选子节点列表；

2）生成全局规则，并添加孩子节点

List<HSNode> children = new ArrayList<HSNode>();
		List<HotSpotHashKey> keyList = new ArrayList<HotSpotHashKey>();
			while(pq.size()>0&&children.size()<HSUtils.MAXBRANCH){
				AttrStateSup attrStateSup = pq.poll();
				
				// 再次进行过滤
				double[] newSplitVals = splitVals.clone();
	            byte[] newTests = tests.clone();
	            newSplitVals[attrStateSup.getAttrIndex()]=attrStateSup.getStateIndex()+1;
	            newTests[attrStateSup.getAttrIndex()] =(byte)2; 
	      
	            HotSpotHashKey key = new HotSpotHashKey(newSplitVals,newTests);
	            if (!HSUtils.m_ruleLookup.containsKey(key)) {
	            	// insert it into the hash table
	            	HSUtils.m_ruleLookup.put(key,"");       // 需要先增加规则，然后才处理子节点     
	            	HSNode child_i= new HSNode(attrStateSup.getAttrIndex(),attrStateSup.getStateIndex(),attrStateSup.getStateCount(),attrStateSup.getAllCount());
					keyList.add(key);
					children.add(child_i);
	            } else {
	              System.out.println("The potential,but not included :"+attrStateSup);
	            }
		}

这里的全局规则使用HotSpotHashKey生成，具体规则的含义没有理解（可能和算法原理有关，都找不到一篇相关的paper！）

添加一个节点后，就会添加相应的规则，这样可以避免孩子节点的孩子有相同的规则被重复添加；

3） 针对每个孩子节点，处理其节点的孩子

// 处理子节点
		for(int i=0;i<children.size();i++){
			HSNode child = children.get(i);
			child.setChidren(constructChildrenNodes(getSubData(intData,child.getSplitAttrIndex(),child.getAttrStateIndex()),child.getSupport(),keyList.get(i).getM_splitValues(),keyList.get(i).getM_testTypes()));
			
		}

这里使用递归进行调用，方便处理。需注意节点规则的生成使用的两个数组newSplitValues 和newTests需要往下传递，所以在每个孩子节点生成规则的时候把其加入到一个keyList，这样在遍历孩子节点，处理其节点的孩子时，可以找到对应的规则传递数组；

这里的getSubData即是找到当前数据集中和给定的属性下标即属性状态一样的数据返回，如下：

/**
	 * 获取和splitAttributeIndex相同下标的属性以及stateIndex的所有数据
	 * @param intData
	 * @param splitAttributeIndex
	 * @param stateIndex
	 * @return
	 */
	private List<int[]> getSubData(List<int[]> intData,int splitAttributeIndex,int stateIndex) {
		List<int[]> subData = new ArrayList<int[]>();
		for(int[] d:intData){
			if(d[splitAttributeIndex]==stateIndex){
				subData.add(d);
			}
		}
		return subData;
	}

4.4 打印规则树

/**
	 * 打印规则树
	 * @param node
	 * @param level
	 */
	public void printHSNode(HSNode node,int level){
		printLevelTab(level);
		System.out.print(node+"n");
		
		List<HSNode> children= node.getChidren();
		for(HSNode child:children){
			printHSNode(child,level+1);
		}
	}
	private void printLevelTab(int level) {
		for(int i=0;i<level;i++){
			System.out.print("|t");
		}
	}

这里可以看到针对当前节点，使用直接打印的方式，因为这里覆写了toString方法，所以可以这样，其toString 方法如下：

/**
	 * 格式化输出
	 */
	public String toString(){
		return HSUtils.getAttr(this.splitAttrIndex)+"="+HSUtils.getAttrState(splitAttrIndex,attrStateIndex)
				+"  ("+HSUtils.formatPercent(this.support)+" ["+this.stateCount+"/"+this.allCount+"])";
	}

4.5 算法调用：

package fz.hotspot;

import fz.hotspot.dataobject.HSNode;

public class HotSpotTest {

	/**
	 * @param args
	 * @throws Exception 
	 */
	public static void main(String[] args) throws Exception {
		String file = "D:/jars/weka-src/data/contact-lenses.txt";
		int labelStateIndex = 0; // 目标属性所在下标 
		int maxBranches=2; // 最大分支数目
		double minSupport =0.13; // 最小支持度
		double minConfidence=0.01;// 最小置信度（在weka中使用的是minImprovement）
		HotSpot hs = new HotSpot();
		HSNode root = hs.run(file,labelStateIndex,maxBranches,minSupport,minConfidence);
		System.out.println("n规则树如下：n");
		hs.printHSNode(root,0);
	}

}

打印的规则树如下：

contact-lenses=soft  (20.83% [5/24])
|	astigmatism=no  (41.67% [5/12])
|	|	tear-prod-rate=normal  (83.33% [5/6])
|	|	|	spectacle-prescrip=hypermetrope  (100.00% [3/3])
|	|	spectacle-prescrip=hypermetrope  (50.00% [3/6])
|	tear-prod-rate=normal  (41.67% [5/12])
|	|	spectacle-prescrip=hypermetrope  (50.00% [3/6])

可以看到和weka给出的是一致的。


最近在看《暗时间》，上面提到说有想法最好写下来，这样不仅可以加深自己的理解，同时在写的过程中，比如一些表达之类的 也可以加强（身为程序员，这方面的能力确实欠缺），同时也可以让别人检验到自己的思维盲点。

文中相关算法理解，仅代表自己观点。

分享，成长，快乐

脚踏实地，专注

转载请注明blog地址：http://blog.csdn.net/fansy1990