[关闭]
@Bruce1Tone 2022-03-13T06:32:59.000000Z 字数 29726 阅读 683

电子科技大学

实 验 报 告

学生姓名：唐智崴
学号：2017110801028
指导教师：邵俊明
数据挖掘实验

目录

  实验一
  实验二
  实验三
  实验四
  附录
   实验一代码
    数据归一化
    缺失值处理
    特征筛选
   实验二代码
    关联规则挖掘
   实验三代码
    KNN分类
    决策树分类
   实验四代码
    K-Means聚类算法

实验一

一、实验项目名称：

认识数据与数据预处理

二、实验原理：

  1. 数据属性归一化：将数据属性观测值按照一定规则映射到规定的区间(如[0,1])
  2. 缺失值处理：利用属性均值填补缺失值
  3. 特征筛选：计算属性的信息增益，过滤掉低信息增益的特征，留下高信息增益的特征

三、实验目的：

了解Weka工具包及Eclipse平台；认识和了解数据，并且能对其进行简单的预处理

四、实验内容：

该实验我选择用两种方法实现：利用Weka实现和自行python编程实现。
首先是利用Weka中现成的功能直接完成上述操作，然后自己再利用python手动实现上述功能，以便对该过程有更深的了解。

五、实验步骤：

Weka实现：

  1. 数据归一化：
    Weka GUI -> Explorer -> Open file -> 选择数据文件data1.xlsx
    然后在Filter选择weka -> filters -> unsupervised -> attribute -> Normalize
    最后将实验结果存储在data1.xlsx文件的另一列中
  2. 缺失值处理：
    数据集为data2.xlsx，同上一步操作，这一步改用Filter -> ReplaceMissingValues，即缺失值填补的滤波器
  3. 特征筛选：
    数据集为data3.xlsx，同上一步操作，这一步改用Filter -> AttributeSelection，参数evaluator选择InfoGainAtrributeEval，Ranker设置为6

Python实现：

1-数据归一化：

完整代码见附录：点此跳转
实验流程是：

  • 首先使用get_data()函数将data_1.xlsx中的数据集读入并存储在Data类的ori_data中
  • 然后使用GetMinAndMax()函数将ori_data中的最大值和最小值找到并存储在Data类中
  • 最后使用Normalize()函数将数据映射到[0,1]区间，由RecordNormalizedData()函数将归一化后的数据写入原文件中

上述函数由下列代码给出：

  1. class Data():
  2.     def __init__(self,sheet_data):
  3.         self.maxA = 0
  4.         self.minA = 0
  5.         self.ori_data = self.get_data(sheet_data)
  6.         self.normalized_data = self.ori_data
  7.         self.length = len(self.ori_data)
  8.         self.GetMinAndMax()
  10.     def get_data(self,sheet_data):
  11.         #获取excel中存储的数据
  12.         data = []
  13.         i = 0
  14.         while True:
  15.             try:
  16.                 data.append(sheet_data.cell(i+1,0).value)
  17.                 i += 1
  18.             except IndexError:
  19.                 break
  20.         return data
  22.     def GetMinAndMax(self):
  23.         #获取数据中的最大值和最小值
  24.         temp_min = self.ori_data[0]
  25.         temp_max = self.ori_data[0]
  26.         for i in range(self.length):
  27.             if self.ori_data[i] <= temp_min:
  28.                 temp_min = self.ori_data[i]
  29.             if self.ori_data[i] >= temp_max:
  30.                 temp_max = self.ori_data[i]
  31.         self.maxA = temp_max
  32.         self.minA = temp_min
  34.     def Normalize(self):
  35.         #数据归一化操作
  36.         for i in range(self.length):
  37.             self.normalized_data[i] = (self.ori_data[i] - self.minA)/(self.maxA - self.minA)
  39.     def RecordNormalizedData(self,sheet):
  40.         #记录归一化的数据
  41.         sheet.write(0,1,'Normalized Data')
  42.         for i in range(self.length):
  43.             sheet.write(i+1,1,round(self.normalized_data[i],2))

2-数据缺失值处理：

完整代码见附录：点此跳转
该操作的核心在于FillBlank()函数，即将数据的均值求出并填回缺失值，函数由如下代码定义：

  1. def FillBlank(self):
  2.     count = 0
  3.     data_sum = 0
  4.     blank_index = []
  5.     for i in range(self.length):
  6.         if self.ori_data[i] is not '':
  7.             count += 1
  8.             data_sum += self.ori_data[i]
  9.         else:
  10.             blank_index.append(i)
  11.     aver = data_sum / count
  12.     for i in blank_index:
  13.         self.filled_data[i] = round(aver,2)

3-特征筛选：

完整代码见附录：点此跳转
该实验的重点在于，统计每一个属性的信息与标签，并进行信息熵和信息增益的计算
信息熵的计算方法由下式给出：


代码实现是：

  1. def get_Ent_D(self):
  2.     #获取根节点的信息熵Ent_D
  3.     count_true = 0
  4.     count_false = 0
  5.     for i in self.table[self.ncols-1]:
  6.         if i == '是':
  7.             count_true += 1
  8.         elif i == '否':
  9.             count_false += 1
  10.     p_true = count_true/(count_true + count_false)
  11.     p_false = count_false/(count_true + count_false)
  12.     Ent_D = 0 - (p_true * math.log(p_true,2) + p_false * math.log(p_false,2))
  13.     return Ent_D

然后计算每个属性的信息增益Gain：


代码实现是：

  1. def get_information_gain(self):
  2.     #获取该属性的信息增益
  3.     Ent_D_i = []        #存储该属性各个状态的信息熵
  4.     p_D_i = []          #存储该属性各个状态的比例
  5.     sample_quantity = 0
  6.     result = 0
  7.     for i in self.dict_True:
  8.         sample_quantity += self.dict_True[i]
  9.     for i in self.dict_False:
  10.         sample_quantity += self.dict_False[i]
  12.     for i in self.status:
  13.         total = self.dict_True[i] + self.dict_False[i]
  14.         if self.dict_True[i] != 0:
  15.             if self.dict_False[i] != 0:
  16.                 temp_Ent_D_i = 0 - ((self.dict_True[i]/total) * math.log(self.dict_True[i]/total,2) + (self.dict_False[i]/total) * math.log(self.dict_False[i]/total,2))
  17.             else:
  18.                 temp_Ent_D_i = 0 - self.dict_True[i]/total * math.log(self.dict_True[i]/total,2)
  19.         else:
  20.             temp_Ent_D_i = 0 - self.dict_False[i]/total * math.log(self.dict_False[i]/total,2)
  21.         temp_p = total/sample_quantity
  22.         Ent_D_i.append(temp_Ent_D_i)
  23.         p_D_i.append(temp_p)
  25.     for i in range(len(Ent_D_i)):
  26.         result += Ent_D_i[i] * p_D_i[i]
  27.     result = self.Ent_D - result
  29.     return result

六、实验数据及结果分析：

数据归一化结果：

image_1ebj11knr1llell0uhu14jo9sv9.png-47.9kB

原数据在[0,100]区间，归一化后映射在[0,1]区间，实验结果符合预期

数据缺失值处理结果：

image_1ebj1474tsvqsgs5iuru9145m.png-38.3kB

