एंट्रोपी और निर्णय पेड़

निर्णय के पेड़ उन मामलों में एक सुविधाजनक उपकरण हैं जहां यह न केवल डेटा को वर्गीकृत करने के लिए आवश्यक है, बल्कि यह भी समझाने के लिए कि किसी वस्तु को किसी भी वर्ग को क्यों सौंपा गया है।

आइए हम पहले पूर्णता के लिए, एन्ट्रापी की प्रकृति और इसके कुछ गुणों पर विचार करें। फिर, एक सरल उदाहरण के साथ, हम देखेंगे कि एंट्रॉपी का उपयोग क्लासिफायर बनाने में कैसे मदद करता है। उसके बाद, सामान्य शब्दों में, हम निर्णय वृक्ष और इसकी विशेषताओं के निर्माण के लिए एक एल्गोरिथ्म तैयार करते हैं।

कंबाइनटोरियल एन्ट्रॉपी

बहुत सारी रंगीन गेंदों पर विचार करें: 2 लाल, 5 हरे और 3 पीले। उन्हें शफल करें और उन्हें एक पंक्ति में व्यवस्थित करें। हम इस ऑपरेशन को क्रमपरिवर्तन कहते हैं :



आइए विभिन्न क्रमांक की संख्या की गणना करें, यह देखते हुए कि एक ही रंग की गेंदें अविभाज्य हैं।

यदि प्रत्येक गेंद में एक अनूठा रंग होता, तो क्रमपरिवर्तन की संख्या 10 होती! लेकिन अगर एक ही रंग की दो गेंदों को आपस में जोड़ा जाए, तो एक नया क्रम विफल हो जाएगा। तो आपको 5 को बाहर करने की आवश्यकता है ! आपस में हरे रंग की गेंदों का क्रमांकन (साथ ही 3! पीला और 2! लाल)। इसलिए, इस मामले में, समाधान होगा:

बहुराष्ट्रीय गुणांक आपको इस समस्या के सामान्य मामले में क्रमपरिवर्तन की संख्या की गणना करने की अनुमति देता है: ( नी - प्रत्येक रंग की समान गेंदों की संख्या)।

सभी क्रमपरिवर्तन को 0 से (डब्ल्यू - 1) संख्या के साथ गिना जा सकता है। इसलिए, लॉग ₂ (W) बिट्स की एक पंक्ति प्रत्येक क्रमपरिवर्तन को विशिष्ट रूप से एन्कोड करती है।

चूँकि क्रमपरिवर्तन में एन गेंदें होती हैं, इसलिए क्रमपरिवर्तन के एक तत्व के प्रति बिट की औसत संख्या को व्यक्त किया जा सकता है:

इस मात्रा को कॉम्बिनेटरियल एन्ट्रापी कहा जाता है:


जितना अधिक समान सेट (एक रंग पूर्वनिर्मित की गेंदें) - उतना ही कम इसका दहनशील एन्ट्रापी, और इसके विपरीत - सेट में जितने अधिक अलग-अलग तत्व हैं, उतनी ही इसकी एन्ट्रोपी।

शैनन एंट्रोपी

चलो ऊपर वर्णित एन्ट्रोपी के लिए अभिव्यक्ति पर करीब से नज़र डालें:

लघुगणक के गुणों को देखते हुए, हम सूत्र को निम्नानुसार रूपांतरित करते हैं:

मान लीजिए कि स्टर्लिंग फॉर्मूला का उपयोग करने के लिए गेंदों की संख्या पर्याप्त है :

स्टर्लिंग सूत्र को लागू करने से हमें प्राप्त होता है:

(जहां कश्मीर प्राकृतिक लघुगणक में संक्रमण का गुणांक है)

दिया है कि अभिव्यक्ति परिवर्तित किया जा सकता है:


चूंकि गेंदों की कुल संख्या एन है , और आई-वें रंग की गेंदों की संख्या नी है , संभावना है कि एक यादृच्छिक रूप से चयनित गेंद इस रंग की होगी: । इसके आधार पर, एन्ट्रापी के लिए फॉर्मूला लगेगा:

यह अभिव्यक्ति शैनन एन्ट्रापी है ।

अधिक गहन निष्कर्ष के साथ, यह दिखाया जा सकता है कि शैनन एन्ट्रापी, कॉम्बीनेटरियल एन्ट्रॉपी की सीमा है; इसलिए, इसका मूल्य हमेशा कॉम्बीनेटोरियल एन्ट्रॉपी के मूल्य से कुछ बड़ा होता है।

दो आकृतियों की तुलना निम्नलिखित आकृति में प्रस्तुत की गई है, जिसकी गणना दो प्रकार की वस्तुओं वाले सेटों के लिए की जाती है - A और B (प्रत्येक सेट में तत्वों की कुल संख्या 100 है):

