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

coreBugZJ

此 blog 已棄。

ID3 算法實(shí)現(xiàn)決策樹(shù)

  1/*
  2
  3ID3 算法實(shí)現(xiàn)決策樹(shù)
  4
  5
  6----問(wèn)題描述：
  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 個(gè)字符串，表示
 44
 45Outlook    Temperature    Humidity    Wind    Play ball
 46
 47如上表。
 48
 49
 50----輸出：
 51
 52決策樹(shù)。
 53
 54
 55----分析：
 56
 57經(jīng)典 ID3 算法。
 58
 59代碼假設(shè)訓(xùn)練集相容。
 60
 61非常經(jīng)典的算法，第一次實(shí)現(xiàn)，如此倉(cāng)促以至于得到如此惡心的代碼！
 62我所寫過(guò)的最惡心的代碼！真想刪了重新寫。
 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 閱讀(3608) 評(píng)論(1)  編輯 收藏 引用 所屬分類: Algorithm 、課內(nèi)作業(yè) 、Intelligence

Feedback

# re: ID3 算法實(shí)現(xiàn)決策樹(shù) 2014-04-23 09:37 CS_J

ignp數(shù)組是做什么的？  回復(fù)  更多評(píng)論   


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

    • <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>
            
午夜日韩av|
黄色影院成人|
欧美在线精品免播放器视频|
麻豆精品视频|
夜夜嗨av一区二区三区四区|
99精品久久久|
亚洲欧美亚洲|
久久米奇亚洲|
最新国产成人在线观看|
日韩一级不卡|
香蕉久久一区二区不卡无毒影院|
久久久国产亚洲精品|
免费成人美女女|
欧美网站在线观看|
国产精品欧美风情|
美女黄网久久|
欧美午夜片在线观看|
国产亚洲第一区|
亚洲精品国产视频|
欧美日韩成人在线|
亚洲欧美视频一区|
欧美国产日产韩国视频|
国产精品综合不卡av|
亚洲激情欧美激情|
欧美一区午夜精品|
亚洲国产成人高清精品|
亚洲男女自偷自拍|
欧美aⅴ99久久黑人专区|
国产精品99免费看|
亚洲国产午夜|
久久久91精品国产一区二区精品|
亚洲级视频在线观看免费1级|
亚洲午夜视频在线|
欧美高清视频www夜色资源网|
国产精品揄拍一区二区|
亚洲美女黄网|
免费视频一区二区三区在线观看|
一区二区三区 在线观看视频|
免费不卡在线观看av|
国语自产精品视频在线看抢先版结局
|
女同一区二区|
国产欧亚日韩视频|
亚洲视频碰碰|
亚洲欧洲精品成人久久奇米网|
国产精品视频男人的天堂|
一区二区三区高清在线|
欧美国产国产综合|
尹人成人综合网|
久久激情五月丁香伊人|
一本色道久久加勒比88综合|
欧美大片国产精品|
亚洲黑丝一区二区|
老司机午夜精品视频|
亚洲影院免费观看|
国产精品乱码人人做人人爱|
宅男噜噜噜66一区二区66|
亚洲福利精品|
欧美88av|
国产精品99久久久久久白浆小说|
亚洲国产精品一区二区第四页av|
久久全球大尺度高清视频|
韩国一区电影|
欧美成年人网|
欧美成va人片在线观看|
亚洲国产一区视频|
亚洲电影专区|
欧美日韩国产在线看|
一区二区激情视频|
亚洲一区二区欧美|
国产日韩精品一区|
国产亚洲欧美一区|
久久久久久午夜|
久久亚洲影院|
99在线精品免费视频九九视|
亚洲精品国产精品乱码不99按摩|
欧美激情在线播放|
亚洲欧美精品伊人久久|
亚洲欧美日韩国产综合在线|
伊人久久噜噜噜躁狠狠躁|
欧美成人激情视频免费观看|
免费亚洲电影在线观看|
一区二区三区日韩欧美|
亚洲影院在线观看|
一区精品在线|
亚洲激情自拍|
国产欧美日韩一区|
亚洲二区在线视频|
国产精品亚洲综合一区在线观看|
欧美在线播放视频|
美女黄色成人网|
午夜日韩在线|
欧美插天视频在线播放|
一片黄亚洲嫩模|
欧美中文字幕在线观看|
国产精品国产三级国产a|
亚洲免费观看|
亚洲男人第一av网站|
亚洲国内精品|
亚洲在线观看免费|
亚洲精品国精品久久99热一|
亚洲在线一区二区|
亚洲精品国偷自产在线99热|
一区二区三区欧美视频|
亚洲福利视频免费观看|
亚洲欧美日韩区|
av不卡在线|
久久av老司机精品网站导航|
亚洲婷婷综合色高清在线|
老鸭窝亚洲一区二区三区|
欧美一级黄色网|
欧美久久久久|
欧美a级理论片|
国产欧美va欧美va香蕉在|
亚洲精选国产|
91久久国产综合久久|
欧美自拍偷拍午夜视频|
亚洲专区免费|
欧美日韩国产bt|
亚洲国产精品一区二区第四页av|
国产精品综合久久久|
亚洲精品免费观看|
亚洲黄色成人久久久|
久久久久久亚洲精品中文字幕|
亚洲色图制服丝袜|
欧美日韩午夜在线|
亚洲蜜桃精久久久久久久|
亚洲激情自拍|
欧美~级网站不卡|
蜜桃久久av一区|
国产一区香蕉久久|
欧美一进一出视频|
久久精品亚洲一区二区三区浴池|
国产精品久久午夜|
亚洲视频网在线直播|
亚洲视频免费看|
国产精品自在线|
99精品视频免费观看视频|
一区二区在线视频播放|
欧美一区2区三区4区公司二百|
亚洲制服少妇|
国产精品久久久久久久久久ktv|
亚洲三级视频|
一区二区三区成人精品|
欧美日韩成人一区二区三区|
欧美成ee人免费视频|
欧美激情亚洲自拍|
亚洲成色999久久网站|
最新国产乱人伦偷精品免费网站|
鲁大师影院一区二区三区|
欧美第十八页|
夜夜嗨av一区二区三区|
欧美午夜三级|
亚洲欧美三级伦理|
久久精品中文字幕一区|
韩日精品在线|
免费欧美视频|
夜夜嗨av色综合久久久综合网|
亚洲一级黄色av|
国产午夜久久久久|
欧美国产精品劲爆|
亚洲天堂第二页|
快she精品国产999|
亚洲精品一区二区在线观看|
欧美三日本三级少妇三2023|
亚洲在线黄色|
欧美激情a∨在线视频播放|
日韩亚洲一区二区|
国产精品午夜在线|
久久亚洲综合色一区二区三区|
亚洲国产综合在线|
午夜亚洲视频|
影院欧美亚洲|
国产精品h在线观看|
久久九九免费|
一本久道久久综合狠狠爱|
欧美一区日本一区韩国一区|
亚洲国产欧洲综合997久久|
欧美日韩一二三四五区|
欧美一区中文字幕|
亚洲免费观看|
欧美成va人片在线观看|
亚洲欧美激情一区|
91久久精品国产91性色|
国产精品一区二区视频|
欧美成在线观看|
欧美一区视频|
亚洲神马久久|
亚洲激情视频网|
久久久久久高潮国产精品视|
亚洲精品在线视频|
黄色亚洲大片免费在线观看|
欧美精品一区二区三|
欧美中文字幕|
午夜精品短视频|
亚洲视频一区二区免费在线观看|
久久久久久久久久久久久女国产乱
|
久久久五月天|
欧美成人小视频|
国产自产2019最新不卡|
欧美视频日韩视频在线观看|