原数据缺失值被填入了保留两位小数的均值，实验结果符合预期

特征筛选处理结果：

原始数据集为：

image_1ebj1au8a1h1l6ba7c6187vdgv13.png-54kB

实验结果为：

image_1ebj1cvvb1sqk1msc9s78j912fu1g.png-42.1kB

成功计算出各个离散属性的信息增益，实验结果符合预期

七、实验结论：

实验结果符合预期，具体结果见上节

八、总结及心得体会：

在数据挖掘的过程中，第一步也是最重要的一步就是数据预处理，通过实际操作我掌握了数据预处理中的数据归一化、数据缺失值处理、特征筛选等预处理的方法，为后面的数据挖掘学习奠定基础

九、对本实验过程及方法的改进建议：

该实验中特征筛选环节，由于没有数据集的限制，所以只做了离散属性的特征筛选。后面有时间可以补上连续属性的信息增益计算和特征筛选

报告评分:          

指导老师签字:          

实验二

一、实验项目名称：

关联规则挖掘

二、实验原理：

先产生频繁项集，然后再从频繁项集中提取高置信度的规则，即强规则。该过程中利用Apriori算法进行剪枝处理

三、实验目的：

掌握关联规则挖掘的基本概念、原理和一般方法，掌握Apriori算法，了解FP-GROWTH算法

四、实验内容：

根据如下数据集，挖掘商品的关联规则，并返回强规则：

image_1ebj3f61bpartimu6l14411h8p9.png-10.7kB

五、实验步骤：

完整代码见附录：点此跳转

读取数据集

首先用ReadData()函数将data.xlsx中的数据集读入到layer1中，如下：

  1. layer1 = ReadData(sheet)
  3. def ReadData(sheet):
  4.     temp_layer = []
  5.     for i in range(1,sheet.ncols):
  6.         temp_node = Node(sheet.nrows - 1)
  7.         temp_node.content.append(sheet.cell(0,i).value)
  8.         count = 0
  9.         for j in range(1,sheet.nrows):
  10.             if sheet.cell(j,i).value == 1:
  11.                 count += 1
  12.             temp_node.data.append(int(sheet.cell(j,i).value))
  13.         temp_node.sup = count
  14.         temp_layer.append(temp_node)
  15.     return temp_layer

剪枝

然后根据Apriori算法，非频繁项集的超集一定是非频繁的，所以对所有的非频繁项集进行剪枝操作，然后更新该层的所有结点。以上过程由UpdateLayer()函数实现，代码如下：

  1. #更新当前层，剪枝
  2. def UpdateLayer(ori_list,threshold):
  3.     temp_list = []
  4.     for i in ori_list:
  5.         if i.sup > threshold:
  6.             temp_list.append(i)
  7.     return temp_list

连接

完成剪枝操作后，将剪枝后的该层各点相互连接，由GenNewLayer()函数构建成新的一层，函数由如下给出：

  1. #连接上层生成下层
  2. def GenNewLayer(ori_list):
  3.     new_list = []
  4.     for i in ori_list:
  5.         for j in ori_list:
  6.             if i != j:
  7.                 new_list.append(Merge(i,j))
  8.     return new_list
  10. #Merge函数合并a,b两个结点           
  11. def Merge(a,b):
  12.     temp = Node(a.total)
  13.     #合并self.content的内容，并去重
  14.     for i in a.content:
  15.         temp.content.append(i)
  16.     for i in b.content:
  17.         if i not in a.content:
  18.             temp.content.append(i)
  19.     #统计data和sup的内容
  20.     count = 0
  21.     for i in range(a.total):
  22.         if a.data[i] == b.data[i] and a.data[i] == 1:
  23.             count += 1
  24.             temp.data.append(1)
  25.         else:
  26.             temp.data.append(0)
  27.     temp.sup = count
  28.     return temp

最后控制输出所有的强规则即可

六、实验数据及结果分析：

image_1ebj46lvkj20mdf1fkp6mo1j9vm.png-39.3kB

其中，第一项为关联规则；第二项为具体关联的事件，1表示规则为真；第三项表示该规则的置信度。

七、实验结论：

利用Apriori算法可以不用遍历所有数据，即可完成关联规则挖掘。最后输出的强关联规则经过验证，是正确的，实验成功。

八、总结及心得体会：

Apriori算法的关键在于其逆应用，即：所有费频繁项集的超集都是非频繁的。借助此算法，在每次连接形成新的一层(layer)后，可以根据该算法将支持度较低的非频繁项集剪枝处理，大大减少了计算量，是一种常用的关联规则挖掘算法

九、对本实验过程及方法的改进建议：

由于是自己手敲的数据，该实验采用的数据集较小，计算开销的节省效果还不明显。可以换成较大的数据集进行测试，就能明显感受到Apriori算法的优越性能

报告评分:          

指导老师签字:          

实验三

一、实验项目名称：

分类实验

二、实验原理：

KNN算法即k邻近算法，即将测试数据放入训练集中，选择距离最短的k个数据作为邻居，然后预测它的类别和k个邻居中其所属类别最多的一致，属于一种无监督的lazy learning，不需要对训练样本进行学习
决策树算法即根据数据的每个属性，分别计算其信息熵和信息增益，然后选择信息增益最大的属性作为父节点，在此基础上重复以上过程直到大部分数据能根据该决策树正确分类

三、实验目的：

了解分类的基本概念、原理和一般方法，掌握分类的基本算法，实现KNN或决策树算法

四、实验内容：

KNN算法

首先将训练数据导入，然后遍历测试集，对每一个测试数据求其k个最邻近的邻居，然后按照邻居最多的属性进行预测，并与该数据的实际属性进行对比，实现分类

决策树算法：

首先将训练数据导入，并计算各个属性的信息增益，然后根据信息增益构建决策树。
再遍历测试数据，对每一个测试数据使用该决策树进行分类预测，并与实际的标签进行对比

以上两个实验共用同一个数据集，训练数据集为iris.2D.train.arff，测试数据集为iris.2D.test.arff

五、实验步骤：

KNN算法详解

完整代码见附录：点此跳转

定义数据类型

首先定义一个Node类，用于存放每一行测试数据，定义如下：

  1. class Node():
  2.     def __init__(self):
  3.         self.petallength = 0
  4.         self.petalwidth = 0
  5.         self.classes =''

利用GetData()函数进行数据读取后，进行上述过程的预测，由Predict()函数实现：

  1. def GetDist(node_a,node_b):
  2.     #计算两点的距离
  3.     distance = math.sqrt((node_a.petallength - node_b.petallength)**2 + (node_a.petalwidth - node_b.petalwidth)**2)
  4.     return distance
  6. def Predict(train_list,node_a,k):
  7.     #开始预测数据
  8.     dist_list = []      #存放离各点距离
  9.     index_list = []     #存放K邻近的点的索引index
  10.     for i in train_list:
  11.         dist_list.append(GetDist(node_a,i))
  12.     dist_copy = dist_list
  13.     for i in range(k):  #寻找k邻近的索引值，并存放在index_list中
  14.         temp_min = 999
  15.         temp_index = 0
  16.         for j in range(len(train_list)):
  17.             if dist_copy[j] <= temp_min:
  18.                 temp_min = dist_copy[j]
  19.                 temp_index = j
  20.         dist_copy[temp_index] = 999
  21.         index_list.append(temp_index)
  22.     classes = {}
  23.     #统计k邻近的分类结果，并以字典形式存放在classes中
  24.     for i in index_list:
  25.         if train_list[i].classes not in classes:
  26.             classes[train_list[i].classes] = 1
  27.         else:
  28.             classes[train_list[i].classes] += 1
  29.     result = ''
  30.     max_times = 0
  31.     #选取次数最多的分类结果并存放在result中
  32.     for i in classes:
  33.         if classes[i] >= max_times:
  34.             max_times = classes[i]
  35.             result = i
  36.     return result

