决策树dlg.cpp

Generate_decision_tree算法由数据划分D的训练元组产生决策树。

// 决策树Dlg.cpp : 实现文件
//

#include "stdafx.h"
#include "决策树.h"
#include "决策树Dlg.h"
#include <math.h>
#ifdef _DEBUG
#define new DEBUG_NEW
#endif


// 用于应用程序“关于”菜单项的 CAboutDlg 对话框

class CAboutDlg : public CDialog
{
public:
	CAboutDlg();

// 对话框数据
	enum { IDD = IDD_ABOUTBOX };

	protected:
	virtual void DoDataExchange(CDataExchange* pDX);    // DDX/DDV 支持

// 实现
protected:
	DECLARE_MESSAGE_MAP()
};

CAboutDlg::CAboutDlg() : CDialog(CAboutDlg::IDD)
{
}

void CAboutDlg::DoDataExchange(CDataExchange* pDX)
{
	CDialog::DoDataExchange(pDX);
}

BEGIN_MESSAGE_MAP(CAboutDlg, CDialog)
END_MESSAGE_MAP()


// C决策树Dlg 对话框




C决策树Dlg::C决策树Dlg(CWnd* pParent /*=NULL*/)
	: CDialog(C决策树Dlg::IDD, pParent)
	, m_strD(_T(""))
	, m_strAttri(_T(""))
	, m_strTree(_T(""))
{
	Dall=NULL;
	m_hIcon = AfxGetApp()->LoadIcon(IDR_MAINFRAME);
}

void C决策树Dlg::DoDataExchange(CDataExchange* pDX)
{
	CDialog::DoDataExchange(pDX);
	DDX_Text(pDX, IDC_STATIC1, m_strD);
	DDX_Text(pDX, IDC_STATIC2, m_strAttri);
	DDX_Text(pDX, IDC_STATIC3, m_strTree);
}

BEGIN_MESSAGE_MAP(C决策树Dlg, CDialog)
	ON_WM_SYSCOMMAND()
	ON_WM_PAINT()
	ON_WM_QUERYDRAGICON()
	//}}AFX_MSG_MAP
	ON_BN_CLICKED(IDC_BUTTON1, &C决策树Dlg::OnBnClickedButton1)
	ON_BN_CLICKED(IDC_BUTTON2, &C决策树Dlg::OnBnClickedButton2)
	ON_BN_CLICKED(IDC_BUTTON3, &C决策树Dlg::OnBnClickedButton3)
	ON_BN_CLICKED(IDC_BUTTON4, &C决策树Dlg::OnBnClickedButton4)
END_MESSAGE_MAP()


// C决策树Dlg 消息处理程序

BOOL C决策树Dlg::OnInitDialog()
{
	CDialog::OnInitDialog();

	// 将“关于...”菜单项添加到系统菜单中。

	// IDM_ABOUTBOX 必须在系统命令范围内。
	ASSERT((IDM_ABOUTBOX & 0xFFF0) == IDM_ABOUTBOX);
	ASSERT(IDM_ABOUTBOX < 0xF000);

	CMenu* pSysMenu = GetSystemMenu(FALSE);
	if (pSysMenu != NULL)
	{
		CString strAboutMenu;
		strAboutMenu.LoadString(IDS_ABOUTBOX);
		if (!strAboutMenu.IsEmpty())
		{
			pSysMenu->AppendMenu(MF_SEPARATOR);
			pSysMenu->AppendMenu(MF_STRING, IDM_ABOUTBOX, strAboutMenu);
		}
	}

	// 设置此对话框的图标。当应用程序主窗口不是对话框时，框架将自动
	//  执行此操作
	SetIcon(m_hIcon, TRUE);			// 设置大图标
	SetIcon(m_hIcon, FALSE);		// 设置小图标

	// TODO: 在此添加额外的初始化代码

	return TRUE;  // 除非将焦点设置到控件，否则返回 TRUE
}