ऊष्मप्रवैगिकी

एन्ट्रापी के लिए इसी तरह के भाव ऊष्मागतिकी में प्राप्त किए जा सकते हैं:

• पदार्थों के सूक्ष्म गुणों के आधार पर: सांख्यिकीय ऊष्मप्रवैगिकी के पश्चात के आधार पर (इस मामले में, वे अविभाज्य कणों पर काम करते हैं जो विभिन्न ऊर्जा राज्यों में हैं)।
  
• पदार्थों के मैक्रोस्कोपिक गुणों के आधार पर: थर्मल मशीनों के संचालन का विश्लेषण करके।
  

एन्ट्रापी की अवधारणा ऊष्मप्रवैगिकी में एक मूलभूत भूमिका निभाती है, जो ऊष्मप्रवैगिकी के दूसरे कानून के निर्माण में दिखाई देती है: यदि एक पृथक मैक्रोस्कोपिक प्रणाली एक नॉनक्लेरिब्रियम राज्य में है, तो एंट्रोपी के एक बड़े मूल्य के साथ एक राज्य में इसका सहज संक्रमण सबसे अधिक संभावना है :

दानव अधिकतम

1867 में थर्मोडायनामिक्स के दूसरे कानून की सांख्यिकीय प्रकृति पर जोर देने के लिए, जेम्स मैक्सवेल ने एक विचार प्रयोग का प्रस्ताव दिया: "एक निश्चित तापमान की गैस से भरे एक जहाज की कल्पना करें, एक शटर के साथ एक विभाजन द्वारा पोत को अलग किया जाता है, जिसे दानव एक दिशा में तेजी से कणों को पारित करने के लिए खोलता है और दूसरे में धीमी गति से कणों को चलाता है। इसलिए, कुछ समय बाद, तेज कण बर्तन के एक हिस्से में केंद्रित होंगे, और दूसरे में धीमे कण। इस प्रकार, ऊष्मप्रवैगिकी के दूसरे नियम के विपरीत, मैक्सवेल के दानव एक बंद प्रणाली के प्रवेश को कम कर सकते हैं। "


बाद में, लियो स्ज़ीलार्ड ने विरोधाभास का समाधान किया, लेकिन यह चर्चा इस लेख के दायरे से कुछ हद तक परे है।

मैक्सवेल दानव == क्लासिफायरियर

यदि "तेज" और "धीमी" कणों के बजाय हम विभिन्न वर्गों से संबंधित वस्तुओं पर विचार करते हैं, तो मैक्सवेल दानव को एक प्रकार का क्लासिफायरियर माना जा सकता है।

विरोधाभास का बहुत सूत्रीकरण सीखने के एल्गोरिथ्म को बढ़ावा देता है: आपको प्रशिक्षण डेटा सेट को तोड़ने के लिए नियमों (विधेय) को खोजने की आवश्यकता है, ताकि एंट्रोपी का औसत मूल्य कम हो जाए । बहुत सारे डेटा को भागों में विभाजित करने की प्रक्रिया, एन्ट्रापी में कमी के लिए अग्रणी, सूचना के उत्पादन के रूप में माना जा सकता है।

एक निश्चित विधेय के अनुसार प्रारंभिक डेटा सेट को दो भागों में विभाजित करने के बाद, हम प्रत्येक सबसेट की एन्ट्रापी की गणना कर सकते हैं, और फिर एन्ट्रॉपी के औसत मूल्य की गणना कर सकते हैं - यदि यह मूल सेट के एन्ट्रॉपी से छोटा हो जाता है, तो डेटा के बारे में कुछ सामान्य जानकारी की भविष्यवाणी होती है।

उदाहरण के लिए, दो-रंगीन गेंदों के एक सेट पर विचार करें, जिसमें गेंद का रंग केवल x समन्वय पर निर्भर करता है:
(व्यावहारिक कारणों के लिए, गणना में शैनन एंट्रोपी का उपयोग करना सुविधाजनक है)



यह आंकड़ा से देखा जा सकता है कि यदि आप सेट को दो भागों में विभाजित करते हैं, बशर्ते कि एक भाग में समन्वय x with 12 के साथ सभी तत्व हों, और दूसरे भाग में x> 12 के साथ सभी तत्व शामिल हों, तो औसत एन्ट्रापी ∆S से मूल से कम होगी। इसका मतलब है कि यह विधेय डेटा के बारे में कुछ जानकारी को सामान्य करता है (यह ध्यान रखना आसान है कि x> 12 के लिए लगभग सभी गेंदें पीले हैं)।