最后是主函数RunTest()，其附带的一个功能是统计预测的正确率并输出：

  1. def RunTest(train_list,test_list,k):
  2.     #开始运行测试
  3.     count = 0
  4.     for i in test_list:
  5.         result = Predict(train_list,i,k)
  6.         if i.classes == result:     #判断预测结果与标签是否相符
  7.             count += 1
  8.             print('sample',test_list.index(i),'is correctly classified as',i.classes,'!')
  9.     rate = float(count / len(test_list))
  10.     return rate

决策树算法详解

完整代码见附录：点此跳转

首先定义一个Node类，同上，然后定一个Tree类作为决策树的结点：

  1. class Tree():
  2.     def __init__(self):
  3.         self.name = ''
  4.         self.standard = 0
  5.         self.left = None
  6.         self.right = None

然后用GetEnt()函数计算某属性的信息熵，用GetGain()函数计算某属性的信息增益：

  1. def GetGain(train_list,name):
  2.     #计算信息增益
  3.     if name is 'petallength':
  4.         data_list = []
  5.         for i in train_list:
  6.             data_list.append(i.petallength)
  7.         median = np.median(data_list)
  8.         ent_d = GetEnt(train_list)
  9.         d_list = []
  10.         temp_list = []
  11.         for i in train_list:
  12.             if i.petallength >= median:
  13.                 temp_list.append(i)
  14.         d_list.append(temp_list)
  15.         gain = ent_d
  16.         for i in d_list:
  17.             gain = gain - len(i)*GetEnt(i)/len(train_list)
  18.         return gain
  20.     elif name is 'petalwidth':
  21.         data_list = []
  22.         for i in train_list:
  23.             data_list.append(i.petalwidth)
  24.         median = np.median(data_list)
  25.         ent_d = GetEnt(train_list)
  26.         d_list = []
  27.         temp_list = []
  28.         for i in train_list:
  29.             if i.petalwidth >= median:
  30.                 temp_list.append(i)
  31.         d_list.append(temp_list)
  32.         gain = ent_d
  33.         for i in d_list:
  34.             gain = gain - len(i)*GetEnt(i)/len(train_list)
  35.         return gain
  37. def GetEnt(train_list):
  38.     #计算信息熵
  39.     count = {}
  40.     for i in train_list:
  41.         if i.classes not in count:
  42.             count[i.classes] = 1
  43.         elif i.classes in count:
  44.             count[i.classes] += 1
  45.     total = 0
  46.     for i in count:
  47.         total += count[i]
  48.     ent = 0
  49.     for i in count:
  50.         ent = ent - count[i]/total * math.log(2,count[i]/total)
  51.     return ent

以上是对于离散属性的求解，而对于连续属性，则需要求中位数进行二分法，将之转换为离散属性再进行计算，其中求中位数的函数为GetMedian()：

  1. def GetMedian(train_list,name):
  2.     if name is 'petallength':
  3.         data_list = []
  4.         for i in train_list:
  5.             data_list.append(i.petallength)
  6.         median = np.median(data_list)
  7.     elif name is 'petalwidth':
  8.         data_list = []
  9.         for i in train_list:
  10.             data_list.append(i.petalwidth)
  11.         median = np.median(data_list)
  12.     return median

最后是生成决策树的函数GenTree()，返回决策树的根节点：

  1. def GenTree(train_list):
  2.     root = Tree()
  3.     gain = []
  4.     gain.append(GetGain(train_list,'petallength'))
  5.     gain.append(GetGain(train_list,'petalwidth'))
  6.     if gain[0] >= gain[1]:
  7.         root.name = 'petallength'
  8.         root.standard = GetMedian(train_list,'petallength')
  9.         root.left = Tree()
  10.         root.left.name = 'petalwidth'
  11.         root.left.standard = GetMedian(train_list,'petalwidth')
  12.         root.left.left = Tree()
  13.         root.left.left.name = '1'
  14.         root.left.right = Tree()
  15.         root.left.right.name = '2'
  17.         root.right = Tree()
  18.         root.right.name = 'petalwidth'
  19.         root.right.standard = GetMedian(train_list,'petalwidth ')
  20.         root.right.left = Tree()
  21.         root.right.left.name = '3'
  22.         root.right.right = Tree()
  23.         root.right.right.name = '4'
  24.     else:
  25.         root.name = 'petalwidth'
  26.         root.standard = GetMedian(train_list,'petalwidth')
  27.         root.left = Tree()
  28.         root.left.name = 'petallength'
  29.         root.left.standard = GetMedian(train_list,'petallength')
  30.         root.left.left = Tree()
  31.         root.left.left.name = '1'
  32.         root.left.right = Tree()
  33.         root.left.right.name = '2'
  35.         root.right = Tree()
  36.         root.right.name = 'petallength'
  37.         root.right.standard = GetMedian(train_list,'petallength')
  38.         root.right.left = Tree()
  39.         root.right.left.name = '3'
  40.         root.right.right = Tree()
  41.         root.right.right.name = '4'
  42.     return root

六、实验数据及结果分析：

KNN结果：

image_1ebj7c6pfkif2qg1ko43a11u3a9.png-213.9kB

可以看到，knn算法的准确率还是比较高的，准确率高达96%

决策树结果：

image_1ebj7e39r1pi5m7p142obi9hs2m.png-188.3kB

决策树算法的准确率低一点，只有72%，推测可能是因为连续数据离散化的过程中直接找中位数的模型过于简单，准确率还是基本表现不错的。

七、实验结论：

根据以上结果显示，knn的算法有96%的准确率，还是比较高了。而决策树算法的准确率只有72%，应该是连续数据离散化处理的过程中出了问题。然后我尝试使用离散数据集进行测试，发现准确率有92%，证实了我的猜想。总体来说，基本达到实验要求

八、总结及心得体会：

分类是数据挖掘中最常见的一种数据处理，他可以根据现有的数据集预测新数据的属性，有广泛的应用。例如模式识别中，涉及到的最基本的思想就是分类。了解了分类的基本方法后，对数据挖掘又有了更深一步的理解

九、对本实验过程及方法的改进建议：

可以再思考一下连续数据离散化的过程，优化一下决策树算法

报告评分:          

指导老师签字:          

实验四

一、实验项目名称：

聚类实验

二、实验原理：

K-Means算法即：首先随机在途中取k个点作为聚类中心，然后对途中每所有点求对这K个聚类中心的距离，将该点归到距离最近的聚类中心的簇。
然后更新簇内的聚类中心，再重复以上操作，直到聚类中心不再移动或聚类中心移动的距离小于一个阈值(Threshold)，即可停止迭代。最后得到聚类的各个簇。