void C决策树Dlg::OnSysCommand(UINT nID, LPARAM lParam)
{
	if ((nID & 0xFFF0) == IDM_ABOUTBOX)
	{
		CAboutDlg dlgAbout;
		dlgAbout.DoModal();
	}
	else
	{
		CDialog::OnSysCommand(nID, lParam);
	}
}

// 如果向对话框添加最小化按钮，则需要下面的代码
//  来绘制该图标。对于使用文档/视图模型的 MFC 应用程序，
//  这将由框架自动完成。

void C决策树Dlg::OnPaint()
{
	if (IsIconic())
	{
		CPaintDC dc(this); // 用于绘制的设备上下文

		SendMessage(WM_ICONERASEBKGND, reinterpret_cast<WPARAM>(dc.GetSafeHdc()), 0);

		// 使图标在工作矩形中居中
		int cxIcon = GetSystemMetrics(SM_CXICON);
		int cyIcon = GetSystemMetrics(SM_CYICON);
		CRect rect;
		GetClientRect(&rect);
		int x = (rect.Width() - cxIcon + 1) / 2;
		int y = (rect.Height() - cyIcon + 1) / 2;

		// 绘制图标
		dc.DrawIcon(x, y, m_hIcon);
	}
	else
	{
		CDialog::OnPaint();
	}
}

//当用户拖动最小化窗口时系统调用此函数取得光标显示。
//
HCURSOR C决策树Dlg::OnQueryDragIcon()
{
	return static_cast<HCURSOR>(m_hIcon);
}


void C决策树Dlg::OnBnClickedButton1()
{
	// TODO: 在此添加控件通知处理程序代码
	CreateTranningElement();
	Output(Dall);
}

void C决策树Dlg::CreateTranningElement(void)
{
	AddToD(YOUTH,		HIGH,	NO,	FAIR,		NO);
	AddToD(YOUTH,		HIGH,	NO,	EXCELLENT,	NO);
	AddToD(MIDDLE_AGED,	HIGH,	NO,	FAIR,		YES);
	AddToD(SENIOR,		MEDIUM,	NO,	FAIR,		YES);
	AddToD(SENIOR,		LOW,	YES,FAIR,		YES);
	AddToD(SENIOR,		LOW,	YES,EXCELLENT,	NO);
	AddToD(MIDDLE_AGED,	LOW,	YES,EXCELLENT,	YES);
	AddToD(YOUTH,		MEDIUM,	NO,	FAIR,		NO);
	AddToD(YOUTH,		LOW,	YES,FAIR,		YES);
	AddToD(SENIOR,		MEDIUM,	YES,FAIR,		YES);
	AddToD(YOUTH,		MEDIUM,	YES,EXCELLENT,	YES);
	AddToD(MIDDLE_AGED,	MEDIUM,	NO,	EXCELLENT,	YES);
	AddToD(MIDDLE_AGED,	HIGH,	YES,FAIR,		YES);
	AddToD(SENIOR,		MEDIUM,	NO,	EXCELLENT,	NO);
}

void C决策树Dlg::AddToD(int age, int income, int student, int credit_rating, int buys_computer)
{
	DNode *newnode=new DNode;
	newnode->attribute[0]=age;
	newnode->attribute[1]=income;
	newnode->attribute[2]=student;
	newnode->attribute[3] =credit_rating;
	newnode->attribute[4]=buys_computer;
	newnode->next =Dall;
	Dall=newnode;
}

void C决策树Dlg::OnBnClickedButton2()
{
	// TODO: 在此添加控件通知处理程序代码
	
	attribute_list[0].strName =_T("age");
	discrete[0]=3;
	discrete[1]=3;
	discrete[2]=2;
	discrete[3]=2;
	attribute_list[1].strName=_T("income");
	attribute_list[2].strName=_T("student");
	attribute_list[3].strName=_T("credit_rating");
	CString str,output;
	str=_T("");
	output=_T("");
	for(int i=0;i<ATTRIBUTE_NUM-1;i++)
	{
		output+=attribute_list[i].strName+_T("\n");
	}
	UpdateData(1);
	m_strAttri=output;
	UpdateData(0);

}

