assoc_sparse.cpp

orange源码 数据挖掘技术

/*
    This file is part of Orange.

    Orange is free software; you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
    the Free Software Foundation; either version 2 of the License, or
    (at your option) any later version.

    Orange is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU General Public License for more details.

    You should have received a copy of the GNU General Public License
    along with Orange; if not, write to the Free Software
    Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA

    Authors: Matjaz Jursic, Janez Demsar, Blaz Zupan, 1996--2002
    Contact: [e-mail]
*/


#include "assoc.hpp"
#include "examplegen.hpp"

/****************************************************************************************
TSparseExample
*****************************************************************************************/

class TSparseExample{
public:
	float weight;			// weight of thi example
	long *itemset;		// vector storing just items that have some value in original example
	int	length;

	TSparseExample(TExample *example, int weightID);
};

/****************************************************************************************
TSparseExamples
*****************************************************************************************/

class TSparseExamples{
public:
	float fullWeight;					// weight of all examples
	vector<TSparseExample*> transaction;	// vector storing all sparse examples
	PDomain domain;						// domain of original example or exampleGenerator
	vector<long> intDomain;				// domain mapped longint values

	TSparseExamples(PExampleGenerator examples, int weightID);
};

/****************************************************************************************
TSparseINode
*****************************************************************************************/

class TSparseINode;
typedef map<long, TSparseINode *> TSparseISubNodes;

class TSparseINode{							//item node used in TSparseITree
public:
	float weiSupp;							//support of itemset consisting node and all of its parents
	long value;								//value of this node
	TSparseINode *parent;					//pointer to parent node
	TSparseISubNodes subNode;				//children items
	
	TSparseINode(long avalue = -1);			//constructor

    TSparseINode *operator[] (long avalue);	//directly gets subnode

	TSparseINode* addNode(long avalue);		//adds new subnode
	bool hasNode(long avalue);				//returns true if has subnode with given value
};

/****************************************************************************************
TSparseITree
*****************************************************************************************/

class TSparseITree{							//item node used in TSparseITree
public:
	TSparseITree(TSparseExamples examples);			//constructor

	int buildLevelOne(vector<long> intDomain);
	long extendNextLevel(int maxDepth, long maxCount);
	bool allowExtend(long itemset[], int iLength);
	long countLeafNodes();
	void considerItemset(long itemset[], int iLength, float weight, int aimLength);
	void considerExamples(TSparseExamples *examples, int aimLength);
	void delLeafSmall(float minSupport);
	PAssociationRules genRules(int maxDepth, float minConf, float nOfExamples);
	long getItemsetRules(long itemset[], int iLength, float minConf, 
						 float nAppliesBoth, float nOfExamples, PAssociationRules rules);
	PDomain domain;

private:
	TSparseINode *root;
};



/****************************************************************************************
TSparseExample
*****************************************************************************************/

TSparseExample::TSparseExample(TExample *example, int weightID){
	weight = WEIGHT(*example);
	length = 0;

  if (example->domain->variables->size()) {
	  // walk through all attributes in example and adding to sparseExample only those having some value
	  PITERATE(TVarList, vi, example->domain->variables)
		  if (!(*example)[(*vi)].isSpecial()) 
			  length++;
		  
	  itemset = new long[length];
	  length = 0;

	  PITERATE(TVarList, vi2, example->domain->variables) 
		  if (!(*example)[(*vi2)].isSpecial()) 
			  itemset[length++] = example->domain->getVarNum(*vi2);
  }
  else {
    length = 0;
    itemset = new long[example->meta.size() - (weightID ? 1 : 0)];
    ITERATE(TMetaValues, mi, example->meta)
      if ((*mi).first != weightID)
        itemset[length++] = (*mi).first;
    sort(itemset, itemset+length);
  }
}

/****************************************************************************************
TSparseExamples
*****************************************************************************************/