三、实验目的：

了解聚类的基本概念、原理和一般方法，掌握聚类的基本算法，学会调用WEKA包处理kmeans聚类问题，并自己编程实现K-Means, DBSCAN算法等

四、实验内容：

  1. 学会调用WEKA包处理kmeans聚类问题：
  2. 自己编程实现K-Means算法

以下为部分原始数据：

image_1ebjaqmcl1gvp1k0f1v69508lr99.png-37.5kB

五、实验步骤：

完整代码详见附录：点击跳转

初始化类

首先定义一个KMeans类，用于存放聚类的结果：

  1. class KMeans():
  2.     #存放kmeans结果的类
  3.     def __init__(self,data_set,k):
  4.         self.data_set = data_set        #原始数据集
  5.         self.num = k                    #聚类
  6.         self.data_result = self.InitResult(k)   #存放聚类结果
  8.     def InitResult(self,k):
  9.         result_list = []
  10.         for i in range(k):
  11.             temp_list = [[],[]]
  12.             result_list.append(temp_list)
  13.         return result_list

分簇、更新聚类中心

然后GetData()读取所需要的数据。在RunTest()中，首先利用随机数初始化k个随机的聚类中心，然后开始GetCluster()将各个点分到各聚类中心的簇、UpdateCenters()更新各个簇的聚类中心：

  1. def RunTest(data_set,k,colors,threshold):
  2.     new_centers = []
  3.     centers = []
  4.     randlist = random.sample(range(0,len(data_set[0])),k)
  5.     #初始化k个聚类中心
  6.     for i in randlist:
  7.         temp_center = [data_set[0][i],data_set[1][i]]
  8.         new_centers.append(temp_center)
  9.     result = KMeans(data_set,k)
  10.     #经过更新后的聚类中心，如果没有变化，就停止迭代
  11.     count = 0
  12.     while new_centers != centers:
  13.         centers = new_centers
  14.         result = GetCluster(centers,data_set)
  15.         new_centers = UpdateCenters(centers,result.data_result,threshold)
  17.     DrawScatter(result,colors,centers)

其中，用于将点分类到各个簇的GetCluster()函数和用于更新各个簇的聚类中心的UpdateCenters()函数由以下给出：

  1. def GetCluster(centers,data_set):
  2.     #根据当前的聚类中心centers进行聚类划分，返回聚类结果
  3.     result = KMeans(data_set,len(centers))
  4.     for i in range(len(data_set[0])):
  5.         #遍历每个点
  6.         min_dist = 99999
  7.         min_index = 0
  8.         for j in range(len(centers)):
  9.             #遍历聚类中心
  10.             temp_dist = math.sqrt((data_set[0][i] - centers[j][0])**2 + (data_set[1][i] - centers[j][10])**2)
  11.             if temp_dist <= min_dist:
  12.                 min_dist = temp_dist
  13.                 min_index = j
  14.         result.data_result[min_index][0].append(data_set[0][i])
  15.         result.data_result[min_index][11].append(data_set[1][i])
  16.     return result
  18. def UpdateCenters(centers,cluster,threshold):
  19.     #寻找新的聚类中心
  20.     new_centers = []
  21.     for i in range(len(centers)):
  22.         #遍历每个现有的聚类中心
  23.         distance = []
  24.         for j in range(len(cluster[i][0])):
  25.             #遍历第i类中的每个点，将之作为临时中心
  26.             temp_center = [cluster[i][0][j],cluster[i][12][j]]
  27.             dists = 0
  28.             for m in range(len(cluster[i][0])):
  29.                 #计算以该点作为聚类中心的各点距离
  30.                 temp_dist = math.sqrt((temp_center[0] - cluster[i][0][m])**2 + (temp_center[1] - cluster[i][13][m])**2)
  31.                 dists += temp_dist
  32.             distance.append(dists)
  33.         min_dist = distance[0]
  34.         for n in distance:
  35.             #找到距离和最小的临时点
  36.             if n <= min_dist:
  37.                 min_dist = n
  38.         min_index = distance.index(min_dist)    #存放距离和最小点的索引
  39.         temp_center = [cluster[i][0][min_index],cluster[i][14][min_index]]
  40.         #判定，当新老中心点距离delta小于一个阈值时，则认为已经不用继续了
  41.         delta = (centers[i][0] - temp_center[0])**2 + (centers[i][15] - temp_center[1])**2
  42.         if delta >= threshold:
  43.             new_centers.append(temp_center)
  44.         else:
  45.             new_centers.append(centers[i])
  46.     return new_centers

数据可视化

最后由DrawScatter()函数画出各个簇的图像和聚类中心，并用不同颜色标注：

  1. def DrawScatter(result,colors,centers):
  2.     #转换一下centers的格式
  3.     centers_trans = []
  4.     temp_centersx = []
  5.     temp_centersy = []
  6.     for i in centers:
  7.         temp_centersx.append(i[0])
  8.         temp_centersy.append(i[1])
  9.     centers_trans = [temp_centersx,temp_centersy]
  10.     for i in range(len(result.data_result)):
  11.         plt.scatter(result.data_result[i][0],result.data_result[i][16],c = colors[i],marker = '.')
  12.     plt.scatter(centers_trans[0],centers_trans[1],c = colors[len(result.data_result) + 1],marker = 'o')
  14.     plt.show()

参数说明

其中，RunTest()的4个参数分别是data_set k colors threshold，其中data_set代表原始数据集，k代表聚类中心的个数，colors是存放颜色参数的一个列表，threshold则是控制迭代出口的阈值，其越小聚类结果越精确。
由于k是事先给出的，所以我们还得先多尝试几个k，选出最佳的k

六、实验数据及结果分析：

由于聚类中心个数k和迭代阈值threshold需要自行给出，所以先尝试不同参数组合的结果：

k=2,threshold=1

结果如图所示：

image_1ebjbgram1jok1h065sc170l6vem.png-40.6kB

很显然，聚类中心应该为3，所以k取3较为合理

k=3,threshold=1

结果如图所示：

image_1ebjbjoje1gd61oet1tl91dpe1l0e1g.png-41kB

聚类效果明显，黄色和红色的聚类中心效果不错，蓝色簇的聚类中心稍偏，可以适当调小threshold

k=3,threshold=0.01

结果如图所示：

image_1ebjbqe011hqqm33gr21m3c1nqu2a.png-41.2kB

可以看出，聚类和聚类中心的效果明显好了很多，基本达到预期结果

误差分析

由于初始的k个聚类中心是随机的，而聚类结果又与初始的聚类中心是相关的，所以偶尔会出现下图这种情况。可以通过多运行几次取平均值来避免偶然误差的产生：

image_1ebjbp3121dvb14031pf2981bjf1t.png-41.5kB

七、实验结论：

K-means算法能够有效地将无标签的数据进行自主聚类，是一种非常实用的无监督学习方式。实验结果如上，基本达到预期效果

八、总结及心得体会：

K-Means算法让人又爱又恨，他虽然十分好用，能够花费很少的计算开销就方便地得到聚类的结果，但是由于其聚类结果与初始随机聚类中心的取值有关，所以不得不多进行几次试验来去除随机误差的影响，而这无形中又增加了计算量

