软件工程硕士论文 基于改进的kNN算法的 MicroDM的设计与实现.doc

《软件工程硕士论文 基于改进的kNN算法的 MicroDM的设计与实现.doc》由会员分享，可在线阅读，更多相关《软件工程硕士论文 基于改进的kNN算法的 MicroDM的设计与实现.doc（48页珍藏版）》请在三一办公上搜索。

1、研 究 生 毕 业 论 文（申请工程硕士学位）论文题目基于改进的k-NN算法的MicroDM的设计与实现作者姓名 学科、专业名称工程硕士(软件工程领域)研究方向软件工程指导教师 2009年 5 月 10 日学 号： MG0732077论文答辩日期： 年 月 日指 导 教 师： （签字）基于改进的k-NN算法的microDM的设计和实现作 者:指导教师:南京大学研究生毕业论文(申请工程硕士学位)南京大学软件学院2009年5月The Design of MicroDM Based on Improved k-NNYU, QinSubmitted in partial fulfillment of

2、the requirements for the degree of Master of EngineeringSupervised by Professor LI, Xuandong Lecturer Liu, HaitaoSoftware InstituteNANJING UNIVERSITYNanjing, ChinaMay, 2009摘 要目前，互联网已经成为重要网络媒体，网上海量资源在迅速膨胀。随着信息量的快速增长，分类已成为信息检索，知识挖掘和管理等领域的关键技术。分类的精确程度取决于特征提取的科学性和分类算法的科学性。现有的分类方法主要有支持向量机（SVM），K-近邻（K-NN）

3、，决策树，线性最小二乘法估计（LLSF）和贝叶斯分类算法（Bayes）等。K-NN算法用已归类到数据训练分类器，是一种基于实例研究的文本分类算法。K-NN算法实现非常简单有效，同时算法分类效率高，适用于海量互联网文本信息分类处理。将传统的K-NN算法直接应用于互联网媒体海量发布信息智能分类时，算法实际效果不佳或者性能不稳定。鉴于此，文中设计与实现了基于改进后的K-NN算法的MicroDM。改进的K-NN方法实现了重要互联网媒体海量发布信息智能分类，并使用脚本自动生成测试数据文件，分别使用传统的K-NN算法以及MicroDM中的K-NN算法进行数据挖掘，评估运行结果，验证改进算法的有效性。实验结

4、果表明改进的K-NN算法能更加有效的分类。关键词：分类，K-NN算法，数据挖掘平台 AbstractToday, internet has become the most import network media and the resources of network inflate quickly. Classification becomes the key technology in the data mining field while the information is increasing crazy. The accuracy of classifier depends on

5、 the scientificity of feature extraction and classifier algorithms. Now there are several classifier algorithms, such as SVM, K-NN, DTree, LLSF and Bayes.K-NN (K nearest neighbor) algorithm use labeled data to build the classifier. It is a instance-based learing algorithm. The K-NN algorithm is almo

6、st the simplest of all machine learing algorithms.It is good at dealing with a classification to information the network medium released.The actual effect is not so good or the performance is unstable if we use the traditional K-NN algorithm dierectly to deal with the massive amount of information t

7、hat released by the important network medium. Owing to this, this article designs and implements the datamining platform named MicroDM based on improved K-NN algorithm. The improved K-NN algorithm implements the information intelligence classification on network media and then validates the validity

8、 of this improved algorithm. Whats more, this article uses data files generated automatically by a script to demonstrate the result produced by the traditional K-NN algorithm as well as the improved K-NN algorithm.The result of the experiment indicates that the improved K-NN algorithm can be more ef

9、fective.Keywords：Classification, K-NN algorithm, datamining platform目 录第一章 引言21.1本文研究的背景及问题21.2 数据挖掘简介21.2.1 数据挖掘概述21.2.2 数据挖掘的对象31.2.3 数据挖掘的流程41.2.4 数据挖掘的方法51.3 k-NN简介61.3.1 朴素的k-NN算法61.3.2 k-NN算法的优缺点分析71.4 本文的工作8第二章 相关技术92.1 数据预处理92.1.1 数据清理92.1.2数据集成102.1.3数据变换102.1.4数据离散化122.2 交叉验证（Cross Validat

