青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

coreBugZJ

此 blog 已棄。

ID3 算法實現決策樹

  1/*
  2
  3ID3 算法實現決策樹
  4
  5
  6----問題描述：
  7
  8Suppose we want ID3 to decide whether the weather is amenable to playing baseball. Over the course of 2 weeks, data is collected to help ID3 build a decision tree (see table 1).
  9
 10The target classification is "should we play baseball?" which can be yes or no.
 11
 12The weather attributes are outlook, temperature, humidity, and wind speed. They can have the following values:
 13
 14•    outlook = { sunny, overcast, rain }
 15•    temperature = {hot, mild, cool }
 16•    humidity = { high, normal }
 17•    wind = {weak, strong }
 18
 19Examples of set S are:
 20
 21Table. 1
 22
 23Day    Outlook    Temperature    Humidity    Wind    Play ball
 24
 25D1    Sunny        Hot    High        Weak    No
 26D2    Sunny        Hot    High        Strong    No
 27D3    Overcast    Hot    High        Weak    Yes
 28D4    Rain        Mild    High        Weak    Yes
 29D5    Rain        Cool    Normal        Weak    Yes
 30D6    Rain        Cool    Normal        Strong    No
 31D7    Overcast    Cool    Normal        Strong    Yes
 32D8    Sunny        Mild    High        Weak    No
 33D9    Sunny        Cool    Normal        Weak    Yes
 34D10    Rain        Mild    Normal        Weak    Yes
 35D11    Sunny        Mild    Normal        Strong    Yes
 36D12    Overcast    Mild    High        Strong    Yes
 37D13    Overcast    Hot    Normal        Weak    Yes
 38D14    Rain        Mild    High        Strong    No
 39
 40
 41----輸入：
 42
 43若干行，每行 5 個字符串，表示
 44
 45Outlook    Temperature    Humidity    Wind    Play ball
 46
 47如上表。
 48
 49
 50----輸出：
 51
 52決策樹。
 53
 54
 55----分析：
 56
 57經典 ID3 算法。
 58
 59代碼假設訓練集相容。
 60
 61非常經典的算法，第一次實現，如此倉促以至于得到如此惡心的代碼！
 62我所寫過的最惡心的代碼！真想刪了重新寫。
 63
 64*/
 65
 66
 67#include <iostream>
 68#include <cstdio>
 69#include <string>
 70#include <map>
 71#include <iomanip>
 72#include <cmath>
 73
 74using namespace std;
 75
 76const int EXAMPLE_NUM  = 1009;
 77const int PROP_NUM     = 4;
 78
 79const int MAX_PROP[ PROP_NUM ] = { 3, 3, 2, 2 };
 80
 81struct  Example
 82{
 83        int  prop[ PROP_NUM ];
 84        bool ignp[ PROP_NUM ];
 85        bool play;
 86
 87        int  node;
 88        Example *link;
 89};
 90
 91struct  Node;
 92
 93struct  Link
 94{
 95        int   prop;
 96        Node  *node;
 97        Link  *link;
 98};
 99