九、对本实验过程及方法的改进建议：

整体的实现过程没有什么问题，可以再研究一下自动调参的功能，让k和threshold这两个参数能够自动得出，效果会更好

报告评分:          

指导老师签字:          

附录

实验一代码

数据归一化

Normalization.py

  1. #!/user/bin/python3
  2. #coding=utf-8
  4. import xlwt
  5. import xlrd
  6. from xlutils.copy import copy
  8. class Data():
  9.     def __init__(self,sheet_data):
  10.         self.maxA = 0
  11.         self.minA = 0
  12.         self.ori_data = self.get_data(sheet_data)
  13.         self.normalized_data = self.ori_data
  14.         self.length = len(self.ori_data)
  15.         self.GetMinAndMax()
  17.     def get_data(self,sheet_data):
  18.     #获取excel中存储的数据
  19.         data = []
  20.         i = 0
  21.         while True:
  22.             try:
  23.                 data.append(sheet_data.cell(i+1,0).value)
  24.                 i += 1
  25.             except IndexError:
  26.                 break
  27.         return data
  29.     def GetMinAndMax(self):
  30.         #获取数据中的最大值和最小值
  31.         temp_min = self.ori_data[0]
  32.         temp_max = self.ori_data[0]
  33.         for i in range(self.length):
  34.             if self.ori_data[i] <= temp_min:
  35.                 temp_min = self.ori_data[i]
  36.             if self.ori_data[i] >= temp_max:
  37.                 temp_max = self.ori_data[i]
  38.         self.maxA = temp_max
  39.         self.minA = temp_min
  41.     def Normalize(self):
  42.         #数据归一化操作
  43.         for i in range(self.length):
  44.             self.normalized_data[i] = (self.ori_data[i] - self.minA)/(self.maxA - self.minA)
  45. #           print(round(self.normalized_data[i],2))
  47.     def RecordNormalizedData(self,sheet):
  48.         #记录归一化的数据
  49.         sheet.write(0,1,'Normalized Data')
  50.         for i in range(self.length):
  51.             sheet.write(i+1,1,round(self.normalized_data[i],2))
  54. book = xlrd.open_workbook('data1.xlsx')
  55. sheet_data = book.sheet_by_index(0)
  56. book_wt = copy(book)
  57. sheet_wt = book_wt.get_sheet(0)
  58. test_1 = Data(sheet_data)
  60. #数据归一化
  61. test_1.Normalize()
  62. test_1.RecordNormalizedData(sheet_wt)
  64. book_wt.save('data1.xlsx')

点此返回

缺失值处理

fill_blank.py

  1. #!/user/bin/python3
  2. #coding=utf-8
  4. import xlrd
  5. import xlwt
  6. from xlutils.copy import copy
  8. class Data():
  9.     def __init__(self,sheet):
  10.         self.ori_data = self.get_data(sheet)
  11.         self.length = len(self.ori_data)
  12.         self.filled_data = self.ori_data
  14.     def get_data(self,sheet):
  15.     #获取excel中存储的数据
  16.         data = []
  17.         i = 0
  18.         while True:
  19.             try:
  20.                 data.append(sheet.cell(i+1,0).value)
  21.                 i += 1
  22.             except IndexError:
  23.                 break
  24.         return data
  26.     def FillBlank(self):
  27.         count = 0
  28.         data_sum = 0
  29.         blank_index = []
  30.         for i in range(self.length):
  31.             if self.ori_data[i] is not '':
  32.                 count += 1
  33.                 data_sum += self.ori_data[i]
  34.             else:
  35.                 blank_index.append(i)
  36.         aver = data_sum / count
  37.         for i in blank_index:
  38.             self.filled_data[i] = round(aver,2)
  40.     def RcordFilledData(self,sheet):
  41.         sheet.write(0,1,'Filled Data')
  42.         for i in range(self.length):
  43.             sheet.write(i+1,1,self.filled_data[i])
  45. data_excel = xlrd.open_workbook('data2.xlsx')
  46. data_sheet = data_excel.sheet_by_index(0)
  47. data_wt = copy(data_excel)
  48. sheet_wt = data_wt.get_sheet(0)
  50. data = Data(data_sheet)
  51. data.FillBlank()
  52. data.RcordFilledData(sheet_wt)
  54. data_wt.save('data2.xlsx')

点此返回

特征筛选

