درخت تصمیم گیری

درخت تصمیم‌گیری (Decision Tree)

مقدمه ای بر درخت تصمیم گیری (Decision tree):

به طور کلی، آنالیز درخت تصمیم گیری یک ابزار مدلسازی پیش بینی کننده است که در بسیاری از زمینه ها قابل استفاده است. درخت های تصمیم گیری می توانند به واسطه یک راهکار الگوریتمی که می تواند مجموعه داده را بر اساس شرایط مختلف به طرق مختلف تفکیک کند، ساخته شوند. درخت های تصمیم گیری از قدرتمند ترین الگوریتم ها هستند که به عنوان زیر مجموعه ای از الگوریتم های تحت نظارت(supervised algorithms) در نظر گرفته می شوند.

از آنها می توان هم برای کارهای طبقه بندی(classification) و هم رگرسیون(regression) استفاده کرد. دو عنصر اصلی یک درخت عبارتند از، گره های تصمیم گیری (decision nodes) که داده در آنجا تقسیم می شود، و برگ ها (leaves) که خروجی را از آنها به دست می آوریم. مثالی از یک درخت دودویی که با ارائه اطلاعات متنوعی از جمله سن، عادات غذایی و عادات ورزشی، به پیش بینی این می پردازد که آیا یک فرد متناسب است یا خیر، در ادامه قرار دارد.

در درخت تصمیم گیری فوق، سوالات، گره های تصمیم گیری هستند و خروجی های نهایی، برگ ها هستند. دو نوع درخت تصمیم گیری وجود دارد که در ادامه مورد بررسی قرار می گیرند.

درخت تصمیم گیری طبقه بندی(Classification decision trees)

در این نوع درخت تصمیم گیری، متغیر تصمیم گیری، قطعی (categorical) است. درخت تصمیم گیری فوق مثالی از یک درخت تصمیم گیری طبقه بندی است.

درخت تصمیم گیری رگرسیون (Regression decision trees)

در این نوع درخت تصمیم گیری، متغیر تصمیم گیری پیوسته است.

پیاده سازی الگوریتم درخت تصمیم گیری:

Gini index:

این نام تابع هزینه (cost function) ای است که برای ارزیابی تفکیک دودویی مجموعه داده از آن استفاده می شود، و با متغیر های هدف قطعی "موفقیت" و "شکست" کار می کند.

هر چه مقدار Gini index بالاتر باشد، همگونی و یکدستی نیز بالاتر است. مقدار ایده آل Gini index ، 0 است و بدترین آن برای مساله ای با دو کلاس، 0.5 است. با کمک مراحل زیر می توان Gini index را برای یک تفکیک، محاسبه کرد.

در ابتدا، با استفاده از فرمول p^2+q^2 که حاصلجمع مربع احتمالات موفقیت و شکست است، Gini index را برای زیر گره ها محاسبه کنید. سپس، با استفاده از امتیاز Gini وزن دار(weighted Gini score) مربوط به هر گره از آن تفکیک، Gini index را محاسبه کنید.

الگوریتم درخت طبقه بندی و رگرسیون (CART) با استفاده از متد Gini ، تفکیک دودویی را تولید می کند.

تولید تفکیک(split creation) :

یک تفکیک اساسا در بردارنده یک خصیصه(attribute) در مجموعه داده و یک مقدار است. با کمک سه مرحله زیر می توان در مجموعه داده یک تفکیک ایجاد کرد.

مرحله 1:‌ ‌

محاسبه Gini Score

در بخش قبلی درباره این موضوع صحبت کردیم.

مرحله 2:‌ ‌

تفکیک یک مجموعه داده

می تواند در قالب تفکیک یک مجموعه داده به دو لیست از سطر هایی که دارای اندیس از یک خصیصه، و یک مقدار تفکیک(split value) از آن خصیصه است، تعریف شود. پس از اینکه دو گروه راست و چپ را از مجموعه داده گرفتیم، می توانیم با استفاده از Gini score که در مرحله اول محاسبه شد، مقدار تفکیک را محاسبه کنیم. مقدار تفکیک، در این باره تصمیم گیری خواهد کرد که خصیصه در کدام گروه باقی بماند.

