API tools faq
paste
Advertisement
nanorocks

exam_python_SNZ_2_decision_trees

nanorocks
Nov 5th, 2017
663
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 13.49 KB | None | 0 0
raw download clone embed print report
  1. """
  2.  
  3. Дрва на одлука (100 поени) Problem 2 (0 / 16)
  4. Да се промени алгоритмот за дрво на одлука така што ќе се изградат две дрва на одлука. Секое од дрвата го користи половина од податочното множество.
  5.  
  6. Да се промени начинот на печатење на дрвото така што покрај секој јазол, ќе се испечати и неговото ниво.
  7.  
  8. Двете дрва да се испечатат и потоа да се испечати резултатот од класификацијата.
  9.  
  10. Доколку некое од дрвата има само една класа тогаш се предвидува истата, но ако има повеќе од една треба да се избере таа со најголем број на инстанци. Ако во листот има неколку класи со ист број на инстанци да се предвиде првата класа по азбучен ред.
  11.  
  12. Доколку двете дрва ја предвидат истата класа да се испечати класата. Во спротивно да се испечати KONTRADIKCIJA.
  13.  
  14.  
  15.  
  16. """
  17.  
  18. trainingData = [
  19.     [6.3, 2.9, 5.6, 1.8, 'I. virginica'],
  20.     [6.5, 3.0, 5.8, 2.2, 'I. virginica'],
  21.     [7.6, 3.0, 6.6, 2.1, 'I. virginica'],
  22.     [4.9, 2.5, 4.5, 1.7, 'I. virginica'],
  23.     [7.3, 2.9, 6.3, 1.8, 'I. virginica'],
  24.     [6.7, 2.5, 5.8, 1.8, 'I. virginica'],
  25.     [7.2, 3.6, 6.1, 2.5, 'I. virginica'],
  26.     [6.5, 3.2, 5.1, 2.0, 'I. virginica'],
  27.     [6.4, 2.7, 5.3, 1.9, 'I. virginica'],
  28.     [6.8, 3.0, 5.5, 2.1, 'I. virginica'],
  29.     [5.7, 2.5, 5.0, 2.0, 'I. virginica'],
  30.     [5.8, 2.8, 5.1, 2.4, 'I. virginica'],
  31.     [6.4, 3.2, 5.3, 2.3, 'I. virginica'],
  32.     [6.5, 3.0, 5.5, 1.8, 'I. virginica'],
  33.     [7.7, 3.8, 6.7, 2.2, 'I. virginica'],
  34.     [7.7, 2.6, 6.9, 2.3, 'I. virginica'],
  35.     [6.0, 2.2, 5.0, 1.5, 'I. virginica'],
  36.     [6.9, 3.2, 5.7, 2.3, 'I. virginica'],
  37.     [5.6, 2.8, 4.9, 2.0, 'I. virginica'],
  38.     [7.7, 2.8, 6.7, 2.0, 'I. virginica'],
  39.     [6.3, 2.7, 4.9, 1.8, 'I. virginica'],
  40.     [6.7, 3.3, 5.7, 2.1, 'I. virginica'],
  41.     [7.2, 3.2, 6.0, 1.8, 'I. virginica'],
  42.     [6.2, 2.8, 4.8, 1.8, 'I. virginica'],
  43.     [6.1, 3.0, 4.9, 1.8, 'I. virginica'],
  44.     [6.4, 2.8, 5.6, 2.1, 'I. virginica'],
  45.     [7.2, 3.0, 5.8, 1.6, 'I. virginica'],
  46.     [7.4, 2.8, 6.1, 1.9, 'I. virginica'],
  47.     [7.9, 3.8, 6.4, 2.0, 'I. virginica'],
  48.     [6.4, 2.8, 5.6, 2.2, 'I. virginica'],
  49.     [6.3, 2.8, 5.1, 1.5, 'I. virginica'],
  50.     [6.1, 2.6, 5.6, 1.4, 'I. virginica'],
  51.     [7.7, 3.0, 6.1, 2.3, 'I. virginica'],
  52.     [6.3, 3.4, 5.6, 2.4, 'I. virginica'],
  53.     [5.1, 3.5, 1.4, 0.2, 'I. setosa'],
  54.     [4.9, 3.0, 1.4, 0.2, 'I. setosa'],
  55.     [4.7, 3.2, 1.3, 0.2, 'I. setosa'],
  56.     [4.6, 3.1, 1.5, 0.2, 'I. setosa'],
  57.     [5.0, 3.6, 1.4, 0.2, 'I. setosa'],
  58.     [5.4, 3.9, 1.7, 0.4, 'I. setosa'],
  59.     [4.6, 3.4, 1.4, 0.3, 'I. setosa'],
  60.     [5.0, 3.4, 1.5, 0.2, 'I. setosa'],
  61.     [4.4, 2.9, 1.4, 0.2, 'I. setosa'],
  62.     [4.9, 3.1, 1.5, 0.1, 'I. setosa'],
  63.     [5.4, 3.7, 1.5, 0.2, 'I. setosa'],
  64.     [4.8, 3.4, 1.6, 0.2, 'I. setosa'],
  65.     [4.8, 3.0, 1.4, 0.1, 'I. setosa'],
  66.     [4.3, 3.0, 1.1, 0.1, 'I. setosa'],
  67.     [5.8, 4.0, 1.2, 0.2, 'I. setosa'],
  68.     [5.7, 4.4, 1.5, 0.4, 'I. setosa'],
  69.     [5.4, 3.9, 1.3, 0.4, 'I. setosa'],
  70.     [5.1, 3.5, 1.4, 0.3, 'I. setosa'],
  71.     [5.7, 3.8, 1.7, 0.3, 'I. setosa'],
  72.     [5.1, 3.8, 1.5, 0.3, 'I. setosa'],
  73.     [5.4, 3.4, 1.7, 0.2, 'I. setosa'],
  74.     [5.1, 3.7, 1.5, 0.4, 'I. setosa'],
  75.     [4.6, 3.6, 1.0, 0.2, 'I. setosa'],
  76.     [5.1, 3.3, 1.7, 0.5, 'I. setosa'],
  77.     [4.8, 3.4, 1.9, 0.2, 'I. setosa'],
  78.     [5.0, 3.0, 1.6, 0.2, 'I. setosa'],
  79.     [5.0, 3.4, 1.6, 0.4, 'I. setosa'],
  80.     [5.2, 3.5, 1.5, 0.2, 'I. setosa'],
  81.     [5.2, 3.4, 1.4, 0.2, 'I. setosa'],
  82.     [5.5, 2.3, 4.0, 1.3, 'I. versicolor'],
  83.     [6.5, 2.8, 4.6, 1.5, 'I. versicolor'],
  84.     [5.7, 2.8, 4.5, 1.3, 'I. versicolor'],
  85.     [6.3, 3.3, 4.7, 1.6, 'I. versicolor'],
  86.     [4.9, 2.4, 3.3, 1.0, 'I. versicolor'],
  87.     [6.6, 2.9, 4.6, 1.3, 'I. versicolor'],
  88.     [5.2, 2.7, 3.9, 1.4, 'I. versicolor'],
  89.     [5.0, 2.0, 3.5, 1.0, 'I. versicolor'],
  90.     [5.9, 3.0, 4.2, 1.5, 'I. versicolor'],
  91.     [6.0, 2.2, 4.0, 1.0, 'I. versicolor'],
  92.     [6.1, 2.9, 4.7, 1.4, 'I. versicolor'],
  93.     [5.6, 2.9, 3.6, 1.3, 'I. versicolor'],
  94.     [6.7, 3.1, 4.4, 1.4, 'I. versicolor'],
  95.     [5.6, 3.0, 4.5, 1.5, 'I. versicolor'],
  96.     [5.8, 2.7, 4.1, 1.0, 'I. versicolor'],
  97.     [6.2, 2.2, 4.5, 1.5, 'I. versicolor'],
  98.     [5.6, 2.5, 3.9, 1.1, 'I. versicolor'],
  99.     [5.9, 3.2, 4.8, 1.8, 'I. versicolor'],
  100.     [6.1, 2.8, 4.0, 1.3, 'I. versicolor'],
  101.     [6.3, 2.5, 4.9, 1.5, 'I. versicolor'],
  102.     [6.1, 2.8, 4.7, 1.2, 'I. versicolor'],
  103.     [6.4, 2.9, 4.3, 1.3, 'I. versicolor'],
  104.     [6.6, 3.0, 4.4, 1.4, 'I. versicolor'],
  105.     [6.8, 2.8, 4.8, 1.4, 'I. versicolor'],
  106.     [6.7, 3.0, 5.0, 1.7, 'I. versicolor'],
  107.     [6.0, 2.9, 4.5, 1.5, 'I. versicolor'],
  108.     [5.7, 2.6, 3.5, 1.0, 'I. versicolor'],
  109.     [5.5, 2.4, 3.8, 1.1, 'I. versicolor'],
  110.     [5.5, 2.4, 3.7, 1.0, 'I. versicolor'],
  111.     [5.8, 2.7, 3.9, 1.2, 'I. versicolor'],
  112.     [6.0, 2.7, 5.1, 1.6, 'I. versicolor'],
  113.     [5.4, 3.0, 4.5, 1.5, 'I. versicolor'],
  114.     [6.0, 3.4, 4.5, 1.6, 'I. versicolor'],
  115.     [6.7, 3.1, 4.7, 1.5, 'I. versicolor'],
  116.     [6.3, 2.3, 4.4, 1.3, 'I. versicolor'],
  117.     [5.6, 3.0, 4.1, 1.3, 'I. versicolor'],
  118.     [5.5, 2.5, 4.0, 1.3, 'I. versicolor'],
  119.     [5.5, 2.6, 4.4, 1.2, 'I. versicolor'],
  120.     [6.1, 3.0, 4.6, 1.4, 'I. versicolor'],
  121.     [5.8, 2.6, 4.0, 1.2, 'I. versicolor'],
  122.     [5.0, 2.3, 3.3, 1.0, 'I. versicolor'],
  123.     [5.6, 2.7, 4.2, 1.3, 'I. versicolor'],
  124.     [5.7, 3.0, 4.2, 1.2, 'I. versicolor'],
  125.     [5.7, 2.9, 4.2, 1.3, 'I. versicolor'],
  126.     [6.2, 2.9, 4.3, 1.3, 'I. versicolor'],
  127.     [5.1, 2.5, 3.0, 1.1, 'I. versicolor'],
  128.     [5.7, 2.8, 4.1, 1.3, 'I. versicolor'],
  129.     [6.4, 3.1, 5.5, 1.8, 'I. virginica'],
  130.     [6.0, 3.0, 4.8, 1.8, 'I. virginica'],
  131.     [6.9, 3.1, 5.4, 2.1, 'I. virginica'],
  132.     [6.7, 3.1, 5.6, 2.4, 'I. virginica'],
  133.     [6.9, 3.1, 5.1, 2.3, 'I. virginica'],
  134.     [5.8, 2.7, 5.1, 1.9, 'I. virginica'],
  135.     [6.8, 3.2, 5.9, 2.3, 'I. virginica'],
  136.     [6.7, 3.3, 5.7, 2.5, 'I. virginica'],
  137.     [6.7, 3.0, 5.2, 2.3, 'I. virginica'],
  138.     [6.3, 2.5, 5.0, 1.9, 'I. virginica'],
  139.     [6.5, 3.0, 5.2, 2.0, 'I. virginica'],
  140.     [6.2, 3.4, 5.4, 2.3, 'I. virginica'],
  141.     [4.7, 3.2, 1.6, 0.2, 'I. setosa'],
  142.     [4.8, 3.1, 1.6, 0.2, 'I. setosa'],
  143.     [5.4, 3.4, 1.5, 0.4, 'I. setosa'],
  144.     [5.2, 4.1, 1.5, 0.1, 'I. setosa'],
  145.     [5.5, 4.2, 1.4, 0.2, 'I. setosa'],
  146.     [4.9, 3.1, 1.5, 0.2, 'I. setosa'],
  147.     [5.0, 3.2, 1.2, 0.2, 'I. setosa'],
  148.     [5.5, 3.5, 1.3, 0.2, 'I. setosa'],
  149.     [4.9, 3.6, 1.4, 0.1, 'I. setosa'],
  150.     [4.4, 3.0, 1.3, 0.2, 'I. setosa'],
  151.     [5.1, 3.4, 1.5, 0.2, 'I. setosa'],
  152.     [5.0, 3.5, 1.3, 0.3, 'I. setosa'],
  153.     [4.5, 2.3, 1.3, 0.3, 'I. setosa'],
  154.     [4.4, 3.2, 1.3, 0.2, 'I. setosa'],
  155.     [5.0, 3.5, 1.6, 0.6, 'I. setosa'],
  156.     [5.1, 3.8, 1.9, 0.4, 'I. setosa'],
  157.     [4.8, 3.0, 1.4, 0.3, 'I. setosa'],
  158.     [5.1, 3.8, 1.6, 0.2, 'I. setosa'],
  159.     [5.9, 3.0, 5.1, 1.8, 'I. virginica']
  160. ]
  161.  
  162.  
  163. class decisionnode:
  164.     def __init__(self, col=-1, value=None, results=None, tb=None, fb=None,l=None):
  165.         self.col = col
  166.         self.value = value
  167.         self.results = results
  168.         self.tb = tb
  169.         self.fb = fb
  170.         self.l = l
  171.  
  172.  
  173. def sporedi_broj(row, column, value):
  174.     return row[column] >= value
  175.  
  176.  
  177. def sporedi_string(row, column, value):
  178.     return row[column] == value
  179.  
  180.  
  181. # Divides a set on a specific column. Can handle numeric
  182. # or nominal values
  183. def divideset(rows, column, value):
  184.     # Make a function that tells us if a row is in
  185.     # the first group (true) or the second group (false)
  186.     split_function = None
  187.     if isinstance(value, int) or isinstance(value, float):  # ako vrednosta so koja sporeduvame e od tip int ili float
  188.         # split_function=lambda row:row[column]>=value # togas vrati funkcija cij argument e row i vrakja vrednost true ili false
  189.         split_function = sporedi_broj
  190.     else:
  191.         # split_function=lambda row:row[column]==value # ako vrednosta so koja sporeduvame e od drug tip (string)
  192.         split_function = sporedi_string
  193.  
  194.     # Divide the rows into two sets and return them
  195.     set_false = []
  196.     set_true = []
  197.     for row in rows:
  198.         if split_function(row, column, value):
  199.             set_true.append(row)
  200.         else:
  201.             set_false.append(row)
  202.     set1 = [row for row in rows if
  203.             split_function(row, column, value)]  # za sekoj row od rows za koj split_function vrakja true
  204.     set2 = [row for row in rows if
  205.             not split_function(row, column, value)]  # za sekoj row od rows za koj split_function vrakja false
  206.     # return (set1, set2)
  207.     return (set_true, set_false)
  208.  
  209.  
  210. #st, sf = divideset(my_data, 3, 20)
  211. #print(sf)
  212. #print(st)
  213.  
  214.  
  215. # Create counts of possible results (the last column of
  216. # each row is the result)
  217. def uniquecounts(rows):
  218.     results = {}
  219.     for row in rows:
  220.         # The result is the last column
  221.         r = row[-1]
  222.         results.setdefault(r, 0)
  223.         results[r] += 1
  224.  
  225.     return results
  226.  
  227.  
  228. #print(uniquecounts(my_data))
  229. #print(uniquecounts(st))
  230. #print(uniquecounts(sf))
  231.  
  232.  
  233. # Probability that a randomly placed item will
  234. # be in the wrong category
  235.  
  236. def log2(x):
  237.     from math import log
  238.     l2 = log(x) / log(2)
  239.     return l2
  240.  
  241.  
  242. # Entropy is the sum of p(x)log(p(x)) across all
  243. # the different possible results
  244. def entropy(rows):
  245.     results = uniquecounts(rows)
  246.     # Now calculate the entropy
  247.     ent = 0.0
  248.     for r in results.keys():
  249.         p = float(results[r]) / len(rows)
  250.         ent = ent - p * log2(p)
  251.     return ent
  252.  
  253.  
  254. #print(entropy(my_data), entropy(st), entropy(sf))
  255.  
  256.  
  257. def buildtree(rows,l=-1, scoref=entropy):
  258.     if len(rows) == 0: return decisionnode()
  259.     current_score = scoref(rows)
  260.  
  261.     # Set up some variables to track the best criteria
  262.     best_gain = 0.0
  263.     best_column = -1
  264.     best_value = None
  265.     best_subsetf = None
  266.     best_subsett = None
  267.  
  268.     column_count = len(rows[0]) - 1
  269.     for col in range(column_count):
  270.         # Generate the list of different values in
  271.         # this column
  272.         column_values = set()
  273.         for row in rows:
  274.             column_values.add(row[col])
  275.         # Now try dividing the rows up for each value
  276.         # in this column
  277.         for value in column_values:
  278.             (set1, set2) = divideset(rows, col, value)
  279.  
  280.             # Information gain
  281.             p = float(len(set1)) / len(rows)
  282.             gain = current_score - p * scoref(set1) - (1 - p) * scoref(set2)
  283.             if gain > best_gain and len(set1) > 0 and len(set2) > 0:
  284.                 best_gain = gain
  285.                 best_column = col
  286.                 best_value = value
  287.                 best_subsett = set1
  288.                 best_subsetf = set2
  289.                 # best_criteria = (col, value)
  290.                 # best_sets = (set1, set2)
  291.  
  292.     # Create the subbranches
  293.     if best_gain > 0:
  294.         l = l + 1
  295.         trueBranch = buildtree(best_subsett,l, scoref)
  296.         falseBranch = buildtree(best_subsetf,l, scoref)
  297.         return decisionnode(col=best_column, value=best_value,
  298.                             tb=trueBranch, fb=falseBranch,l = l)
  299.     else:
  300.         return decisionnode(results=uniquecounts(rows))
  301.  
  302.  
  303. def printtree(tree, indent=''):
  304.     # Is this a leaf node?
  305.     if tree.results != None:
  306.         print str(sorted(tree.results.items()))
  307.     else:
  308.         # Print the criteria
  309.         print( str(tree.col) + ':' + str(tree.value) + '? '+'Level='+str(tree.l))
  310.         # Print the branches
  311.         print(indent + 'T->'),
  312.         printtree(tree.tb, indent + '  ')
  313.         print(indent + 'F->'),
  314.         printtree(tree.fb, indent + '  ')
  315.  
  316.  
  317. def classify(observation, tree):
  318.     if tree.results != None:
  319.  
  320.          maxi=0
  321.         # print tree.results
  322.         #for k in tree.results:
  323.         #    if tree.results[k]>=maxi:
  324.         #        maxi=tree.results[k]
  325.         #for k in tree.results:
  326.         #    if tree.results[k] == maxi:
  327.         #        lista.append(k)
  328.         #lista.sort()
  329.         #return lista[0]
  330.         return tree.results
  331.     else:
  332.         vrednost = observation[tree.col]
  333.         branch = None
  334.  
  335.         if isinstance(vrednost, int) or isinstance(vrednost, float):
  336.             if vrednost >= tree.value:
  337.                 branch = tree.tb
  338.             else:
  339.                 branch = tree.fb
  340.         else:
  341.             if vrednost == tree.value:
  342.                 branch = tree.tb
  343.             else:
  344.                 branch = tree.fb
  345.  
  346.         return classify(observation, branch)
  347.  
  348.  
  349.  
  350. if __name__ == '__main__':
  351.  
  352.     arg1 = 1
  353.     arg2 = 2.2
  354.     arg3 = 4.0
  355.     arg4 = 1.1
  356.     cl = 'I. virginica'
  357.  
  358.     tmp = [arg1,arg2,arg3,arg4,cl]
  359.  
  360.     p1 = []
  361.     p2  = []
  362.     leng = len(trainingData)
  363.  
  364.     for i in range(0,leng/2):
  365.         p1.append(trainingData[i])
  366.  
  367.     for i in range(leng/2,len(trainingData)):
  368.         p2.append(trainingData[i])
  369.  
  370.     d1 = buildtree(p1)
  371.     d2 = buildtree(p2)
  372.  
  373.     print 'DRVO 1\n',printtree(d1)
  374.     print 'DRVO 2\n', printtree(d2)
  375.  
  376.     k1 = classify(tmp,d1)
  377.     k2 = classify(tmp,d2)
  378.  
  379.     print k1
  380.     print k2
  381.  
  382.     if k1.keys()[0] == k2.keys()[0]:
  383.         print k1.keys()[0]
  384.     if(k1.values()[0]>k2.values()[0]):
  385.         print k1.keys()[0]
  386.         print 'KONTRADIKCIJA'
  387.     if(k2.values()[0]>k1.values()[0]):
  388.         print k2.keys()[0]
  389.         print 'KONTRADIKCIJA'
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!