feature_select.py

  1. #!/user/bin/python3
  2. #coding=utf-8
  3. import xlrd
  4. import xlwt
  5. from xlutils.copy import copy
  6. import math
  8. class Data():
  9.     def __init__(self,sheet):
  10.         self.nrows = sheet.nrows
  11.         self.ncols = sheet.ncols
  12.         self.table = self.get_data(sheet)
  13.         self.Ent_D = self.get_Ent_D()
  15.     def get_data(self,sheet):
  16.         temp_table = []
  17.         for i in range(self.ncols):
  18.             temp_col = sheet.col_values(i)[0:self.nrows]
  19.             temp_table.append(temp_col)
  20.         return temp_table
  22.     def get_feature_information(self,n):
  23.         #获取第n+1列的相关信息
  24.         temp_feature = Feature(self.table[n][0],self.Ent_D)
  25.         dict_True = {}        
  26.         dict_False = {}
  27.         #将数据统计进dict_True和dict_False中
  28.         for i in range(1,self.nrows):
  29.             if self.table[self.ncols-1][i] == '是':
  30.                 if self.table[n][i] in dict_True:
  31.                     dict_True[self.table[n][i]] += 1
  32.                 else:
  33.                     temp_dict = {self.table[n][i]:1}
  34.                     dict_True.update(temp_dict)
  35.             elif self.table[self.ncols-1][i] == '否':
  36.                 if self.table[n][i] in dict_False:
  37.                     dict_False[self.table[n][i]] += 1
  38.                 else:
  39.                     temp_dict = {self.table[n][i]:1}
  40.                     dict_False.update(temp_dict)
  41.         #保证两词典的键一致
  42.         for i in dict_True:
  43.             if i not in dict_False:
  44.                 temp_dict = {i:0}
  45.                 dict_False.update(temp_dict)
  46.         for i in dict_False:
  47.             if i not in dict_True:
  48.                 temp_dict = {i:0}
  49.                 dict_True.update(temp_dict)
  51.         temp_feature.dict_True = dict_True
  52.         temp_feature.dict_False = dict_False
  53.         #将属性的每个状态存储在列表status中
  54.         for i in dict_True:
  55.             if i not in temp_feature.status:
  56.                 temp_feature.status.append(i)
  57.         for i in dict_False:
  58.             if i not in temp_feature.status:
  59.                 temp_feature.status.append(i)
  60.         temp_feature.information_gain = temp_feature.get_information_gain()
  61.         return temp_feature
  63.     def get_Ent_D(self):
  64.         #获取根节点的信息熵Ent_D
  65.         count_true = 0
  66.         count_false = 0
  67.         for i in self.table[self.ncols-1]:
  68.             if i == '是':
  69.                 count_true += 1
  70.             elif i == '否':
  71.                 count_false += 1
  72.         p_true = count_true/(count_true + count_false)
  73.         p_false = count_false/(count_true + count_false)
  74.         Ent_D = 0 - (p_true * math.log(p_true,2) + p_false * math.log(p_false,2))
  75.         return Ent_D
  77. class Feature():
  78.     #对象的其中一个属性，例如'色泽'
  79.     def __init__(self,name,Ent_D):
  80.         self.name = name
  81.         self.dict_True = {}
  82.         self.dict_False = {}
  83.         self.status = []
  84.         self.Ent_D = Ent_D
  85.         self.information_gain = 0
  87.     def get_information_gain(self):
  88.         #获取该属性的信息增益
  89.         Ent_D_i = []        #存储该属性各个状态的信息熵
  90.         p_D_i = []          #存储该属性各个状态的比例
  91.         sample_quantity = 0
  92.         result = 0
  93.         for i in self.dict_True:
  94.             sample_quantity += self.dict_True[i]
  95.         for i in self.dict_False:
  96.             sample_quantity += self.dict_False[i]
  98.         for i in self.status:
  99.             total = self.dict_True[i] + self.dict_False[i]
  100.             if self.dict_True[i] != 0:
  101.                 if self.dict_False[i] != 0:
  102.                     temp_Ent_D_i = 0 - ((self.dict_True[i]/total) * math.log(self.dict_True[i]/total,2) + (self.dict_False[i]/total) * math.log(self.dict_False[i]/total,2))
  103.                 else:
  104.                     temp_Ent_D_i = 0 - self.dict_True[i]/total * math.log(self.dict_True[i]/total,2)
  105.             else:
  106.                 temp_Ent_D_i = 0 - self.dict_False[i]/total * math.log(self.dict_False[i]/total,2)
  107.             #input()
  108.             temp_p = total/sample_quantity
  109.             Ent_D_i.append(temp_Ent_D_i)
  110.             p_D_i.append(temp_p)
  112.         for i in range(len(Ent_D_i)):
  113.             result += Ent_D_i[i] * p_D_i[i]
  114.         result = self.Ent_D - result
  115.         #print('gain is :',result)
  117.         return result
  120. book = xlrd.open_workbook('data3.xlsx')
  121. sheet_rd = book.sheet_by_index(0)
  122. book_wt = copy(book)
  123. sheet_wt = book_wt.get_sheet(0)
  125. data = Data(sheet_rd)
  126. features = []
  127. for i in range(1,data.ncols-3):
  128.     temp_feature = data.get_feature_information(i)
  129.     features.append(temp_feature)
  131. #print(data.table)
  132. sheet_wt2 = book_wt.get_sheet(1)
  134. sheet_wt2.write(1,0,'信息增益')
  135. for i in range(1,data.ncols-3):
  136.     sheet_wt2.write(0,i,features[i-1].name)
  137.     sheet_wt2.write(1,i,round(features[i-1].information_gain,3))
  139. book_wt.save('data3.xlsx')
  141. print('Ent_D of the root note is:',round(data.Ent_D,3))
  142. for i in features:
  143.     print('the information gain of',i.name,'is :',round(i.information_gain,3))

点此返回

实验二代码

关联规则挖掘：

dig_rules.py

  1. #!/user/bin/python3
  2. #coding=utf-8
  4. import xlrd
  5. import xlwt
  7. class Node():
  8.     def __init__(self,total):
  9.         self.content = []
  10.         self.data = []
  11.         self.sup = 0
  12.         self.total = total
  14. #更新当前层，剪枝
  15. def UpdateLayer(ori_list,threshold):
  16.     temp_list = []
  17.     for i in ori_list:
  18.         if i.sup > threshold:
  19.             temp_list.append(i)
  20.     return temp_list
  22. #连接上层生成下层
  23. def GenNewLayer(ori_list):
  24.     new_list = []
  25.     for i in ori_list:
  26.         for j in ori_list:
  27.             if i != j:
  28.                 new_list.append(Merge(i,j))
  29.     return new_list
  31. #Merge函数合并a,b两个结点           
  32. def Merge(a,b):
  33.     temp = Node(a.total)
  34.     #合并self.content的内容，并去重
  35.     for i in a.content:
  36.         temp.content.append(i)
  37.     for i in b.content:
  38.         if i not in a.content:
  39.             temp.content.append(i)
  40.     #统计data和sup的内容
  41.     count = 0
  42.     for i in range(a.total):
  43.         if a.data[i] == b.data[i] and a.data[i] == 1:
  44.             count += 1
  45.             temp.data.append(1)
  46.         else:
  47.             temp.data.append(0)
  48.     temp.sup = count
  49.     return temp
  51. def ReadData(sheet):
  52.     temp_layer = []
  53.     for i in range(1,sheet.ncols):
  54.         temp_node = Node(sheet.nrows - 1)
  55.         temp_node.content.append(sheet.cell(0,i).value)
  56.         count = 0
  57.         for j in range(1,sheet.nrows):
  58.             if sheet.cell(j,i).value == 1:
  59.                 count += 1
  60.             temp_node.data.append(int(sheet.cell(j,i).value))
  61.         temp_node.sup = count
  62.         temp_layer.append(temp_node)
  63.     return temp_layer
  65. book = xlrd.open_workbook('data.xlsx')
  66. sheet = book.sheet_by_index(0)
  68. layer1 = ReadData(sheet)
  69. layer1 = UpdateLayer(layer1,2)
  70. layer2 = GenNewLayer(layer1)
  71. layer2 = UpdateLayer(layer2,2)
  73. for i in layer2:
  74.     print(i.content,';',i.data,';',i.sup/i.total)

点此返回

实验三代码

临时锚点

KNN分类

