خوارزمية شجرة القرار في التعلم الآلي باستخدام Python

أولاً، مبادئ شجرة القرار

شجرة القرار هي بنية شجرة تستخدم الصفات كعقد، وتستخدم القيم الممكنة للصفات كفروع.
العقدة الجذر في شجرة القرار هي الصفة التي تحتوي على أكبر كمية من المعلومات في جميع العينات. العقدة الوسطى في الشجرة هي الصفة التي تحتوي على أكبر كمية من المعلومات في مجموعة العينات الفرعية للعقدة الجذر. العقدة الأوراق في شجرة القرار هي قيمة الفئة للعينة. شجرة القرار هي شكل تمثيل المعرفة، وهي تلخص بيانات العينة بكثافة عالية. يمكن لشجرة القرار التعرف بدقة على فئة جميع العينات، ويمكنها أيضًا التعرف على فئة العينات الجديدة بشكل فعال.　

الفكرة الأساسية لخوارزمية شجرة القرار ID3 هي:

أولاً، يتم العثور على الصفة الأكثر قوة في الت评判، ثم تقسيم العينة إلى عدة مجموعات فرعية، ويتم اختيار الصفة الأكثر قوة في الت评判 لكل مجموعة فرعية لتحديد الفروع، ويستمر هذا العمل حتى يتمكن كل مجموعة فرعية من تحتوي فقط على بيانات من نفس النوع.

عمل J.R.Quinlan كان التركيز على استيراد مفهوم معرفة الربح من نظرية المعلومات، ويسميه معرفة الربح (information gain)، كقياس للقدرة الت评判ية للصفات، وتصميم خوارزمية بناء شجرة القرار التكرارية.

من الممكن فهم الأمثلة بشكل أفضل:

للمشكلة تصنيف المناخ، الصفات هي:
الطقس (A1) القيم الممكنة: مشمس، غائم، مطر
درجة الحرارة (A2) القيم الممكنة: باردة، مناسبة، حارة
الرطوبة (A3) القيم الممكنة: عالية، طبيعية
الرياح (A4) القيم الممكنة: مع الرياح، بدون رياح

كل عينة تنتمي إلى فئة مختلفة، في هذا المثال هناك فئتان فقط، P وN. العينات في الفئة P وN تُسمى الأمثلة الإيجابية والأمثلة السلبية على التوالي. يتم جمع بعض الأمثلة الإيجابية والأمثلة السلبية معًا للحصول على مجموعة التدريب.
تم الحصول على شجرة القرار من قبل خوارزمية ID3 لكل عينة في مجموعة التدريب الصحيحة، كما هو موضح في الشكل التالي.

أوراق الشجرة هي أسماء الفئات، مثل P أو N. العقد الأخرى تتكون من صفات العينة، وكل قيمة ممكنة للصفة تُعتبر فرعاً.
إذا كان يجب تصنيف عينة، يتم البدء من الجذر للاختبار، وتحديد الفروع بناءً على القيم الممكنة للصفات، والتحرك نحو العقد الأدنى، يتم اختبار العقد، ويستمر هذا العمل حتى الوصول إلى العقدة الأوراق، وتُصنف العينة بأنها تنتمي إلى الفئة المحددة في العقدة الأوراق.
إليك مثالاً محدداً باستخدام الرسوم البيانية الحالية،
وصف المناخ في صباح يوم معين هو:
الطقس: غائم
درجة الحرارة: باردة
الرطوبة: طبيعية
الرياح: بدون رياح

ما هو نوع المناخ الذي ينتمي إليه؟-------------من الشجرة يمكن التحقق من أن هذا النموذج ينتمي إلى الفئةP.　

يهدف ID3 إلى بناء شجرة القرار من مجموعة التدريب في جدول.في الواقع،هناك أكثر من شجرة قرار يمكنها تصنيف مجموعة التدريب بشكل صحيح.يستطيع خوارزمية ID3 لـ Quinlan بناء شجرة القرار التي تحتوي على عدد أقل من العقد.

خوارزمية ID3:

　　　　　1-حساب زيادة المعلومات لكل ميزة في مجموعة النماذج الحالية；
　　　　　2-اختيار الميزةAk التي تزيد من المعلومات بشكل أكبر؛
　　　　　3-تم جمع النماذج التي تأخذ نفس القيمة في الميزةAk في مجموعة فرعية،وكل قيمة تأخذها الميزةAk تؤدي إلى مجموعة فرعية؛
　　　　 4-للمجموعات الفرعية التي تحتوي على نماذج إيجابية وسلبية،تم استدعاء خوارزمية بناء الشجرة بشكل متكرر;
　　　　　5-إذا كانت المجموعة الفرعية تحتوي فقط على نماذج إيجابية أو سلبية،تم وضع علامةP أوN على الفرع المتباين،وتم التراجع إلى مكان الاستدعاء.