10、ion）122.3 评估方法132.4 小结13第三章 基于改进的K-NN算法的MicroDM的分析与设计143.1 项目简介143.2 运行界面143.3 设计图163.4 数据挖掘流程图173.5 K-NN算法分析与改进183.5.1数据文件（ARFF）分析183.5.2数据特征集分析213.5.3算法分析233.5.4算法详解233.5.5K-NN算法流程图253.6 小结26第四章 MicroDM的实现与效果评估274.1算法实现274.1.1Z-Score算法实现274.1.2Min-Max算法实现284.1.3改进后的k-NN中距离的算法实现294.2 实现结果与分析314.2.1

11、 评估指标314.2.2 实验设置314.2.3 运行过程324.2.4结果分析344.3 小结37第五章 总结和展望38参 考 文 献39致 谢41图表目录图1.1 KDD过程示意图4图1.2 K-NN6图3.1 MicroDM运行界面15图3.2 设计的包图16图3.3 类图17图3.5 数据挖掘流程图18图3.4 data.arff19表3.1 labbor.arff22图3.6 结构图26图4.1 Z-score算法定义28图4.2 Max-Min算法定义29图4.3 扩展的距离算法定义31图4.4 运行界面33图4.5 运行结果输出界面34表4.1 best K对比34表4.2 传统

12、的K-NN算法36表4.3 改进&不使用ordinal36表4.4 改进&使用ordinal37第一章 引言1.1本文研究的背景及问题目前，互联网已经成为重要网络媒体，网上海量资源在快速膨胀。随着信息量的快速增长，分类已成为信息检索，知识挖掘和管理等领域的关键技术。分类的精确程度取决于特征提取的科学性和分类算法的科学性。现有的分类方法主要有支持向量机（SVM），K近邻（KNN），决策树，线性最小二乘法估计（LLSF）和贝叶斯分类算法（Bayes）等。相关研究证明，KNN算法是VSM（向量空间模型）下最好的分类算法之一。KNN方法基于类比学习，是一种非参数的分类技术，在基于统计的模式识别中非常有

13、效，对于未知和非正态分布可以取得较高的分类正确率，具有鲁帮性，概念清晰等诸多优点。而且，KNN算法实现非常简单有效。同时算法分类效率高，适用于海量互联网文本信息分类处理。对于灵活多变的互联网文本信息，传统的KNN方法的缺陷逐渐暴露出来，如，KNN算法是建立在VSM模型上的，计算临近性时主要处理的对象是数值属性, 大多使用欧几里德距离，并且每个数值属性都取相同的权值；这严重限制了KNN方法的应用范围以及分类精度。1.2 数据挖掘简介1.2.1 数据挖掘概述随着数据库技术的迅速发展以及数据库管理系统的广泛应用，人们积累的数据越来越多。激增的数据背后隐藏着许多重要的信息，人们希望能够对其进行更高层次

14、的分析，以便更好地利用这些数据。目前的数据库系统可以高效地实现数据的录入、查询、统计等功能，但无法发现数据中存在的关系和规则，无法根据现有的数据预测未来的发展趋势。缺乏挖掘数据背后隐藏的知识的手段，导致了“数据爆炸但知识贫乏”的现象。同时，计算机技术的另一领域人工智能自1956年诞生之后取得了重大进展。经历了博弈时期、自然语言理解、知识工程等阶段， 目前的研究热点是机器学习。机器学习是用计算机模拟人类学习的一门科学，比较成熟的算法有决策树、K-NN算法等。用数据库管理系统来存储数据，用机器学习的方法来分析数据，挖掘大量数据背后的知识，这两者的结合促成了数据库中的知识发现(KDD：Knowled

15、ge Discovery in Databases)的产生。数据挖掘是KDD最核心的部分，是采用机器学习、统计等方法进行知识学习的阶段。预测和描述是数据挖掘的主要任务。预测是指用一些变量或数据库中的若干字段预测其他感兴趣的变量或字段的值；描述是指挖掘出数据库的一般特性。许多人将数据挖掘看成是数据库中的知识发现(Knowledge Discovery in Database KDD)的一部分，这是狭义上的数据挖掘；从广义的观点来看，数据挖掘系统代表了KDD的整个过程。KDD的目标是从大型数据集中获取有用知识，它是一个交互式的半自动分析工具，系统的用户应当对有关领域具备良好的理解力。1.2.2 数