knn_train&test.py

  1. #!/user/bin/python3
  2. #coding=utf-8
  3. #KNN
  4. from scipy.io import arff
  5. import pandas as pd
  6. import math
  8. class Node():
  9.     def __init__(self):
  10.         self.petallength = 0
  11.         self.petalwidth = 0
  12.         self.classes =''
  14. def GetData(df):
  15.     #读取arff文件，将每一行存成一个Node类，存在data_list列表中
  16.     data_list = []
  17.     ptl = df['petallength'].values
  18.     ptw = df['petalwidth'].values
  19.     classes = df['class'].values
  20.     num = len(ptl)
  21.     for i in range(num):
  22.         temp_node = Node()
  23.         temp_node.petallength = ptl[i]
  24.         temp_node.petalwidth = ptw[i]
  25.         temp_node.classes = classes[i]
  26.         data_list.append(temp_node)
  27.     return data_list
  29. def GetDist(node_a,node_b):
  30.     #计算两点的距离
  31.     distance = math.sqrt((node_a.petallength - node_b.petallength)**2 + (node_a.petalwidth - node_b.petalwidth)**2)
  32.     return distance
  34. def Predict(train_list,node_a,k):
  35.     #开始预测数据
  36.     dist_list = []      #存放离各点距离
  37.     index_list = []     #存放K邻近的点的索引index
  38.     for i in train_list:
  39.         dist_list.append(GetDist(node_a,i))
  40.     dist_copy = dist_list
  41.     for i in range(k):  #寻找k邻近的索引值，并存放在index_list中
  42.         temp_min = 999
  43.         temp_index = 0
  44.         for j in range(len(train_list)):
  45.             if dist_copy[j] <= temp_min:
  46.                 temp_min = dist_copy[j]
  47.                 temp_index = j
  48.         dist_copy[temp_index] = 999
  49.         index_list.append(temp_index)
  50.     classes = {}
  51.     #统计k邻近的分类结果，并以字典形式存放在classes中
  52.     for i in index_list:
  53.         if train_list[i].classes not in classes:
  54.             classes[train_list[i].classes] = 1
  55.         else:
  56.             classes[train_list[i].classes] += 1
  57.     result = ''
  58.     max_times = 0
  59.     #选取次数最多的分类结果并存放在result中
  60.     for i in classes:
  61.         if classes[i] >= max_times:
  62.             max_times = classes[i]
  63.             result = i
  64.     return result
  66. def RunTest(train_list,test_list,k):
  67.     #开始运行测试
  68.     count = 0
  69.     for i in test_list:
  70.         result = Predict(train_list,i,k)
  71.         if i.classes == result:     #判断预测结果与标签是否相符
  72.             count += 1
  73.             print('sample',test_list.index(i),'is correctly classified as',i.classes,'!')
  74.     rate = float(count / len(test_list))
  75.     return rate
  77. data_train = arff.loadarff('iris.2D.train.arff')
  78. df_train = pd.DataFrame(data_train[0])
  79. train_list = GetData(df_train)
  81. data_test = arff.loadarff('iris.2D.test.arff')
  82. df_test = pd.DataFrame(data_test[0])
  83. test_list = GetData(df_test)
  84. '''
  85. for i in test_list:
  86.     print(i.petallength,i.petalwidth,i.classes)
  87. '''
  88. rate = RunTest(train_list,test_list,3)
  89. #输出最后的预测准确率
  90. print('the accuracy of classification is:',rate)

点此返回

决策树分类

decision_tree.py

  1. #!/user/bin/python3
  2. #coding=utf-8
  3. #KNN
  4. from scipy.io import arff
  5. import pandas as pd
  6. import numpy as np
  7. import math
  9. class Node():
  10.     def __init__(self):
  11.         self.petallength = 0
  12.         self.petalwidth = 0
  13.         self.classes =''
  15. class Tree():
  16.     def __init__(self):
  17.         self.name = ''
  18.         self.standard = 0
  19.         self.left = None
  20.         self.right = None
  22. def GetData(df):
  23.     #读取arff文件，将每一行存成一个Node类，存在data_list列表中
  24.     data_list = []
  25.     ptl = df['petallength'].values
  26.     ptw = df['petalwidth'].values
  27.     classes = df['class'].values
  28.     num = len(ptl)
  29.     for i in range(num):
  30.         temp_node = Node()
  31.         temp_node.petallength = ptl[i]
  32.         temp_node.petalwidth = ptw[i]
  33.         temp_node.classes = classes[i]
  34.         data_list.append(temp_node)
  35.     return data_list
  37. def GenTree(train_list):
  38.     root = Tree()
  39.     gain = []
  40.     gain.append(GetGain(train_list,'petallength'))
  41.     gain.append(GetGain(train_list,'petalwidth'))
  42.     if gain[0] >= gain[1]:
  43.         root.name = 'petallength'
  44.         root.standard = GetMedian(train_list,'petallength')
  45.         root.left = Tree()
  46.         root.left.name = 'petalwidth'
  47.         root.left.standard = GetMedian(train_list,'petalwidth')
  48.         root.left.left = Tree()
  49.         root.left.left.name = '1'
  50.         root.left.right = Tree()
  51.         root.left.right.name = '2'
  53.         root.right = Tree()
  54.         root.right.name = 'petalwidth'
  55.         root.right.standard = GetMedian(train_list,'petalwidth ')
  56.         root.right.left = Tree()
  57.         root.right.left.name = '3'
  58.         root.right.right = Tree()
  59.         root.right.right.name = '4'
  60.     else:
  61.         root.name = 'petalwidth'
  62.         root.standard = GetMedian(train_list,'petalwidth')
  63.         root.left = Tree()
  64.         root.left.name = 'petallength'
  65.         root.left.standard = GetMedian(train_list,'petallength')
  66.         root.left.left = Tree()
  67.         root.left.left.name = '1'
  68.         root.left.right = Tree()
  69.         root.left.right.name = '2'
  71.         root.right = Tree()
  72.         root.right.name = 'petallength'
  73.         root.right.standard = GetMedian(train_list,'petallength')
  74.         root.right.left = Tree()
  75.         root.right.left.name = '3'
  76.         root.right.right = Tree()
  77.         root.right.right.name = '4'
  78.     return root
  80. def GetGain(train_list,name):
  81.     #计算信息增益
  82.     if name is 'petallength':
  83.         data_list = []
  84.         for i in train_list:
  85.             data_list.append(i.petallength)
  86.         median = np.median(data_list)
  87.         ent_d = GetEnt(train_list)
  88.         d_list = []
  89.         temp_list = []
  90.         for i in train_list:
  91.             if i.petallength >= median:
  92.                 temp_list.append(i)
  93.         d_list.append(temp_list)
  94.         gain = ent_d
  95.         for i in d_list:
  96.             gain = gain - len(i)*GetEnt(i)/len(train_list)
  97.         return gain
  99.     elif name is 'petalwidth':
  100.         data_list = []
  101.         for i in train_list:
  102.             data_list.append(i.petalwidth)
  103.         median = np.median(data_list)
  104.         ent_d = GetEnt(train_list)
  105.         d_list = []
  106.         temp_list = []
  107.         for i in train_list:
  108.             if i.petalwidth >= median:
  109.                 temp_list.append(i)
  110.         d_list.append(temp_list)
  111.         gain = ent_d
  112.         for i in d_list:
  113.             gain = gain - len(i)*GetEnt(i)/len(train_list)
  114.         return gain
  116. def GetEnt(train_list):
  117.     #计算信息熵
  118.     count = {}
  119.     for i in train_list:
  120.         if i.classes not in count:
  121.             count[i.classes] = 1
  122.         elif i.classes in count:
  123.             count[i.classes] += 1
  124.     total = 0
  125.     for i in count:
  126.         total += count[i]
  127.     ent = 0
  128.     for i in count:
  129.         ent = ent - count[i]/total * math.log(2,count[i]/total)
  130.     return ent
  132. def GetMedian(train_list,name):
  133.     if name is 'petallength':
  134.         data_list = []
  135.         for i in train_list:
  136.             data_list.append(i.petallength)
  137.         median = np.median(data_list)
  138.     elif name is 'petalwidth':
  139.         data_list = []
  140.         for i in train_list:
  141.             data_list.append(i.petalwidth)
  142.         median = np.median(data_list)
  143.     return median
  145. def print_all(root):
  146.     if root.left is not None:
  147.         print('name:',root.name,'standard:',root.standard)
  148.         print_all(root.left)
  149.         print_all(root.right)
  150.     if root.left is None:
  151.         print('type:',root.name)
  153. def RunTest(root,test_list,name):
  154.     count = 0
  155.     for i in test_list:
  156.         if root.name is 'petallength':
  157.             #petallength -> petalwidth
  158.             if i.petallength >= root.standard:
  159.                 #left
  160.                 if i.petalwidth >= root.left.standard:
  161.                     #left.left
  162.                     pred = root.left.left.name
  163.                 else:
  164.                     ##left.right
  165.                     pred = root.left.right.name
  166.             else:
  167.                 #right
  168.                 if i.petalwidth >= root.right.standard:
  169.                     #right.left
  170.                     pred = root.right.left.name
  171.                 else:
  172.                     #right.right
  173.                     pred = root.right.right.name
  174.         elif root.name is 'petalwidth':
  175.             #petalwidth -> petallength
  176.             if i.petalwidth >= root.standard:
  177.                 #left
  178.                 if i.petallength >= root.left.standard:
  179.                     #left.left
  180.                     pred = root.left.left.name
  181.                 else:
  182.                     ##left.right
  183.                     pred = root.left.right.name
  184.             else:
  185.                 #right
  186.                 if i.petallength >= root.right.standard:
  187.                     #right.left
  188.                     pred = root.right.left.name
  189.                 else:
  190.                     #right.right
  191.                     pred = root.right.right.name
  192.         result = ''
  193.         if pred is '1':
  194.             result = name[2]
  195.         elif pred is '2':
  196.             result = name[1]
  197.         elif pred is '3' or pred is '4':
  198.             result = name[0]
  199. #       print('i.classes:',i.classes,'; result:',result)
  200.         if result == i.classes:
  201.             count += 1
  202.             print('case',test_list.index(i),'is correctly predicted as',i.classes)
  203.     rate = float(count/len(test_list))
  204.     return rate
  206. data_train = arff.loadarff('iris.2D.train.arff')
  207. df_train = pd.DataFrame(data_train[0])
  208. train_list = GetData(df_train)
  210. data_test = arff.loadarff('iris.2D.test.arff')
  211. df_test = pd.DataFrame(data_test[0])
  212. test_list = GetData(df_test)
  214. decision_tree = GenTree(train_list)
  216. name = []
  217. for i in train_list:
  218.     if i.classes not in name:
  219.         name.append(i.classes)
  221. #print_all(decision_tree)
  222. rate = RunTest(decision_tree,test_list,name)
  223. print('the accuracy of prediction is:',rate)

