association.cpp

关联规则发现vc源代码

// CAssociationRule.cpp: implementation of the CAssociationRule class.
//
//////////////////////////////////////////////////////////////////////
#include "stdafx.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#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);
}