عندما يتم استخدامه في بناء الشجرة،يتم استخدامه بشكل متكرر.　

لحساب مشكلة تصنيف المناخ بشكل دقيق:
1-حساب معادلة ال熵: حيث S هو مجموعة النماذج،P(ui) هو احتمال الفئة i:

|S| تمثل عدد النماذج في مجموعة النماذج S،|ui| تمثل عدد النماذج في الفئة ui.لـ9 نماذج إيجابية و5 نماذج سلبية:
P(u1)=9/14
P(u2)=5/14
H(S)=(9/14)log(14/9)+(5/14)log(14/5)=0.94bit　

2-حساب زيادة المعلومات:

حيث A هي الميزة،Value(A) هي مجموعة القيم التي يمكن أن تأخذها الميزةA،v هي قيمة معينة من الميزةA،Sv هي مجموعة النماذج التي تحتوي على قيمةv من الميزةA،|Sv| هو عدد النماذج في Sv.

على سبيل المثال،بناءً على معادلة زيادة المعلومات،زيادة معلومات الميزةA1 هي

S=[9+،5-] //النماذج الأصلية تبلغ 14،9 إيجابية،5 سلبية
Sالسماء الصافية=[2+،3-]//نماذج السماء الصافية لـA1 تبلغ 5،2 إيجابية،3 سلبية
Sالغائمة=[4+،0-] //نماذج الغيوم المتوسطة لـA1 تبلغ 4،4 إيجابية،0 سلبية
Sالغيث=[3+،2-] //نماذج السماء الصافية لـA1 تبلغ 5،3 إيجابية،2 سلبية
لذلك　

8-النتيجة هي

7-تم اختيار الميزةA1 لأن زيادة المعلومات أكبر،لذلك يتم اختيارها كـجذر الشجرة.

4-بناء الجذر والورقة في شجرة القرار

5-اختيار الجذر والورقة في شجرة القرار،يختار خوارزمية ID3 الميزة التي تزيد من المعلومات بشكل أكبر كجذر الشجرة،في 14 نموذج،يتم تقسيم القيم الثلاثة للطقس إلى ثلاثة فروع،وكل فروع هي:

في S2،تنتمي جميع النماذج إلى الفئةP،لذلك يتم وضع علامةP على الفرع المتباين،بينما تحتوي الأنماط الأخرى على نماذج إيجابية وسلبية،ويتم استدعاء خوارزمية بناء الشجرة بشكل متكرر.

5-بناء الشجرة بشكل متكرر

2-تم استدعاء خوارزمية ID3 بشكل متكرر على مجموعات S1 وS3،وتم حساب زيادة المعلومات في كل مجموعة.
1-للـS1،فـمعلومات الزيادة في الميزة أكبر،ويتم استخدامها كـجذر الشجرة في هذا الفرع،ثم يتم تقسيمها إلى فرعين.النماذج التي تظهر الرطوبة العالية جميعها تنتمي إلى الفئةN،ويتم وضع علامةN على هذا الفرع.النماذج التي تظهر القيمة الطبيعية جميعها تنتمي إلى الفئةP،ويتم وضع علامةP على هذا الفرع.
2) بالنسبة لـ S3، هو أكبر في معلومات مكافأة التأثير، لذا يُستخدم كجذر فرع هذا. ثم تفرع نحو أسفل، عند وجود الرياح تكون جميعها من فئة N، ويُعرف هذا الفرع بـ N. عند عدم وجود الرياح تكون جميعها من فئة P، ويُعرف هذا الفرع بـ P.}

2. تنفيذ خوارزمية شجرة القرار في PYTHON

هذا الكود هو مثال من كتاب machine learning in action 第三章، تم التحقق منه.
　1. وظيفة لحساب قيمة shannon للبيانات المحددة:

تعريف func calcShannonEnt(dataSet): 
 #حساب قيمة shannon 
 numEntries = len(dataSet) 
 labelCounts = {} 
 لـ featVec في dataSet:  #إنشاء قاموس لجميع البيانات 
  currentLabel = featVec[-1] 
  إذا لم يكن currentLabel في مفاتيح labelCounts: 
   labelCounts[currentLabel] = 0 
  labelCounts[currentLabel] += 1 
 shannonEnt = 0.0 
 لـ key في labelCounts: 
  prob = float(labelCounts[key])/numEntries 
  shannonEnt -= prob*log(prob,2) #الحصول على قيمة الحساب 
 العودة shannonEnt 

　2. إنشاء وظيفة لإنشاء البيانات

تعريف func createDataSet(): 
 dataSet = [[1,1,'yes'], 
    [1,1, 'yes'], 
    [1,0,'no'], 
    [0,1,'no'], 
    [0,1,'no']] 
 labels = ['no surfacing','flippers'] 
 العودة dataSet, labels 

