تحليل داده هاي آماري تصادفات رانندگی به وسيله درختهاي تصميم
علیرضا پاک گوهر
عضو هیئت علمی دانشگاه آزاد اسلامی واحد آیت الله آمل[1]
سرهنگ 2 عباس صادقي كيا
عضو هيئت علمي دانشگاه علوم انتظامي ناجا و معاون پژوهش دانشكده پليس راهور[2]
چکیده:
امروزه محققان با انفجار اطلاعات مواجه شده اند. براي نمونه، چند منشأ اين اطلاعات سرمايه گذاريهاي بسيار زيادي است كه در توليد بانک هاي اطلاعاتي، انتقال مفاهيم(داده ها و اطلاعات) از طريق شبكه، و كامپيوتري شدن فرايندهاي اجرايي انجام ميگيرد. يکي از مجموعه دادههايي Data bases) ( که حاوي اطلاعات ذيقيمتي درباره فاکتورهاي مؤثر و احتمالاً داراي همبستگي هاي خطي و غير خطي (از ديدگاه تحليل رگرسيوني) براي موضوع تصادفات مي باشد نرم افزار سيستم جامع تصادفات جاده اي موسوم به نرم افزار کام113 و کام114 مي باشد.
نويسنده مقاله با توجه به اهميت دانش پنهان در انبوه اطلاعات موجود در مجموعه داده هاي فوق الذکر و لزوم به کارگيري مديريت دانش در اين خصوص بالاخص به کار گيري الگوريتم هاي تحليلي در حوزه داده کاوي هم اکنون طي موضوع تحقيقاتي با عنوان بررسي علل و عوامل موثر بر تصادفات بر اساس مدلهاي رگرسيوني LR و CART به تحليل رگرسيوني درختي و لجستيک متغيرهاي مستقل و وابسته پرداخته است.
ما بر اين عقيدهايم كه اين روشها اساساً متكي به الگوريتمها و ساختارهاي داده براي آمار محاسباتي با كارآيي بالا خواهند بود. همچنين مي توان انتظار داشت از اين بلوكهاي سازنده مدولي براي تشكيل ” سيستمهاي اكتشاف“ بزرگتر بكار برود كه به عنوان دستياران صنعتي و هوشمند عمل كنند كه بطور خودكار دادههاي مورد علاقه را براي محقق مشخص نموده و خلاصه كنند؛ و فرضيههاي محقق را درباره دادهها آزمايش نمايند.[1]
همچنين معتقديم كه براي اينكه يك سيستم اكتشاف واقعا براي جامعه اطلاعاتي محققان ترافيک مفيد باشد، بايد بتواند آناليز را به محض اينكه دانشمندان پرسشهايشان را فرمول بندي كنند و فرضيهشان را توضيح دهند انجام دهد. اين كار، نياز به ساختارهاي داده مقياس پذير و الگوريتمهايي دارد كه قادر باشند ميليونها نقطه داده را با دهها يا دهها هزار بعد بر روي سختافزارهاي محاسباتي مدرن، در زمان چند ثانيه آناليز نمايند. که نيازمند طراحي الگوريتمهاي مبتني بر چنين نيازي بوده و تا حصول منظور نهايي در چنين سيستم اكتشافي كه به محققان امكان ميدهد به جاي علم محاسبات بر روي موضوع تحقيقشان متمركز شوند گامهاي نپيموده بسياري هستيم که در ح.صله اين مقاله نمي گنجد.[1]
این مقاله می کوشد تا با معرفی الگوریتم درخت تصمیم علاوه بر آموزش روش تحلیلی مذکور، محققان حوزه ترافیک را با یکی از ابزارهای داده کاوی آشنا نماید.
مقدمه
از آنجا كه حيات اقتصاد نوين مبتني بر داده ها شده است. به علت گستردگي استفاده از بانك هاي اطلاعاتي و پايگاه هاي داده هاي بزرگ درتمامي زمينه هاي تجاري، علمي، صنعتي وخدماتي كه در اثر توسعه فن آوري اطلاعات(IT )و انفورماتيك بوجود آورده است ما باداده هاي بسيار بسيارزيادي مواجهيم. بطوريكه فقط در سال 2000 ميزان ظرفيت نصب شده جهت ذخيره سازي اطلاعات از كل ظرفيت موجود در دهه 1990بيشتر بوده است. در حال حاضرتقريبا حجم كل اطلاعات در كامپيوترها هر 5 سال دو برابر مي شود و با توجه به سرعت ايجاد برنامه هاي چند رسانه اي و بانكهاي اطلاعاتي پيش بيني مي شود كه شتاب رشد اطلاعات به دو برابر در سال برسد.[2]
براي يك محقق و پردازشگر اطلاعات، تكنيكهاي توليد و ذخيره سازي پايگاه داده هاي كنوني و دستيابي به اطلاعات نهفته در اين داده هاي حجيم از اهميت بسياري برخوردار شده اند . از سوي ديگر نياز به چگونگي بهره برداري ازاين داده ها معمولي است. زيرا هرجايي كه داده اي وجود دارد.اطلاعات نهفته اي نيز هست كه تنها آگاهي از روش استخراج اطلاعات و پردازش داده ها را لازم دارد و اين امر براي يك تحقيق آماري مفروض است.[3]
امروزه ديگر نمي توان آنچنان كه بايد و شايد تنها با بكار گيري سيستمها و تكنيك هاي سنتي از داده هاي بانك هاي اطلاعاتي استفاده برد. زيرا اين داده ها معمولاًٌ جزو داده هاي دست دوم محسوب مي شدند و بر اساس نياز محقق براي دستيابي به اطلاعات خاص در مورد فرضيه، سوال يا هدف پژوهشي مورد نظر بدست نيامده اند. تا به استخراج سريع اطلاعات مورد نظر و پردازش داده هاي موجود پرداخته شوند. بنابراين نياز به طراحي سيستمهايي كه قادر به اكتشاف و دستيابي به اطلاعات مورد نظر كاربران با تأكيد بر مداخله حداقل انسان و با همان سرعتي كه داده ها در بانك هاي اطلاعاتي توليد مي شوند احساس شده است.[4]
بنابر اين در دنياي کنوني اين کمبود اطلاعات نيست که مسئله است بلکه کمبود دانشي است که از اين اطلاعات مي توان حاصل کرد. ميليونها صفحه ي وب، ميليونها کلمه در کتابخانه هاي ديجيتال و هزاران صفحه اطلاعات در هر شرکت تنها چند دست از اين منابع اطلاعاتي هستند. اما نمي توان به طور مشخص منبعي از دانش را در اين بين معرفي کرد. دانش خلاصه ي اطلاعات است و نيز نتيجه گيري و حاصل فکر و تحليل بر روي اطلاعات.[5]
بنا براين اصل كه داده ها سرچشمه اطلاعاتند و اطلاعات سازمان يافته و غير سازمان يافته در هر ساختار سازماني بطور مشهودي در اختيار و در دسترس است نياز به مديريت اطلاعات و در يك معناي غايي تر مديريت دانش ملموس بود.
2- مديريت دانش[3]
مديريت دانش، حوزه نسبتاً جديد و رو به توسعه اي است كه به ارايه متدولوژي جهت جمعآوري و استفاده مجدد از دانش سازماني ميپردازد. از جمله نتايج موفقيت آميز مديريت دانش، درك و استفاده سازنده از يادگيري سازماني و جريان اطلاعاتي درون سازمان است.
اشاره شد كه هر سازماني متشكل از اطلاعات نهفته اي از افراد و دانشهاي در اختيار است. در اين راستا تعريفي كه Metes و Gundry (1997) از اصلي ترين مشخصات عملياتي دانش داشته اند، ميتواند مفيد باشد:
· اصل يكم، دانش توانايي انسان است؛ بطور مثال توانايي انجام كار يا توانايي قضاوت در مورد مسئله اي چه در حال و چه در آينده. دانش دگرديسي اطلاعات توسط شخص است .
· اصل دوم، كسب دانش يك فرآيند دايناميك و پويا است.
· اصل سوم، دانش زايشي و چند بعدي است. بدان معنا كه ميتوان آنرا مورد كاوش، پژوهش و توسعه قرار داد و يا اينكه ميتوان آنرا خلاصه و چكيده نمود؛ به ديگر سخن، داشتن دانش، مالك آنرا قادر ميسازد تا تنها صرفاً به بازگويي اطلاعات كسب شده نپردازد بلكه به توليد مطالب جديدي در رابطه با موضوع نيز بپردازد.
· اصل چهارم، دانش تودرتو و پيچيده است. در حقيقت طبيعت چند بعدي دانش به اين ديدگاه گره خورده است. دانش بدنه پيچيده اطلاعات سازمان يافته است كه در بسته هاي بزرگ توزيع شده است و بنابراين اكتساب دانش توسط يك فرد، بدون كمك ابزارهاي فيلتر كننده يا راهنما ممكن است به جهت افزونگي اطلاعات، با مشكل مواجه شود.
در اين بين، ابزارهاي مديريت دانش، كمك به جمعآوري، سازمان دهي، ذخيره و انتقال اطلاعاتي مينمايند كه يك انسان از آنها به كسب دانش ميپردازد.[6]
2-1- يادگيري دانش و سازمانهاي يادگيرنده
هدف از مطالعات درزمينه مديريت اطلاعات غالباً تسهيل كار تيمي و در عين حال يادگيري دانش است. بخشهاي مهم مقوله يادگيري دانش عبارتند از:
· اكتساب دانش – يادگيري وقتي رخ ميدهد كه سازمان، دانش كسب نمايد، كه اين دانش نه تنها از محيط خارج، كه از مرتب سازي و نوساماندهي دانش موجود بدست ميآيد (, Dodgson 1993).
· توزيع اطلاعات – توزيع و اشتراك اطلاعات بين واحدهاي مختلف درون سازمان، منجر به افزايش يادگيري ميگردد ( , Brown & Danguid1991).
· تفسير اطلاعات – اهميت تبديل اطلاعات يا داده ها به دانش قبل از شروع يادگيري بسيار بالا است (, Huber1991 ).
· حافظه سازماني – دانش گروهي و فراگيري مطالب قبلي، به يادگيري بهتر كمك مينمايد (, Prahalad & Hamel1994 ) .
بسياري از محققان، رابطه بين مديريت دانش و يادگيري سازماني را به عنوان نمادي از پيشرفت سازمان، در گذر از تمركز بر منابع مادي به منابـع و پتانسيـل انسانـي پذيـرفته و بر آن تاكيد دارند (1994, Prahalad & Hamel ; 1992( Senge [4].
بنابر اين سازمان ها همواره نيازمند كسب اطلاع درباره محيط، شرايط و رخدادهاي پيرامون خود ميباشد؛ براي يك مديريت مستمر و مفيد بايد اطلاعات مستمر و مفيدي درمورد مشتريان، فن آوريها و رقباي جديد و... كسب گردد.
توسعه شيوه هاي صحيح گردآوري و تحليل اطلاعات بيروني به طور روزافزون، چالش عمده مديريت دانش گرديد كه يكي از ره آوردهاي آن توليد و توسعه دانشي جديد با ريشهايي استوار از علوم كهنسال از قبيل آمار، مديريت، مهندسي سيستم و... به نام كشف دانش گرديد. [5]
2-2- كشف دانش[5]
امروه اندازه داده هاي بدست آمده محاسبه شده در بانك هاي اطلاعاتي[6] فراتر از توانايي ما براي كاهش و تجزيه و تحليل داده ها بدون استفاده از تكنيك هاي آناليز مكانيزه[7] شده است.بسياري از بانك هاي اطلاعاتي علمي و بازرگاني پر تراكنش[8] در حد خارق العاده اي در حال گسترشند.
يك تشكيلات ساده، مانند نقشه برداري نجومي اجرايي به نام SCICAT پيش بيني كرده است كه متجاوز از سه تريليون بايت داده توليد نمايد.]6 [ كشف دانش در پايگاه هاي داده ها(KDD)[9] حوزه اي است كه به استنتاج فراهم آوري پاسخهاي تجزيه و تحليل هاي مكانيزه شده مي پردازد.
كشف دانش به عنواان استخراج غير بديهي از اطلاعات ناشناخته، ضمني و بطور بالقوه مفيد در ميان داده ها ]7 [تعريف مي شود. فياض در مرجع ]8 [ بين داده كاوي و كشف دانش يك تعمق كامل داشته است. بر طبق تعاريف آنها فرايند كشف دانش از نتايج اوليه داده كاوي ( فرايند نظام يافته يا الگوهاي تلخيص كننده داده ها) و با دقت و صحت تبديلات آنها به اطلاعات قابل فهم و مورد استفاده بدست مي آيد.اين اطلاعات نوعاً با استفاده از تكنيك هاي استاندارد، بازيافتني نيستند اما بواسطه استفاده از تكنيك هاي هوش مصنوعي[10]AI آشكار شده اند. دانش KDD يك رشته در حال گسترش است. متدولوژي هاي[11]( روش شناسي) كشف دانش بسياري در حال اجرا و گسترش وجود دارد. بعضي از اين تكنيك ها كلي هستند در حاليكه بعضي ديگر قلمرو خاص خود را دارند.
2-3-داده كاوي چيست؟
داده كاوي عبارت است از فرايند بكارگيري تكنيك هاي يادگيري كامپيوتري براي تحليل و آناليز اتوماتيك و كشف دانش از داده هاي موجود در يك پايگاه داده است.
داده كاوي فرايند كشف روابط ناشناخته و الگو ها در داده استداده کاوي، يک روش بسيار کاراست براي کشف اطلاعات از داده هاي ساخت يافته اي که در جداول نگهداري مي شوند. داده کاوي، الگوها را از تراکنش ها[12]، استخراج مي کند، داده را گروه بندي مي کند و نيز آنرا دسته بندي مي کند. بوسيله ي داده کاوي مي توانيم پي به وجود روابطي ميان اقلام داده اي که ديتابيس را پر کرده اند ببريم. در عين حال ما با داده کاوي مشکلي داريم و آن عدم وجود عاميت در کاربرد آن است. تعداد منابع داده اي ساخت يافته ي ما که به حد کافي بزرگ نيز باشند که مفاهيم داده کاوي قابل اعمال بر آنها باشد، چندان زياد نيستند. در واقع بيشتر دانش ما اگر به صورت غير ديجيتال نباشند، کاملاً غير ساختياقته اند. کتابخانه هاي ديجيتال، اخبار، کتابهاي الکترونيکي، بسياري از مدارک مالي، مقالات علمي و تقريباً هر چيزي که شما مي توانيد در داخل وب بيابيد، ساخت ياقته نيستند. در نتيجه ما نمي توانيم آموزه هاي داده کاوي را در مورد آنها به طور مستقيم استفاده کنيم.
با اين حال، سه روش اساسي در مواجهه با اين حجم وسيع از اطلاعات غير ساختيافته گسترده شده در جهان وجود دارد. بازيابي اطلاعات[13]، استخراج اطلاعات[14] و کشف دانش در متن اين سه روش برخورد با اين مسئله هستند.
2-4 ضرورت داده كاري
پس از توسعه فوق العاده پايگاه داده ها كه درنتيجه پيشرفت فوق العاده فن آوري اطلاعات دركسب وذخيره سازي داده هاي عددي بوجود آمد . دراواخردهه 1980 تلاش براي استخراج و استفاده از اطلاعات پايگاه هاي داده هاي بزرگ آغاز شد.
طي سالهاي 1989 و1991 كارگاهي كشف دانش از پايگاه داده ها (Knowledge Discovery and Data Mining ) توسط پياتقسكي (Piatetsky ) و همكارانش برگزار شد. در فواصل سالهاي 1991 تا1994 كارگاههاي كشف دانش از پايگاه داده ها توسط فياض (Fayyad ) و پياتتسكي و ديگران برگزارشد. به طور رسمي اصطلاح داده كاري براي اولين با توسط فياض در اولين كنفرانس بين المللي كشف معرفت و داده كاري در سال 1995 مطرح شد.
داده كاوي يك رشته نسبتاً جديد علمي مي باشد كه از انجام تحقيقات در رشته هاي آمار يا يادگيري ماشين (Machine learning) علوم كامپيوتر (Computer Sience) به خصوص مديريت پايگاه داده ها شكل گرفته است . البته مرزهاي اين رشته ها در داده كاوي كاري حجيم مي باشد .
3- طبقه بندي با درختهاي تصميمگيري در پايگاهدادهها
طبقهبندي دادهها يک فرآيند دو مرحلهاي است:
در مرحله اول يک مدل ساختهميشود که مجموعهاي از طبقه هاي دادهاي يا مفاهيم را مشخص ميکند. اين مرحله را مرحله يادگيري[15] گوييم که در آن يک الگوريتم طبقهبندي يک مدل را با تحليل يک مجموعه آموزشي[16] که مجموعهاي از مؤلفههاي پايگاه است مي سازد و برچسب طبقه هاي مربوط به اين مؤلفهها را مشخص ميکند. يک مؤلفه X با يک بردار صفت X=(x1,x2,…,xn) نمايش داده ميشود. فرض مي شود که هر مؤلفه به يک طبقه از پيش تعريف شده متعلق است و طبقه با يک صفت که به آن صفت برچسب طبقه ميگوييم مشخص ميشود. مجموعه آموزشي به صورت تصادفي از پايگاه انتخاب مي شود.
در مرحله دوم، يادگيري از طريق يک تابع y=f(X)انجام ميشود که ميتواند برچسب طبقه هر مؤلفه X از پايگاه را پيش بيني کند. اين تابع به صورت قواعد طبقهبندي، درختهاي تصميم گيري يا فرمولهاي رياضي است. [9]
آنچه ما در اينجا براي طبقهبندي بررسي ميکنيم طبقه بندي با درختان تصميمگيري[17] است.
4- درخت تصميم چيست؟
يک درخت معمولا تشکيل شده از ريشه[18]، شاخه ها[19]، گره ها[20] (جايي که شاخه ها منشعب مي شوند)، و برگها[21]. درختهاي تصميم هم بصورت مشابه تشکيل شده اند از گره ها که با دايره نشان داده مي شوند و شاخه ها که با پاره خطهاي اتصال بين گره ها نشان داده مي شوند. درخت تصميم را به منظور سادگي در رسم، معمولا از چپ براست يا از بالا به پايين رسم مي کنند بطوريکه ريشه در بالا قرار بگيرد. گره اول را ريشه مي گويند. انتهاي يک زنجيره " ريشه – شاخه – گره - . . . گره " را يک "برگ" مي نامند. از هر يک از گره هاي داخلي (يعني هر گره اي که برگ نباشد)، دو يا چند شاخه ديگر مي توانند منشعب شوند. هر گره مربوط به يک خصوصيت معين مي باشد و شاخه ها به معناي بازه اي از مقادير هستند. اين بازه هاي مقادير بايد بخشهاي مختلف مجموعه مقادير معلوم براي خصوصيتها را بدست دهند.
هنگامي که دقيقا دو شاخه از يک گره داخلي منشعب شوند (چنين درختي را درخت دوحالته[22] مي گويند)، همانطور که در شکل 1 نشان داده شده، هر يک از اين دو شاخه مي تواند نماينده يک عبارت درست يا غلط برحسب خصوصيات معلوم باشد.
شکل 1
هر مقدار Y به يکي از گره هاي پاياني درخت (برگها) منتسب مي شود. در مورد مسئله تشخيص الگو، مقدار داده شده بصورت يک کلاس معين مي باشد و در مورد آناليز رگرسيون اين مقدار بصورت يک عدد حقيقي است.
با استفاده از يک درخت تصميم مي توانيم براي هر يک از مشاهدات X يک مقدار پيش بيني شده Y را پيدا کنيم. براي اين منظور از ريشه درخت آغاز مي کنيم، خصوصيات مربوط به ريشه را در نظر مي گيريم و تعيين مي کنيم که مقدار مشاهده شده براي خصوصيت معلوم به کدام شاخه تعلق دارد. آنگاه گره اي را در نظر مي گيريم که شاخه مورد نظر به آن مي رسد. اين کار را براي اين گره نيز انجام مي دهيم و به همين صورت ادامه مي دهيم تا به يک برگ برسيم. مقدار YS منتسب به برگ S ام مقدار پيش بيني شده براي X خواهد بود. بنابراين، درخت تصميم مدل وابستگي T را براي Y از X بصورت Y=T(X) بدست مي دهد.
درختهايي تصميمي که در يک مسئله آناليز رگرسيون در نظر گرفته مي شوند، درختهاي رگرسيون ناميده مي شوند.
در اين مقاله ما ساده ترين نوع درختهاي تصميم را که در بالا توضيح داده شد در نظر مي گيريم. اما انواع پيچيده تر درختها نيز وجود دارد که در آنها گره هاي داخلي متناظر با عبارات پيچيده تري از بيش از يک خصوصيت معلوم مي باشند. براي مثال، اين عبارتها مي توانند ترکيبي خطي از خصوصيتهاي کمي (مثلا عبارت باشند، که مربوط به چندين منطقه محلي از فضاي چند متغيره است که توسط صفحات فرضي از هم جدا شده اند.
از اين ديدگاه، صفحات فرضي درختهاي تصميم مورد نظر، بر محورهاي عددي عمود هستند.
درخت تصميم بايد يکپارچه باشد، يعني در مسير از ريشه تا يک برگ، نبايد بازه هاي تغيير در نظر گرفته نشده وجود داشته باشد. براي مثال .
مي توان خصوصيات زير را براي درختهاي تصميم شناسايي نمود.
توسط درختهاي تصميم مي توان خصوصيات کمي و خصوصيات کيفي را بطور همزمان پردازش کرد.
بنابراين درخت تصميم نشان دهنده يک مدل منطقي از پديده مورد تحقيق مي باشد.
نقیصه درختهاي تصميم در واقع اين است که در موردي که تمام خصوصيتها کمي باشند، درختهاي تصميم تخمينهاي غير دقيقي را از جواب نهايي به دست مي دهند. براي مثال يک درخت رگرسيون که در شکل 3 نشان داده شده، تقريباً تخمين ثابتي را از تابع رگرسيون ارائه مي کند. از طرف ديگر، امکان جبران اين کمبود به وسيله افزايش تعداد برگها، يعني با کاهش طول "پاره خطها" يا "مرحله ها" وجود دارد.
يک درخت تصميم با M برگ را در نظر بگيريد. اين درخت تصميم نتيجه تجزيه فضاي خصوصيات به M زيرمنطقه غير همپوشان E1 تا EM است بصورتي که زيرمنطقه ES نشان دهنده برگ S ام (شکل4) مي باشد. هر زير منطقه چگونه شکل گرفته است؟
شکل 3
Es به صورت حاصلضرب دکارتي تعريف شده که در آن Esj تصوير Es بر روي j امين خصوصيت است. Esj در مسير بعدي به دست مي آيد. اگر خصوصيت Xj در مسير از ريشه به S امين برگ اصلا اتفاق نيافتد، آنگاه Esj با بازه اي از تعريفات خصوصيت Xj طلاقي خواهد نمود. در غير اينصورت، Esj برابر با سطح مشترک بين تمام زيرمنطقه هاي خصوصيت Xj مي باشد که در مسير ريشه تا S امين برگ قرار دارند.
شکل 4
فرض کنيد که برخي مشاهدات بصورت را داشته باشيم که هر يک از اين مشاهدات (برحسب X) به يکي از زير مجموعه هاي در نظر گرفته شده مربوط باشد. يعني، . مجموعه داده هاي مربوط به ES را DATAS مي ناميم، و تعداد مشاهدات را با NS نشان مي دهيم. فرض کنيد NSi تعداد مشاهدات از DATAS باشد که به کلاس i ام تعلق دارد (مسئله تشخيص الگو PRP ).
4-1- چگونه درختهاي تصميم را بسازيم؟
روش تشکيل دادن يک درخت تصميم از داده هاي آماري را ساختن درخت نيز مي گويند. در اين قسمت با برخي روشهاي ساخت درخت و نيز روشهاي تعيين کيفيت درختها آشنا مي شويم.
براي هر منظور خاص در تحليل آماري تعداد بسيار زيادي از انواع درختهاي تصميم وجود دارد که بسياري از آنها حتي شناخته نشده اند. يک سئوال وجود دارد: کدام درخت بهترين است و چگونه آنرا پيدا کنيم. براي پاسخ به قسمت اول، روشهاي مختلف تعريف پارامترهايي را در نظر مي گيريم که کيفيت درخت را تعيين مي کنند. از نظر تئوري، مي توانيم خطاي مورد انتظار در پيش بيني را به عنوان پارامتر پايه در نظر بگيريم. به هرحال درعمل اين قانون هنوز به عنوان اصل شناخته نشده است. بنابراين فقط مي توانيم کيفيت را با توجه به مجموعه اي از مشاهدات که به ما داده شده تخمين بزنيم.
4-1-1- پارامترهاي کيفيت يک درخت
فرض کنيم يک درخت تصميم و نمونه اي از N شيئ داريم. امکان انتخاب دو نوع اصلي از پارامترها توضيح دهنده کيفيت يک درخت وجود دارد. نوع اول پارامترهاي دقت هستند و نوع دوم پارامترهاي پيچيدگي درخت.
پارامترهاي دقت يک درخت را مي توان با کمک نمونه تعريف کرد و کيفيت تقسيم اشياء در کلاسهاي مختلف (در مورد يک مسئله تشخيص)، يا اندازه بزرگي خطا (در مورد يک مسئله آناليز رگرسيون) را تعيين نمود.
عدد نسبي (فراواني) خطاها به معناي کسري از اشياء است که توسط درخت بطور اشتباه به يک کلاس نسبت داده شده:
که در آن
که در آن نيز K تعداد کلاسها مي باشد.
واريانس نسبي براي يک درخت تصميم را مي توان از فرمول زير محاسبه نمود :
که در آن واريانس باقيمانده است،
واريانس اوليه بصورت :
تعريف مي شود و داريم :
پارامترهاي پيچيدگي خصوصيات شکل درخت را تعيين مي کنند و به نمونه بستگي ندارند.
براي مثال، پارامترهاي پيچيدگي يک درخت به صورت تعداد برگهاي درخت، تعداد گره هاي داخلي آن و بيشترين طول مسير از ريشه تا يک برگ مي باشند.
همچنين مي توان از طول يک مسير خارجي استفاده نمود که به صورت تعداد شاخه هايي تعريف مي شود که يک درخت کامل را تشکيل مي دهند.
پارامترهاي پيچيدگي و دقت با هم داراي پيوستگي داخلي هستند: به عنوان يک قانون مي توان گفت درختي که پيچيده تر باشد داراي دقت بيشتري است (در درختي که هر برگ آن نماينده يک شيئ باشد بيشترين ميزان دقت وجود دارد).
اگر ديگر شرايط يکسان باشند، درختي که پيچيدگي کمتري داشته باشد، ترجيح داده مي شود. چنين درختي مدل ساده تري از پديده مورد تحقيق را بدست مي دهد و تفسيرهاي بعدي (توضيح مدل) را آسان مي کند. علاوه بر اين، از تحقيقات تئوري چنين بر مي آيد که در صورت کوچک بودن اندازه نمونه (در مقايسه با تعداد خصوصيات) درختهايي که بيش از حد پيچيده باشند ناپايدار هستند يعني داراي تعداد خطاهاي بيشتري براي مشاهدات جديد خواهند بود.
از طرف ديگر، روشن است که يک درخت خيلي ساده نيز امکان رسيدن به پيش بيني خوبي را فراهم نمي کند. بنابراين، در انتخاب بهترين درخت تصميم بايد به يک "توافق" معيني بين پارامترهاي دقت و پيچيدگي برسيم.
براي رسيدن به چنين توافقي مثلا مي توانيم از اين شرط براي کيفيت استفاده کنيم: که در آن p يک پارامتر دقت و a يک پارامتر معلوم هستند. بهترين درخت با توجه به اين شرط بايد داراي کمترين مقدار Q باشد.
از روشي که در آن بيشترين پيچيدگي مجاز براي درخت تعيين مي شود، بطور همزان با جستجوي دقيقترين درخت هم مي توان استفاده نمود.
4-1-2- تخميني از کيفيت بر روي يک نمونه کنترل
"نمونه کنترل (يا تست)" به نمونه اي گفته مي شود که براي ساختن يک درخت بکار برده نمي شود، بلکه براي تخمين زدن کيفيت يک درخت ساخته شده بکار مي رود. دو پارامتر محاسبه مي شود: اين دو پارامتر تعداد نسبي خطاها براي مسائل تشخيص، و واريانس نمونه کنترل براي مسائل آناليز رگرسيون هستند. از آنجا که اين نمونه در ساخت درخت تصميم نقشي ندارد، اين پارامترها خطاي نامعلوم "واقعي" را بهتر نشان مي دهند. هر چه اندازه نمونه کنترل بزرگتر باشد، درجه تخمين هم بالاتر خواهد بود.
در يک مسئله تشخيص، تحت شرايط مستقل بودن مشاهدات، فراواني خطاها از توزيع دو جمله اي بدست مي آيد. بنابراين، با دانستن تعداد خطاها در نمونه کنترل مي توان بازه اطميناني را پيدا کرد که به احتمال معيني تعداد خطاهاي کلاس بندي اشتباه به آن بازه تعلق دارد. در مرجع [5] نمودارهايي آمده که در آنها مي توان بازه اطمينان را بازاي اندازه نمونه مشخص و تعداد خطاها در نمونه کنترل تعيين نمود.
4-2-روشهاي ساخت درخت تصميم
روشهاي موجود (چندين روش وجود دارد) را مي توان به دو گروه اصلي تقسيم نمود. گروه اول شامل روشهايي براي ساختن درخت با ميزان بهينگي صريح (با توجه به شرط کيفيت درخت)، و گروه دوم شامل روشهاي ساخت درخت با ميزان تقريبي بهينگي مي شوند.
مسئله جستجو بدنبال درخت بهينه مي تواند به مسئله برنامه ريزي گسسته (discrete programming) يا انتخاب از ميان تعداد محدود (ولي بسيار بزرگ) منجر شود. اين از اين حقيقت ناشي مي شود که براي يک نمونه آموزشي محدود، تعداد محدودي حالت شاخه ها (شکل زير) براي هر خصوصيت وجود دارد.
انواع روشهاي پايه برنامه ريزي گسسته عبارتند از: جستجوي کامل، روش برنامه ريزي ديناميک، و روش شاخه ها و اتصالات. به هرحال، استفاده از اين روشها براي درختهاي تصميم نياز به کار بسيار زيادي دارد، مخصوصا اگر تعداد مشاهدات يا تعداد خصوصيتها زياد باشد. بنابراين، روشهاي تقريبي را در نظر مي گيريم که عبارتند از: روش شاخه بندي ساختماني، روش هرس کردن، و روش برگشتي.
اجازه بدهيد تمام اعمال پايه بر روي درخت تصميم را در نظر بگيريم. روشهاي ساخت درخت شامل توالي رشته اي از اين اعمال خواهد بود.
4-2-1- عمل شاخه بندي (تقسيم)
عمل شاخه بندي پايه ساخت درخت است. يک گره از درخت و يک خصوصيت Xj را در نظر مي گيريم. فرض کنيد بازه تعريف اين خصوصيت به تعداد Lj زير مجموعه تقسيم شود (در زير روشهاي انتخاب چنين زير مجموعه هايي خواهد آمد). در مورد خصوصيتهاي کمي، اين زير مجموعه ها گروهي از زير بازه هاي مجزا هستند، در مورد خصوصيتهاي کيفي، زير مجموعه اي از مقادير، و در مورد داده هاي خصويات ترتيبي زير مجموعه هايي شامل مقادير همسايه مي باشند.
فرض کنيد به هر يک از اين زير مجموعه ها يک شاخه نسبت دهيم که از گره فعلي (مادر) به سمت يک گره جديد که (فرزند) ناميده مي شود امتداد مي يابد. بنابراين، گره به تعداد Lj گره جديد "منشعب" شده ("تقسيم شده") است (شکل5).
شکل 5
توجه کنيد که براي درختهاي باينري Lj هميشه برابر با 2 است. اگر Lj براي يک درخت هميشه برابر با 3 باشد آن درخت را "سه گانه" مي ناميم. اگر Lj هميشه برابر با 4 باشد يک درخت "چهارگانه" خواهيم داشت.
چگونه بازه اي از تعريف را تقسيم کنيم؟ مجموعه اي از مشاهدات را براي گره مورد نظر بدست مي آوريم و مقادير Xj را براي اين مشاهدات در نظر مي گيريم.
شکل 6
يک خصوصيت کمي را در نظر بگيريد. در اين مورد، مرزها در وسط بازه هاي بين مقادير همسايه قرار دارند و تقسيم با توجه به اين مرزها صورت مي گيرد (شکل 6).
براي مثال در شکل 7 (مقادير مشاهده شده براي خصوصيات با Ä نشان داده شده اند) براي يک درخت باينري (دوحالته) مي توان شرايط زير را براي تقسيم در نظر گرفت: Xj < 0.5 يا Xj >= 0.5 و Xj < 1.5 يا Xj >= 1.5 . اگر خصوصيت کيفي باشد، آنگاه تقسيمات بر حسب مقادير خصوصيت صورت مي گيرد. براي مثال، اگر Xj به معناي يک کشور باشد مي توان شرايط تقسيم بندي زير را در نظر گرفت: } کانادا، مکزيک، امريکاXj Î { يا } برزيل، آرژانتين Xj Î {
شکل 7
در موردي که تعداد مقادير زياد باشد تعداد شرايط تقسيم بندي بيش از حد زياد مي شود. بنابراين براي تسريع فرايند ساخت درخت، تمام شرايط را در نظر نمي گيريم بلکه از برخي از آنها استفاده مي کنيم (براي مثال، "کانادا" Xj = يا "کانادا" Xj ¹ ).
در مورد خصوصيات ترتيبي، شرايط تقسيم شامل مقادير ترتيبي هستند. براي مثال، اگر Xj درجه نظامي باشد، تقسيم بندي مي تواند بصورت [ گروهبان يکم – سرباز ] Xj Î يا [سرگرد- ستوان ] Xj Î باشد.
براي خصوصيتهاي کيفي يا ترتيبي مواردي مي تواند وجود داشته باشد (هنگاميکه اندازه نمونه مشاهدات کوچک است) که مجموعه مقادير مشاهدات خصوصيت انجام شده براي يک گره تنها قسمتي از کل بازه تعريف مقادير خصوصيت را در بر بگيرد. در چنين مواردي لازم است که بقيه مقادير را به يک شاخه جديد نسبت دهيم. تا در پيش بيني نمونه کنترل که داراي چنين مقداري باشد بتوانيم تعيين کنيم که اين مقدار به کدام شاخه تعلق دارد. براي مثال، ممکن است مقادير معلوم را با توجه به بيشترين تعداد مشاهدات به شاخه ها نسبت دهيم.
4-2-2- عمل تعريف درجه توافق براي شاخه بندي گره (قانون توقف)
يک گره آزاد (گره اي که شاخه اي از آن منشعب نشده) را در درخت در نظر بگيريد، که مشخص نيست آيا اين گره يک برگ است يا اينکه بايد شاخه بندي شود. زير مجموعه مشاهدات مربوط به اين گره را در نظر مي گيريم. گره ها را به دو دسته تقسيم مي کنيم: اول آنکه اين مقادير همگن باشند، يعني اساسا متعلق به يک کلاس باشند (مسئله تشخيص الگو RP). يا اينکه واريانس Y آنها به اندازه کافي کوچک باشد (مسئله آناليز رگرسيون RA). موردي که در آن مقدار خصوصيت براي تمام مشاهدات يکسان باشد نيز به اين مورد مربوط مي شود. دوم آنکه تعداد مشاهدات کافي نباشد.
گره اي که داراي شرايط شاخه بندي نباشد يک برگ ناميده مي شود.
براي تعريف درجه توافق مي توان پارامترهاي زير را تعريف نمود: خطاي مجاز براي گره (مسئله PR)، واريانس مجاز (مسئله RA) و آستانه براي مشاهدات کيفي.
4-3- الگوريتم درختهاي تصميم گيري
در زير شبه کد يک الگوريتم پايه براي درختهاي تصميم گيري را ميبينيد:
عملکرد الگوريتم فوق به شرح ذيل است:
· الگوريتم با پارامترهاي D، attribute_list، Attribute_selection_method فراخواني ميشود. D در واقع يک بخش[23] دادهاي است. در ابتدا D شامل مجموعه آموزشي و برچسب طبقه هاي متناظر با آنها است. attribute_list فهرستی از صفات موجود در مؤلفهها است. Attribute_selection_methodيک روال ابتکاري[24] است که بهترين صفت را براي جداکردن مؤلفهها براساس طبقه ها ميدهد. اين متد از يک معيار انتخاب صفت مانند information gain يا gini index استفاده مي کند که در ادامه شرح داده مي شود.
· درخت در گام اول با يک گره تنهاي N که کل مجموعه آموزشي داده ها را نشان مي دهد ايجاد مي شود.
· اگر مؤلفههاي D همه از يک طبقه باشند گره N يک برگ خواهد بود و با آن طبقه برچسب مي خورد(گام 2 و 3). گام 4 و 5 شرايط خاتمه هستند که در ادامه شرح داده مي شوند .
· در غير اين صورت Attribute_selection_method فراخواني ميشود تا معيار شکاف[25] را مشخص کند. معيار شکاف مشخص ميکند که کدام صفت بايد در گره N مورد آزمون قرار گيرد. معيار شکاف همچنين بيان ميکند که چه شاخههايي بايد از گره N با توجه به آزمون مربوطه، خارج شوند. به عبارت ديگر معيار شکاف، صفت يا نقطه شکاف را تعيين ميکند. نقطه شکاف، D را به يکسري بخش تبديل ميکند. اين بخش ها بايد تا حد ممکن خالص[26] باشند به اين معني که همه مؤلفه هاي موجود در يک بخش بايد مربوط به يک طبقه باشند.[4]
· گره N با معيار شکاف برچسب ميخورد(گام 7). يک شاخه از گره N به هر يک از خروجيهاي معيار شکاف مي رود. مؤلفههاي D متناظراً بخش بندي ميشوند(گام10و11).
· الگوريتم فرايند مشابهي را به صورت بازگشتي در هر يک از بخش هاي حاصل شده دنبال ميکند(گام 14).
· بخش بندي بازگشتي در صورتي که يکي از شرايط زير بوجود آيد متوقف ميشود:
1. اگر تمام مؤلفه ها در بخش D متعلق به يک طبقه باشند(گام 2 و 3).
2. صفتي براي بخش بندي بيشتر وجود نداشته باشد(گام 4).در اين حالت گره N به يک برگ تبديل مي شود و برچسب طبقه آن طبقه متداول در D خواهد بود.
3. مؤلفه اي براي يک شاخه وجود نداشته باشد، در واقع اگر يکي از بخش هاي D مانند Dj تهي باشد(گام 12). در اين موارد يک برگ با برچسب طبقه متداول در D ايجاد مي شود(گام 13)[4].
4-3-1-معيارهاي انتخاب صفت:
معيارهاي مختلفي براي تعيين صفتي که شکاف بايد بر اساس آن انجام شود وجود دارد مانند:
· بهره اطلاعاتي[27]
· نسبت بهره[28]
· ششاخص جيني[29]
ما در اينجا تنها به معرفي بهره اطلاعاتي ميپردازيم.
4-3-2-بهره اطلاعاتي:
اطلاعات مورد نياز براي طبقه بندي يک مؤلفه در D برابر:
است که در آن pi احتمال آن است که يک مؤلفه دلخواه در D متعلق به طبقه Ci باشد که اين احتمال به صورت |D|/|Ci,D| تخمين زده ميشود(|D| و | Ci,D | تعداد مؤلفهها در D و Ci,D را نشان ميدهد). تعداد طبقه هاي موجود m است. در واقع Info(D)همان آنتروپی یا بی نظمی[30] ميباشد.
فرض ميکنيم صفت A داراي v مقدار متمايز به صورت {a1,a2,…,av} باشد يا به عبارت ديگر A يک صفت گسسته باشد. اگر بخواهيم D را بر حسب صفت A بشکافيم v بخش يا زيرمجموعه مانند {D1,D2,…,Dv} حاصل مي شود که در آن Dj شامل مؤلفههايي از D است که مقدار صفت A در آنها برابر aj است. اگر فرض کنيم که D در گرهاي چون N قرار داشته باشد آنگاه اين بخشها متناظر با شاخههايي هستند که از N خارج ميشوند. اطلاعات مورد نياز براي طبقهبندي يک مؤلفه از D بر حسب صفت A برابر:
است. عبارت |Dj|/|D| در واقع وزن بخش j را نشان ميدهد.
اطلاعات حاصل از انشعاب بر حسب صفت A را به صورت زير تعريف ميکنيم:
هر چه مقدار بهره صفتA (Gain(A)) بيشتر باشد يا به عبارت ديگر هر چه InfoA(D))) کمتر باشد صفت A به عنوان صفت شکاف انتخاب مي شود[4].
Reference:
[1] Komarek, P. and Moore, A. (2003). Fast Robust Logistic Regression for Large Sparse Datasets with Binary Outputs. In Artificial Intelligence and Statistics.
[2] http://www.mehravid.ir/mod.php
[4] ناظمي عبدالرضا 1384
[3] پاك گوهر عليرضا – نشريه تخصصي علمي تحقيقاتي راهور - شماره 8
[4] و ظيفه دوست عليرضا – متن كاوي
[5] پاشنه طلا - مديريت دانش و سازمانهاي سومين هزاره smart and
[6] Fayyad, U.M., Djorgovski, S.G., and Weir, N , 1996
[7] Frawley, W.J., Piatetsky-Shapiro, G., and Matheus, C,1991
[8] Fayyad, U.M., Piatetsky-Shapiro, G., and Smyth,1996
[9] قدیمی، یوحنا؛ عباسی علی ؛ پاشایی کاوه؛دادهکاوي جرياندادهها با درختهاي تصميمگيري
[2] - msadeghikia@yahoo.com
[7] automated analysis techniques
[9] Knowledge discovery in databases
[10] Artificial Inteligence
[13] Information Retrieval
[14] Information Extraction
نخست آنکه پاک گوهر يعني پاک نژاد. اصیل . مَحض . پاکزاد: