dmdlg.cpp

数据挖掘的算法实现

// DMDlg.cpp : implementation file
//

#include "stdafx.h"
#include "DM.h"
#include "DMDlg.h"
#include <stdlib.h>
#include <stdio.h>
#include <iostream.h>
#include <time.h>
#include <windows.h>

#ifdef _DEBUG
#define new DEBUG_NEW
#undef THIS_FILE
static char THIS_FILE[] = __FILE__;
#endif

#define MAX_PARTITION_NUMBER 100
#define MAX_ATTR_NUM 100

/////////////////////////////////////////////////////////////////////////////
// CDMDlg dialog

CDMDlg::CDMDlg(CWnd* pParent /*=NULL*/)
	: CDialog(CDMDlg::IDD, pParent)
{
	//{{AFX_DATA_INIT(CDMDlg)
		// NOTE: the ClassWizard will add member initialization here
	//}}AFX_DATA_INIT
	// Note that LoadIcon does not require a subsequent DestroyIcon in Win32
	m_hIcon = AfxGetApp()->LoadIcon(IDR_MAINFRAME);
}




struct tidlist_node
{
	int tid;
	struct tidlist_node *next;
};


struct partition_node
{
	int sup_count;
	struct partition_node *next;
	struct attribute *attr_name;
};

struct item
{
	struct attribute *name;
	struct item *next;
	int list_num;
	struct tidlist_node *tidlist;
	struct tidlist_node *listtail;
};

struct attribute
{
	int attr_no;
	struct attribute *next;
};

char A[MAX_ATTR_NUM][50];

void free_item(struct item *p)
{
	struct attribute *del_attr;
	struct attribute *del_attr_temp;
	struct tidlist_node *del_tidlist;
	struct tidlist_node *del_tidlist_temp;
	del_attr=p->name;
	del_tidlist=p->tidlist;
	while(del_attr!=NULL)
	{
		del_attr_temp=del_attr->next;
		free(del_attr);
		del_attr=del_attr_temp;
	}
	while(del_tidlist!=NULL)
	{
		del_tidlist_temp=del_tidlist->next;
		free(del_tidlist);
		del_tidlist=del_tidlist_temp;
	}
	free(p);
}