void C决策树Dlg::OnBnClickedButton3()
{
	// TODO: 在此添加控件通知处理程序代码
	int a=15;
	Tree=Generate_decision_tree(Dall,a);
}

TreeNode* C决策树Dlg::Generate_decision_tree(DNode* D,int list)
{
	int splitting_criterion;
	DNode *Dj;
	Dj=NULL;
	TreeNode *N=new TreeNode;
	N->bIsLeaf =false;
	for(int i=0;i<MAX_DISCRETE;i++)
	{
		N->p[i]=NULL;
	}
	
	if(SameC(D))            //aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa////
	{
		N->bIsLeaf =true;
		N->leaf = Majority(D);
		return N;//////////////////////////////////////////////////////
	}
#if 0	
	if(ListEmpty(attribute_list))
	{
		N->bIsLeaf =true;
		N->leaf = Majority(D);
		return N;
	}
	for(int i=0;i<ATTRIBUTE_NUM-1;i++)
	{
		if(attribute_list[i].bSplitted ==false)
		{
			splitting_criterion=i;
			break;
		}
	}
	attribute_list[splitting_criterion].bSplitted=true;
#else
	if(list==0)
	{
		N->bIsLeaf =true;
		N->leaf = Majority(D);
		return N;
	}
/*	int temp=list;
	for(int i=0;i<ATTRIBUTE_NUM-1;i++)
	{
		if(temp%2==1)
		{
			splitting_criterion=i;
			break;
		}
		temp=temp/2;
	}
*/
	splitting_criterion=attribute_selection_method(D,list);
	if(splitting_criterion==0)
	{
		list=list-1;
	}
	else if(splitting_criterion==1)
	{
		list=list-2;
	}
	else if(splitting_criterion==2)
	{
		list=list-4;
	}
	else if(splitting_criterion==3)
	{
		list=list-8;
	}
	UpdateData(1);
	m_strD.Format (_T("%d"),list);
	UpdateData(0);
//	MessageBox(_T(""));

#endif

	N->AttributeID=splitting_criterion;
	for(int i=0;i<discrete[splitting_criterion];i++)
	{
		Dj=FindDj(D,splitting_criterion,i);//////////////////////////////
		if(!Dj)
		{
			TreeNode* newnode=new TreeNode;
			newnode->bIsLeaf=true;
			newnode->leaf =Majority(D);
			N->p[i]=newnode;
		}
		else
		{
			N->p[i]=Generate_decision_tree(Dj,list);
		}
	}
	return N;
}
		

bool C决策树Dlg::SameC(DNode* Di)
{
	DNode* p;
	p=Di;
	int a;
	a=p->attribute [ATTRIBUTE_NUM-1];
	while(p)
	{
		if(p->attribute [ATTRIBUTE_NUM-1]==a)
		{
			p=p->next;
		}
		else return false;
	}
	return true;
}

int C决策树Dlg::Majority(DNode* Di)
{
	DNode* p;
	p=Di;
	int sum=0;
		
	while(p)
	{
		if(p->attribute [ATTRIBUTE_NUM-1]==YES)
		{
			sum++;
		}
		else sum--;
		p=p->next;
	}
	if(sum>=0) return YES;
	else return NO;
}

DNode* C决策树Dlg::FindDj(DNode* D, int nIndexAttr,int nAttrValue)
{
	
	DNode* p;//遍历指针
	p=D;
	DNode* ret;//输出节点指针
	ret=NULL;
	while(p)
	{
		if(p->attribute[nIndexAttr]==nAttrValue)
		{
			DNode* q=new DNode;
			for(int i=0;i<ATTRIBUTE_NUM;i++)
			{
				q->attribute [i]=p->attribute[i];
			}
			q->next =ret;
			ret=q;
		}
		p=p->next ;
	}
	return ret;
}