点此返回

实验四代码

临时锚点2

K-Means聚类算法

k_means.py

  1. #!user/bin/python3
  2. #coding=utf-8
  3. import xlrd
  4. import xlwt
  5. import matplotlib.pyplot as plt
  6. import math
  7. import random
  9. class KMeans():
  10.     #存放kmeans结果的类
  11.     def __init__(self,data_set,k):
  12.         self.data_set = data_set        #原始数据集
  13.         self.num = k                    #聚类
  14.         self.data_result = self.InitResult(k)   #存放聚类结果
  16.     def InitResult(self,k):
  17.         result_list = []
  18.         for i in range(k):
  19.             temp_list = [[],[]]
  20.             result_list.append(temp_list)
  21.         return result_list
  23. def GetData(sheet):
  24.     data_set = []
  25.     col_1 = sheet.col_values(0)[1:]
  26.     col_2 = sheet.col_values(1)[1:]
  27.     data_set.append(col_1)
  28.     data_set.append(col_2)
  29.     return data_set
  31. def DrawScatter(result,colors,centers):
  32.     #转换一下centers的格式
  33.     centers_trans = []
  34.     temp_centersx = []
  35.     temp_centersy = []
  36.     for i in centers:
  37.         temp_centersx.append(i[0])
  38.         temp_centersy.append(i[1])
  39.     centers_trans = [temp_centersx,temp_centersy]
  40.     for i in range(len(result.data_result)):
  41.         plt.scatter(result.data_result[i][0],result.data_result[i][1],c = colors[i],marker = '.')
  42.     plt.scatter(centers_trans[0],centers_trans[1],c = colors[len(result.data_result) + 1],marker = 'o')
  44.     plt.show()
  46. def GetCluster(centers,data_set):
  47.     #根据当前的聚类中心centers进行聚类划分，返回聚类结果
  48.     result = KMeans(data_set,len(centers))
  49.     for i in range(len(data_set[0])):
  50.         #遍历每个点
  51.         min_dist = 99999
  52.         min_index = 0
  53.         for j in range(len(centers)):
  54.             #遍历聚类中心
  55.             temp_dist = math.sqrt((data_set[0][i] - centers[j][0])**2 + (data_set[1][i] - centers[j][1])**2)
  56.             if temp_dist <= min_dist:
  57.                 min_dist = temp_dist
  58.                 min_index = j
  59.         result.data_result[min_index][0].append(data_set[0][i])
  60.         result.data_result[min_index][1].append(data_set[1][i])
  61.     return result
  63. def UpdateCenters(centers,cluster,threshold):
  64.     #寻找新的聚类中心
  65.     new_centers = []
  66.     for i in range(len(centers)):
  67.         #遍历每个现有的聚类中心
  68.         distance = []
  69.         for j in range(len(cluster[i][0])):
  70.             #遍历第i类中的每个点，将之作为临时中心
  71.             temp_center = [cluster[i][0][j],cluster[i][1][j]]
  72.             dists = 0
  73.             for m in range(len(cluster[i][0])):
  74.                 #计算以该点作为聚类中心的各点距离
  75.                 temp_dist = math.sqrt((temp_center[0] - cluster[i][0][m])**2 + (temp_center[1] - cluster[i][1][m])**2)
  76.                 dists += temp_dist
  77.             distance.append(dists)
  78.         min_dist = distance[0]
  79.         for n in distance:
  80.             #找到距离和最小的临时点
  81.             if n <= min_dist:
  82.                 min_dist = n
  83.         min_index = distance.index(min_dist)    #存放距离和最小点的索引
  84.         temp_center = [cluster[i][0][min_index],cluster[i][1][min_index]]
  85.         #判定，当新老中心点距离delta小于一个阈值时，则认为已经不用继续了
  86.         delta = (centers[i][0] - temp_center[0])**2 + (centers[i][1] - temp_center[1])**2
  87.         if delta >= threshold:
  88.             new_centers.append(temp_center)
  89.         else:
  90.             new_centers.append(centers[i])
  91.     return new_centers
  93. def RunTest(data_set,k,colors,threshold):
  94.     new_centers = []
  95.     centers = []
  96.     randlist = random.sample(range(0,len(data_set[0])),k)
  97.     #初始化k个聚类中心
  98.     for i in randlist:
  99.         temp_center = [data_set[0][i],data_set[1][i]]
  100.         new_centers.append(temp_center)
  101.     result = KMeans(data_set,k)
  102.     #经过更新后的聚类中心，如果没有变化，就停止迭代
  103.     count = 0
  104.     while new_centers != centers:
  105.         centers = new_centers
  106.         result = GetCluster(centers,data_set)
  107.         new_centers = UpdateCenters(centers,result.data_result,threshold)
  109.     DrawScatter(result,colors,centers)
  112. book = xlrd.open_workbook('dataset.xlsx')
  113. sheet = book.sheet_by_index(0)
  115. data_set = GetData(sheet)
  116. colors = ['b','r','y','k','g','m','c','w']
  118. RunTest(data_set,3,colors,0.01)
  119. '''
  120. for i in range(10):
  121.     RunTest(data_set,i,colors)
  122. '''

点此返回

添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注