TSparseExamples::TSparseExamples(PExampleGenerator examples, int weightID){
	fullWeight = 0.0;				
	TSparseExample *sparseExm;
	domain = examples->domain;

  const bool sparseExamples = examples->domain->variables->empty();
  set<long> ids;

	// walk through all examples converting them to sparseExample and add them to transaction
	PEITERATE(example, examples) {
			sparseExm = new TSparseExample(&*example, weightID);
      if (sparseExamples) {
        for(long *vi = sparseExm->itemset, le = sparseExm->length; le--; vi++)
          ids.insert(*vi);
      }
			transaction.push_back(sparseExm);
			fullWeight += sparseExm->weight;
  }

	// walk through all existing attributes in example and add them to intDomain
  if (sparseExamples) {
    intDomain.reserve(ids.size());
    ITERATE(set<long>, si, ids)
      intDomain.push_back(*si);
  }
  else {
    for(int i = 0, e = examples->domain->variables; i!=e; i++)
      intDomain.push_back(i);
	}
}

/****************************************************************************************
TSparseINode
*****************************************************************************************/

TSparseINode::TSparseINode(long avalue) {
	weiSupp = 0.0;
	value = avalue;
};

TSparseINode *TSparseINode::operator[] (long avalue) {
	return subNode[avalue];
};

//if no subNode with that key exists add new
TSparseINode* TSparseINode::addNode(long avalue) {
	if (subNode.find(avalue)==subNode.end()) {
		subNode[avalue] = new TSparseINode(avalue);
		subNode[avalue]->parent = this;
	} 
	//returns new node
	return subNode[avalue];
};

bool TSparseINode::hasNode(long avalue) {
	return (subNode.find(avalue)!=subNode.end());
};

/****************************************************************************************
TSparseITree
*****************************************************************************************/

// constructor
TSparseITree::TSparseITree(TSparseExamples examples){
	root = new TSparseINode();
	domain = examples.domain;
};

// generates all itemsets with one element
int TSparseITree::buildLevelOne(vector<long> intDomain) {
	int count = 0;
	
	ITERATE(vector<long>,idi,intDomain) {
		root->addNode(*idi);
		count++;
	}

	return count;
};

// generates candiate itemsets of size k from large itemsets of size k-1
long TSparseITree::extendNextLevel(int maxDepth, long maxCount) {
	typedef pair<TSparseINode *,int> NodeDepth; //<node,depth>

	long count = 0;
	vector<NodeDepth> nodeQue;
	
	long *cItemset = new long[maxDepth +1];
	int currDepth;
	TSparseINode *currNode; 

	nodeQue.push_back(NodeDepth(root,0)); // put root in que

	while (!nodeQue.empty()) {			//repeats until que is empty
		currNode = nodeQue.back().first;			// node
		currDepth = nodeQue.back().second;			// depth

		nodeQue.pop_back();

		if (currDepth) cItemset[currDepth - 1] = currNode->value;		// generates candidate itemset
		
		if (currDepth == maxDepth) 										// we found an instance that can be extended
			for(TSparseISubNodes::iterator iter(++(root->subNode.find(currNode->value))), \
											   iter_end(root->subNode.end()); \
				iter!=iter_end; \
				iter++) {
					cItemset[currDepth] = iter->second->value;

					if (allowExtend(cItemset, currDepth + 1)) {
						currNode->addNode(cItemset[currDepth]);
						count++;
						if (count>maxCount) return count;
					}
					
				}	
		else RITERATE(TSparseISubNodes,sni,currNode->subNode)		//adds subnodes to list
			nodeQue.push_back(NodeDepth(sni->second, currDepth + 1));
	}
	return count;
};


// tests if some candidate itemset can be extended to large itemset 
bool TSparseITree::allowExtend(long itemset[], int iLength) {	
	typedef pair<int,int> IntPair; // <parent node index, depth>
	typedef pair<TSparseINode *,IntPair> NodeDepth;

	vector<NodeDepth> nodeQue;
	
	int currDepth;
	int currPrIndex;								//parent index
	TSparseINode *currNode; 
	int i;
	
	nodeQue.push_back(NodeDepth(root,IntPair(-1,1))); // put root in que

	while (!nodeQue.empty()) {						//repeats until que is empty
		currNode = nodeQue.back().first;			// node
		currPrIndex = nodeQue.back().second.first;	// parentIndex
		currDepth = nodeQue.back().second.second;	// depth
		
		nodeQue.pop_back();

		if (currDepth == iLength) continue;			// we found an instance
		
		for (i = currDepth; i!=currPrIndex; i--)		//go through all posible successors of this node
			if (currNode->hasNode(itemset[i]))
				nodeQue.push_back(NodeDepth((*currNode)[itemset[i]],IntPair(i,currDepth + 1)));
			else return 0;
	}
	return 1;
}