머신 러닝 알고리즘 중 하나(C4.5)

기계 학습에서 결정 트리는 예측 모델이다. 이것은 대상 속성과 대상 값 간의 반사 관계를 대표한다.나무의 각 노드는 특정한 대상을 나타내고, 각 분기 경로는 가능한 속성 값을 나타내며, 각 잎 노드는 뿌리 노드에서 이 잎 노드까지 겪는 경로에 대응하는 값을 나타낸다.결정 트리는 단일 출력만 있고 복수 출력이 있으면 독립된 결정 트리를 만들어서 서로 다른 출력을 처리할 수 있다.
데이터에서 결정 트리를 만드는 기계 학습 기술을 결정 트리 학습이라고 하는데 통속적으로 말하면 결정 트리다.
결정 트리 학습도 데이터 발굴의 일반적인 방법이다.여기서 모든 결정 트리는 하나의 트리 구조를 설명했고 그는 이 유형의 대상을 속성에 의존하여 편집할 수 있는 지점을 가지고 있다.모든 결정 트리는 원본 데이터베이스에 대한 분할에 의존하여 데이터 테스트를 진행할 수 있다.이 과정은 나무를 차례대로 잘라낼 수 있다.더 이상 분할할 수 없거나 하나의 단독 클래스가 특정한 지점에 적용될 수 있을 때 귀속 과정은 완성된다.또한 랜덤 삼림 분류기는 많은 결정 트리를 결합시켜 분류의 정확도를 높인다.
결정 트리는 조건 확률을 계산하여 구성할 수도 있다.결정 트리는 수학의 계산 방법에 의존하면 더욱 이상적인 효과를 얻을 수 있다.
결정 트리는 어떻게 작동합니까?
결정을 내릴 때는 일반적으로 위에서 아래로 이루어진다.
분할을 선택하는 방법은 여러 가지가 있지만 목적은 일치한다. 목적에 대한 시도를 가장 잘 분할하는 것이다.
뿌리부터 잎 노드까지 모두 하나의 경로가 있는데 이 경로가 바로 하나의'규칙'이다.
결정 트리는 두 갈래일 수도 있고 여러 갈래일 수도 있다.
각 노드에 대한 측정:

이 노드를 통과한 기록 수

잎 노드라면 분류 경로

잎 노드를 정확하게 분류하는 비율

어떤 규칙의 효과는 다른 몇몇 규칙보다 좋을 수 있다.
 
ID3 알고리즘이 실제 응용에서 문제가 있기 때문에Quilan은 C4.5 알고리즘, 엄밀히 말하면 C4.5는 ID3의 개선 알고리즘일 수 있습니다.ID3 알고리즘 소개
　　C4.5 알고리즘은 ID3 알고리즘의 장점을 계승하고 다음과 같은 측면에서 ID3 알고리즘을 개선한다.

정보 이득률로 속성을 선택하여 정보 이득으로 속성을 선택할 때 값이 많은 속성을 선호하는 부족함을 극복했다.

수 구조 과정에서 가지를 자르기;

연속 속성에 대한 이산화 처리를 완성할 수 있다.

불완전한 데이터를 처리할 수 있습니다.