16、据挖掘的流程下面是对数据挖掘流程的介绍图1.1 KDD过程示意图1. 确定发现任务的应用领域、背景知识和性质。2. 准备相关的数据子集：将分布在各处以各种形式存放的数据，按照KDD的需求收集过来，并根据分析需求，选择适当的和典型的数据，缩小处理范围。3. 对数据进行预处理：通过汇总或聚集操作将数据变换统一成适合挖掘的形式。4. 进行数据挖掘，发现模式并表达成易于理解的规则或树的形式：模式是数据的一个子集的抽象表示，它可以以人工的方式或自动的方式建立。5. 评价和解释发现的模式：根据设定目标(通常为兴趣度度量)，利用专业知识，对数据挖掘结果进行评估和解释，去除多余的或不重要的模式，将结果提交给用

17、户。KDD表示了从低层数据抽象到高级知识的过程。KDD过程必然是重复的。数据挖掘的结果可能会要求在数据准备阶段作某些必要的变化。模式的后处理也可能导致用户对模式类型作适当的修改等等。1.2.3 数据挖掘的对象根据信息存储格式，用于挖掘的对象有关系数据库、面向对象数据库、数据仓库、文本数据源、多媒体数据库、空间数据库、时态数据库、异质数据库以及internet等。1.2.4 数据挖掘的方法1. 空间分析方法指采用综合属性数据分析、拓扑分析、缓冲区分析、密度分析、距离分析、叠置分析、网络分析、地形分析、趋势面分析、预测分析等在内 的分析模型和方法，用以发现目标在空间上的相连、相邻和共生等关联规则，

18、或挖掘出目标之间的最短路径、最优路径等知识。目前常用的空间分析方法包括探测性 的数据分析、空间相邻关系挖掘算法、探测性空间分析方法、探测性归纳学习方法、图像分析方法等。2. 统计分析方法指利用空间对象的有限信息和/或不确定性信息进行统计分析，进而评估、预测空间对象属性的特征、统计规律等知识的方法。它主要运用空间自协方差结构、变异函数或与其相关的自协变量或局部变量值的相似程度实现包含不确定性的空间数据挖掘。3. 空间关联规则挖掘方法即在空间数据库（数据仓库）中搜索和挖掘空间对象（及其属性）之间的关联关系的算法。最著名的关联规则挖掘算法是Agrawal提出的Apriori算法；此外还有程继华等提出

19、的多层次关联规则的挖掘算法、许龙飞等提出的广义关联规则模型挖掘方法等。4. 聚类分析方法即根据实体的特征对其进行聚类或分类，进而发现数据集的整个空间分布规律和典型模式的方法。常用的聚类方法有K-mean, K-medoids方法、Ester等提出的基于R树的数据聚焦法及发现聚合亲近关系和公共特征的算法、周成虎等提出的基于信息熵的时空数据分割聚类模型等。5. 神经网络方法即通过大量神经元构成的网络来实现自适应非线性动态系统，并使其具有分布存储、联想记忆、大规模并行处理、自学习、自组织、自适应等功能的方法；在空间数据挖掘中可用来进行分类和聚类知识以及特征的挖掘。6. 决策树方法即根据不同的特征，以

20、树型结构表示分类或决策集合，进而产生规则和发现规律的方法。采用决策树方法进行空间数据挖掘的基本步骤如下：首先利用训练空间实体集生成测试函数；其次根据不同取值建立决策树的分支，并在每个分支子集中重复建立下层结点和分支，形成决策树；然后对决策树进行 剪枝处理，把决策树转化为据以对新实体进行分类的规则。1.3 k-NN简介k-NN(k-Nearest Neighbors)算法又叫k-最临近方法。假设每一个类包含多个样本数据，而且每个数据都有一个唯一的类标记表示这些样本是属于哪一个分类， k-NN就是计算每个样本数据到待分类数据的距离，取和待分类数据最近的k各样本数据，那么这个k个样本数据中哪个类别的