3. تقسيم مجموعة البيانات، وفقًا للخصائص المحددة

تعريف func splitDataSet(dataSet, axis, value): 
 retDataSet = [] 
 لـ featVec في dataSet: 
  إذا كان featVec[axis] == value: #استخراج الخاصية 
   reducedFeatVec = featVec[:axis] 
   reducedFeatVec.extend(featVec[axis+1:]) 
   retDataSet.append(reducedFeatVec) 
 return retDataSet 

4. اختيار أفضل طريقة تقسيم مجموعة البيانات

def chooseBestFeatureToSplit(dataSet): 
 numFeatures = len(dataSet[0])-1 
 baseEntropy = calcShannonEnt(dataSet) 
 bestInfoGain = 0.0; bestFeature = -1 
 for i in range(numFeatures): 
  featList = [example[i] for example in dataSet] 
  uniqueVals = set(featList) 
  newEntropy = 0.0 
  للفالوس المميزة في: 
   subDataSet = splitDataSet(dataSet, i , value) 
   prob = len(subDataSet)/float(len(dataSet)) 
   newEntropy +=prob * calcShannonEnt(subDataSet) 
  infoGain = baseEntropy - newEntropy 
  if(infoGain > bestInfoGain): 
   bestInfoGain = infoGain 
   bestFeature = i 
 return bestFeature 

5. إنشاء شجرة بالتكرار

الوظيفة المستخدمة لتحديد الاسم الأكثر تكرارًا للفئة

def majorityCnt(classList): 
 classCount = {} 
 for vote in classList: 
  if vote not in classCount.keys(): classCount[vote] = 0 
  classCount[vote] += 1 
 sortedClassCount = sorted(classCount.iteritems(), key=operator.itemgetter(1), reverse=True) 
 return sortedClassCount[0][0] 

كود الدالة لإنشاء الشجرة

def createTree(dataSet, labels): 
 classList = [example[-1] for example in dataSet] 
 # النوع هو نفسه، لذا توقف عن الفئة 
 if classList.count(classList[0]) == len(classList): 
  return classList[0] 
 # استكشاف جميع الخصائص والاختيار الخاصية الأكثر تكرارًا 
 if (len(dataSet[0]) == 1): 
  return majorityCnt(classList) 
 bestFeat = chooseBestFeatureToSplit(dataSet) 
 bestFeatLabel = labels[bestFeat] 
 myTree = {bestFeatLabel:{}} 
 del(labels[bestFeat]) 
 # الحصول على القائمة التي تحصل على جميع الخصائص 
 featValues = [example[bestFeat] for example in dataSet] 
 uniqueVals = set(featValues) 
 للفالوس المميزة في: 
  subLabels = labels[:] 
  myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet, bestFeat, value), subLabels) 
 return myTree 

ثم في إدخال الأوامر التالية في دليل النصوص في بايثون:

myDat, labels = trees.createDataSet() 
myTree = trees.createTree(myDat, labels) 
print myTree 

النتيجة هي:
{'no surfacing': {0: 'لا', 1: {'flippers': {0: 'لا', 1: 'نعم'}}}}

6. وظيفة للتصنيف باستخدام شجرة القرار الممارسة

def classify(inputTree, featLabels, testVec): 
 firstStr = inputTree.keys()[0] 
 secondDict = inputTree[firstStr] 
 featIndex = featLabels.index(firstStr) 
 for key in secondDict.keys(): 
  if testVec[featIndex] == key: 
   if type(secondDict[key]).__name__ == 'dict': 
    classLabel = classify(secondDict[key], featLabels, testVec) 
   else: classLabel = secondDict[key] 
 return classLabel 

في سطر الأوامر لـ Python، اكتب:
trees.classify(myTree,labels,[1,0])　

الحصول على النتيجة:
'لا'
تهاني. أوه نعم. قمت بذلك.!!!

هذا هو نهاية محتوى المقال، آمل أن يكون قد ساعدكم في التعلم، وأتمنى أن تشجعوا تعليمات الشعور.

بيان: محتوى هذا المقال تم جمعه من الإنترنت، يملك الحقوق الملكية للمساهمين في الإنترنت الذين قاموا بتحميله بشكل مستقل، ويملك هذا الموقع حقوق الملكية، لم يتم تعديل المحتوى بشكل يدوي، ولا يتحمل هذا الموقع أي مسؤولية قانونية مرتبطة. إذا اكتشفتم محتوى مخالف للحقوق النشرية، الرجاء إرسال بريد إلكتروني إلى: notice#oldtoolbag.com (الرجاء استبدال #بـ @ عند إرسال البريد الإلكتروني) للإبلاغ، وتقديم الأدلة ذات الصلة، وإذا تم التحقق من ذلك، سيتم حذف المحتوى المزعوم بشكل فوري.