www.pudn.com > apriori的vc源代码.zip > association.cpp

// CAssociationRule.cpp: implementation of the CAssociationRule class. 
// 
////////////////////////////////////////////////////////////////////// 
#include "stdafx.h" 
#include  
#include  
#include  
 
#include "Association.h" 
 
////////////////////////////////////////////////////////////////////// 
// Construction/Destruction 
////////////////////////////////////////////////////////////////////// 
 
CAssociationRule::CAssociationRule() 
{ 
    m_minConfidence = 0.90; 
    m_numRules = 0; 
	 
    m_LargeItemSets = (List *)NULL; 
	 
    m_Rules = (ARRuleSetNode *)NULL; 
}; 
 
CAssociationRule::~CAssociationRule() 
{ 
    ARRuleSetNode *rn, *temp; 
 
    rn = m_Rules; 
    while(rn != (ARRuleSetNode *)NULL) 
    { 
        temp = rn->next; 
        if(rn->m_premise != NULL) 
            delete rn->m_premise; 
 
        if(rn->m_consequence != NULL) 
            delete rn->m_consequence; 
 
        delete rn; 
        rn = temp; 
    } 
 
}; 
 
 
 
void CAssociationRule::genrules() 
{ 
    itemSet *current; 
     
    for(int i = 0; i < m_LargeItemSets->size(); i++) 
    { 
        current = (itemSet *)m_LargeItemSets->get(i); 
        if(current->size() > 1) 
            ruler(current, current); 
 
//        delete current; 
    } 
     
    return; 
} 
 
void CAssociationRule::ruler(itemSet *Lk, itemSet *Am) 
{ 
    itemSet *current; 
    itemSet *Aminusone; 
    int pos; 
    double conf; 
    long necConfidence; 
 
 
    for(int i = 0; i < Am->size(); i++) 
    { 
        current = (itemSet *)Am->clone(); 
        current->remove(i); 
 
        pos = m_LargeItemSets->indexOf(current); 
        if(pos >= 0) 
        { 
            Aminusone = (itemSet *)m_LargeItemSets->get(pos); 
 
            conf = ((double)(Lk->support()))/(double)(Aminusone->support()); 
            necConfidence = (long)(m_minConfidence*(double)(Aminusone->support()) + 0.5); 
 
            if(necConfidence <= Lk->support()) 
            { 
                add(Lk, Aminusone, conf); 
 
                if(Aminusone->size() > 1) 
                    ruler(Lk, Aminusone); 
            } 
 
//            delete Aminusone; 
        } 
 
        delete current; 
    } 
 
    return; 
} 
 
 
void CAssociationRule::add(itemSet *Lk, itemSet *Aminusone, double confidence) 
{ 
    itemSet *rightitems; 
    ARRuleSetNode *newRule; 
    ARRuleSetNode *browser; 
 
    rightitems = Lk->substract(Aminusone); 
 
    browser = m_Rules; 
    while(browser != (ARRuleSetNode *)NULL) 
    { 
        if((browser->m_premise->compare(Aminusone) == TOTALEQUAL) && (browser->m_consequence->compare(rightitems) == TOTALEQUAL)) 
        { 
            delete rightitems; 
            return; 
        } 
 
        browser = browser->next; 
    } 
 
    newRule = (ARRuleSetNode *) new ARRuleSetNode(); 
 
    newRule->m_premise = (itemSet *)Aminusone->clone(); 
    newRule->m_consequence = (itemSet *)rightitems->clone(); 
 
    newRule->m_confidence = confidence; 
    newRule->m_support = Lk->support(); 
 
    newRule->next = m_Rules; 
    m_Rules = newRule; 
 
    m_numRules++; 
 
    return; 
} 
 
 
void CAssociationRule::save(const char *filename) 
{ 
    ARRuleSetNode *currentRule; 
    FILE *fp; 
	int i; 
	itemSet *pitem; 
 
    fp = fopen(filename,"wt"); 
 
    /* 
	fprintf(fp, "Large Item Sets ...\n\n\n"); 
	for(i = 0; i < m_LargeItemSets->size(); i++) 
	{ 
		pitem = (itemSet *)m_LargeItemSets->get(i); 
		for(int j = 0; j < pitem->size(); j++) 
			fprintf(fp, "%d ", pitem->get(j)); 
		fprintf(fp, "\n"); 
	} 
	fprintf(fp, "\n\n\n"); 
    */ 
 
    currentRule = m_Rules; 
    while(currentRule != (ARRuleSetNode *)NULL) 
    { 
        /* 
        fprintf(fp, "%f %f\n", currentRule->m_confidence, currentRule->m_support); 
		fprintf(fp, "%d", currentRule->m_premise->size()); 
        */ 
                 
        for(i = 0; i < currentRule->m_premise->size(); i++) 
            fprintf(fp, " %d", currentRule->m_premise->get(i)); 
        fprintf(fp, "  ---> "); 
 
        /* 
		fprintf(fp, "%d", currentRule->m_consequence->size()); 
        */ 
                 
        for(i = 0; i < currentRule->m_consequence->size(); i++) 
            fprintf(fp, " %d", currentRule->m_consequence->get(i)); 
        fprintf(fp, "\n"); 
		 
        currentRule = currentRule->next; 
    } 
 
	fflush(fp); 
	fclose(fp); 
 
    return; 
} 
 
 
void CAssociationRule::load(const char *filename) 
{ 
    ARRuleSetNode *currentRule; 
	double support, confidence; 
	int count, pageno; 
    FILE *fp; 
	int i; 
 
	printf("Loading Association Rules from %s ... ", filename); 
	fflush(stdout); 
	 
    fp = fopen(filename,"rt"); 
	while( !feof(fp) ) 
	{ 
	    currentRule = (ARRuleSetNode *)new ARRuleSetNode(); 
		 
        fscanf(fp, "%f %f\n", &confidence, &support); 
		 
        currentRule->m_confidence = confidence; 
        currentRule->m_support = support; 
		 
		fscanf(fp, "%d", &count); 
		currentRule->m_premise = (itemSet *)new itemSet(); 
        for(i = 0; i < count; i++) 
		{ 
            fscanf(fp, " %d", &pageno); 
			currentRule->m_premise->add(pageno); 
		} 
        fscanf(fp, "\n"); 
 
 
		fscanf(fp, "%d", &count); 
		currentRule->m_consequence = (itemSet *)new itemSet(); 
        for(i = 0; i < count; i++) 
		{ 
            fscanf(fp, " %d", &pageno); 
			currentRule->m_consequence->add(pageno); 
		} 
        fscanf(fp, "\n"); 
		 
		currentRule->next = m_Rules; 
		m_Rules = currentRule; 
    } 
 
	printf(" Finish!"); 
	fflush(stdout); 
	 
    return; 
} 
 