21、样本数据占多数，则待分类数据就属于该类别。 k-NN 分类规则是较为常见的一种有规划的非参数分类算法。它的基本思想就是给定一个包含n个记录的训练数据集, k-NN 分类器根据特定的相似度,分派输入样本到训练集合中k个最近的类中最公共的类。图1.2 K-NN1.3.1 朴素的k-NN算法最临近分类基于类比学习。训练样本用n维数值属性描述,每个样本代表n 维空间的一个点。这样,所有的训练样本都存放在n维模式空间中。给定一个未知样本, k-NN搜索模式空间,找出最接近未知样本的k个训练样本,这k个训练样本是未知样本的k 个近邻。临近性用欧几里德距离定义, 其中两个点X = ( x1 , x2 , .

22、 . . , x n ) 和Y = ( y1 ,y2 , . . . , yn) 的欧氏距离是未知样本被分配到k个最临近者中最公共的类。1.3.2 k-NN算法的优缺点分析1. 优点k-NN的原理非常直观，算法的实现也很简单；k-NN没有训练过程，不需要特征选取和训练，很容易处理类比数目多的情况；k-NN是一种在线（online）技术，这意味着新的数据可以在任何时候被添加进来，这一点不同于以支持向量机为代表的一类技术，后者在数据改变之后必须重新进行训练。而对于k-NN而言，添加新的数据根本不须要进行任何的计算，只要将数据添加到集合中即可；在基于统计的模式识别中非常有效，对于未知和非正态分布可以

23、取得较高的分类正确率，具有鲁帮性，概念清晰等诸多优点。2. 缺点原始k-NN 算法中计算临近性时主要处理的对象是数值属性, 大多使用欧几里德距离，并且每个数值属性都取相同的权值；k-NN是基于距离的局部最优的算法，当数据中存在噪声时，k-NN算法会受到明显的影响；为了完成预测，它要求所有的训练数据都必须缺一不可；为了找到最为接近的数据项，每一项待预测的数据都必须和所有其他数据项进行比较，这一过程对于某些应用而言也许会显得非常低效；k-NN在计算距离时考虑了所有的变量。这意味着，如果这些变量衡量的是不同的事物，而其中某个变量的取值又比其他变量大很多时，则该变量会对“接近”的含义形成非常大的影响。

24、1.4 本文的工作文中设计与实现了基于改进后的K-NN算法的MicroDM，并使用脚本自动生成测试数据文件，分别使用传统的K-NN算法以及MicroDM中的K-NN算法进行数据挖掘，评估运行结果，验证改进算法的有效性。本文的组织结构如下：第一章 引言部分 对数据挖掘以及K-NN算法做了一个简单的介绍。第二章 分析了相关的技术以及算法。第三章 MicroDM的分析与设计第四章 MicroDM的实现与评估第五章 对论文期间所做工作进行了总结，分析了下一步的工作，对这个平台的进一步实现作了一个展望。第二章 相关技术2.1 数据预处理现实世界中数据大体上都是不完整，不一致的脏数据，无法直接进行数据挖掘

25、，或挖掘结果差强人意。为了提前数据挖掘的质量产生了数据预处理技术。数据预处理有多种方法：数据清理，数据集成，数据变换，数据归约等。这些数据处理技术在数据挖掘之前使用，大大提高了数据挖掘模式的质量，降低实际挖掘所需要的时间。数据预处理的主要任务如下：1. 数据清理：填写空缺值，平滑噪声数据，识别，删除孤立点，解决不一致2. 数据集成：集成多个数据库，数据立方体，文件3. 数据变换：规范化（消除冗余属性）和聚集（数据汇总），将数据从一个较大的子空间投影到一个较小的子空间4. 数据归约：得到数据集的压缩表示，量小，但可以得到相近或相同的结果数据离散化：数据规约的一部分，通过概念分层和数据的离散化来规

26、约数据，对数字型数据比较重要。2.1.1 数据清理填写空缺的值，平滑噪声数据，识别，删除孤立点，解决不一致性。1. 处理空缺值：1) 忽略元组：当一个记录中有多个属性值空缺，特别是关键信息丢失时，已不能反映真实情况，它的效果特别差。2) 人工填写空缺值3) 使用一个全局变量填充空缺值4) 使用属性的平均值填充空缺值5) 使用与给定元组属同一类的所有样本的平均值6) 使用最可能的值填充空缺值，使用像Bayesian公式或判定树这样的基于推理的方法2. 处理噪声数据 噪声：一个测量变量中的随机错误或偏差1) 分箱（binning）（等深或等宽分箱）首先排序数据，并将他们分到等深的箱中；然后可以按箱

