Phân tích thiết kế giải thuật

                       Trí Tuệ Nhân Tạo P7 
            ( Nhập môn Học Máy)
=> những nội dung khó sẽ có môn học riêng

1. Khái niệm

+ Xây dựng module học cho hệ thống

2 Học quy nạp

+ ví dụ:

=> như sơ đồ ta thấy có vẻ 1 vài dữ liệu bị sai=> giải pháp chia 2 bộ dữ liệu:  Training(70%) ,Testing(20%), điều chỉnh ngay trong qt Training(10%)

3 Cây quyết định

+ Biểu diễn:

=> giải pháp:
Thuật toán học cây quyết định (ID3,C4.5,C5.0)( bài sd ID3)

+ Cấu trúc:

+ b1:chọn thuộc tính

+ Khi nào học tốt

Code in C++ bên dưới

4 Mạng Perceptron đơn lớp
học sau ở phần học máy






Cây quyết đinh ID3 
+ file: Text
15 6
id outlook temperature humidity wind play
1 sunny hot high weak no
2 sunny hot high strong no
3 overcast hot high weak yes
4 rainy mild high weak yes
5 rainy cool normal weak yes
6 rainy cool normal strong no
7 overcast cool normal strong yes
8 sunny mild high weak no
9 sunny cool normal weak yes
10 rainy mild normal weak yes
11 sunny mild normal strong yes
12 overcast mild high strong yes
13 overcast hot normal weak yes
14 rainy mild high strong no

+ Code:
#include<iostream>
#include<fstream>
#include<math.h>
using namespace std;

int soExamble,soAttribute;
string Data[20][20];

void Nhap(int &soExamble,int &soAtribute,string Data[20][20])
{
fstream f;
f.open("id3.txt");
f>>soExamble;
f>>soAtribute;
for(int i=0;i<soExamble;i++)
{
for(int j=0;j<soAtribute;j++)
{
f>>Data[i][j];
}
}
}
// ham xuat chi de test thoi a
void Xuat(int soExamble, int soAtribute, string Data[20][20])
{
for(int i=0;i<soExamble;i++)
{
for(int j=0;j<soAtribute;j++)
{
cout<<Data[i][j]<< " ";
}
cout<<endl;
}
}

class Con// con cua cac Attribute
{
public:
string Ten;
int Positive;// so luong yes
int Nagative;// so luong no
int soPt;// tong so pt

Con();
double Entropy();// tinh entropy
};

Con::Con()
{
Positive=Nagative=0;
}

double Con::Entropy()
{
double T;
double p=(double)Positive;
double n=(double)Nagative;
if(Nagative==0 || Positive==0) {
T= 0;
}

else {
T= -p/soPt* (log(p/soPt)/log(2.0)) - n/soPt* (log(n/soPt)/log(2.0));
}
return T;
}

class Object// moi 1 thuoc tinh ban dau la 1 object: 1 Attribute
{
public:
string name;// ten Attribute
int soPt;
int soCon;
Con tenCon[10];

void Create(int j,int soExamble,int soAttribute,string Data[20][20]);
void Xuat();
double Remainder();// remainder con nao nho hon thi chon con do
void ChonGoc();// ghi ra nhung anh true hoac false va loai khoi danh sach tenCon
};

void Object::ChonGoc()//ghi ra nhung anh true hoac false, loai khoi danh sach xet
{
for(int i=0;i<soCon;i++)
{
if(tenCon[i].Entropy()==0){
string str="   chon : "+tenCon[i].Ten;
if(tenCon[i].Positive>0)
{
str+=" => Yes";
}
else{
str+=" => No";
}
cout<<endl<<str;
for(int j=i;j<soCon-1;j++){
tenCon[j]=tenCon[j+1];
}
soCon--;
}
}
}

double Object::Remainder()
{
double S=0;
for(int i=0;i<soCon;i++)
{
S+=tenCon[i].Entropy()*tenCon[i].soPt/soPt;
}
return S;
}

void Object:: Create(int j,int soExamble,int soAttribute,string Data[20][20])
{
soPt=0;
soCon=0;
name= Data[0][j];
for(int i=1;i<soExamble;i++)
{
soPt++;
int co=1;
for(int k=0;k<soCon;k++)
{
if(Data[i][j]==tenCon[k].Ten){
tenCon[k].soPt++;
if(Data[i][soAttribute-1]=="yes"){
tenCon[k].Positive++;
}
else{
tenCon[k].Nagative++;
}
co=0;
break;
}
}
if(co==1){
tenCon[soCon].Ten=Data[i][j];
tenCon[soCon].soPt=1;
if(Data[i][soAttribute-1]=="yes"){
tenCon[soCon].Positive++;
}
else{
tenCon[soCon].Nagative++;
}
soCon++;
}

}
}