　　C4.5 알고리즘은 다음과 같은 장점이 있다. 발생하는 분류 규칙은 이해하기 쉽고 정확도가 높다.그 단점은 트리를 구성하는 과정에서 데이터 집합에 대해 여러 차례의 순서 스캔과 정렬을 해야 하기 때문에 알고리즘의 저효과가 발생한다는 것이다.또한 C4.5 메모리에 주재할 수 있는 데이터 집합에만 적합하며, 훈련 집합이 메모리를 더 이상 수용할 수 없을 정도로 크면 프로그램이 실행되지 않습니다.
 

  1 // C4.5_test.cpp : Defines the entry point for the console application.
  2 //
  3 #include "stdafx.h"
  4 #include <stdio.h>
  5 #include <math.h>
  6 #include "malloc.h"
  7 #include <stdlib.h>
  8 const int MAX = 10;
  9 int** iInput;
 10 int i = 0;// 
 11 int j = 0;// 
 12 void build_tree(FILE *fp, int* iSamples, int* iAttribute,int ilevel);// 
 13 int choose_attribute(int* iSamples, int* iAttribute);// test_attribute
 14 double info(double dTrue,double dFalse);// 
 15 double entropy(double dTrue, double dFalse, double dAll);// 
 16 double splitinfo(int* list,double dAll);
 17 int check_samples(int *iSamples);// samples 
 18 int check_ordinary(int *iSamples);// 
 19 int check_attribute_null(int *iAttribute);// attribute 
 20 void get_attributes(int *iSamples,int *iAttributeValue,int iAttribute);
 21 int _tmain(int argc, _TCHAR* argv[])
 22 {
 23  FILE *fp;
 24  FILE *fp1;
 25  char iGet;
 26  int a = 0;
 27  int b = 0;//a,b 
 28  int* iSamples;
 29  int* iAttribute;
 30  fp = fopen("c:\\input.txt","r");
 31  if (NULL == fp)
 32  {
 33   printf("error
");
 34   return 0;
 35  }
 36  iGet = getc(fp);
 37  
 38  while (('
' != iGet)&&(EOF != iGet))
 39  {
 40   if (',' == iGet)
 41   {
 42    i++;
 43   }
 44   iGet = getc(fp);
 45  }
 46  i++;
 47  
 48  iAttribute = (int *)malloc(sizeof(int)*i);
 49  for (int k = 0; k<i; k++)
 50  {
 51   iAttribute[k] = (int)malloc(sizeof(int));
 52   iAttribute[k] = 1;
 53  }
 54  while (EOF != iGet)
 55  {
 56   if ('
' == iGet)
 57   {
 58    j++;
 59   }
 60   iGet = getc(fp);
 61  }
 62  j++;
 63  
 64  iInput = (int **)malloc(sizeof(int*)*j);
 65  iSamples = (int *)malloc(sizeof(int)*j);
 66  for (a = 0;a < j;a++)
 67  {
 68   iInput[a] = (int *)malloc(sizeof(int)*i);
 69   iSamples[a] = (int)malloc(sizeof(int));
 70   iSamples[a] = a;
 71  }
 72  a = 0;
 73  fclose(fp);
 74  fp=fopen("c:\\input.txt","r");
 75  iGet = getc(fp);
 76  while(EOF != iGet)
 77  {
 78   if ((',' != iGet)&&('
' != iGet))
 79   {
 80    iInput[a][b] = iGet - 48;
 81    b++;
 82   }
 83   if (b == i)
 84   {
 85    a++;
 86    b = 0;
 87   }
 88   iGet = getc(fp);
 89  }
 90  
 91  fp1 = fopen("d:\\output.txt","w");
 92  build_tree(fp1,iSamples,iAttribute,0);
 93  fclose(fp);
 94  return 0;
 95 }
 96 
 97 void build_tree(FILE * fp, int* iSamples, int* iAttribute,int level)//
 98 {
 99  int iTest_Attribute = 0;
100  int iAttributeValue[MAX];
101  int k = 0;
102  int l = 0;
103  int m = 0;
104  int *iSamples1;
105  for (k = 0; k<MAX; k++)
106  {
107   iAttributeValue[k] = -1;
108  }
109  if (0 == check_samples(iSamples))
110  {
111   fprintf(fp,"result: %d
",iInput[iSamples[0]][i-1]);
112   return;
113  }
114  if (1 == check_attribute_null(iAttribute))
115  {
116   fprintf(fp,"result: %d
",check_ordinary(iSamples));
117   return;
118  }
119  iTest_Attribute = choose_attribute(iSamples,iAttribute);
120  iAttribute[iTest_Attribute] = -1;
121  get_attributes(iSamples,iAttributeValue,iTest_Attribute);
122  k = 0;
123  while ((-1 != iAttributeValue[k])&&(k < MAX))
124  {
125   l = 0;
126   m = 0;
127   while ((-1 != iSamples[l])&&(l < j))
128   {
129    if (iInput[iSamples[l]][iTest_Attribute] == iAttributeValue[k])
130    {
131     m++;
132    }
133    l++;
134   }
135   iSamples1 = (int *)malloc(sizeof(int)*(m+1));
136   l = 0;
137   m = 0;
138   while ((-1 != iSamples[l])&&(l < j))
139   {
140    if (iInput[iSamples[l]][iTest_Attribute] == iAttributeValue[k])
141    {
142     iSamples1[m] = iSamples[l];
143     m++;
144    }
145    l++;
146   }
147   iSamples1[m] = -1;
148   if (-1 == iSamples1[0])
149   {
150    fprintf(fp,"result: %d
",check_ordinary(iSamples));
151    return;
152   }
153   fprintf(fp,"level%d: %d = %d
",level,iTest_Attribute,iAttributeValue[k]);
154   build_tree(fp,iSamples1,iAttribute,level+1);
155   k++;
156  }
157 }
158 int choose_attribute(int* iSamples, int* iAttribute)
159 {
160  int iTestAttribute = -1;
161  int k = 0;
162  int l = 0;
163  int m = 0;
164  int n = 0;
165  int iTrue = 0;
166  int iFalse = 0;
167  int iTrue1 = 0;
168  int iFalse1 = 0;
169  int iDepart[MAX];
170  int iRecord[MAX];
171  double dEntropy = 0.0;
172  double dGainratio = 0.0;
173  double test = 0.0;
174  
175  for (k = 0;k<MAX;k++)
176  {
177   iDepart[k] = -1;
178   iRecord[k] = 0;
179  }
180  k = 0;
181  while ((l!=2)&&(k<(i - 1)))
182  {
183   if (iAttribute[k] == -1)
184   {
185    l++;
186   }
187   k++;
188  }
189  if (l == 1)
190  {
191   for (k = 0;k<(k-1);k++)
192   {
193    if (iAttribute[k] == -1)
194    {
195     return iAttribute[k];
196    }
197   }
198  }
199  for (k = 0;k < (i-1);k++)
200  {
201   l = 0;
202   iTrue = 0;
203   iFalse = 0;
204   if (iAttribute[k] != -1)
205   {
206    while ((-1 != iSamples[l])&&(l < j))
207    {
208     if (0 == iInput[iSamples[l]][i-1])
209     {
210      iFalse++;
211     }
212     if (1 == iInput[iSamples[l]][i-1])
213     {
214      iTrue++;
215     }
216     l++;    
217    }
218    for (n = 0;n<l;n++)// 
219    {
220     m = 0;
221     while((iDepart[m]!=-1)&&(m!=MAX))
222     {
223      if (iInput[iSamples[n]][iAttribute[k]] == iDepart[m])
224      {
225       break;
226      }
227      m++;
228     }
229     if (-1 == iDepart[m])
230     {
231      iDepart[m] = iInput[iSamples[n]][iAttribute[k]];
232     }
233    }
234    while ((iDepart[m] != -1)&&(m!=MAX))
235    {
236     for (n = 0;n<l;n++)
237     {
238      if (iInput[iSamples[n]][iAttribute[k]] == iDepart[m])
239      {
240       if (1 == iInput[iSamples[n]][i-1])
241       {
242        iTrue1++;
243       }
244       if (0 == iInput[iSamples[n]][i-1])
245       {
246        iFalse1++;
247       }
248       iRecord[m]++;
249      }
250     }
251     
252     dEntropy += entropy((double)iTrue1,(double)iFalse1,(double)l);
253     iTrue1 = 0;
254     iFalse1 = 0;
255     m++;
256    }
257    double dSplitinfo = splitinfo(iRecord,(double)l);
258    if (-1 == iTestAttribute)
259    {
260     iTestAttribute = k;
261     dGainratio = (info((double)iTrue,(double)iFalse)-dEntropy)/dSplitinfo;
262    }
263    else
264    {
265     test = (info((double)iTrue,(double)iFalse)-dEntropy)/dSplitinfo;
266     if (dGainratio < test)
267     {
268      iTestAttribute = k;
269      dGainratio = test;
270     }
271    }
272   }
273  }
274  return iTestAttribute;
275 }
276 double info(double dTrue,double dFalse)
277 {
278  double dInfo = 0.0;
279  dInfo = ((dTrue/(dTrue+dFalse))*(log(dTrue/(dTrue+dFalse))/log(2.0))+(dFalse/(dTrue+dFalse))*(log(dFalse/(dTrue+dFalse))/log(2.0)))*(-1);
280  return dInfo;
281 }
282 double entropy(double dTrue, double dFalse, double dAll)
283 {
284  double dEntropy = 0.0;
285  dEntropy = (dTrue + dFalse)*info(dTrue,dFalse)/dAll;
286  return dEntropy;
287 }
288 double splitinfo(int* list,double dAll)
289 {
290  int k = 0;
291  double dSplitinfo = 0.0;
292  while (0!=list[k])
293  {
294   dSplitinfo -= ((double)list[k]/(double)dAll)*(log((double)list[k]/(double)dAll));
295   k++;
296  }
297  return dSplitinfo;
298 }
299 int check_samples(int *iSamples)
300 {
301  int k = 0;
302  int b = 0;
303  while ((-1 != iSamples[k])&&(k < j-1))
304  {
305   if (iInput[k][i-1] != iInput[k+1][i-1])
306   {
307    b = 1;
308    break;
309   }
310   k++;
311  }
312  return b;
313 }
314 int check_ordinary(int *iSamples)
315 {
316  int k = 0;
317  int iTrue = 0;
318  int iFalse = 0;
319  while ((-1 != iSamples[k])&&(k < i))
320  {
321   if (0 == iInput[iSamples[k]][i-1])
322   {
323    iFalse++;
324   }
325   else
326   {
327    iTrue++;
328   }
329   k++;
330  }
331  if (iTrue >= iFalse)
332  {
333   return 1;
334  }
335  else
336  {
337   return 0;
338  }
339 }
340 int check_attribute_null(int *iAttribute)
341 {
342  int k = 0;
343  while (k < (i-1))
344  {
345   if (-1 != iAttribute[k])
346   {
347    return 0;
348   }
349   k++;
350  }
351  return 1;
352 }
353 void get_attributes(int *iSamples,int *iAttributeValue,int iAttribute)
354 {
355  int k = 0;
356  int l = 0;
357  while ((-1 != iSamples[k])&&(k < j))
358  {
359   l = 0;
360   while (-1 != iAttributeValue[l])
361   {
362    if (iInput[iSamples[k]][iAttribute] == iAttributeValue[l])
363    {
364     break;
365    }
366    l++;
367   }
368   if (-1 == iAttributeValue[l])
369   {
370    iAttributeValue[l] = iInput[iSamples[k]][iAttribute];
371   }
372   k++;
373  }
374 }

코드가 검증되지 않았습니다...