यदि आप अपेक्षाकृत सरल विधेय ("अधिक", "कम", "बराबर", आदि) का उपयोग करते हैं, तो सबसे अधिक संभावना है, एक नियम एक पूर्ण वर्गीकरण बनाने के लिए पर्याप्त नहीं होगा। लेकिन विधेय खोज प्रक्रिया को प्रत्येक उपसमुच्चय के लिए पुनरावर्ती रूप से दोहराया जा सकता है। स्टॉपिंग मानदंड एन्ट्रापी का शून्य (या बहुत छोटा) मान है। परिणाम पेड़ों की तरह का एक सेट है जिसे निर्णय वृक्ष कहा जाता है:


निर्णय वृक्ष की पत्तियां वर्ग हैं। निर्णय पेड़ का उपयोग करके किसी वस्तु को वर्गीकृत करने के लिए, आपको क्रमिक रूप से पेड़ के नीचे जाने की जरूरत है (वर्गीकृत वस्तु पर लागू होने वाले विधेय के मूल्यों के आधार पर एक दिशा चुनना)। पेड़ की जड़ से पत्तियों तक का रास्ता इस बात की व्याख्या के रूप में समझा जा सकता है कि यह या उस वस्तु को किसी भी वर्ग को क्यों सौंपा गया है।

माना जाता है उदाहरण में, सादगी के लिए, सभी वस्तुओं को केवल एक विशेषता द्वारा चित्रित किया जाता है - एक्स समन्वय करते हैं, लेकिन वास्तव में एक ही दृष्टिकोण को कई विशेषताओं के साथ वस्तुओं पर लागू किया जा सकता है।

इसके अलावा, वस्तु की विशेषताओं के मूल्यों पर कोई प्रतिबंध नहीं है - वे या तो श्रेणीबद्ध हो सकते हैं, साथ ही साथ संख्यात्मक या स्वभाव में तार्किक भी हो सकते हैं। केवल उन विधेयकों को निर्धारित करना आवश्यक है जो विशेषता मानों को सही ढंग से संसाधित कर सकते हैं (उदाहरण के लिए, यह शायद ही तार्किक मूल्यों के साथ विशेषताओं के लिए "अधिक" या "कम") का उपयोग करने के लिए समझ में आता है।

निर्णय वृक्ष निर्माण एल्गोरिथ्म

सामान्य शब्दों में, निर्णय वृक्ष निर्माण एल्गोरिदम को निम्नानुसार वर्णित किया जा सकता है:
(यह मुझे लगता है कि "मानव भाषा" द्वारा वर्णित एल्गोरिदम पढ़ने में आसान है)

s0 =      s0 == 0 :    ,             s0 != 0 :  ,                  ,       ,          

"विधेय की तलाश" का क्या अर्थ है?
वैकल्पिक रूप से, हम मान सकते हैं कि मूल सेट के प्रत्येक तत्व के आधार पर, हम एक विधेय का निर्माण कर सकते हैं जो सेट को दो भागों में तोड़ता है। इसलिए, एल्गोरिथ्म में सुधार किया जा सकता है:

 s0 =      s0 == 0 :    ,             s0 != 0 :     :      ,             ∆S   ,    ∆S       ,       ,          

कैसे एक "एक सेट के प्रत्येक तत्व के आधार पर एक विधेय उत्पन्न कर सकता है " ?
सबसे सरल मामले में, आप केवल एक विशेषता के मूल्य (उदाहरण के लिए, "x , 12" , या "रंग == पीला" , आदि) का उल्लेख करने वाले विधेय का उपयोग कर सकते हैं। इसलिए, एल्गोरिथ्म फार्म ले जाएगा:

 s0 =      s0 == 0 :    ,             s0 != 0 :     :       :      ,             ∆S   ,    ∆S       ,       ,          

वास्तव में, यदि हम वर्गीकृत वस्तुओं को एक बहुआयामी स्थान के बिंदुओं के रूप में मानते हैं, तो हम देख सकते हैं कि उप-सेट में डेटा को विभाजित करने वाले विधेय हाइपरप्लेन्स हैं, और क्लासिफायरियर प्रशिक्षण प्रक्रिया संस्करणों की बाउंडिंग के लिए एक खोज है (सामान्य तौर पर, किसी भी अन्य प्रकार के क्लासिफायरियर के रूप में) ।

मुख्य लाभ पेडिकेट्स की परिणामी वृक्ष जैसी संरचना है, जो आपको वर्गीकरण परिणामों की व्याख्या करने की अनुमति देता है (हालांकि इसके "लालच" के कारण, वर्णित एल्गोरिदम हमेशा पेड़ की समग्रता को सुनिश्चित नहीं करता है)।