// Generate recommendations based on observed session 
itemSet * CAssociationRule::genRecommendations(itemSet *observed_session, int NumberofTopPages) 
{ 
    ARRuleSetNode *browser; 
    TopRule *topRules; 
    int i, j, pos, pagenum; 
	double pweight; 
    itemSet *result; 
 
	pagenum = NumberofTopPages; 
	 
    topRules = (TopRule *)new TopRule[pagenum]; 
    for(i = 0; i < pagenum; i++) 
    { 
        topRules[i].prule = NULL; 
        topRules[i].m_similarity = 0.0; 
    } 
 
    browser = m_Rules; 
    while(browser != (ARRuleSetNode *)NULL) 
    { 
		pweight = calSimilarity(browser->m_premise, observed_session); 
		 
		for(pos = 0; pos < pagenum; pos++) 
		{ 
			if(pweight > topRules[pos].m_similarity) 
				break; 
		} 
		if(pos < pagenum) 
		{ 
			for(j = pagenum-2; j >= pos; j--) 
			{ 
				topRules[j+1].prule = topRules[j].prule; 
				topRules[j+1].m_similarity = topRules[j].m_similarity; 
			} 
			topRules[pos].prule = browser; 
			topRules[pos].m_similarity = pweight; 
		} 
		 
        browser = browser->next; 
    } 
 
	result = (itemSet *)new itemSet(); 
	result->keeporder(false); 
    for(i = 0; i < pagenum; i++) 
    { 
		if(topRules[i].prule != NULL) 
			for(j = 0; j < topRules[i].prule->m_consequence->size(); j++) 
				result->add(topRules[i].prule->m_consequence->get(j)); 
    } 
 
	delete topRules; 
	if(result->size() == 0) 
	{ 
		delete result; 
		result = (itemSet *)NULL; 
	} 
	 
	return result;	 
} 
 
 
// Calculate the contribution of trace to observed_session 
double CAssociationRule::calSimilarity(itemSet *trace, itemSet *observed_session) 
{ 
    int i, observed_page, numIntersection; 
	itemSet *itrace, *isession, *iunion; 
	double score; 
	 
	itrace = (itemSet *)new itemSet(); 
	itrace->keeporder(false); 
	for(i = 0; i < trace->size(); i++) 
		itrace->add(trace->get(i)); 
	 
	isession = (itemSet *)new itemSet(); 
	isession->keeporder(false); 
	for(i = 0; i < observed_session->size(); i++) 
		isession->add(observed_session->get(i)); 
	 
	iunion = (itemSet *)new itemSet(); 
	iunion->keeporder(false); 
	for(i = 0; i < trace->size(); i++) 
		iunion->add(trace->get(i)); 
	for(i = 0; i < observed_session->size(); i++) 
		iunion->add(observed_session->get(i)); 
	 
    numIntersection = 0; 
	for(i = 0; i < isession->size(); i++) 
	{ 
		observed_page = observed_session->get(i); 
		if(itrace->indexOf(observed_page) != -1) 
			numIntersection++; 
	} 
 
	if(numIntersection == trace->size()) 
		score = 1.0; 
	else 
		score = (double)numIntersection / (double)iunion->size(); 
	 
	delete itrace; 
	delete isession; 
	delete iunion; 
	 
	return(score); 
}