مرحله 3:‌ ‌

ارزیابی تفکیک ها

مرحله بعدی پس از پیدا کردن Gini score و تفکیک مجموعه داده، ارزیابی تمام تفکیک ها است. با این هدف، ابتدا باید همه مقادیر مربوط به هر خصیصه را به عنوان یک کاندید تفکیک بررسی کنیم. سپس، باید با ارزیابی هزینه تفکیک، بهترین تفکیک ممکن را پیدا کنیم. بهترین تفکیک به عنوان یک گره در درخت تصمیم گیری مورد استفاده قرار می گیرد.

ساخت یک درخت: ‌

همانطور که می دانیم یک درخت دارای یک گره ریشه و گره های پایانی است. پس از ساخت گره ریشه، با پیروی از دو بخش زیر می توانیم درخت را بسازیم.

بخش 1:‌ ‌

ساخت گره پایانی:

در زمان ساخت گره های پایانی یک درخت تصمیم گیری، تصمیم گیری درباره زمان اتمام رشد درخت یا ساخت گره های پایانی بیشتر، یکی از مهمترین نکات است. با استفاده از دو معیار به نام های حداکثر عمق درخت و حداقل رکوردهای(records) گره که در ادامه معرفی می شوند، می توان این کار را انجام داد.

حداکثر عمق درخت (Maximum Tree Depth) :

همانطور که از نام آن بر می آید، این حداکثر تعداد گره های یک درخت است که پس از گره ریشه قرار می گیرد. زمانی که یک درخت به حداکثر عمق خود برسد، باید افزودن گره های پایانی را متوقف کنیم. برای مثال ، زمانی که یک درخت حداکثر تعداد گره های پایانی را داشته باشد.

حداقل رکورد های گره (Minimum Node Records):

به صورت حداقل تعداد الگوهای یادگیری تعریف می شود که گره داده شده مسئول آن است. زمانی که درخت به این حداقل رکورد های گره یا کمتر از این حداقل برسد، افزودن گره های پایانی را باید متوقف کنیم .

از گره پایانی برای ساختن پیش بینی نهایی استفاده می شود.

بخش 2:‌ ‌

تفکیک بازگشتی (Recursive splitting):

حال، پس از فهمیدن زمان ساخت گره های پایانی، می توانیم شروع به ساختن درخت خود کنیم. تفکیک بازگشتی متدی برای ساخت درخت است. در این متد، زمانی که یک گره ساخته می شود، می توانیم گره های فرزند (گره های افزوده شده به یک گره موجود) را در هر گروه از داده، که به واسطه تفکیک مجموعه داده تولید شده است، با فراخوانی دوباره و دوباره همین تابع، به صورت بازگشتی ایجاد کنیم.

پیش بینی (prediction):

پس از ساخت یک درخت تصمیم گیری، باید یک پیش بینی درباره آن بسازیم. اساسا، پیش بینی کردن شامل هدایت درخت تصمیم گیری با ارائه ردیف های مشخص از داده است.

مطابق فوق، می توان با کمک تابع بازگشتی، یک پیش بینی ساخت. این روال پیش بینی مشابه، مجددا برای گره های فرزند چپ و راست فراخوانی می شود.

فرضیات: ‌

موارد زیر برخی از فرضیات موجود در زمان ساخت درخت تصمیم گیری است.

• در زمان آماده سازی درختان تصمیم گیری، مجموعه یادگیری به عنوان گره ریشه خواهد بود.
• طبقه بندی کننده های درخت تصمیم گیری ترجیح می دهند که مقادیر خصیصه ها به صورت قطعی باشد. در صورتی که قصد استفاده از مقادیر پیوسته را داشته باشیم، باید قبل از ساخت مدل آنها را به صورت گسسته در بیاوریم.
• بر اساس مقادیر خصیصه ها، رکورد ها به صورت بازگشتی توزیع می شوند.
• برای مستقر ساختن خصیصه ها در مکان هر گره – مانند گره ریشه یا گره های میانی- از روش آماری استفاده می شود.