struct partition_node **gen_large_itemsets(FILE *fp,int tuple_number,float min_sup,int attr_number,int &total_number)
{
	char ch;
	int TID;
	int i=1;
	struct item *item_head;
	struct item *item_head_last;
	struct item *item_head_last1;
	struct item *item_head_last2;
	struct item *p1;
	struct item *p2;
	struct item *item_cp;
	struct item *item_cp1;
	struct partition_node *save_p1;
	struct partition_node *save_p2;
	struct attribute *attr_p1;
	struct attribute *attr_p2;
	struct attribute *attr_p3;
	struct attribute *attr_p4;
	struct attribute *attr_p5;
	struct attribute *candidate;
	struct tidlist_node *list_p1;
	struct tidlist_node *list_p2;
	struct tidlist_node *list_p;
	struct tidlist_node *list_temp;
	struct partition_node **index=new struct partition_node *[20];
	for(int j=0;j<20;j++)
		index[j]=NULL;
	item_head=NULL;
	while(i<=attr_number)
	{
		item_cp=(struct item*)malloc(sizeof(struct item));
		item_cp->list_num=0;
		item_cp->listtail=NULL;
		item_cp->next=NULL;
		item_cp->tidlist=NULL;
		item_cp->name=(struct attribute*)malloc(sizeof(struct attribute));
		item_cp->name->attr_no=i;
		item_cp->name->next=NULL;
		if(item_head==NULL)
			item_head=item_cp;
		else
			item_cp1->next=item_cp;
		item_cp1=item_cp;
		i++;
	}
	i=1;
	while(!feof(fp)&&(i<=tuple_number))
	{
		fscanf(fp,"%d\t",&TID);
		item_cp=item_head;
		while(item_cp!=NULL)
		{
			ch=fgetc(fp);
			if(ch=='1')
			{
				if(item_cp->tidlist!=NULL)
				{
					item_cp->listtail->next=(struct tidlist_node*)malloc(sizeof(struct tidlist_node));
					item_cp->listtail=item_cp->listtail->next;
					item_cp->listtail->tid=TID;
					item_cp->listtail->next=NULL;
				}
				else
				{
					item_cp->tidlist=(struct tidlist_node*)malloc(sizeof(struct tidlist_node));
					item_cp->tidlist->tid=TID;
					item_cp->tidlist->next=NULL;
					item_cp->listtail=item_cp->tidlist;
				}
				item_cp->list_num+=1;
			}
			ch=fgetc(fp);
			item_cp=item_cp->next;
		}
		i++;
	}
	int min_sup_count=(int)(min_sup*(i-1))+1;
	item_cp=item_head;
	while(item_cp!=NULL)
	{
		if(item_cp->list_num<min_sup_count)
		{
			if(item_cp==item_head)
			{
				item_head=item_cp->next;
				free_item(item_cp);
				item_cp=item_head;
			}
			else
			{
				item_cp1->next=item_cp->next;
				free_item(item_cp);
				item_cp=item_cp1->next;
			}
		}
		else
		{
			item_cp1=item_cp;
			item_cp=item_cp->next;
		}
	}
	int k=1;
	int flag;
	int tid1;
	int tid2;
	item_cp1=NULL;
	while(item_head!=NULL)
	{
		item_head_last=item_head;
		item_head=NULL;
		for(p1=item_head_last;p1!=NULL;p1=p1->next)
		{
			for(p2=p1->next;p2!=NULL;p2=p2->next)
			{
				flag=k;
				attr_p1=p1->name;
				attr_p2=p2->name;
				while(flag-1)
				{
					if(attr_p1->attr_no!=attr_p2->attr_no)
						break;
					attr_p1=attr_p1->next;
					attr_p2=attr_p2->next;
					flag--;
				}
				if(flag==1)
				{
					candidate=NULL;
					attr_p5=p1->name;
					while(attr_p5!=NULL)
					{
						attr_p3=(struct attribute*)malloc(sizeof(struct attribute));
						attr_p3->attr_no=attr_p5->attr_no;
						attr_p3->next=NULL;
						if(candidate==NULL)
							candidate=attr_p3;
						else
							attr_p4->next=attr_p3;
						attr_p4=attr_p3;
						attr_p5=attr_p5->next;
					}
					attr_p3=(struct attribute*)malloc(sizeof(struct attribute));
					attr_p3->attr_no=attr_p2->attr_no;
					attr_p3->next=NULL;
					attr_p4->next=attr_p3;
					item_cp=(struct item*)malloc(sizeof(struct item));
					item_cp->list_num=0;
					item_cp->next=NULL;
					item_cp->tidlist=NULL;
					item_cp->name=candidate;
					list_p1=p1->tidlist;
					list_p2=p2->tidlist;
					while((list_p1!=NULL)&&(list_p2!=NULL))
					{
						tid1=list_p1->tid;
						tid2=list_p2->tid;
						if(tid1==tid2)
						{
							list_p=(struct tidlist_node*)malloc(sizeof(struct tidlist_node));
							list_p->tid=tid1;
							list_p->next=NULL;
							if(item_cp->tidlist==NULL)
								item_cp->tidlist=list_p;
							else
								list_temp->next=list_p;
							list_temp=list_p;
							item_cp->list_num+=1;
							list_p1=list_p1->next;
							list_p2=list_p2->next;
						}
						else if(tid1>tid2)
							list_p2=list_p2->next;
						else
							list_p1=list_p1->next;
					}
					if((item_cp->list_num)>=min_sup_count)
					{
						if(item_head==NULL)
							item_head=item_cp;
						else
							item_cp1->next=item_cp;
						item_cp1=item_cp;
					}
					else
						free_item(item_cp);
				}
			}
		}
		item_cp=item_head_last;
		while(item_cp!=NULL)
		{
			save_p1=(struct partition_node*)malloc(sizeof(struct partition_node));
			save_p1->sup_count=item_cp->list_num;
			save_p1->next=NULL;
			save_p1->attr_name=item_cp->name;
			item_cp->name=NULL;
			if(index[k]==NULL)
				index[k]=save_p1;
			else
				save_p2->next=save_p1;
			save_p2=save_p1;
			item_cp=item_cp->next;
		}
		item_head_last1=item_head_last;
		while(item_head_last1!=NULL)
		{
			item_head_last2=item_head_last1->next;
			free_item(item_head_last1);
			item_head_last1=item_head_last2;
		}
		k++;
	}
	total_number+=(i-1);
	return index;
}

int init_attribute(FILE *fp,int &offset)
{
	char ch;
	int attr_number=0;
	int i=0;
	ch=fgetc(fp);
	while(ch!='\t')
	{
		ch=fgetc(fp);
	}
	while(ch!='\n')
	{
		if(ch=='\t')
		{
			attr_number++;
			ch=fgetc(fp);
			i=0;
		}
		else
		{
			A[attr_number][i++]=ch;
			ch=fgetc(fp);
		}
	}
	offset=ftell(fp);
	return attr_number;
}

void Merge_partition(struct partition_node **partition[],struct partition_node *Large_set[])
{
	struct partition_node **p;
	struct partition_node *cp;
	struct partition_node *cp1;
	struct partition_node *cp_in_large;
	struct partition_node *cp_in_large1;
	struct attribute *p1;
	struct attribute *p2;
	int k=2;
	int i=1;
	p=partition[1];
	while(p[i]!=NULL)
	{
		Large_set[i]=p[i];
		p[i]=NULL;
		i++;
	}
	int flag;
	int attr1;
	int attr2;
	while(partition[k]!=NULL)
	{
		p=partition[k];
		i=1;
		while(p[i]!=NULL)
		{
			cp=p[i];
			cp_in_large=Large_set[i];
			cp_in_large1=NULL;
			while(cp!=NULL)
			{
				if(cp_in_large==NULL)
				{
					if(Large_set[i]==NULL)
						Large_set[i]->next=cp;
					else
						cp_in_large1->next=cp;
					cp=NULL;
				}
				else
				{
					flag=0;
					p1=cp->attr_name;
					p2=cp_in_large->attr_name;
					while(p1!=NULL)
					{
						attr1=p1->attr_no;
						attr2=p2->attr_no;
						if(attr1<attr2)
						{
							flag=1;
							break;
						}
						if(attr1>attr2)
						{
							flag=2;
							break;
						}
						p1=p1->next;
						p2=p2->next;
					}
					if(flag==0)
					{
						cp_in_large->sup_count+=cp->sup_count;
						cp=cp->next;
						cp_in_large1=cp_in_large;
						cp_in_large=cp_in_large->next;
					}