100struct  Node
101{
102        int   pid;
103        Link  *link;
104        bool  play;
105};
106
107map< string, int > Str2Val;
108map< int, string > Val2Str[ PROP_NUM ];
109string  Pro2Str[ PROP_NUM ] = { "Outlook", "Temperature", "Humidity", "Wind" };
110
111
112double  entropy( Example *s, int nd, int &ts ) {
113        int ct = 0, cf = 0, c = 0;
114        double es = 0;
115        while ( NULL != s ) {
116                if ( nd == s->node ) {
117                        ++c;
118                        if ( s->play ) {
119                                ++ct;
120                        }
121                        else {
122                                ++cf;
123                        }
124                }
125                s = s->link;
126        }
127        ts = c;
128        if ( 0 == c ) {
129                return 0;
130        }
131        if ( 0 != ct ) {
132                es += -(((double)(ct))/c) * log(((double)(ct))/c);
133        }
134        if ( 0 != cf ) {
135                es += -(((double)(cf))/c) * log(((double)(cf))/c);
136        }
137        return es;
138}
139        // pid 合法
140double gain( Example *s, int nd, int pid ) {
141        Example *e;
142        double  es, ev;
143        int     ts, tv, i;
144
145        es = entropy( s, nd, ts );
146
147        if ( 0 == ts ) {
148                return 0;
149        }
150
151        for ( i = 0; i < MAX_PROP[ pid ]; ++i ) {
152                for ( e = s; NULL != e; e = e->link ) {
153                        if ( (nd == e->node) && (i == e->prop[pid]) && (! e->ignp[pid]) ) {
154                                e->node = nd + 1;
155                        }
156                }
157
158                ev = entropy( s, nd+1, tv );
159
160                for ( e = s; NULL != e; e = e->link ) {
161                        if ( nd+1 == e->node ) {
162                                e->node = nd;
163                        }
164                }
165
166                es -= ev * ( ((double)(tv)) / ts );
167        }
168
169        return es;
170}
171
172int gainMaxId( Example *s, int nd ) {
173        double m = -1e100, tm;
174        int    k = -1, i;
175        bool   ign[ PROP_NUM ] = { 0 };
176
177        for ( Example *e = s; NULL != e; e = e->link ) {
178                if ( e->node == nd ) {
179                        for ( i = 0; i < PROP_NUM; ++i ) {
180                                if ( e->ignp[ i ] ) {
181                                        ign[ i ] = true;
182                                }
183                        }
184                }
185        }
186
187        for ( i = 0; i < PROP_NUM; ++i ) {
188                if ( ign[ i ] ) {
189                        continue;
190                }
191
192                tm = gain( s, nd, i );
193                if ( tm > m ) {
194                        m = tm;
195                        k = i;
196                }
197        }
198
199        return k;
200}
201        // s 非空
202bool sameDecd( Example *s, int nd, bool &decd ) {
203        bool set = false;
204        bool play;
205        while ( NULL != s ) {
206                if ( s->node == nd ) {
207                        play = s->play;
208                        set  = true;
209                        break;
210                }
211                s = s->link;
212        }
213        if ( ! set ) {
214                return false; ////////
215        }
216        while ( NULL != s ) {
217                if ( (s->node == nd) && (s->play != play) ) {
218                        return false;
219                }
220                s = s->link;
221        }
222        decd = play;
223        return true;
224}
225        // 用完所有屬性
226bool isLeaf( Example *s, int nd, bool &decd ) {
227        int i;
228        while ( NULL != s ) {
229                if ( s->node == nd ) {
230                        for ( i = 0; (i < PROP_NUM)&&(s->ignp[i]); ++i ) {
231                        }
232                        if ( i < PROP_NUM ) {
233                                return false;
234                        }
235                        decd = s->play;
236                }
237                s = s->link;
238        }
239        return true;
240}
241
242int node;
243Node* createTreeSub( Example *example ) {
244        Node *res = new Node;
245        res->link = NULL;
246        res->pid = -1;
247        if ( sameDecd( example, node, res->play ) ) {
248                return res;
249        }
250        if ( isLeaf( example, node, res->play ) ) {
251                return res;
252        }
253
254        res->pid = gainMaxId( example, node );
255
256        int i, c, nd = node;
257        Example *e;
258        for ( i = 0; i < MAX_PROP[ res->pid ]; ++i ) {
259                e = example;
260                c = 0;
261                ++node;
262                while ( NULL != e ) {
263                        if ( (nd == e->node) && (i == e->prop[ res->pid ]) ) {
264                                e->ignp[ res->pid ] = true;
265                                e->node = node;
266                                ++c;
267                        }
268                        e = e->link;
269                }
270                if ( 0 < c ) {
271                        Link *link = new Link;
272                        link->node = createTreeSub( example );
273                        link->prop = i;
274                        link->link = res->link;
275                        res->link  = link;
276                }
277        }
278
279        return res;
280}
281
282Node* createTree( Example* example ) {
283        Example *ptr;
284        int i;
285
286        if ( NULL == example ) {
287                return NULL;
288        }
289
290        for ( ptr = example; NULL != ptr; ptr = ptr->link ) {
291                for ( i = 0; i < PROP_NUM; ++i ) {
292                        ptr->ignp[ i ] = false;
293                }
294                ptr->node = 0;
295        }
296        node = 0;
297        return createTreeSub( example );
298}
299
300void outputTreeSub( Node *tree, int dep );
301
302void outputLink( Link *link, int dep, int pid ) {
303        if ( (NULL == link) || (0 > dep) ) {
304                return;
305        }
306
307        for ( int i = 0; i < dep; ++i ) {
308                cout << setw(16) << " ";
309        }
310        cout << left << setw(16) << Val2Str[pid][link->prop];
311        outputTreeSub( link->node, dep+1 );
312
313        outputLink( link->link, dep, pid );
314}
315
316void outputTreeSub( Node *tree, int dep ) {
317        if ( (NULL == tree) || (0 > dep) ) {
318                return;
319        }
320
321        if ( 0 > tree->pid ) {
322                cout << (tree->play ? "Yes *" : "No  *") << endl;
323                return;
324        }
325
326        cout << left << setw(16) << Pro2Str[tree->pid] << endl;
327        outputLink( tree->link, dep+1, tree->pid );
328}
329
330void outputTree( Node *tree ) {
331        outputTreeSub( tree, 0 );
332}
333
334void destroyTree( Node **pTree ) {
335        if ( (NULL == pTree) || (NULL == *pTree) ) {
336                return;
337        }
338
339        Link *link;
340        for ( link = (*pTree)->link; NULL != link; link = link->link ) {
341                destroyTree( &(link->node) );
342        }
343
344        delete *pTree;
345        *pTree = NULL;
346}
347
348void destroyExample( Example **pExample ) {
349        if ( (NULL == pExample) || (NULL == *pExample) ) {
350                return;
351        }
352        Example  *head = *pExample, *p;
353        while ( NULL != head ) {
354                p = head;
355                head = head->link;
356                delete p;
357        }
358        *pExample = NULL;
359}
360
361void init() {
362        Val2Str[ 0 ][ 0 ] = "Sunny";
363        Val2Str[ 0 ][ 1 ] = "Overcast";
364        Val2Str[ 0 ][ 2 ] = "Rain";
365        Str2Val[ "Sunny"    ] = 0;
366        Str2Val[ "Overcast" ] = 1;
367        Str2Val[ "Rain"     ] = 2;
368        
369        Val2Str[ 1 ][ 0 ] = "Hot";
370        Val2Str[ 1 ][ 1 ] = "Mild";
371        Val2Str[ 1 ][ 2 ] = "Cool";
372        Str2Val[ "Hot"  ] = 0;
373        Str2Val[ "Mild" ] = 1;
374        Str2Val[ "Cool" ] = 2;
375
376        Val2Str[ 2 ][ 0 ] = "High";
377        Val2Str[ 2 ][ 1 ] = "Normal";
378        Str2Val[ "High"   ] = 0;
379        Str2Val[ "Normal" ] = 1;
380
381        Val2Str[ 3 ][ 0 ] = "Weak";
382        Val2Str[ 3 ][ 1 ] = "Strong";
383        Str2Val[ "Weak"   ] = 0;
384        Str2Val[ "Strong" ] = 1;
385}
386
387Example*  inputExample() {
388        Example   *preHead = new Example;
389        Example   *ptr;
390        string    Outlook, Temperature, Humidity, Wind, Play;
391
392        preHead->link = NULL;
393        ptr = preHead;
394
395        while ( cin >> Outlook >> Temperature >> Humidity >> Wind >> Play ) {
396                ptr->link = new Example;
397                ptr = ptr->link;
398                ptr->link = NULL;
399
400                if (    (Str2Val.find( Outlook     ) == Str2Val.end()) || 
401                        (Str2Val.find( Temperature ) == Str2Val.end()) || 
402                        (Str2Val.find( Humidity    ) == Str2Val.end()) || 
403                        (Str2Val.find( Wind        ) == Str2Val.end()) 
404                        ) {
405                                destroyExample( &preHead );
406                                return NULL;
407                }
408                ptr->prop[ 0 ] = Str2Val[ Outlook     ];
409                ptr->prop[ 1 ] = Str2Val[ Temperature ];
410                ptr->prop[ 2 ] = Str2Val[ Humidity    ];
411                ptr->prop[ 3 ] = Str2Val[ Wind        ];
412
413                if ( "Yes" == Play ) {
414                        ptr->play = true;
415                }
416                else if ( "No" == Play ) {
417                        ptr->play = false;
418                }
419                else {
420                        destroyExample( &preHead );
421                        return NULL;
422                }
423        }
424
425        ptr = preHead->link;
426        delete preHead;
427        return ptr;
428}
429
430int main() {
431        init();
432
433        Example  *example = inputExample();
434        if ( NULL == example ) {
435                cout << "輸入不合法" << endl;
436                return 0;
437        }
438
439        Node  *tree = createTree( example );
440
441        outputTree( tree );
442
443        destroyTree( &tree );
444        destroyExample( &example );
445        return 0;
446}
447
448
449/*
450
451輸入：
452    Sunny        Hot    High        Weak    No
453    Sunny        Hot    High        Strong    No
454    Overcast    Hot    High        Weak    Yes
455    Rain        Mild    High        Weak    Yes
456    Rain        Cool    Normal        Weak    Yes
457    Rain        Cool    Normal        Strong    No
458    Overcast    Cool    Normal        Strong    Yes
459    Sunny        Mild    High        Weak    No
460    Sunny        Cool    Normal        Weak    Yes
461    Rain        Mild    Normal        Weak    Yes
462    Sunny        Mild    Normal        Strong    Yes
463    Overcast    Mild    High        Strong    Yes
464    Overcast    Hot    Normal        Weak    Yes
465    Rain        Mild    High        Strong    No
466
467輸出：
468
469Outlook
470                Rain            Wind
471                                                Strong          No  *
472                                                Weak            Yes *
473                Overcast        Yes *
474                Sunny           Humidity
475                                                Normal          Yes *
476                                                High            No  *
477
478*/
479

