2022年 11月 3日

python编程实现决策树算法

最近布置了个课堂作业，用python实现决策树算法 。整了几天勉勉强强画出了棵歪脖子树，记录一下。

大体思路：

1.创建决策树My_Decision_Tree类，类函数__init__()初始化参数、fit()进行决策树模型训练、predict()进行预测、evaluate()进行模型评估、save_model()保存模型(csv格式)、load_model()加载模型、show_tree()使用Pillow库绘制决策树以及其他一些封装的功能函数；

2.最佳划分点的度量通常有Gini值、Entropy、Classification error等，本程序采用Gini值，计算方法如下： 

构建决策数模型所用到的功能函数(gini值计算相关)说明： 

①get_col_gini(self,threshold_point, value_series, label_series)：计算一列数据在某一阈值划分点下的gini_split值；

②get_best_point(self,value_series, label_series)：对连续型数据进行大小排序，分别计算切分点及其对应的gini_split值，找到使得gini_split值最小的最佳切分点；

③get_best_column(self,data,label_series)：遍历数据表中的属性列，计算每列的最佳划分点和gini_split值，并对比找到最适合划分的一列及其对应的划分点；

3.决策树构建（训练）的逻辑： 

①程序开始以root为父节点，先找到6列属性（剩余属性）中最适合划分的列和划分点，并将其划分为两个子节点，记录判断条件和此节点位置。删除子节点中的该列属性以避免最终决策树模型倾向于某个属性，利用剩余的属性继续构造决策树；

②判断各个子节点中的标签是否相同，如果为同一类则移到叶节点中，否则将此节点更新到下个流程中的父节点中；

