API tools faq
paste
Advertisement
Guest User

DRVA NA ODLUKA2

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