posted on 2012-06-05 15:02 coreBugZJ 閱讀(3611) 評論(1)  編輯 收藏 引用 所屬分類: Algorithm 、課內作業 、Intelligence

Feedback

# re: ID3 算法實現決策樹 2014-04-23 09:37 CS_J

ignp數組是做什么的？  回復  更多評論   


青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

    • <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>

    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>

            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            
亚洲视频一二区|
亚洲经典自拍|
国产精品久久久久久久久搜平片
|
欧美成人免费播放|
欧美在线视频二区|
亚洲一级黄色片|
欧美h视频在线|
欧美在线3区|
99国产一区|
最新国产精品拍自在线播放|
噜噜噜躁狠狠躁狠狠精品视频|
国产亚洲欧美一区二区|
久久久亚洲精品一区二区三区
|
亚洲一区区二区|
亚洲人永久免费|
亚洲黄色一区|
亚洲级视频在线观看免费1级|
国产伦精品一区二区三区在线观看|
欧美日韩一区视频|
欧美色偷偷大香|
欧美日韩亚洲视频|
欧美成年人在线观看|
久久久久成人精品免费播放动漫|
久久精品99国产精品|
久久精品一区二区三区不卡|
久久久精品tv|
免费的成人av|
欧美精品国产精品日韩精品|
欧美精品精品一区|
欧美激情视频一区二区三区不卡|
欧美大片一区二区三区|
欧美日韩国产精品一区二区亚洲
|
亚洲缚视频在线观看|
亚洲国产影院|
艳妇臀荡乳欲伦亚洲一区|
亚洲视频久久|
欧美一区深夜视频|
久久久久久综合网天天|
久久资源在线|
欧美日韩国产精品专区|
欧美精品福利|
国产精品私拍pans大尺度在线
|
一区二区自拍|
在线免费日韩片|
欧美日韩中文字幕日韩欧美|
国产精品成人观看视频国产奇米|
国产欧美精品一区aⅴ影院|
国产中文一区|
亚洲人成网站999久久久综合|
一本色道久久综合亚洲精品按摩|
99精品国产高清一区二区|
亚洲免费在线观看|
久久理论片午夜琪琪电影网|
乱码第一页成人|
99精品视频免费观看视频|
久久久人成影片一区二区三区观看|
欧美视频不卡中文|
亚洲国产精品久久久久秋霞蜜臀|
午夜欧美精品久久久久久久|
亚洲电影免费观看高清完整版|
亚洲男女自偷自拍|
欧美激情一区二区三区在线|
好吊色欧美一区二区三区视频|
亚洲午夜女主播在线直播|
欧美顶级少妇做爰|
欧美专区中文字幕|
国产精品高清网站|
99re6热在线精品视频播放速度
|
国产精品igao视频网网址不卡日韩|
尤物99国产成人精品视频|
亚洲欧美一区二区三区久久|
91久久亚洲|
久久综合色影院|
国产一区视频在线看|
亚洲欧美日韩成人高清在线一区|
亚洲人成啪啪网站|
老鸭窝91久久精品色噜噜导演|
国产一区二区三区奇米久涩
|
国产目拍亚洲精品99久久精品|
日韩亚洲欧美在线观看|
欧美xxxx在线观看|
午夜日韩福利|
国产精品美腿一区在线看
|
欧美11—12娇小xxxx|
狠狠色综合一区二区|
久久精品人人|
午夜精品一区二区三区电影天堂|
国产精品高精视频免费|
亚洲一区999|
日韩视频在线一区|
欧美精品一区二区蜜臀亚洲|
亚洲欧洲在线一区|
欧美国产精品中文字幕|
玖玖综合伊人|
最新成人在线|
亚洲国产cao|
欧美精品免费播放|
9国产精品视频|
亚洲精品无人区|
欧美日韩不卡合集视频|
一区二区精品在线|
99在线热播精品免费99热|
欧美三级资源在线|
亚洲综合国产精品|
一区二区三区高清不卡|
国产精品国产精品国产专区不蜜|
亚洲欧美韩国|
午夜精品久久久久久久久|
国产日本欧美一区二区三区|
久久精品国内一区二区三区|
欧美专区日韩视频|
亚洲成人影音|
亚洲国产视频一区二区|
欧美日韩国产欧|
午夜久久tv|
久久国产精品黑丝|
亚洲第一网站免费视频|
亚洲国产精品美女|
欧美揉bbbbb揉bbbbb|
亚洲你懂的在线视频|
午夜免费久久久久|
尤物99国产成人精品视频|
亚洲成人中文|
久久精品一区中文字幕|
亚洲国产专区校园欧美|
亚洲精品国产精品久久清纯直播|
欧美日本精品|
先锋亚洲精品|
久久久噜噜噜|
99re热精品|
亚洲欧美日韩国产|
一区二区在线观看视频在线观看
|
免播放器亚洲|
亚洲天堂网在线观看|
亚洲欧美中文字幕|
亚洲国产高潮在线观看|
9国产精品视频|
国产一区二区三区在线观看免费
|
亚洲人成网站在线观看播放|
国产精品成人aaaaa网站|
久久久成人精品|
欧美激情日韩|
欧美一区二区在线视频|
麻豆成人综合网|
亚洲欧美视频在线观看|
玖玖精品视频|
午夜精品www|
欧美粗暴jizz性欧美20|
午夜在线不卡|
欧美成人免费观看|
欧美一级精品大片|
欧美第一黄网免费网站|
羞羞色国产精品|
欧美福利视频在线|
欧美在线国产精品|
欧美精品观看|
久久午夜羞羞影院免费观看|
欧美日韩欧美一区二区|
免费成人性网站|
国产精品视频男人的天堂|
亚洲丶国产丶欧美一区二区三区|
亚洲一区二区三区四区视频|
亚洲伊人伊色伊影伊综合网|
亚洲黄色天堂|
欧美一级视频|
亚洲一品av免费观看|
狂野欧美一区|
久久精品国产99|
国产精品va在线播放|
亚洲第一页中文字幕|
国产一二精品视频|
一区二区三区欧美|
亚洲精品少妇网址|
久久久久久久91|
亚欧成人在线|
欧美性大战xxxxx久久久|
欧美国产日本|
一区在线视频|
欧美一区二区三区日韩视频|
亚洲一区二区三区四区视频|
欧美福利在线|
欧美成人精品高清在线播放|
国产一区二区三区久久悠悠色av
|
午夜精品福利一区二区三区av|
欧美精品久久99久久在免费线|
欧美成人a∨高清免费观看|
国产欧美va欧美不卡在线|
一本色道久久综合亚洲精品按摩|
亚洲精品无人区|
欧美 日韩 国产在线|
你懂的国产精品永久在线|
国产综合久久久久久鬼色|
亚洲欧美一区二区三区极速播放|
亚洲欧美国产精品va在线观看|
欧美母乳在线|
亚洲国产乱码最新视频|
1769国产精品|
另类人畜视频在线|
欧美高清你懂得|
亚洲黄色在线视频|