پیاده سازی در پایتون:

مثال: ‌

در مثال زیر، طبقه بندی کننده درخت تصمیم گیری را روی Pima Indian Diabetes پیاده سازی می کنیم. ابتدا، با وارد کردن بسته های(packages) ضروری پایتون شروع می کنیم.

                        import pandas as pd
                        from sklearn.tree import DecisionTreeClassifier
                        from sklearn.model_selection import train_test_split

                                   
                    

سپس، مطابق زیر، مجموعه داده iris را از لینک زیر دانلود کنید.

                        
                     col_names = ['pregnant', 'glucose', 'bp', 'skin', 'insulin', 'bmi', 'pedigree', 'age', 'label']
                     pima = pd.read_csv(r"C:\pima-indians-diabetes.csv", header = None, names = col_names)
                     pima.head()

                                   
                    

حال، مطابق زیر، مجموعه داده را به دو دسته متغیر های ویژگی و هدف تفکیک کنید.

                        
                        feature_cols = ['pregnant', 'insulin', 'bmi', 'age','glucose','bp','pedigree']
                        X = pima[feature_cols] # Features
                        y = pima.label # Target variable

   
                                      
                       

سپس، داده را به دو دسته یادگیری و تست تقسیم می کنیم. کد زیر، داده را به گونه ای تقسیم می کند که 70 درصد داده آموزشی و 30 درصد داده تست داشته باشیم.

                        
                        X_train, X_test, y_train, y_test = train_test_split(X, y, test_size = 0.3, random_state = 1)

   
                                      
                       

سپس، به صورت زیر ، با کمک کلاس DecisionTreeClassifier از sklearn ، مدل را آموزش دهید.

                        
                        clf = DecisionTreeClassifier()
                        clf = clf.fit(X_train,y_train)
                        
            
                       

در انتها، باید پیش بینی کنیم که این کار را با کمک اسکریپت زیر انجام می دهیم.

                        
                        y_pred = clf.predict(X_test)
                        
            
                       

سپس، می توانیم گزارش امتیاز دقت(accuracy score) ، ماتریس سردرگمی(confusion matrix) و طبقه بندی(classification) را به صورت زیر داشته باشیم.

                        
                        from sklearn.metrics import classification_report, confusion_matrix, accuracy_score
                        result = confusion_matrix(y_test, y_pred)
                        print("Confusion Matrix:")
                        print(result)
                        result1 = classification_report(y_test, y_pred)
                        print("Classification Report:",)
                        print (result1)
                        result2 = accuracy_score(y_test,y_pred)
                        print("Accuracy:",result2)

                        
            
                       

خروجی:

                        
                        Confusion Matrix:
                        [[116 30]
                        [ 46 39]]
                        Classification Report:
                        precision     recall      f1-score     support
                        0          0.72       0.79          0.75         146
                        1          0.57       0.46          0.51          85
                        micro avg          0.67       0.67          0.67         231
                        macro avg          0.64       0.63          0.63         231
                        weighted avg       0.66       0.67          0.66         231

                        Accuracy: 0.670995670995671

                       

مصور سازی درخت تصمیم گیری:

با استفاده از کد زیر می توان درخت تصمیم گیری را تجسم کرد.

                        
                        from sklearn.tree import export_graphviz
                        from sklearn.externals.six import StringIO
                        from IPython.display import Image
                        import pydotplus
                        dot_data = StringIO()
                        export_graphviz(clf, out_file=dot_data, filled=True, rounded=True,
                           special_characters=True,feature_names = feature_cols,class_names=['0','1'])
                        
                        graph = pydotplus.graph_from_dot_data(dot_data.getvalue())
                        graph.write_png('Pima_diabetes_Tree.png')
                        Image(graph.create_png())