void Object::Xuat()
{
cout<<endl<<name<<" : "<<soPt<<" : "<<soCon<<" remainder: "<<Remainder()<<endl;
for(int i=0;i<soCon;i++)
{
cout<<tenCon[i].Ten<<": "<<tenCon[i].soPt<<": "<<tenCon[i].Nagative<<": ";
cout<<tenCon[i].Positive<<"  Entropy: "<<tenCon[i].Entropy()<<endl;
}
}

class ListObject
{
public:
Object DsObject[10];

void Create(int soExamble,int soAttribute,string Data[20][20]);
Object ChoseAttribute(int soAttribute);//
void DTL(int soExamble,int soAttribute,string Data[20][20],int dem,int maxTang);
bool KtExamble_1_class(int soExamble,int soAttribute,string Data[20][20]);
// ham kiem tra xem tat ca cac Examble cung thuoc 1 lop Yes hoac NO
};

bool ListObject::KtExamble_1_class(int soExamble,int soAttribute,string Data[20][20])
{
string check= Data[1][soAttribute-1];
for(int i=2;i<soExamble;i++)
{
if(Data[i][soAttribute-1]!=check){
return false;
}
}
cout<<"tat ca deu chon: "<<check;
return true;
}

Object ListObject::ChoseAttribute(int soAttribute)
{
double remainderMin=DsObject[1].Remainder();
int vtMin=1;
for(int j=2;j<soAttribute-1;j++)
{
if(remainderMin>DsObject[j].Remainder()) {
remainderMin=DsObject[j].Remainder();
vtMin=j;
}
}
DsObject[vtMin].Xuat();
cout<<endl<<"neu chon: "<<DsObject[vtMin].name<<" thi: "<<endl;
return DsObject[vtMin];
}

void ListObject::Create(int soExamble,int soAttribute,string Data[20][20])
{
for(int j=1;j<soAttribute-1;j++)
{
DsObject[j].Create(j,soExamble,soAttribute,Data);
}
}

void ListObject::DTL(int soExamble,int soAttribute,string Data[20][20],int dem,int maxTang)
{
dem++;
if(soExamble<2) return ;// het examble
else if(KtExamble_1_class(soExamble,soAttribute,Data)) return ;
else if(soAttribute<2) return ;//het attribute
else{
Object Best=ChoseAttribute(soAttribute);// xuat them ten Attribute
Best.ChonGoc();//xuat them ten con da dk yes hoac no va loai no ra khoi danh sach con
// gioi han so tang kiem tra cua cay quyet dinh
if(dem>maxTang){
for(int i=0;i<Best.soCon;i++){
if(Best.tenCon[i].Positive>Best.tenCon[i].Nagative){
cout<<" chon "<<Best.tenCon[i].Ten<<"=> Yes"<<endl;
}
else{
cout<<" chon "<<Best.tenCon[i].Ten<<"=> NO"<<endl;
}
}
return;
}

int soAttribute1=0;
int vtBest;// vt Attribute tuong ung

//tim vitri best
for(int j=1;j<soAttribute;j++)
{
if(Data[0][j]==Best.name){
vtBest=j;
soAttribute1=soAttribute-1;
}
}


for(int k=0;k<Best.soCon;k++)
{
int soExamble1=1;
string Data1[20][20];
//lay du lieu data moi
cout<<endl<<"    chon  "<<Best.tenCon[k].Ten<<" thi: "<<endl;
int m=0,n=0;
for(int i=0;i<soExamble;i++)
{
if(Data[i][vtBest]==Best.tenCon[k].Ten){
m++;
soExamble1++;
n=0;
for(int j=0;j<soAttribute;j++){
if(j==vtBest) continue;
Data1[0][n]=Data[0][j];
Data1[m][n]=Data[i][j];//loi
n++;
}
}
}
// create ra listObject moi va...
for(int j=1;j<soAttribute1-1;j++)
{
DsObject[j].Create(j,soExamble1,soAttribute1,Data1);
}
//dequy
// cout<<soAttribute1<<":  "<<soExamble1<<endl;
// Xuat(soExamble1,soAttribute1,Data1);
DTL(soExamble1,soAttribute1,Data1,dem,maxTang);
// Object Best=ChoseAttribute(soAttribute1);// xuat them ten Attribute
// Best.ChonGoc();
}
}
}

int main()
{
int dem=0;
Nhap(soExamble,soAttribute,Data);
ListObject list1;

list1.Create(soExamble,soAttribute,Data);
// list1.ChoseAttribute(soAttribute).ChonGoc();
list1.DTL(soExamble,soAttribute,Data,dem,3);


}