③一直循环以上过程，当父节点为空时结束训练，如果所有子节点都为叶节点时则决策树完美将数据分类；当然也会出现所有属性都用完但子节点中标签依旧不唯一的情况，这时以该节点中个数较多的标签类作为分类结果，终止模型构建。

  1. # -*- coding: utf-8 -*-
  2. # @Version: Python 3.8.2
  3. # @Author: 707
  4. # @Use: 决策树算法编写
  5.  
  6. import numpy as np
  7. import pandas as pd
  8. from sklearn.model_selection import train_test_split  #数据集划分
  9. #采用Pillow可视化决策树
  10. from PIL import Image
  11. from PIL import ImageDraw
  12. from PIL import ImageFont
  13.  
  14. ###决策树框架###
  15. class My_Decision_Tree(object):
  16. 	'''决策树框架'''
  17.  
  18. 	def __init__(self, arg=None):
  19. 		##初始化类参数
  20. 		self.arg = arg
  21.  
  22. 		#存放决策树中的各层判断条件
  23. 		self.decision_df=pd.DataFrame(columns=['parent_depth','parent_pos','this_depth','this_pos','column','point','label'])
  24. 		self.Parent_node_list=[]	#存放父节点和子节点的DataFrame
  25. 		self.Child_node_list=[]	
  26. 		self.leaf_list=[] #存放划分好的叶节点
  27. 		self.branch_list=[]	#存放未能划分出来的节点
  28.  
  29. 	def fit(self,x_train,y_train):
  30. 		'''传入训练集和标签构造决策树'''
  31.  
  32. 		'''		
  33. 		程序逻辑：
  34. 		(1)程序开始以root为父节点，先找到6列属性（剩余属性）中最适合划分的列和划分点，并将其划分为两个子节点，
  35. 		记录判断条件和此节点位置。删除子节点中的该列属性以避免最终决策树模型倾向于某个属性，利用剩余的属性继续构造决策树
  36. 		(2)判断各个子节点中的标签是否相同，如果为同一类则移到叶节点中，否则将此节点更新到下个流程中的父节点中
  37. 		(3)一直循环以上过程，当父节点为空时结束训练，如果所有子节点都为叶节点时则决策树完美将数据分类；当然也会出现所有属性都用完但子节点
  38. 		中标签依旧不唯一的情况，这时以该节点中个数较多的标签类作为分类结果，终止模型构建。
  40. 		'''
  41.  
  42. 		x_data=x_train.copy()
  43. 		if(y_train.name not in x_data.columns):
  44. 			x_data[y_train.name]=y_train
  45. 		
  46. 		#把第一层（原数据）放入父节点列表Parent_node_list
  47. 		self.Parent_node_list.append(x_data)
  48. 		#写入第一层的决策(跟节点)
  49. 		decision={'this_depth':1,'this_pos':0,'column':'root','label':'#'}
  50. 		self.decision_df=self.decision_df.append(decision,ignore_index=True)
  51. 		#开始循环计算分类节点
  52. 		parent_count=0 #循环的父节点数
  53. 		child_pos=0  #子节点的位置
  54. 		depth=2 #第几层节点
  55. 		while True:
  56. 			parent_node=self.Parent_node_list[parent_count]
  57. 			#找到第一个适合划分的列和划分点
  58. 			col_1,point_1=self.get_best_column(parent_node,parent_node[y_train.name])
  59. 			print('decision condition:',col_1,point_1)
  60.  
  61. 			#根据条件把父节点划分为两部分
  62. 			Child_node1=parent_node.loc[parent_node[col_1]<=point_1]
  63. 			Child_node2=parent_node.loc[parent_node[col_1]>point_1]
  64. 			#每一部分的分类结果
  65. 			result=[]
  66. 			for child_node in [Child_node1,Child_node2]:
  67. 				#删除已使用过的属性
  68. 				del(child_node[col_1])
  69.  
  70. 				#判断子节点标签是否为一类，是则将其放入叶节点列表中
  71. 				if(len(child_node[y_train.name].unique())==1):
  72. 					self.leaf_list.append(child_node)
  73. 					print('添加一个叶节点，标签类型:',child_node[y_train.name].unique()[0],'数据大小:',child_node.shape)
  74. 					result.append(child_node[y_train.name].unique()[0])
  75.  
  76. 				# 判断子节点标签是否还有剩余属性可以作为分类依据,如果有则添加到子节点列表中用于后续分类
  77. 				elif(child_node.shape[1]!=1):
  78. 					self.Child_node_list.append(child_node)
  79. 					print('添加一个子节点，数据大小:',child_node.shape)
  80. 					result.append('#')
  81. 				#都不满足说明该节点没有分完但是分不下去了，提示错误
  82. 				else:
  83. 					self.branch_list.append(child_node)
  84. 					print('child_node节点已用完所有属性，仍然没分出来,剩余数据大小:')
  85. 					print(child_node[y_train.name].value_counts())
  86.  
  87. 					values=child_node[y_train.name].value_counts()
  88. 					if(len(values)==0):
  89. 						replace=list(parent_node[y_train.name].value_counts().index)[0]
  90. 					else:
  91. 						replace=list(values.index)[0]
  92. 					print('用%s作为该条件下的预测结果' %replace)
  93. 					result.append(replace)
  94.  
  95. 			#找到该父节点在该层中所对应的位置
  96. 			p_pos_list=self.decision_df.loc[(self.decision_df['this_depth']==depth-1)&(self.decision_df['label']=='#'),'this_pos']
  97. 			p_pos_list=list(p_pos_list)
  98. 			# print('p_pos_list:',p_pos_list)
  99.  
  100. 			#判断完一个父节点之后,把判断条件加入decision_df中  
  101. 			decision1={'parent_depth':depth-1,'parent_pos':p_pos_list[parent_count],'this_depth':depth,'this_pos':child_pos,
  102. 						'column':col_1,'point':point_1,'label':result[0]}
  103. 			decision2={'parent_depth':depth-1,'parent_pos':p_pos_list[parent_count],'this_depth':depth,'this_pos':child_pos+1,
  104. 						'column':col_1,'point':point_1,'label':result[1]}
  105. 			self.decision_df=self.decision_df.append([decision1,decision2],ignore_index=True)
  106.  
  107. 			#当遍历完父节点列表所有值后，将子节点更新为父节点
  108. 			child_pos+=2
  109. 			parent_count+=1
  110. 			if(parent_count==len(self.Parent_node_list)):
  111. 				parent_count=0
  112. 				child_pos=0
  113. 				depth+=1
  114. 				print('该层决策结束,进行下一层决策\n')
  115. 				self.Parent_node_list=self.Child_node_list.copy()
  116. 				self.Child_node_list.clear()
  117. 				print('更新parent_node_list,大小：%d' %len(self.Parent_node_list))
  118.  
  119. 				#判断父节点列表中是否还有未分类的节点，如果没有则表示已经全部分好，结束训练
  120. 				if(len(self.Parent_node_list)==0):
  121. 					print('决策树构建完成')
  122. 					#显示构建好的决策树：判断条件及结果(叶节点)
  123. 					print(self.decision_df)
  124.  
  125. 					break
  126.  
  127. 	def predict(self,x_test):
  128. 		'''输入测试数据进行决策判断'''
  129. 		y_predict=list()
  130. 		
  131. 		if(type(x_test)==pd.core.series.Series):
  132. 			pred=self.get_ylabel(x_test)
  133. 			y_predict.append(pred)
  134. 		else:
  135. 			for index,row in x_test.iterrows():
  136. 				pred=self.get_ylabel(row)
  137. 				y_predict.append(pred)
  138.  
  139. 		y_predict=np.array(y_predict,dtype=str)
  140. 		return y_predict
  141.  
  142.  
  143.  
  144. 	def evaluate(self,x_test,y_test):
  145. 		'''输入测试集和标签评估决策树准确性，返回acc'''
  146. 		y_true=np.array(y_test,dtype=str)
  147. 		y_pred=self.predict(x_test)
  148. 		# print(y_pred)
  149. 		# print(y_true)
  150. 		label_list=list(self.decision_df['label'].unique())
  151. 		label_list.remove('#')
  152. 		label_list=np.array(label_list,dtype=str) #类型转换
  153. 		#创建混淆矩阵(index为true，columns为pred)
  154. 		confusion_matrix=pd.DataFrame(data=0,columns=label_list,index=label_list)
  155. 		for i in range(len(y_true)):
  156. 			confusion_matrix.loc[y_true[i],y_pred[i]]+=1
  157. 		print('混淆矩阵:')
  158. 		print(confusion_matrix)
  159. 		#计算准确率
  160. 		acc=0
  161. 		for i in range(len(label_list)):
  162. 			acc+=confusion_matrix.iloc[i,i]
  163. 		acc/=len(y_true)
  164. 		print('acc:%.5f' %acc)
  165. 		return acc
  166.  
  167. 	def save_model(self,path):
  168. 		'''以csv格式保存模型'''
  169. 		self.decision_df.to_csv(path,index=False)
  170.  
  171. 	def load_model(self,path):
  172. 		'''以csv格式读取模型'''
  173. 		self.decision_df=pd.read_csv(path)
  174.  
  175. 	def get_col_gini(self,threshold_point, value_series, label_series):
  176. 	    '''Gini值计算函数'''
  177.  
  178. 	    # 将输入进行重组
  179. 	    df_input = pd.DataFrame()
  180. 	    df_input['value'] = value_series
  181. 	    df_input['label'] = label_series
  182. 	    # print(df_input)
  183. 	    # 设计Gini值的计算表格
  184. 	    label_cols = label_series.value_counts()
  185. 	    df_gini = pd.DataFrame(columns=['node1', 'node2'], index=label_cols.index)
  186. 	    
  187. 	    for c in label_cols.index:
  188. 	        df_c = df_input.loc[df_input['label'] == c]
  189. 	        df_gini.loc[c, 'node1'] = df_c.loc[df_c['value']<= threshold_point].shape[0]
  190. 	        df_gini.loc[c, 'node2'] = df_c.loc[df_c['value']> threshold_point].shape[0]
  191.  
  192.         #计算node1、node2节点gini值中和的部分
  193. 	    sum_n1=df_gini['node1'].sum()
  194. 	    sum_n2=df_gini['node2'].sum()
  195. 	    # print(df_gini)
  196.  
  197. 	    # 计算node节点gini值
  198. 	    gini_n1=gini_n2=0
  199. 	    if(sum_n1==0):
  200. 	    	for c in label_cols.index:
  201. 	    		gini_n2+=(df_gini.loc[c,'node2']/sum_n2)**2
  202. 	    elif(sum_n2==0):
  203. 	    	for c in label_cols.index:
  204. 	    		gini_n1+=(df_gini.loc[c,'node1']/sum_n1)**2
  205. 	    else:
  206. 	    	for c in label_cols.index:
  207. 		    	gini_n1+=(df_gini.loc[c,'node1']/sum_n1)**2
  208. 		    	gini_n2+=(df_gini.loc[c,'node2']/sum_n2)**2
  209. 	    gini_n1 = 1-gini_n1
  210. 	    gini_n2 = 1-gini_n2
  211. 	    #计算gini_split
  212. 	    gini_split=sum_n1/(sum_n1+sum_n2)*gini_n1 +sum_n2/(sum_n1+sum_n2)*gini_n2
  213. 	    # print("point:%f,gini_split:%f" %(threshold_point,gini_split))
  214. 	    return gini_split
  215.  
  216. 	def get_best_point(self,value_series, label_series):
  217. 	    '''找到一列属性中最适合划分(gini值最小)的点'''
  218.  
  219. 	    value_array=np.array(value_series)
  220. 	    value_array=np.sort(value_array)
  221. 	    df_point = pd.DataFrame(columns=['point', 'gini_value'])
  222.  
  223. 	    # 循环属性值列，计算划分点及其gini值并添加至df_point数据表中
  224. 	    for i in range(len(value_array) + 1):
  225. 	        if(i == 0):
  226. 	            point = value_array[i] - 1
  227. 	        elif(i == len(value_array)):
  228. 	            point = value_array[i - 1]
  229. 	        else:
  230. 	            point = 0.5 * (value_array[i] + value_array[i - 1])
  231. 	        gini = self.get_col_gini(point, value_series, label_series)
  232.  
  233. 	        s = pd.Series(data={'point': point, 'gini_value': gini})
  234. 	        df_point.loc[i] = s
  235.  
  236. 	    df_point.sort_values(by='gini_value', inplace=True)
  237. 	    best_point = df_point.iloc[0, 0]
  238. 	    best_gini = df_point.iloc[0,1]
  239. 	    # print("best point for column '%s':%f" %(value_series.name,best_point))
  240. 	    # print(df_point)
  241. 	    return best_point,best_gini
  242.  
  243. 	def get_best_column(self,data,label_series):
  244. 		'''遍历data中的属性列，计算其最佳划分点及gini值，找出最适合划分的一列和划分点'''
  245. 		x_data=data.copy()
  246. 		if(label_series.name in x_data.columns):
  247. 			del(x_data[label_series.name])
  248.  
  249. 		gini_columns=pd.DataFrame(columns=['point','gini'],index=x_data.columns)
  250. 		for col_name in x_data.columns:
  251. 			point,gini=self.get_best_point(x_data[col_name],label_series)
  252. 			s=pd.Series({'point':point,'gini':gini})
  253. 			gini_columns.loc[col_name]=[point,gini]
  254. 			# gini_columns=gini_columns.append(s,ignore_index=True)	#append会更改索引
  255. 		gini_columns.sort_values(by='gini',inplace=True)
  256. 		# print(gini_columns)
  257. 		best_col=gini_columns.index[0]
  258. 		best_point=gini_columns.iloc[0,0]
  259. 		return best_col,best_point
  260.  
  261. 	def get_ylabel(self,x_series):
  262. 		'''计算一行x数据(Series)对应的标签'''
  263. 		model=self.decision_df
  264.  
  265. 		y_pred='#'
  266. 		x_index=1
  267. 		parent_index=[]
  268. 		child_df=pd.DataFrame()
  269.  
  270. 		# for i in range(1):
  271. 		while (y_pred=='#'):
  272. 			#判断条件
  273. 			condition=[model.loc[x_index,'column'],model.loc[x_index,'point']]
  274. 			if(x_series[condition[0]]>condition[1]):
  275. 				x_index+=1
  276. 			# 	print('%s>%f' %(condition[0],condition[1]))
  277. 			# else:
  278. 			# 	print('%s<=%f' %(condition[0],condition[1]))
  279. 				
  280. 			y_pred=model.loc[x_index,'label']
  281. 			#更新父节点索引并找到其子节点
  282. 			parent_index=[model.loc[x_index,'this_depth'],model.loc[x_index,'this_pos']]
  283. 			child_df=model.loc[(model['parent_depth']==parent_index[0])&(model['parent_pos']==parent_index[1])]
  284. 			
  285. 			#找到标签时结束
  286. 			if(child_df.shape[0]!=0):
  287. 				x_index=list(child_df.index)[0]
  288. 			# 	print('跳到第%d行继续判断' %x_index)
  289. 			# else:
  290. 			# 	print('预测结束')
  291. 		# print('pred:',y_pred)
  292. 		return y_pred
  293.  
  294. 	def show_tree(self):
  295. 		'''将决策树进行可视化'''
  296.  
  297. 		def add_text(im_draw,text_str,xy,multiline=1):
  298. 			'''在绘图对象的某个位置添加文字'''
  299. 			#设置大小
  300. 			font_h,font_w=25,14
  301. 			font_h*=multiline
  302. 			text_len=round(len(text_str)/multiline)
  303.  
  304. 			font=ImageFont.truetype(font='simsun.ttc',size=20)
  305. 			im_draw.text(xy=(xy[0]-font_w*3,xy[1]),text=text_str,font=font,fill='black',align='center')
  306. 			#绘制矩形
  307. 			# im_draw.rectangle(xy=(xy[0],xy[1],xy[0]+font_w*text_len,xy[1]+font_h),outline='black',width=2)
  308.  
  309. 		interval_x,interval_y=60,80
  310. 		model=self.decision_df.copy()
  311. 		model['x_pos']=model['this_pos']
  312. 		model['y_pos']=(model['this_depth']-1)*interval_y
  313. 		model['text']='text'
  314. 		max_depth=model.iloc[-1,2]
  315. 		
  316. 		#创建图像
  317. 		img_w,img_h=1500,600
  318. 		tree_img=Image.new(mode='RGB',size=(img_w,img_h),color='white')
  319. 		draw=ImageDraw.Draw(tree_img) #创建绘图对象
  320.  
  321. 		parent_pos=[]
  322. 		parent_x_pos=0
  323. 		x_pos=0
  324. 		for x_index in model.index:
  325. 			text=model.loc[x_index,'column']
  326. 			if (str(model.loc[x_index,'point']) == 'nan'):
  327. 				x_pos=img_w/4
  328. 			else:
  329. 				#跟新text内容和x位置
  330. 				model.loc[x_index,'x_pos']=x_pos
  331. 				parent_pos=[model.loc[x_index,'parent_depth'],model.loc[x_index,'parent_pos']]
  332. 				parent_x_pos=model.loc[(model['this_depth']==parent_pos[0])&(model['this_pos']==parent_pos[1]),'x_pos']
  333. 				depth=model.loc[x_index,'this_depth']-1
  334. 				if(model.loc[x_index,'this_pos']%2==0):
  335. 					text+='\n<='+('%.3f' %model.loc[x_index,'point'])
  336. 					x_pos=parent_x_pos-interval_x*np.sqrt(max_depth-depth)
  337.  
  338. 				else:
  339. 					text+='\n>'+('%.3f' %model.loc[x_index,'point'])
  340. 					x_pos=parent_x_pos+interval_x*np.sqrt(max_depth-depth)
  341. 				x_pos=x_pos.iloc[0]
  342. 				if(model.loc[x_index,'label'] !='#'):
  343. 					text+='\nClass:'+str(model.loc[x_index,'label'])
  344. 			
  345. 			#将文字和位置添加到
  346. 			model.loc[x_index,'text']=text
  347. 			model.loc[x_index,'x_pos']=x_pos
  348. 		
  349. 		# 调整节点横坐标位置
  350. 		gap=140
  351. 		for depth in model['this_depth'].unique():
  352.  
  353. 			if(depth!=1):
  354. 				same_depth=model.loc[model['this_depth']==depth]
  355. 				for x_index in same_depth.index[:-1]:
  356. 					if(x_index==same_depth.index[0]):
  357. 						if((model.loc[same_depth.index[0],'x_pos']-model.loc[same_depth.index[-1],'x_pos'])<gap*len(same_depth.index)):
  358. 							#如果整体太挤，整层先往左移一段
  359. 							for i in same_depth.index:
  360. 								model.loc[i,'x_pos']-=gap*len(same_depth.index)/8
  361. 					#如果相邻两个靠太近，右边的往右移一点
  362. 					if((model.loc[x_index+1,'x_pos']-model.loc[x_index,'x_pos'])<gap):
  363. 						model.loc[x_index+1,'x_pos']=model.loc[x_index,'x_pos']+gap
  364. 						# model.loc[x_index,'x_pos']-=gap/2
  365.  
  366. 		#绘制文字和线
  367. 		this_img_pos=[]
  368. 		parent_img_pos=[]
  369. 		for x_index in model.index:
  370. 			#绘制直线
  371. 			if(x_index !=0):
  372. 				this_img_pos=[model.loc[x_index,'x_pos'],model.loc[x_index,'y_pos']]
  373. 				parent_pos=[model.loc[x_index,'parent_depth'],model.loc[x_index,'parent_pos']]
  374. 				parent_img_pos=model.loc[(model['this_depth']==parent_pos[0])&(model['this_pos']==parent_pos[1]),['x_pos','y_pos']]
  375. 				parent_img_pos=[parent_img_pos.iloc[0,0],parent_img_pos.iloc[0,1]]
  376. 				draw.line(xy=(parent_img_pos[0],parent_img_pos[1],this_img_pos[0],this_img_pos[1]),fill='gray',width=1)
  377.  
  378. 			#添加文字
  379. 			this_pos=(model.loc[x_index,'x_pos'],model.loc[x_index,'y_pos'])
  380. 			text=model.loc[x_index,'text']
  381. 			add_text(im_draw=draw,text_str=text,xy=this_pos)
  382. 		
  383. 		#显示图片
  384. 		tree_img.show()
  385.  
  386.  
  387. if __name__ == '__main__':
  388.  
  389.     # 读取文件
  390.     data = pd.read_csv('./paras_labels.csv')
  391.     #数据按8:2进行训练集、测试集切分
  392.     x_train,x_test,y_train,y_test=train_test_split(data,data['label'],test_size=0.2,random_state=7)
  393.  
  394.  
  395.     ds_tree=My_Decision_Tree()
  396.  
  397.     ds_tree.fit(x_train,y_train)
  398.     # ds_tree.save_model('my_decision_tree%d.csv' %e)
  399.  
  400.     # ds_tree.load_model('my_decision_tree%d.csv' %e)
  401.     # print(ds_tree.decision_df)
  402.  
  403.     print('训练集评估模型:')
  404.     ds_tree.evaluate(x_train,y_train)
  405.     print('测试集评估模型:')
  406.     ds_tree.evaluate(x_test,y_test)
  407.  
  408.     ds_tree.show_tree()

结果：

用我的数据跑了一下，成功长出一棵歪脖子树，nice! 

 代码能力有限，有错误的地方欢迎大佬们交流，批评指正[狗头抱拳]