वर्णित एल्गोरिथ्म के कोनेस्टोन में से एक पेड़ का निर्माण करते समय स्टॉपिंग मानदंड है। ऊपर वर्णित छद्म संहिताओं में, मैंने पेड़ का निर्माण तभी रोक दिया था जब मैं एक सेट पर पहुंचा था जिसमें सभी तत्व एक ही वर्ग के थे ( एन्ट्रॉपी == 0 )। यह दृष्टिकोण आपको निर्णय पेड़ को प्रशिक्षण डेटा सेट के लिए पूरी तरह से अनुकूलित करने की अनुमति देता है, लेकिन यह हमेशा व्यावहारिक दृष्टिकोण से प्रभावी नहीं होता है (परिणामस्वरूप पेड़ पीछे हट जाता है )।

संभावित रोक मानदंडों में से एक छोटा theS मान हो सकता है। लेकिन इस दृष्टिकोण के साथ, फिर भी, सार्वभौमिक सलाह देना असंभव है: पेड़ को ∆S के किन मूल्यों को रोका जाना चाहिए।

बेतरतीब जंगल

ट्री बनाते समय स्टॉपिंग मानदंड से परेशान न होने के लिए, आप निम्न कार्य कर सकते हैं: प्रशिक्षण डेटा सेट से रैंडम सबसेट का चयन करें, और प्रत्येक उपसमुच्चय के लिए अपना निर्णय ट्री बनाएं (सिद्धांत रूप में, यह भी मायने नहीं रखता है कि मानदंड को रोकना क्या होगा) :



पेड़ों का परिणामी पहनावा ( यादृच्छिक वन का एक सरलीकृत संस्करण) सभी पेड़ों के माध्यम से वर्गीकृत वस्तु चलाकर वर्गीकरण के लिए इस्तेमाल किया जा सकता है। प्रत्येक पेड़ एक विशेष वर्ग से संबंधित वस्तु के लिए "वोट" लगता है। इस प्रकार, पेड़ों के किस हिस्से के आधार पर किसी विशेष वर्ग के लिए मतदान किया जाता है, हम यह निष्कर्ष निकाल सकते हैं कि ऑब्जेक्ट किसी भी वर्ग के लिए किस संभावना से संबंधित है।

यह विधि आपको सीमा डेटा क्षेत्रों को पर्याप्त रूप से संसाधित करने की अनुमति देती है:



आप देख सकते हैं कि एक एकल निर्णय वृक्ष एक ऐसे क्षेत्र का वर्णन करता है जिसमें पूरी तरह से लाल डॉट्स होते हैं, जबकि पेड़ों का एक समूह एक आंकड़े का वर्णन करता है जो एक सर्कल के करीब है।

अगर आप प्रयोग करना चाहते हैं

मैंने निर्णय पेड़ और यादृच्छिक वन की तुलना करने के लिए एक छोटा अनुप्रयोग बनाया। हर बार जब एप्लिकेशन लॉन्च किया जाता है, तो हरे रंग की पृष्ठभूमि पर लाल सर्कल के अनुरूप एक यादृच्छिक डेटा सेट बनाया जाता है, और एप्लिकेशन निष्पादन के परिणामस्वरूप, एक चित्र प्राप्त होता है, जैसे कि ऊपर दिखाया गया है।

• आपके पास जावा रनटाइम स्थापित होना चाहिए
  
• यहाँ से dec_tree_demo.jar बाइनरी डाउनलोड करें ।
  
• एप्लिकेशन को चलाने के लिए, कमांड लाइन में टाइप करें: java -jar dec_tree_demo.jar out.png
  

सूत्र जीथुब पर हैं ।

एक निष्कर्ष के बजाय

स्वीकृति के पेड़ उन मामलों में एक अच्छा विकल्प हैं जब आप अन्य वर्गीकरण एल्गोरिदम में अमूर्त भार और गुणांक को समायोजित करने से थक जाते हैं, या जब आपको मिश्रित (श्रेणीबद्ध और संख्यात्मक) विशेषताओं के साथ डेटा संसाधित करना पड़ता है।

अतिरिक्त जानकारी

1. यत्सिमिरस्की वी.के. भौतिक रसायन विज्ञान (एन्ट्रापी की अवधारणा यहाँ अच्छी तरह वर्णित है, और इस घटना के कुछ दार्शनिक पहलुओं पर भी विचार किया गया है)
   
2. संपीड़न के बारे में एक दिलचस्प धागा और संपीड़न पर एन्ट्रापी
   
3. Habré पर निर्णय पेड़ों के बारे में एक और लेख
   
4. टोबी सेगरान, प्रोग्रामिंग कलेक्टिव इंटेलिजेंस (इस किताब में एक अध्याय है जो पेड़ों को तय करने के लिए समर्पित है, और सामान्य तौर पर, अगर आपने अभी तक इस किताब को नहीं पढ़ा है - मैं आपको निश्चित रूप से वहां देखने की सलाह देता हूं :-)
   
5. Weka और Apache Mahout जैसी लाइब्रेरी में निर्णय पेड़ों का कार्यान्वयन होता है।