API tools faq
paste
Advertisement
Nikolovska

[ВИ] лаб 5.1 Дрва на одлука

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