27、的平均值平滑，按箱中值平滑，按箱的边界值平滑、2) 聚类：检测并且去除孤立点3) 计算机和人工检查结合：计算机检测可疑数据，然后对他们进行人工判断4) 回归：通过让数据适应回归函数来平滑数据，对连续的数字型数据较好3. 处理不一致的数据主要方法是参照其它资料，如纸上记录，人工的加以更正2.1.2数据集成1. 数据集成将多个数据源中的数据整合到一个一致的存储中。2. 模式集成 1) 整合不同数据源中的元数据2) 实体识别问题：匹配来自不同数据源的现实世界中相同的实体。比如：A.cust_id=B.customer_no3. 检测并解决数据值的冲突1) 对现实世界种的同一实体，来自不同数据源的属性

28、值可能是不同的2) 可能的原因：不同的数据表示，不同的度量等等。2.1.3数据变换1. 平滑：去除数据中的噪声2. 聚集：数据汇总，数据立方体的构建3. 数据概化：沿概念分层向上汇总4. 属性构造通过现有属性构造新的属性，并添加到属性集中，以增加对高维数据的结构的理解和精确度5. 规范化：将数据按比例缩放，使这些数据落入到一个较小的特定的区间之内。方法有：5.1. min-max规范化min-max标准化方法是对原始数据的线性变换。设minA和maxA分别为属性A的原始值中的最小值和最大值，将属性A的一个原始值v通过min-max标准化映射成在区间new_minA, new_maxA中的值v的

29、计算方法是：若新的取值区间是0,1，则公式可简化为：min-max标准化方法保留了原始数据之间的相互关系，但是如果标准化后，新输入的数据超过了原始数据的取值范围，即不在原始区间minA, maxA中，则会产生越界错误。因此这种方法适用于原始数据的取值范围已经确定的情况。5.2. Z-score规范化这种方法基于原始数据的均值(mean)和标准差(standard deviation)进行数据的标准化。将属性A的原始值v使用z-score标准化到v的计算方法是：其中是属性A原始值得均值，是属性A原始值的标准差。标准差即为方差的平方根。方差的计算公式如下：z-score标准化方法适用于属性A的最大

30、值和最小值未知的情况，或有超出取值范围的离群数据的情况。5.3. 小数定标规范化， where j is the smallest integer such that 2.1.4数据离散化离散化：将连续属性的范围划分为区间，以减少所必需处理的数据的量。使用连续属性的范围的划分，使用某一范围的值来代替某一段的值。离散化可以有效的规约数据（基于判定树的分类挖掘）。数值概念分层生成方法有分箱、直方图分析、聚类分析、基于嫡的离散化和通过“自然划分”的数据分段等。1. 分箱 通过将数据分布到箱中，并用箱中的平均值或中值替换箱中的每个值，可以将属性值离散化。就像用箱的平均值平滑或用箱的中值平滑一样。这些技

31、术可以递归地作用于结果划分，产生概念分层。 2. 聚类分析 聚类算法可以用来将数据划分成簇或群。每一个簇形成概念分层的一个节点，而所有的节点在同一概念层。每一个簇可以进一步分成若干子簇，形成较低的概念层。簇也可以聚集在一起，以形成分层结构中较高的概念层。 2.2 交叉验证（Cross Validation）交叉验证是一种模型评估方法。分类是有监督学习，通过学习可以对未知的数据进行测试。在训练过程开始之前，将一部分数据予以保留，在训练之后，利用这部分数据对学习的结果进行验证，这种模型评估方法为交叉验证。两分法(Holdout)是交叉验证最简单的方法，数据集被分为两个独立的子集，称为训练集(Tra

32、ning Set)及测试集(Test Set)，有时也称为正集(Positive Set)与反集(Negative Set)。K次迭代交叉验证(K-Fold Cross Validation)是在将数据集分成K个子集，K个子集中的一个用作测试集，而其余的K-1个数据集作为训练集，最后对K个数据子集的正确率计算平均值，K次迭代验证是对监督学习算法的结果进行评估的方法。数据集的划分一般采取等均分或随机划分。留一法(Leave-one-out)交叉验证是K次迭代交叉验证的一个特例。设数据集有N个数据，令K=N，只保留一个数据作为测试。2.3 评估方法因为文本分类从根本上说是一个映射过程，所以评估文本