bool C决策树Dlg::ListEmpty(Attribute* pAttri)
{
	Attribute* p;
	p=pAttri;
	for(int i=0;i<ATTRIBUTE_NUM-1;i++)
	{
		if(!p->bSplitted)
		{
			return false;
		}
		p++;
	}
	return true;
}

void C决策树Dlg::Output(DNode* D)
{
	DNode* p;
	p=D;
	CString str,output;
	output=_T("");
	str=_T("");
	while(p)
	{
		for(int i=0;i<ATTRIBUTE_NUM;i++)
		{
			str.Format (_T("%d\t"),p->attribute[i]);
			output+=str;
		}
		output+=_T("\n");
		p=p->next ;
	}
	MessageBox(output);
}


void C决策树Dlg::OnBnClickedButton4()
{
	OutputTree(Tree);
	// TODO: 在此添加控件通知处理程序代码
}

void C决策树Dlg::OutputTree(TreeNode *tree)
{
	TreeNode* p;
	p=tree;
	if(p)
	{
		UpdateData(1);
		if(p->bIsLeaf ==false)
		{
			
			m_strTree+=attribute_list[p->AttributeID].strName +_T("\t");
			
		}
		else
		{
			if(p->leaf ==YES)
			{
				m_strTree+=_T("yes\t");
			}
			else if(p->leaf ==NO)
			{
				m_strTree+=_T("no\t");
			}
		}
		UpdateData(0);
		if(p->bIsLeaf)
		{
			return;
		}
		else
		{
			for(int i=0;i<  discrete[p->AttributeID] && p->p[i];i++)
			{
				OutputTree(p->p [i]);
				
			}
			return;
		}
	}
	return;
}

int C决策树Dlg::attribute_selection_method(DNode* D,int aList)
{
	int ret=-1;
	double sum=0.0;
	double info=0.0;
	double yes=0.0;
	DNode *p;
	p=D;
	while(p)
	{
		if(p->attribute [ATTRIBUTE_NUM-1]==YES)
		{
			yes+=1.0;
		}
		sum+=1.0;
		p=p->next;
	}
	info=-((sum-yes)/sum*log((sum-yes)/sum)/log(2.0)+yes/sum*log(yes/sum)/log(2.0));
	double info1[ATTRIBUTE_NUM-1];
	double Gain[ATTRIBUTE_NUM-1];
	for(int i=0;i<ATTRIBUTE_NUM-1;i++)
	{
		Gain[i]=0.0;
		info1[i]=0.0;
	}
	int temp=aList;
	double a[2][MAX_DISCRETE];//a[m][n]表示决定为m的，属性为n的数据总数

	for(int i=0;i<ATTRIBUTE_NUM-1;i++)
	{	
		for(int z=0;z<2;z++)
		{
			for(int s=0;s<MAX_DISCRETE;s++)
			{
				a[z][s]=0;
			}
		}
		if(temp%2 ==1)
		{
			p=D;
			while(p)
			{
				a[p->attribute [ATTRIBUTE_NUM-1]][p->attribute[i]]+=1;
				p=p->next;
			}
			for(int j=0;j<discrete[i];j++)
			{
				if(abs(a[0][j])<1e-6||abs(a[1][j])<1e-6)
				{

				}
				else 
				{
					info1[i]+=-((a[1][j]+a[0][j])/sum*(a[0][j]/(a[0][j]+a[1][j])*log(a[0][j]/(a[0][j]+a[1][j]))/log(2.0)+a[1][j]/(a[0][j]+a[1][j])*log(a[1][j]/(a[0][j]+a[1][j]))/log(2.0)));
				}
			}
			Gain[i]=info-info1[i];
		}
		temp=temp/2;
	}
	temp=aList;
	int max=-1;
	for(int i=0;i<ATTRIBUTE_NUM-1;i++)
	{
		if((max==-1||Gain[i]>Gain[max]) && temp%2==1)
		{
			max=i;
		}
		temp=temp/2;
	}
	CString str;str.Format(_T("%d"),max);MessageBox(str);
	return max;
}