Advertisement
Guest User

Untitled

a guest
Nov 11th, 2019
166
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 11.25 KB | None | 0 0
  1. from math import log
  2.  
  3. training_data=[['slashdot','USA','yes',18,'None'],
  4. ['google','France','yes',23,'Premium'],
  5. ['google','France','yes',23,'Basic'],
  6. ['google','France','yes',23,'Basic'],
  7. ['digg','USA','yes',24,'Basic'],
  8. ['kiwitobes','France','yes',23,'Basic'],
  9. ['google','UK','no',21,'Premium'],
  10. ['(direct)','New Zealand','no',12,'None'],
  11. ['(direct)','UK','no',21,'Basic'],
  12. ['google','USA','no',24,'Premium'],
  13. ['slashdot','France','yes',19,'None'],
  14. ['digg','USA','no',18,'None'],
  15. ['google','UK','no',18,'None'],
  16. ['kiwitobes','UK','no',19,'None'],
  17. ['digg','New Zealand','yes',12,'Basic'],
  18. ['slashdot','UK','no',21,'None'],
  19. ['google','UK','yes',18,'Basic'],
  20. ['kiwitobes','France','yes',19,'Basic']]
  21.  
  22.  
  23.  
  24. def unique_counts(rows):
  25. """Креирај броење на можни резултати (последната колона
  26. во секоја редица е класата)
  27.  
  28. :param rows: dataset
  29. :type rows: list
  30. :return: dictionary of possible classes as keys and count
  31. as values
  32. :rtype: dict
  33. """
  34. results = {}
  35. for row in rows:
  36. # Клацата е последната колона
  37. r = row[len(row) - 1]
  38. if r not in results:
  39. results[r] = 0
  40. results[r] += 1
  41. return results
  42.  
  43.  
  44. def gini_impurity(rows):
  45. """Probability that a randomly placed item will
  46. be in the wrong category
  47.  
  48. :param rows: dataset
  49. :type rows: list
  50. :return: Gini impurity
  51. :rtype: float
  52. """
  53. total = len(rows)
  54. counts = unique_counts(rows)
  55. imp = 0
  56. for k1 in counts:
  57. p1 = float(counts[k1]) / total
  58. for k2 in counts:
  59. if k1 == k2:
  60. continue
  61. p2 = float(counts[k2]) / total
  62. imp += p1 * p2
  63. return imp
  64.  
  65.  
  66. def entropy(rows):
  67. """Ентропијата е сума од p(x)log(p(x)) за сите
  68. можни резултати
  69.  
  70. :param rows: податочно множество
  71. :type rows: list
  72. :return: вредност за ентропијата
  73. :rtype: float
  74. """
  75. log2 = lambda x: log(x) / log(2)
  76. results = unique_counts(rows)
  77. # Пресметка на ентропијата
  78. ent = 0.0
  79. for r in results.keys():
  80. p = float(results[r]) / len(rows)
  81. ent = ent - p * log2(p)
  82. return ent
  83.  
  84.  
  85. class DecisionNode:
  86. def __init__(self, col=-1, value=None, results=None, level=None, tb=None, fb=None):
  87. """
  88. :param col: индексот на колоната (атрибутот) од тренинг множеството
  89. која се претставува со оваа инстанца т.е. со овој јазол
  90. :type col: int
  91. :param value: вредноста на јазолот според кој се дели дрвото
  92. :param results: резултати за тековната гранка, вредност (различна
  93. од None) само кај јазлите-листови во кои се донесува
  94. одлуката.
  95. :type results: dict
  96. :param tb: гранка која се дели од тековниот јазол кога вредноста е
  97. еднаква на value
  98. :type tb: DecisionNode
  99. :param fb: гранка која се дели од тековниот јазол кога вредноста е
  100. различна од value
  101. :type fb: DecisionNode
  102. """
  103. self.col = col
  104. self.value = value
  105. self.results = results
  106. self.tb = tb
  107. self.fb = fb
  108. self.level = level
  109.  
  110.  
  111. def compare_numerical(row, column, value):
  112. """Споредба на вредноста од редицата на посакуваната колона со
  113. зададена нумеричка вредност
  114.  
  115. :param row: дадена редица во податочното множество
  116. :type row: list
  117. :param column: индекс на колоната (атрибутот) од тренирачкото множество
  118. :type column: int
  119. :param value: вредност на јазелот во согласност со кој се прави
  120. поделбата во дрвото
  121. :type value: int or float
  122. :return: True ако редицата >= value, инаку False
  123. :rtype: bool
  124. """
  125. return row[column] >= value
  126.  
  127.  
  128. def compare_nominal(row, column, value):
  129. """Споредба на вредноста од редицата на посакуваната колона со
  130. зададена номинална вредност
  131.  
  132. :param row: дадена редица во податочното множество
  133. :type row: list
  134. :param column: индекс на колоната (атрибутот) од тренирачкото множество
  135. :type column: int
  136. :param value: вредност на јазелот во согласност со кој се прави
  137. поделбата во дрвото
  138. :type value: str
  139. :return: True ако редицата == value, инаку False
  140. :rtype: bool
  141. """
  142. return row[column] == value
  143.  
  144.  
  145. def divide_set(rows, column, value):
  146. """Поделба на множеството според одредена колона. Може да се справи
  147. со нумерички или номинални вредности.
  148.  
  149. :param rows: тренирачко множество
  150. :type rows: list(list)
  151. :param column: индекс на колоната (атрибутот) од тренирачкото множество
  152. :type column: int
  153. :param value: вредност на јазелот во зависност со кој се прави поделбата
  154. во дрвото за конкретната гранка
  155. :type value: int or float or str
  156. :return: поделени подмножества
  157. :rtype: list, list
  158. """
  159. # Направи функција која ни кажува дали редицата е во
  160. # првата група (True) или втората група (False)
  161. if isinstance(value, int) or isinstance(value, float):
  162. # ако вредноста за споредба е од тип int или float
  163. split_function = compare_numerical
  164. else:
  165. # ако вредноста за споредба е од друг тип (string)
  166. split_function = compare_nominal
  167.  
  168. # Подели ги редиците во две подмножества и врати ги
  169. # за секој ред за кој split_function враќа True
  170. set1 = [row for row in rows if
  171. split_function(row, column, value)]
  172. # set1 = []
  173. # for row in rows:
  174. # if not split_function(row, column, value):
  175. # set1.append(row)
  176. # за секој ред за кој split_function враќа False
  177. set2 = [row for row in rows if
  178. not split_function(row, column, value)]
  179. return set1, set2
  180.  
  181.  
  182. def build_tree(rows, level=0, scoref=entropy):
  183. if len(rows) == 0:
  184. return DecisionNode()
  185. current_score = scoref(rows)
  186.  
  187. # променливи со кои следиме кој критериум е најдобар
  188. best_gain = 0.0
  189. best_criteria = None
  190. best_sets = None
  191.  
  192. column_count = len(rows[0]) - 1
  193. for col in range(0, column_count):
  194. # за секоја колона (col се движи во интервалот од 0 до
  195. # column_count - 1)
  196. # Следниов циклус е за генерирање на речник од различни
  197. # вредности во оваа колона
  198. column_values = {}
  199. for row in rows: # for distinct we use dictionary instead of list
  200. column_values[row[col]] = 1
  201. # за секоја редица се зема вредноста во оваа колона и се
  202. # поставува како клуч во column_values
  203. for value in column_values.keys():
  204. (set1, set2) = divide_set(rows, col, value)
  205.  
  206. # Информациона добивка
  207. p = float(len(set1)) / len(rows)
  208. gain = current_score - p * scoref(set1) - (1 - p) * scoref(set2)
  209. if gain > best_gain and len(set1) > 0 and len(set2) > 0:
  210. best_gain = gain
  211. best_criteria = (col, value)
  212. best_sets = (set1, set2)
  213.  
  214. # Креирај ги подгранките
  215. if best_gain > 0:
  216. true_branch = build_tree(best_sets[0], level + 1, scoref)
  217. false_branch = build_tree(best_sets[1], level + 1, scoref)
  218. return DecisionNode(col=best_criteria[0], value=best_criteria[1], level=level,
  219. tb=true_branch, fb=false_branch)
  220. else:
  221. return DecisionNode(results=unique_counts(rows))
  222.  
  223.  
  224. def print_tree(tree, indent=''):
  225. # Дали е ова лист јазел?
  226. if tree.results:
  227. print(str(tree.results))
  228. else:
  229. # Се печати условот
  230. print(str(tree.col) + ':' + str(tree.value) + '? Level=' + str(tree.level))
  231. # Се печатат True гранките, па False гранките
  232. print(indent + 'T->', end='')
  233. print_tree(tree.tb, indent + ' ')
  234. print(indent + 'F->', end='')
  235. print_tree(tree.fb, indent + ' ')
  236.  
  237.  
  238. def classify(observation, tree):
  239. if tree.results:
  240. return tree.results
  241. else:
  242. value = observation[tree.col]
  243. if isinstance(value, int) or isinstance(value, float):
  244. compare = compare_numerical
  245. else:
  246. compare = compare_nominal
  247.  
  248. if compare(observation, tree.col, tree.value):
  249. branch = tree.tb
  250. else:
  251. branch = tree.fb
  252.  
  253. return classify(observation, branch)
  254.  
  255. trainingData=[['slashdot','USA','yes',18,'None'],
  256. ['google','France','yes',23,'Premium'],
  257. ['google','France','yes',23,'Basic'],
  258. ['google','France','yes',23,'Basic'],
  259. ['digg','USA','yes',24,'Basic'],
  260. ['kiwitobes','France','yes',23,'Basic'],
  261. ['google','UK','no',21,'Premium'],
  262. ['(direct)','New Zealand','no',12,'None'],
  263. ['(direct)','UK','no',21,'Basic'],
  264. ['google','USA','no',24,'Premium'],
  265. ['slashdot','France','yes',19,'None'],
  266. ['digg','USA','no',18,'None'],
  267. ['google','UK','no',18,'None'],
  268. ['kiwitobes','UK','no',19,'None'],
  269. ['digg','New Zealand','yes',12,'Basic'],
  270. ['slashdot','UK','no',21,'None'],
  271. ['google','UK','yes',18,'Basic'],
  272. ['kiwitobes','France','yes',19,'Basic']]
  273.  
  274.  
  275. if __name__ == "__main__":
  276. referrer = input()
  277. location = input()
  278. readFAQ = input()
  279. pagesVisited = int(input())
  280. serviceChosen = input()
  281.  
  282. testCase = [referrer, location, readFAQ, pagesVisited, serviceChosen]
  283. trainingData.append(testCase)
  284. t = build_tree(trainingData)
  285. print_tree(t)
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement