SHARE
TWEET

Untitled

a guest Nov 17th, 2019 83 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. dataset = [
  2.     [6.3, 2.9, 5.6, 1.8, 0],
  3.     [6.5, 3.0, 5.8, 2.2, 0],
  4.     [7.6, 3.0, 6.6, 2.1, 0],
  5.     [4.9, 2.5, 4.5, 1.7, 0],
  6.     [7.3, 2.9, 6.3, 1.8, 0],
  7.     [6.7, 2.5, 5.8, 1.8, 0],
  8.     [7.2, 3.6, 6.1, 2.5, 0],
  9.     [6.5, 3.2, 5.1, 2.0, 0],
  10.     [6.4, 2.7, 5.3, 1.9, 0],
  11.     [6.8, 3.0, 5.5, 2.1, 0],
  12.     [5.7, 2.5, 5.0, 2.0, 0],
  13.     [5.8, 2.8, 5.1, 2.4, 0],
  14.     [6.4, 3.2, 5.3, 2.3, 0],
  15.     [6.5, 3.0, 5.5, 1.8, 0],
  16.     [7.7, 3.8, 6.7, 2.2, 0],
  17.     [7.7, 2.6, 6.9, 2.3, 0],
  18.     [6.0, 2.2, 5.0, 1.5, 0],
  19.     [6.9, 3.2, 5.7, 2.3, 0],
  20.     [5.6, 2.8, 4.9, 2.0, 0],
  21.     [7.7, 2.8, 6.7, 2.0, 0],
  22.     [6.3, 2.7, 4.9, 1.8, 0],
  23.     [6.7, 3.3, 5.7, 2.1, 0],
  24.     [7.2, 3.2, 6.0, 1.8, 0],
  25.     [6.2, 2.8, 4.8, 1.8, 0],
  26.     [6.1, 3.0, 4.9, 1.8, 0],
  27.     [6.4, 2.8, 5.6, 2.1, 0],
  28.     [7.2, 3.0, 5.8, 1.6, 0],
  29.     [7.4, 2.8, 6.1, 1.9, 0],
  30.     [7.9, 3.8, 6.4, 2.0, 0],
  31.     [6.4, 2.8, 5.6, 2.2, 0],
  32.     [6.3, 2.8, 5.1, 1.5, 0],
  33.     [6.1, 2.6, 5.6, 1.4, 0],
  34.     [7.7, 3.0, 6.1, 2.3, 0],
  35.     [6.3, 3.4, 5.6, 2.4, 0],
  36.     [5.1, 3.5, 1.4, 0.2, 1],
  37.     [4.9, 3.0, 1.4, 0.2, 1],
  38.     [4.7, 3.2, 1.3, 0.2, 1],
  39.     [4.6, 3.1, 1.5, 0.2, 1],
  40.     [5.0, 3.6, 1.4, 0.2, 1],
  41.     [5.4, 3.9, 1.7, 0.4, 1],
  42.     [4.6, 3.4, 1.4, 0.3, 1],
  43.     [5.0, 3.4, 1.5, 0.2, 1],
  44.     [4.4, 2.9, 1.4, 0.2, 1],
  45.     [4.9, 3.1, 1.5, 0.1, 1],
  46.     [5.4, 3.7, 1.5, 0.2, 1],
  47.     [4.8, 3.4, 1.6, 0.2, 1],
  48.     [4.8, 3.0, 1.4, 0.1, 1],
  49.     [4.3, 3.0, 1.1, 0.1, 1],
  50.     [5.8, 4.0, 1.2, 0.2, 1],
  51.     [5.7, 4.4, 1.5, 0.4, 1],
  52.     [5.4, 3.9, 1.3, 0.4, 1],
  53.     [5.1, 3.5, 1.4, 0.3, 1],
  54.     [5.7, 3.8, 1.7, 0.3, 1],
  55.     [5.1, 3.8, 1.5, 0.3, 1],
  56.     [5.4, 3.4, 1.7, 0.2, 1],
  57.     [5.1, 3.7, 1.5, 0.4, 1],
  58.     [4.6, 3.6, 1.0, 0.2, 1],
  59.     [5.1, 3.3, 1.7, 0.5, 1],
  60.     [4.8, 3.4, 1.9, 0.2, 1],
  61.     [5.0, 3.0, 1.6, 0.2, 1],
  62.     [5.0, 3.4, 1.6, 0.4, 1],
  63.     [5.2, 3.5, 1.5, 0.2, 1],
  64.     [5.2, 3.4, 1.4, 0.2, 1],
  65.     [5.5, 2.3, 4.0, 1.3, 2],
  66.     [6.5, 2.8, 4.6, 1.5, 2],
  67.     [5.7, 2.8, 4.5, 1.3, 2],
  68.     [6.3, 3.3, 4.7, 1.6, 2],
  69.     [4.9, 2.4, 3.3, 1.0, 2],
  70.     [6.6, 2.9, 4.6, 1.3, 2],
  71.     [5.2, 2.7, 3.9, 1.4, 2],
  72.     [5.0, 2.0, 3.5, 1.0, 2],
  73.     [5.9, 3.0, 4.2, 1.5, 2],
  74.     [6.0, 2.2, 4.0, 1.0, 2],
  75.     [6.1, 2.9, 4.7, 1.4, 2],
  76.     [5.6, 2.9, 3.6, 1.3, 2],
  77.     [6.7, 3.1, 4.4, 1.4, 2],
  78.     [5.6, 3.0, 4.5, 1.5, 2],
  79.     [5.8, 2.7, 4.1, 1.0, 2],
  80.     [6.2, 2.2, 4.5, 1.5, 2],
  81.     [5.6, 2.5, 3.9, 1.1, 2],
  82.     [5.9, 3.2, 4.8, 1.8, 2],
  83.     [6.1, 2.8, 4.0, 1.3, 2],
  84.     [6.3, 2.5, 4.9, 1.5, 2],
  85.     [6.1, 2.8, 4.7, 1.2, 2],
  86.     [6.4, 2.9, 4.3, 1.3, 2],
  87.     [6.6, 3.0, 4.4, 1.4, 2],
  88.     [6.8, 2.8, 4.8, 1.4, 2],
  89.     [6.7, 3.0, 5.0, 1.7, 2],
  90.     [6.0, 2.9, 4.5, 1.5, 2],
  91.     [5.7, 2.6, 3.5, 1.0, 2],
  92.     [5.5, 2.4, 3.8, 1.1, 2],
  93.     [5.4, 3.0, 4.5, 1.5, 2],
  94.     [6.0, 3.4, 4.5, 1.6, 2],
  95.     [6.7, 3.1, 4.7, 1.5, 2],
  96.     [6.3, 2.3, 4.4, 1.3, 2],
  97.     [5.6, 3.0, 4.1, 1.3, 2],
  98.     [5.5, 2.5, 4.0, 1.3, 2],
  99.     [5.5, 2.6, 4.4, 1.2, 2],
  100.     [6.1, 3.0, 4.6, 1.4, 2],
  101.     [5.8, 2.6, 4.0, 1.2, 2],
  102.     [5.0, 2.3, 3.3, 1.0, 2],
  103.     [5.6, 2.7, 4.2, 1.3, 2],
  104.     [5.7, 3.0, 4.2, 1.2, 2],
  105.     [5.7, 2.9, 4.2, 1.3, 2],
  106.     [6.2, 2.9, 4.3, 1.3, 2],
  107.     [5.1, 2.5, 3.0, 1.1, 2],
  108.     [5.7, 2.8, 4.1, 1.3, 2],
  109.     [6.4, 3.1, 5.5, 1.8, 0],
  110.     [6.0, 3.0, 4.8, 1.8, 0],
  111.     [6.9, 3.1, 5.4, 2.1, 0],
  112.     [6.8, 3.2, 5.9, 2.3, 0],
  113.     [6.7, 3.3, 5.7, 2.5, 0],
  114.     [6.7, 3.0, 5.2, 2.3, 0],
  115.     [6.3, 2.5, 5.0, 1.9, 0],
  116.     [6.5, 3.0, 5.2, 2.0, 0],
  117.     [6.2, 3.4, 5.4, 2.3, 0],
  118.     [4.7, 3.2, 1.6, 0.2, 1],
  119.     [4.8, 3.1, 1.6, 0.2, 1],
  120.     [5.4, 3.4, 1.5, 0.4, 1],
  121.     [5.2, 4.1, 1.5, 0.1, 1],
  122.     [5.5, 4.2, 1.4, 0.2, 1],
  123.     [4.9, 3.1, 1.5, 0.2, 1],
  124.     [5.0, 3.2, 1.2, 0.2, 1],
  125.     [5.5, 3.5, 1.3, 0.2, 1],
  126.     [4.9, 3.6, 1.4, 0.1, 1],
  127.     [4.4, 3.0, 1.3, 0.2, 1],
  128.     [5.1, 3.4, 1.5, 0.2, 1],
  129.     [5.0, 3.5, 1.3, 0.3, 1],
  130.     [4.5, 2.3, 1.3, 0.3, 1],
  131.     [4.4, 3.2, 1.3, 0.2, 1],
  132.     [5.0, 3.5, 1.6, 0.6, 1],
  133.     [5.9, 3.0, 5.1, 1.8, 0],
  134.     [5.1, 3.8, 1.9, 0.4, 1],
  135.     [4.8, 3.0, 1.4, 0.3, 1],
  136.     [5.1, 3.8, 1.6, 0.2, 1],
  137.     [5.5, 2.4, 3.7, 1.0, 2],
  138.     [5.8, 2.7, 3.9, 1.2, 2],
  139.     [6.0, 2.7, 5.1, 1.6, 2],
  140.     [6.7, 3.1, 5.6, 2.4, 0],
  141.     [6.9, 3.1, 5.1, 2.3, 0],
  142.     [5.8, 2.7, 5.1, 1.9, 0],
  143. ]
  144. from math import log
  145.  
  146.  
  147. def unique_counts(rows):
  148.     """Креирај броење на можни резултати (последната колона
  149.     во секоја редица е класата)
  150.  
  151.     :param rows: dataset
  152.     :type rows: list
  153.     :return: dictionary of possible classes as keys and count
  154.              as values
  155.     :rtype: dict
  156.     """
  157.     results = {}
  158.     for row in rows:
  159.         # Клацата е последната колона
  160.         r = row[len(row) - 1]
  161.         if r not in results:
  162.             results[r] = 0
  163.         results[r] += 1
  164.     return results
  165.  
  166.  
  167. def gini_impurity(rows):
  168.     """Probability that a randomly placed item will
  169.     be in the wrong category
  170.  
  171.     :param rows: dataset
  172.     :type rows: list
  173.     :return: Gini impurity
  174.     :rtype: float
  175.     """
  176.     total = len(rows)
  177.     counts = unique_counts(rows)
  178.     imp = 0
  179.     for k1 in counts:
  180.         p1 = float(counts[k1]) / total
  181.         for k2 in counts:
  182.             if k1 == k2:
  183.                 continue
  184.             p2 = float(counts[k2]) / total
  185.             imp += p1 * p2
  186.     return imp
  187.  
  188.  
  189. def entropy(rows):
  190.     """Ентропијата е сума од p(x)log(p(x)) за сите
  191.     можни резултати
  192.  
  193.     :param rows: податочно множество
  194.     :type rows: list
  195.     :return: вредност за ентропијата
  196.     :rtype: float
  197.     """
  198.     log2 = lambda x: log(x) / log(2)
  199.     results = unique_counts(rows)
  200.     # Пресметка на ентропијата
  201.     ent = 0.0
  202.     for r in results.keys():
  203.         p = float(results[r]) / len(rows)
  204.         ent = ent - p * log2(p)
  205.     return ent
  206.  
  207.  
  208. class DecisionNode:
  209.     def __init__(self, col=-1, value=None, results=None, tb=None, fb=None):
  210.         """
  211.         :param col: индексот на колоната (атрибутот) од тренинг множеството
  212.                     која се претставува со оваа инстанца т.е. со овој јазол
  213.         :type col: int
  214.         :param value: вредноста на јазолот според кој се дели дрвото
  215.         :param results: резултати за тековната гранка, вредност (различна
  216.                         од None) само кај јазлите-листови во кои се донесува
  217.                         одлуката.
  218.         :type results: dict
  219.         :param tb: гранка која се дели од тековниот јазол кога вредноста е
  220.                    еднаква на value
  221.         :type tb: DecisionNode
  222.         :param fb: гранка која се дели од тековниот јазол кога вредноста е
  223.                    различна од value
  224.         :type fb: DecisionNode
  225.         """
  226.         self.col = col
  227.         self.value = value
  228.         self.results = results
  229.         self.tb = tb
  230.         self.fb = fb
  231.  
  232.  
  233. def compare_numerical(row, column, value):
  234.     """Споредба на вредноста од редицата на посакуваната колона со
  235.     зададена нумеричка вредност
  236.  
  237.     :param row: дадена редица во податочното множество
  238.     :type row: list
  239.     :param column: индекс на колоната (атрибутот) од тренирачкото множество
  240.     :type column: int
  241.     :param value: вредност на јазелот во согласност со кој се прави
  242.                   поделбата во дрвото
  243.     :type value: int or float
  244.     :return: True ако редицата >= value, инаку False
  245.     :rtype: bool
  246.     """
  247.     return row[column] >= value
  248.  
  249.  
  250. def compare_nominal(row, column, value):
  251.     """Споредба на вредноста од редицата на посакуваната колона со
  252.     зададена номинална вредност
  253.  
  254.     :param row: дадена редица во податочното множество
  255.     :type row: list
  256.     :param column: индекс на колоната (атрибутот) од тренирачкото множество
  257.     :type column: int
  258.     :param value: вредност на јазелот во согласност со кој се прави
  259.                   поделбата во дрвото
  260.     :type value: str
  261.     :return: True ако редицата == value, инаку False
  262.     :rtype: bool
  263.     """
  264.     return row[column] == value
  265.  
  266.  
  267. def divide_set(rows, column, value):
  268.     """Поделба на множеството според одредена колона. Може да се справи
  269.     со нумерички или номинални вредности.
  270.  
  271.     :param rows: тренирачко множество
  272.     :type rows: list(list)
  273.     :param column: индекс на колоната (атрибутот) од тренирачкото множество
  274.     :type column: int
  275.     :param value: вредност на јазелот во зависност со кој се прави поделбата
  276.                   во дрвото за конкретната гранка
  277.     :type value: int or float or str
  278.     :return: поделени подмножества
  279.     :rtype: list, list
  280.     """
  281.     # Направи функција која ни кажува дали редицата е во
  282.     # првата група (True) или втората група (False)
  283.     if isinstance(value, int) or isinstance(value, float):
  284.         # ако вредноста за споредба е од тип int или float
  285.         split_function = compare_numerical
  286.     else:
  287.         # ако вредноста за споредба е од друг тип (string)
  288.         split_function = compare_nominal
  289.  
  290.     # Подели ги редиците во две подмножества и врати ги
  291.     # за секој ред за кој split_function враќа True
  292.     set1 = [row for row in rows if
  293.             split_function(row, column, value)]
  294.     # set1 = []
  295.     # for row in rows:
  296.     #     if not split_function(row, column, value):
  297.     #         set1.append(row)
  298.     # за секој ред за кој split_function враќа False
  299.     set2 = [row for row in rows if
  300.             not split_function(row, column, value)]
  301.     return set1, set2
  302.  
  303.  
  304. def build_tree(rows, scoref=entropy):
  305.     """Градење на дрво на одлука.
  306.  
  307.     :param rows: тренирачко множество
  308.     :type rows: list(list)
  309.     :param scoref: функција за одбирање на најдобар атрибут во даден чекор
  310.     :type scoref: function
  311.     :return: коренот на изграденото дрво на одлука
  312.     :rtype: DecisionNode object
  313.     """
  314.     if len(rows) == 0:
  315.         return DecisionNode()
  316.     current_score = scoref(rows)
  317.  
  318.     # променливи со кои следиме кој критериум е најдобар
  319.     best_gain = 0.0
  320.     best_criteria = None
  321.     best_sets = None
  322.  
  323.     column_count = len(rows[0]) - 1
  324.     for col in range(0, column_count):
  325.         # за секоја колона (col се движи во интервалот од 0 до
  326.         # column_count - 1)
  327.         # Следниов циклус е за генерирање на речник од различни
  328.         # вредности во оваа колона
  329.         column_values = {}
  330.         for row in rows:
  331.             column_values[row[col]] = 1
  332.         # за секоја редица се зема вредноста во оваа колона и се
  333.         # поставува како клуч во column_values
  334.         for value in column_values.keys():
  335.             (set1, set2) = divide_set(rows, col, value)
  336.  
  337.             # Информациона добивка
  338.             p = float(len(set1)) / len(rows)
  339.             gain = current_score - p * scoref(set1) - (1 - p) * scoref(set2)
  340.             if gain > best_gain and len(set1) > 0 and len(set2) > 0:
  341.                 best_gain = gain
  342.                 best_criteria = (col, value)
  343.                 best_sets = (set1, set2)
  344.  
  345.     # Креирај ги подгранките
  346.     if best_gain > 0:
  347.         true_branch = build_tree(best_sets[0], scoref)
  348.         false_branch = build_tree(best_sets[1], scoref)
  349.         return DecisionNode(col=best_criteria[0], value=best_criteria[1],
  350.                             tb=true_branch, fb=false_branch)
  351.     else:
  352.         return DecisionNode(results=unique_counts(rows))
  353.  
  354.  
  355. def print_tree(tree, indent=''):
  356.     """Принтање на дрво на одлука
  357.  
  358.     :param tree: коренот на дрвото на одлучување
  359.     :type tree: DecisionNode object
  360.     :param indent:
  361.     :return: None
  362.     """
  363.     # Дали е ова лист јазел?
  364.     if tree.results:
  365.         print(str(tree.results))
  366.     else:
  367.         # Се печати условот
  368.         print(str(tree.col) + ':' + str(tree.value) + '? ')
  369.         # Се печатат True гранките, па False гранките
  370.         print(indent + 'T->', end='')
  371.         print_tree(tree.tb, indent + '  ')
  372.         print(indent + 'F->', end='')
  373.         print_tree(tree.fb, indent + '  ')
  374.  
  375.  
  376. def classify(observation, tree):
  377.     """Класификација на нов податочен примерок со изградено дрво на одлука
  378.  
  379.     :param observation: еден ред од податочното множество за предвидување
  380.     :type observation: list
  381.     :param tree: коренот на дрвото на одлучување
  382.     :type tree: DecisionNode object
  383.     :return: речник со класите како клуч и бројот на појавување во листот на дрвото
  384.     за класификација како вредност во речникот
  385.     :rtype: dict
  386.     """
  387.     if tree.results:
  388.         return tree.results
  389.     else:
  390.         value = observation[tree.col]
  391.         if isinstance(value, int) or isinstance(value, float):
  392.             compare = compare_numerical
  393.         else:
  394.             compare = compare_nominal
  395.  
  396.         if compare(observation, tree.col, tree.value):
  397.             branch = tree.tb
  398.         else:
  399.             branch = tree.fb
  400.  
  401.         return classify(observation, branch)
  402.  
  403. from copy import deepcopy
  404.  
  405. if __name__ == "__main__":
  406.     column_ind = int(input())
  407.  
  408.     # Vashiot kod tuka
  409.     eighty_percentage = int(len(dataset)*0.8)
  410.     training_data = deepcopy(dataset[:eighty_percentage])
  411.     training_data_without_column = deepcopy(dataset[:eighty_percentage])
  412.     test_data = deepcopy(dataset[eighty_percentage:])
  413.     test_data_without_column = deepcopy(dataset[eighty_percentage:])
  414.     for row in training_data_without_column:
  415.         del row[column_ind]
  416.     for row in test_data_without_column:
  417.         del row[column_ind]
  418.     tree = build_tree(training_data)
  419.     tree_without_column = build_tree(training_data_without_column)
  420.     correct_tree = 0
  421.     correct_tree_without_column = 0
  422.     for row in test_data:
  423.         classification_tree = classify(row, tree)
  424.        
  425.         for item in classification_tree.items():
  426.             if item[0] == row[-1]:
  427.                 correct_tree += 1
  428.     for row in test_data_without_column:
  429.         classification_tree_without_column = classify(row, tree_without_column)
  430.         for item in classification_tree_without_column.items():
  431.             if item[0] == row[-1]:
  432.                 correct_tree_without_column += 1
  433.     print("Tochnost so prvoto drvo na odluka:", correct_tree/len(test_data))
  434.     print("Tochnost so vtoroto drvo na odluka:", correct_tree_without_column / len(test_data))
RAW Paste Data
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
 
Top