33、分类系统的标志是映射的准确程度和映射的速度。映射的速度取决于映射规则的复杂程度，而评估映射准确程度的参照物是通过专家思考判断后对文本的分类结果（这里假设人工分类完全正确并且排除个人思维差异的因素），与人工分类结果越相近，分类的准确程度就越高，这里隐含了评估文本分类系统的两个指标：准确率和召回率。准确率是所有判断的文本中与人工分类结果吻合的文本所占的比率。其数学公式为准确率(precision) = 分类的正确文本数/分类的实际文本数召回率是人工分类结果应有的文本中与分类系统吻合的文本所占的比率。其数学公式为召回率(recall) = 分类的正确文本数/ 分类的应有文本数准确率和召回率反映了分类

34、质量的两个不同方面，二者必须综合考虑，不可偏废，因此，存在一种新的评估指标，即F1测试集，其数学公式为F1测试集 = 准确率 * 召回率 * 2 / （准确率 + 召回率）上述指标可以对每个类分别求出，然后进行平均。也可以通过一张全局结果布尔矩阵(n篇测试文档分类到m个类中)来求总平均。前者称为宏平均(Macro平均)，后者称为微平均(Micro平均)。微平均常常用于不同分类方法之间的比较，而宏平均只在某些场合使用。显然，微平均指标(包括recall/precision/F1)很受那些大类的影响，而宏平均指标相对微平均指标而言更受小类的影响。数学公式为Macro平均 = 每个类的准确率 / 类

35、的个数Micro平均 = 每个分类的正确文本数 / 测试集的文本数MicroDM实现的k-NN同时使用两种指标，最终使用微平均作为标准选出最优的K值。2.4 小结本章节介绍了数据挖掘的概念与技术，模型评估方法以及对分类算法的评估指标。第三章 基于改进的K-NN算法的MicroDM的分析与设计3.1 项目简介将传统的K-NN算法直接应用于互联网媒体海量发布信息智能分类时，算法实际效果不佳或者性能不稳定。鉴于此，文中设计与实现了基于改进后的K-NN算法的MicroDM。改进的K-NN方法实现了重要互联网媒体海量发布信息智能分类，使用脚本生成测试数据文件，分别使用传统的K-NN算法以及MicroDM

36、中的K-NN算法进行数据挖掘，使用交叉验证方法建立训练集以及测试集，使用Macro平均，Micro平均等指标对运行结果进行评估，验证改进算法的有效性。实验结果表明改进的K-NN算法能更加有效的分类。3.2 运行界面这个平台通过读入ARFF格式的数据文件，对数据进行预处理，再将处理后的数据集置于学习方案中，进行相应的挖掘任务。从下图可以清晰的看出数据挖掘流程：Step1.Setting读取ARFF格式的数据文件并显示属性的具体信息，初始装载入文件时，属性只有两种:Categorical以及Numberical。Step2. Preprocessing 数据预处理，包括对缺失数据项的填补，数据变换

37、，数据离散化等功能。Step3.Building and Testing Model选择交叉验证参数，选择需要进行数据挖掘的算法以及设置相应的参数Start 按钮开始数据挖掘，这时会跳出一个可视化的运行结果界面Result of Testing。运行界面清晰的显示出挖掘算法的相关信息以及运行状况。可以对挖掘后的结果进行储存。Log记录运行过程中产生的各种信息。图3.1 MicroDM运行界面3.3 设计图图3.2 设计的包图图3.3 类图3.4 数据挖掘流程图在Micro平台上进行数据挖掘的过程如下：先输入要测试的数据集，然后对待测数据进行预处理，再将处理后的数据集置于一种学习方案中并分析其结

38、果或是将已学习到的模型来预测未知的实例等。具体流程图如下：选择数据文件并载入数据预处理模式评估（目前是K-NN）挖掘结果可视化以及储存图3.5 数据挖掘流程图选择数据文件并载入：支持ARFF格式文件，装载数据，对属性进行分析，并得出相应的统计值。数据预处理：包括对缺失数据项的填补，数据离散化，数据标准化等功能。模式评估：目前是K-NN算法，对于数据挖掘的结果进行模式评估, 分析并学习数据挖掘结果。挖掘结果可视化以及存储:以特定的格式对挖掘过后的结果进行存储。3.5 K-NN算法分析与改进3.5.1数据文件（ARFF）分析ARFF（Attribute-Relation File Format），

39、是WEKA存储数据的文件格式，这是一种ASCII文本文件。MicroDM将ARFF文件作为输入的数据文件。本文使用produceTestData.java来生成测试数据，下面将使用生成的data.arff文件为例，讲解MicroDM对ARFF文件的解析。data.arff不仅包含数值属性，还包含其它属性。下图截取了data.arff的一部分图3.4 data.arff需要注意的是，在Windows记事本打开这个文件时，可能会因为回车符定义不一致而导致分行不正常。可以使用UltraEdit这样的字符编辑软件察看ARFF文件的内容。下面对data.arff的内容进行详细说明。1. 文件格式1) 识

40、别ARFF文件的重要依据是分行，因此不能在这种文件里随意的断行。空行（或全是空格的行）将被忽略。2) 将以“%”开始的行是注释，忽略这些行。3) 除去注释后，整个ARFF文件可以分为两个部分。第一部分给出了头信息（Head information），包括了对关系的声明和对属性的声明。第二部分给出了数据信息（Data information），即数据集中给出的数据。从“data”标记开始，后面的就是数据信息了。2. 关系声明 关系名称在ARFF文件的第一个有效行来定义，格式为relation 是一个字符串。如果这个字符串包含空格，它必须加上引号（指英文标点的单引号或双引号）。3. 属性声明属性声

41、明用一列以“attribute”开头的语句表示。数据集中的每一个属性都有它对应的“attribute”语句，来定义它的属性名称和数据类型。这些声明语句的顺序很重要。首先它表明了该项属性在数据部分的位置。例如，“height”是第二个被声明的属性，这说明数据部分那些被逗号分开的列中，第六列数据1.6 1.83 1.66 1.73 . 是相应的“height”值。其次，最后一个声明的属性被称作class属性，在分类或回归任务中，它是默认的目标变量。 属性声明的格式为 attribute 其中是必须以字母开头的字符串。和关系名称一样，如果这个字符串包含空格，它必须加上引号。WEKA支持的有四种，分别

42、是numeric-数值型-分类（nominal）型 string-字符串型date -日期和时间型其中 和 将在下面说明。还可以使用两个类型“integer”和“real”，但是WEKA把它们都当作“numeric”看待。注意“integer”，“real”，“numeric”，“date”，“string”这些关键字是区分大小写的，而“relation”“attribute ”和“date”则不区分。1. 数值属性数值型属性可以是整数或者实数，但WEKA把它们都当作实数看待。2. 分类属性分类属性由列出一系列可能的类别名称并放在花括号中：, , . 。数据集中该属性的值只能是其中一种类别。例

43、如如下的属性声明说明“vacation”属性有四种类别：”none”,“below_average”，“average”和“generous”。而数据集中每个实例对应的“vacation”值必是这三者之一。如果类别名称带有空格，仍需要将之放入引号中。3. 字符串属性字符串属性中可以包含任意的文本。这种类型的属性在文本挖掘中非常有用。示例：ATTRIBUTE LCC string4. 日期和时间属性日期和时间属性统一用“date”类型表示，它的格式是attribute date 其中是这个属性的名称，是一个字符串，来规定该怎样解析和显示日期或时间的格式，默认的字符串是ISO-8601所给的日期时

44、间组合格式“yyyy-MM-ddTHH:mm:ss”。数据信息部分表达日期的字符串必须符合声明中规定的格式要求5. 数据信息数据信息中“data”标记独占一行，剩下的是各个实例的数据。每个实例占一行。实例的各属性值用逗号“,”隔开。如果某个属性的值是缺失值（missing value），用问号“?”表示，且这个问号不能省略。例如：data69,1.6,108707.7,Male,Self-emp-inc,Preschool,2.75,below_average,50K.3.5.2数据特征集分析根据上面介绍的规则，对data.arff进行分析，结合属性定义以及数据值，分析结果如下：属性类型范围age数值属性1.099.0height数值属性0.31.85personal_property数值属性32.05136592.33sex分类属性Male,Femaleworkclass分类属性Never-worked,Without-pay,Part-time,Self-emp-inc,State-Enterprise,Private-Enterprise,Foreign-enterprises,Gov-employeeeducation分类属性Preschool,Primary-s