毕业设计（论文）-蚁群聚类在学生成绩评价中的应用.doc

i 蚁群聚类算法在学生成绩评价中的应用研究 摘摘 要要 近些年，数据挖掘是各行各业的研究人员关注的热点和重点研究的内容，它 是基于传统数据库技术但是又高于传统数据库技术。数据挖掘是指从不完整的、 随机的、大量的数据仓库中通过算法搜索隐藏于其中有意义的信息并做出决策的 过程。数据挖掘虽然只是在没有明确假设的前提下去挖掘信息，发现信息，但是 通过挖掘却能发现这些数据中隐藏的关联网。通过数据挖掘的得到的信息和知识 有时是与我们的直觉相反的，然而，挖掘出的信息越是出乎我们的意料，可能越 有价值，越是具有潜在的有用特征。数据挖掘有很多有趣和重要的研究方向，蚁 群算法作为一种模拟进化的算法，具有良好的性能并成功的解决了较为复杂的组 合优化问题。 论文对蚁群算法和聚类分析进行了详尽的分析，深入探讨了蚁群算法的基本 原理及优缺点，对蚁群算法解决的经典问题：旅行商问题加以描述和探讨。基于 蚁群算法的聚类分析与传统聚类算法不同的是，传统聚类分析首先要设定聚类条 件才能实现聚类，基于蚁群算法的聚类分析则不需要，因此具有更快的收敛速度， 被越来越多研究者所重视。 论文在理论研究的基础上，将基于蚁群算法的聚类分析应用到学生成绩评价 工作中，用以挖掘隐藏在学生成绩背后潜在信息。本文的主要工作如下： （1）简单介绍了数据挖掘概念及功能方法。对数据挖掘的应用及其发展趋 势作简单阐述。 （2）重点介绍蚁群算法和聚类分析。引入了群体智能的概念，对蚁群算法 的基本原理和聚类分析的问题模型及聚类的一般过程进行介绍。 （3）分析了当前学生成绩评价的现状、背景和重要意义。通过真实实验数 据指出传统学生成绩评价存在的缺点，突出蚁群聚类分析应用到学生成绩评价的 必要性。 （4）从成绩的综合评价和等级评价两个方面进行学生成绩的挖掘。通过挖 掘学生综合成绩得出的结果可以从宏观上分析学生的整体学习能力，对学生进行 不同类别分析，为教务管理、教学工作提供理论依据，便于特殊问题特殊处理。 利用聚类分析对学生单科成绩进行分析，聚类结果动态的制定学生成绩等级标准。 由于采用的是聚类而不是根据传统硬性等级评价，使得成绩等级评价更具有科学 性，能够更好的指导教学工作，分析学生成绩等级。将传统等级评价结果与聚类 分析产生的动态结果相比较，进一步证明了基于聚类分析动态评价方法的科学性 ii 和客观性。这两种模型的分析印证了数据挖掘在教务、教学管理中的重要意义。 关关键键词词：数据挖掘 ；蚁群算法 ；聚类；成绩评价； abstract in recent years,data mining is a hot topic of researchers from all walks of life and the content of the key research,which is based on the traditional database technology but higher than the traditional database technology.data mining refers to the process from incomplete, random, a large amount of data warehouses in the algorithm to search for hidden useful information and make decisions. data mining is premised on the hypothesis to dig up information, but it can be found by mining association network hidden in these data.through the data mining to get information and knowledge is sometimes contrary to our intuition.however, digging out more information is contrary to our expectations, may be more valuable, more potential and useful features.data mining has many interesting and important research direction, the ant colony algorithm is a novel simulated evolutionary algorithm, success and good performance in solving complex combinatorial optimization problems. the paper of ant colony algorithm and clustering analysis has been carried on the detailed analysis, the basic principle and advantages and disadvantages of ant colony algorithm are in-depth exploration, by solving the classic question with the ant colony algorithm : traveling salesman problem is described and discussed. clustering analysis is based on ant colony algorithm and the traditional clustering algorithm, the traditional clustering analysis is set about the conditions to achieve clustering firstly, clustering analysis is based on ant colony algorithm that is not required, thus it has faster convergence speed, paid great attention by more and more researchers. thesis is on the basis of the theoretical research, the clustering analysis is based on ant colony algorithm which is applied to the evaluation of student performance in work, excavating potential information that is hidden behind the student performance. in this thesis, the main work is as follows: (1) this article is briefly introduced about the concept and function of data mining method. the application of data mining and its developments trend are briefly described. (2)the key point of this article is introduced about ant colony algorithm and cluster iii analysis. by introducing the concept of swarm intelligence, the basic principle of ant colony algorithm and clustering analysis model and the general process of clustering are introduced. (3)this article is analysed about the current students achievement evaluation, the background and significance. through the real experimental data ,which is pointed out the disadvantages of the evaluation of traditional students performance, highlighted the necessity that the ant clustering analysis is applied to evaluation of student performance. (4)mining on student achievement from two aspects of the comprehensive evaluation scores and grade evaluation.by mining the students comprehensive performance results from the macroscopic analysis on the students overall learning ability, classification analysis for the student, providing a theoretical basis for the educational administration, teaching, special processing for special affairs. by using cluster analysis on students scores, clustering procedures.only branch grade ratings by dynamic clustering results of student performance rating standard, as a result of clustering is not according to the traditional rigid hierarchy evaluation, making the performance level evaluation is more scientific ,whats more, it can better guide the teaching work with analysis of student achievement level. traditional hierarchical evaluation results compare with the results of dynamic clustering analysis, this further proves that the dynamic evaluation method based on clustering analysis is scientific and objective. this two kinds of model analysis confirms the important value of data mining in educational administration and teaching management. keywords: data mining；ant colony algorithm；clustering；performance evaluation iv 目目 录录 第一章第一章 绪绪 论论.1 1.1 数据挖掘概述1 1.2 数据挖掘的过程2 1.3 数据挖掘的功能4 1.3.1 概念描述5 1.3.2 关联分析5 1.3.3 分类和预测5 1.3.4 聚类6 1.3.5 孤立点分析6 1.4 数据挖掘的方法6 1.4.1 人工神经网络6 1.4.2 决策树7 1.4.3 遗传算法8 1.4.4 粗集方法8 1.5 数据挖掘的应用和发展趋势9 1.5.1 数据挖掘的应用9 1.5.2 数据挖掘的发展趋势9 1.6 论文的工作10 第二章第二章 蚁群算法蚁群算法.12 2.1 引言12 2.2 群体智能12 2.3 蚁群算法的基本原理13 2.3.1 蚂蚁的觅食行为13 2.3.2 蚁群算法的提出及数学模型14 2.3.3 蚁群算法的实现16 2.3.4 算法的复杂度.17 2.4 蚁群算法的参数分析17 2.5 蚁群算法的优缺点18 2.5.1 蚁群算法的优点18 2.5.2 蚁群算法的缺点19 2.6 蚁群算法的发展现状与应用研究19 v 2.6.1 蚁群算法的研究现状.19 2.6.2 蚁群算法的应用研究20 2.7 本章小结20 第三章第三章 聚类分析聚类分析.21 3.1 引言21 3.2 聚类的基本概念21 3.3 聚类分析理论基础23 3.3.1 聚类问题模型23 3.3.2 聚类过程23 3.3.3 数据规范化变换方法24 3.3.4 相似度度量方法24 3.3.5 聚类分析主要方法25 3.4 蚁群聚类26 3.4.1 基于蚂蚁觅食的聚类算法26 3.4.2 基于蚂蚁自我聚集行为的聚类算法27 3.4.3 基于蚂蚁堆形成原理的聚类算法28 3.4.4 基于蚂蚁化学识别系统的聚类算法29 3.5 本章小结30 第四章第四章 蚁群聚类在学生成绩评价中的应用蚁群聚类在学生成绩评价中的应用.31 4.1 学生成绩评价的意义31 4.2 学生成绩综合评价32 4.2.1 蚁群聚类算法在学生综合成绩聚类结果32 4.2.2 k-means 算法学生综合成绩聚类结果34 4.2.3 学生成绩综合评价34 4.3 学生成绩等级评价35 4.3.1 学生成绩原始结果评价36 4.3.2 应用蚁群聚类算法聚类的学生成绩结果37 4.4 实验对比结论38 4.5 本章小结39 第五章第五章 总结与展望总结与展望.40 5.1 研究总结40 5.2 研究展望40 参参考考文文献献 42 vi 插图清单插图清单 图 1.1 数据库发现知识的过程示意图.3 图 1.2 数据提取过程.3 图 1.3 数据预处理.4 图 1.4 人工神经网络示意图.7 图 1.5 分类树决策示意图.8 图 2.1 对称双桥实验.14 图 2.2 蚁群算法流程图.15 图 3.1 待聚类的数据.22 图 3.2 聚类后的结果.22 图 3.3 蚁群聚类算法流程图.29 图 4.1 聚类结果.34 图 4.2 学生成绩统计结果.38 图 4.3 聚类结果折线图.39 vii 表格清单表格清单 表 1.1 商业数据到商业数据信息化预测阶段的进化过程.2 表 4.1 安财贸财务会计专业学生综合成绩样本.33 表 4.2 聚类结果信息.34 表 4.3 k-means 聚类结果信息.35 表 4.4 学生成绩评价标准一.36 表 4.5 学生成绩评价标准二.36 表 4.6 高等数学成绩等级统计.37 表 4.7 高数成绩聚类结果.38 表 4.8 合并类结果.39 第一章 绪 论 1 第一章第一章 绪绪 论论 随着人类社会活动越来越频繁和多样化，人们积累的数据和信息也极度增长。 起初各种商业数据是存储在计算机的数据库中的，面对海量的数据时人们往往束 手无策，为了充分地利用数据，首先必须对数据进行有效的管理，这样就产生了 数据库技术。数据库技术的发展主要从对数据库进行查询和访问到对数据库的即 时遍历，可以使人们有条理地记录数据，也能够对数据进行初步的分析和加工。 随着信息技术和商业的快速发展，数据库技术和数据库管理技术得到迅速、广泛 应用。数据库系统可以高效地实现数据的录入、查询、统计等功能，随着计算机 硬件技术的发展，人类可以存储、积累的数据越来越多。快速增长的数据导致各 种各样数据库的建立，这些数据中隐藏着很多重要的信息，相关的行业从业者希 望从中获得更为高层次的信息进一步有助于更好的利用这些数据。数据库系统只 是单存的录入和调用数据，不能自身发现数据之间的关系，无法根据数据库中的 数据预测未来的趋势，导致了“数据爆炸但知识贫乏”的现象。面对大数据时代的 来临，如何发现有价值的信息预测、预测未来的趋势成为亟需解决的问题。如网 购平台希望根据购物者的购物习惯推荐相关产品，医学研究者希望从大量的患者 的样本中寻找相似的病患特征寻求治愈的途径。在大数据的存储以及相关需求的 推动下，数据挖掘1-5（data mining）和数据仓库6-10（data warehouse）研究应运 而生。数据挖掘可以在数据库中遍历和查询数据并且可以寻找出这些数据之间可 能存在的潜在关系，可以总结知识、预测趋势，促进信息的传递和使用，它的出 现使数据库技术进入了一个更高级的阶段。 1.1 数据挖掘概述 知识的数据信息多储存于数据库中，因此把获取知识的过程也称为数据库中 的知识发现(knowledge discovery in database, kdd)，kdd11是 1989 年在美国召 开的第 11 届国际人工智能联合会议的专题讨论会上提出的。一般，kdd 泛指所 有从源数据中发现模式或者联系的方法，经常用来描绘整个数据挖掘的过程，因 此与数据挖掘有一个概念的相互关系问题。关于 kdd 与数据挖掘的关系，有多 种观点，相对早期的观点是 kdd 是数据挖掘的一个特例，认为数据库中发现知 识只是发现知识的一个来源而已；第二种观点认为数据挖掘是 kdd 过程的一个 步骤。数据库发现知识的过程一般需要经过问题定义、数据的选择、数据预处理、 数据挖掘、模型建立及评估等步骤，因此 kdd 的主体过程可分为三个部分：数 据预处理、数据挖掘和解释评估。数据的预处理、和解释评估的研究相对较为简 单、成熟，由于数据的几何式增长导致 kdd 的研究热点和难点主要在数据挖掘 合肥工业大学硕士学位论文 2 这个步骤。因此数据挖掘是从数据库获取知识的一个关键和特定的步骤，正是因 为如此，在很多场合往往不加区分的使用数据挖掘（dm）和知识发现（kdd） 两个术语，也就是说将 dm 等同于 kdd。 因此，数据挖掘可以简单认为是一个从大量数据中提取、挖掘出未知的、有 价值的模式或规律等知识的非平凡过程121314。简而言之，它是一种对数据进行 深层次分析的方法。数据挖掘是在海量数据中搜索、计算机处理技术、挖掘算法 三种基础技术的发展出来的按照确定的问题，对跟本问题相关的大量数据进行历 遍和分析，从这些看似杂乱无章的数据中揭示出未知的规律性，并进一步将这些 规律进行模型化，从而可以概括出知识，为趋势预测作出指导。数据挖掘与传统 数据库系统中的数据分析有本质区别，以前的数据库技术主要是查询、报表、联 机应用分析，如商场中的调货、库存查询等等，而数据挖掘是在没有明确假设的 前提下去挖掘信息、发现知识，达到可以预测行为的目的，如根据周围小区居民 长期的购物习惯可以推送相应的商品信息。一般来说，数据挖掘得到的信息具有 先前未知、实际有效和领域可实用三个典型的特征。先前未知的信息是指该信息 在挖掘前是不可知的，即不预设预期，不认为对其进行归类；实际有效是获得的 信息是在有效数据上获得的，具有实际有效的特点，领域可用是“知识转化为生 产力”获得的知识要能够在相关领域进行应用，如医学领域、商业领域等等。其 中数据挖掘在商业领域中引用相对较早，见证了商业领域中从商业数据到商业数 据信息化预测阶段的进化过程，可见表 1.1。 表 1.1 商业数据到商业数据信息化预测阶段的进化过程 tap 1.1 the evolutionary process of business data to the forecast stage of business data informationization 时间决策目标计算机技术产品特点 数据搜集 (60年代) “一年或者一个季度的 营业额是多少？” 计算机、磁带和磁盘 提供历史性的、静态的 数据 数据访问 (80年代) “不同地域的商场是否 可以跨库检索库存？” 结构化查询语言、关系 数据结构，局域网、互 联网 提供历史性的、动态可 查询的数据 数据库； 决策支持 (90年代) “在a地的销售额与b地 的销售的关系？” 联机分析处理、多维数 据库、数据仓库 在不同层次上提供回溯 的、动态的数据信息 数据挖掘 （正在流行） “预测下一个季度的销 售额？” 高级算法、多处理器计 算机、大数据的存储 提供预测性的信息 1.2 数据挖掘的过程 第一章 绪 论 3 数据挖掘是一个多阶段数据处理过程15，包括数据选择、数据预处理、数据 转换、数据挖掘、结果分析和知识同化几个部分，如图 1.1 所示。 图 1.1 数据库发现知识的过程示意图 fig 1.1 the process diagram of the knowledge discovery in database step 1：定义问题。在开始知识发现之前首先进行的，目标明确才能进行成 功的挖掘，在大量的数据面前要了解业务领域的背景，了解数据和业务问题，明 确所要完成 dm 任务性质、问题的范围、计算模型所使用的度量以及项目的待定 目标。 step 2：数据准备。数据的准备是能够进行成功挖掘的首要条件，高质量的 数据是成功挖掘的关键，否则从劣质的信息中获取的知识极有可能是错误的。一 般来说，数据的准备大致分以下三步： （1）数据选择：由于工作单位的分工化运作，各个部门具有相对独立的系 统，往往有多个不同结构、运行在不同的软硬件平台上的信息系统同时运行。这 些数据就像是数据孤岛，各个部分的数据彼此独立没有交流和共享。因此在数据 准备的第一步是选择和整合挖掘的数据库，把不同来源、格式、特点性质的数据 在逻辑上或物理上有机地集中，将于问题相关的多数据进行合并处理，然后根据 相关问题的需求从数据库中提取与 dm 相关的数据。 数据源数据挖掘库 图 1.2 数据提取过程 fig1.2 data extraction procedure 合肥工业大学硕士学位论文 4 （2）数据预处理：数据的预处理是对原始数据进行改进，也可称为数据清 洗，主要是过滤那些不完整、错误、重复等不符合要求的数据，数据预处理是与 问卷审核不同，录入后的数据处理一般是由计算机而不是人工完成。数据预处理 则是解决数据中语义的模糊性，纠正错误，查找数据中的隐含相关性、标识最准 确的数据源并确定哪些列最适合用于分析。 图 1.3 数据预处理 fig 1.3 data preprocessing （3）数据转换：是将数据从一种表示形式变为另一种表现形式的过程，将 原始数据转换成适合特定的技术途径或者方法分析的数据形式。 step 3：数据挖掘。数据挖掘是整个知识发现过程中最核心的步骤，根据任 务的发现和数据的样本，利用数理统计方法以及人工智能和知识工程等领域的研 究成果，诸如推理、机器学习、知识获取、模糊理论、神经网络、遗传算法、模 式识别、粗糙集理论、支持向量机理论等，选择合适的数据挖掘算法，寻找合适 的模型和参数来获取有价值的信息。 step 4：结果分析和知识同化。对发现的模式进行解释和评估，必要时返回 前面处理中的某些步骤进行反复提取。一般数据挖掘后的结果通常是基于某种语 言，因此需要将发现的知识以简单的方式提供给用户进行试用。这时便需要相关 的知识体系和算法将数据挖掘后的结果转变为应用领域可以理解的表达方式。最 后将获得结果变为知识同化的过程，这也是 dm 的最终目的，用来预判或者决策 所遇到的问题。 以前计算能力的限制，对大数据量进行分析的复杂数据分析方法受到很大限 制，随着计算机性能的不断提高，使得对海量数据可以进行分析；各种智能分析 理论的日趋成熟，统计、在线分析处理、情报检索、机器学习、专家系统（依靠 过去的经验法则）和模式识别等诸多方法的发展为开发对数据进行深度分析的工 具提供了坚实而丰富的理论和技术基础。 1.3 数据挖掘的功能数据挖掘的功能 第一章 绪 论 5 数据挖掘可以根据数据库中看似杂乱无章的数据机型关联和分析，基于相关 的模型构建，分析和预测未来趋势及行为，瞄准的目标是从数据库中发现隐藏的、 有价值的知识，一般可以将数据挖掘分为以下五类功能。 1.3.1 概念描述概念描述 概念描述就是对某一类或者几类对象的内在特征进行描述，基于数据对县官 对象数据进行统计分析，目的是对将选择的数据进行集中并浓缩，高度的概括相 关数据的统一性并指出这类对象的内涵特征。如所有出售的平板电脑、笔记本、 智能手机的基本情况都有整体概念具备智能芯片处理功能。概念描述分为分为两 种：特征性描述和区别性描述。如果描述的是对象的一般特征，则成为是特征性 描述；如果将目标一般特征与一个或多个处理对象的特性进行比较，则称为区别 性描述。生成区别性描述的方法很多，如决策树方法、遗传算法等。 1.3.2 关联分析关联分析 数据挖掘的目的是发现在数据库中的大量数据背后隐藏的知识，因此知识实 际就是反应不同数据或者对象之间的内在关系和关联。但是关联作用可反应事件 或者对象之间的主次影响、相互依赖性或者内在的逻辑关系。简而言之，关联分 析就是找出隐藏的关联信息。关联可分为简单关联、时序关联、因果关联。如购 买轿车的顾客中有 90%会购置导航设备，如果房地产持续低迷则水泥行业有 75% 的可能性出现不景气。通常数据库中的数据关系的函数关系是不可知的，即使可 知，一般来说也是有可信度的，因此关联分析有置信度的问题。关联规则挖掘是 关联分析中最常用的方法，关联规则挖掘的研究和应用是数据挖掘中比较活跃和 深入的分支。 1.3.3 分类和预测分类和预测 分类是最基本的一种认知形式，分类的目的是学会一个分类函数或者分类模 型。一般需要一个训练样本数据作为输入，将不同数据属性的数据输入至不同的 分类块中，并预测新数据将属于哪个分类，从而完成数据对象的认识和标识工作。 作为数据挖掘中一个重要的主题，相关的研究成果较多，常用的数据分类算法有 cart、c45、sliq 等。如我们可以根据将肯德基餐厅盈利分为良好、正常、较 差差，以此分析不同的网点对应盈利的属性，可以考虑人流、交通、环境并决定 他们分类的关键属性和相互关系。在这些商业应用中，人们希望可以预测在新的 地方开设餐厅是否能够有较好的盈利，因此需要数据挖掘在已经存在的肯德基餐 厅所有地址、人类、环境、营业额等大型数据库中寻找相关的信息并进行关联挖 掘，从而可以迅速直接由大量的数据本身得出预测性的判断，即在之前肯德基餐 厅进行分类分析后，可以对新餐厅的属性进行分析从而判断，分析新的位置如果 合肥工业大学硕士学位论文 6 开出餐厅将会属于哪一种盈利类型的餐厅。 1.3.4 聚类聚类 数据库中的记录可被化分为一系列有意义的子集，即聚类。一般学习算法可 以分为有监督和无监督两种。数据分类是一种监督学习，而聚类是典型的无监督 学习算法。数据类聚是将物理或者抽象的对象分成几个群体，与分类相比，聚类 事先不知晓需要处理的数据属于哪一个模块类。比如，大型企业希望知道那些客 户可能对新的产品感兴趣，聚类分析就是寻找新的模块类，而分类则是通过对数 据分析形成模块类的标识。聚类功能增强了人们对事实的认知，是前面所讲的概 念描述的条件和基础。 1.3.5 孤立点分析孤立点分析 根据常识，一般数据库中的大量数据总会有一些偏离常规的点，从统计学上 一般认为数据会符合正态分布的规律，大部分数据在一个中间状态，但是两端可 能会出现一些数据孤点，检测这些数据孤点可能也会具有重要的意义。比如学生 成绩统计过程中，成绩一般的同学呈现的一些孤点如果表现出是某门学科的“瘸 腿” ，可以在数据挖掘分类后，对这些同学进行单独的交流和补习，可能有助于 成绩的提高。再比如，小概率事件发生的欺诈、诱骗等信息的挖掘有助于银行、 保险行业对个人的信用进行评估，从而判断是否贷款或者进行快速理赔。这些所 显示的应用为数据挖掘提供了新的研究课题，即孤立点分析。 1.4 数据挖掘的方法数据挖掘的方法 1.4.1 人工神经网络人工神经网络 因为神经网络为复杂的问题提供了一个简单、快捷的解决办法，它可以很容 易的处理多参数的问题，导致近些年来这种方法得到越来越多人的关注和重视。 人工神经网络实际是在处理在结构上模仿生物的神经网络，进行分布式并行信息 处理的算法数学模型，输入的处理数据经过“黑盒”处理，最后输出数据，如图 1- 4 所示。这种方法主要通过训练来学习的非线性预测模型，它主要是通过调整内 部各个节点的关系来达到处理问题的目的。神经网络可以分为输入节点、黑盒 （隐含层）和输出节点。输入层的每一个节点均对应一个预测的变量参数，输出 节点则表示对应目标的变量，也可以有多个节点。中间的隐含层对用户来说是不 可见的，因此也叫黑盒，这里主要包括了传递时需要使用的非线性函数，因此该 神经网络有等价于逻辑回归。神经网络一般需要进行不断的训练，通过不断的训 练来描述训练过程中应变量与预测变量之间的关系，一般来说不需要掌握隐含层 里面是什么，只需要知道出来的知识就可以。比如识别签名的系统，一般系统只 第一章 绪 论 7 要知道这个对应客服的签出的字迹与原始的电子签名吻合就可以了，而不需要知 道为什么这些线条的组合就是这个名字。 1.4.2 决策树决策树 决策树，顾名思义，是以树干树枝的形式来对数据进行分类，树木一般经历 生长和修剪两个阶段，决策树也具有相同的过程，一般分决策树的构造和修剪两 个阶段。这种方法是通过对现有条件进行判断，在概率的基础上进行决策是否进 行的一种方式，是直接使用概率进行分析的一种图像方法，这种方法可以评价一 些项目的风险性。每个决策形成的过程实际上是对数据进行分割的过程，每一次 修剪和决策的过程对应一个问题，也就是一个树枝或者节点。mitchell 在机器 学习中对决策书有个简单的例子，主要是通过天气的预报寻找什么时候人们会 打高尔夫，尝试研究人们决定是否打球的原因最主要取决于天气情况。根据天气 的通常情况可以将天气状况分为晴，云和雨；环境还有温度、相对湿度以及是否 有风。如此，我们便可以构造一棵决策树，如下（根据天气这个分类决策这天是 否合适打网球） ，根据相应的结构可以对相关的数据进行分析，决策过程就是典 型的分类树决策。在实际生活中也有相似的运用，比如在被父母要求相亲的时候， 可能在询问一些问题后才会决定是否前去，比如首先提问“他年纪多大？”这个问 题的答案是结果，如果超过你心目中的岁数，你可能就直接否决了，而如果满意， 则通过这个节点继续向下，询问工资待遇如何，这又会变成一个新的节点，比如 5000 成为这个节点的新的决策，如是或者否。以此类推，联系几个问题决策以后， 你可能选择是否前去相亲或者不去。最上面的节点也称为根节点，是最关心的决 策点，也是整个决策树的开始，向下每个节点成为新的决策点，也称为叶子。 图 1.4 人工神经网络示意图 fig 1.4 schematic diagram of artificial neural network 合肥工业大学硕士学位论文 8 图 1.5 分类树决策示意图 fig 1.5 decision diagram of classification tree 决策树的直观性对使用者来说是一个明显的优点，这种方法比较适合处理非 数值型的数据，这与神经网络相比可以免去很多数据的预处理工作。在实际应用 的过程中，可能决策点非常多，会导致决策树非常庞大，这样会降低决策树的可 读性和可理解性，也是没有必要的。为了使得到的决策树所蕴含的规则具有普遍 意义，常用的方法是设定决策树的最大高度（层数）来限制树的生长。 1.4.3 遗传算法遗传算法 遗传，顾名思义，类似于生物自身的进化过程，优胜劣汰。在第一代数据群 中可能存在很多不同群体的个体，类似于生物遗传学中的染色体。在数据挖掘时， 可以完成数据的遗传过程，即类似于染色体的复制、交换和突变过程。对于开始 的数据库中，个体用复合某一特征的函数表示，在遗传过程中个体是否保留则取 决于个体适应环境的能力。因此在遗传算法的开始就需要从表现型向基因型进行 编码，一般采用二进制的编码对初代种群进行生存的筛选，逐渐演化为越来越好 的近似解。这样的工作可以让后一代的数据群获得的种群比前面的更加适应环境， 最后一代的群中个体则可以认为是该问题的最近似解。 1.4.4 粗集方法粗集方法 粗集是波兰数学家 pawlak 在 1982 提出的，他给出粗集的一般性研究，粗集 是以 r-元素等价类定义的。这种方法主要是将群数据进行矩阵化，将行数据看出 对象，将列数据看成属性。将不同研究对象的几个属性进行统一定义，设定它们 的取值相同，设立一个等价的函数 r，对符合等价关系的对象进行集合的构建。 在挖掘的过程中，会有孤点、噪音数据，有很多不确定性。传统的处理方式需要 对数据的附加信息要先进行验证和识别，而且常常还不能进行有效的处理。而粗 第一章 绪 论 9 集是一种软计算方法，可以进一步对不确定信息的数据进行处理，可以克服传统 方法不能解决不确定数据的不足。在这个理论中，知识实际上被定义为对事物分 类的能力，这种而为二维矩阵的建立为粗集的数据挖掘提供了坚实的基础。 1.5 数据挖掘的应用和发展趋势数据挖掘的应用和发展趋势 1.5.1 数据挖掘的应用数据挖掘的应用 数据挖掘自诞生以来就瞄准应用，也是在应用需求的变化下进行发展和衍生。 运用数据挖掘技术目前为止，已经在很多场合进行了应用，如零售、市场营销领 域、金融保险领域、电子图书馆领域和医学领域等等。 （1）零售、市场营销领域。这是数据挖掘应用最早的领域，主要通过通过 获取、处理涉与消费者消费行为的大量信息，从而根据不同的消费群体或者个体 的消费的时间、习惯或者倾向和消费的需求，推断或者预测消费者的下一个消费 行为，从而向消费者推销某些商品。如阿里巴巴的大数据时代就包含了跟消费者 平时的购物习惯、消费的年龄等各种数据对市场进行定位，如向经常搜索电子产 品的青年男子在经常购物的时间推荐最新的电子产品，完成商品的定位定点的促 销和预售。这中营销方式与传统的不区分消费者对象特征的大规模营销手段相比， 可以大大节省了营销成本，提高了营销效果，从而为企业带来更多的利润。 （2）金融、保险领域。由于金融和保险对数据具有强大的依赖性，导致数 据挖掘在这两个领域也有广泛的应用。通过对特点人群的信用记录，消费记录， 收入水平，工作稳定性可以判断该群体的信用程度，可以判断是否能够选择发放 贷款、进行理赔等决策。对用户群体的分类和辨识具有快速的发现和定位作用， 离不开信用体系的评价，离不开对数据的挖掘。 （3）电子图书领域。报纸等传统印刷的知识传播方式被削弱，以数字技术 为代表的技术在图书馆、媒体客户端、期刊杂志等领域得到快速的应用和发展。 为了充分发挥图书馆或者科学领域的资源利用。通过数据挖掘可以实现对借阅、 查阅数字化图书和资料的种类、领域进行分析，实现个性化和智能化的服务，实 现相关服务的优质化，留住特定的客服人群。 （4）医学领域。这是一个具有重要意义的应用领域，通过数据挖掘可以完 成多大样本病人的病发特征进行关联分析，通过相应的指标用于疾病学的研究、 疾病的预警等方向。同时大样本的数据挖掘在医学的影像，致病的基因等方面都 有所应用。 1.5.2 数据挖掘的发展趋势数据挖掘的发展趋势 就目前来看，由于数据挖掘的内容广泛，技术手段多样，高效、交互性强、 界面友好的数据挖掘系统将进一步有助于在未来海量信息中获取有价值的信息， 合肥工业大学硕士学位论文 10 因此大数据时代下数据挖掘的研究仍将是一个重要的研究课题，发展的趋势和研 究的热点将主要集中在以下几个方面16: （1）应用的扩展。随着人类信息化社会的推进，随着不同领域的要求，随 着新领域的诞生，数据挖掘将来将会持续扩展至不同的领域，在新兴的领域的数 据挖掘研究和数据挖掘人员规模将会不断扩大。 （2）挖掘方法的衍生。随着大数据时代的到来，数据类型变得多样性，数 据库结构也各种各样，如何高效的获取需要的信息，并且采用合适的挖掘方法对 大样本数据进行分析将会成为数据挖掘发展的一个重要趋势，也是一个难题。 （3）数据挖掘语言的统一。数据挖掘语言的统一和标准化将有助于开发更 为完善和功能强大的数据挖掘系统，使数据挖掘能够在社会中得到较高的普及和 应用。 （4）网站的数据挖掘。由于电子信息技术的发展，使得 web 上有太多的信 息可以、需要挖掘，使数据挖掘的子研究系统web 挖掘变得越来越重要。 （5）可视化数据挖掘。将数据挖掘后的结果更好的呈现可视化界面将大大 影响数据挖掘的普及速率，犹如计算机的 dos 系统向 windows 交互系统转变引 起的普及速率，因此直接展示结果的可视化交互界面也是重要的发展趋势和研究 热点。 1.6 论文论文的工作 本文研究的内容是将蚁群聚类算法应用到学生成绩评价中，通过数据挖掘技 术对学校教务管理系统中存在的大量学生成绩数据加以分析，充分利用数据信息 来反馈学校的教务管理和教学水平，是高校信息化建设的一个很好体现。在高等 学校日常运行过程中产生了大量繁琐的、看似杂乱无章的数据，实则蕴含着大量 有重要价值的关联信息，对学校各方面的工作具有重要意义。本文主要完成两方 面内容： （1）运用聚类分析对学生综合成绩进行分析，得出六类学生成绩类型：综 合成绩较为优秀的、综合成绩良好的、综合成绩中等的、综合成绩较差的、偏文 科类型、偏理科类型。这是传统学生成绩较难实现的分析功能。 （2）学生成绩等级评价的分析。通过与传统学生成绩等级评价对比，得到 传统等级评价缺点所在，进一步论证了聚类分析在学生成绩等级评价中的科学性、 公平性、客观性。 论文分为五个章节对蚁群聚类算法在学生成绩评价的应用研究进行阐述，具 体组织如下： 第一章 绪论。主要介绍了数据挖掘技术的概念，挖掘过程和其应用现状及 未来发展趋势。 第一章 绪 论 11 第二章 蚁群算法。重点介绍蚁群算法的提出背景，阐述了蚁群算法概念及 模型，分析了影响蚁群算法结果的参数和算法的优缺点。 第三章 聚类分析。详细介绍了聚类分析的相关定义和理论基础，在此基础 上提出蚁群聚类并分析。 第四章 蚁群聚类分析在学生成绩评价中的应用。分析了学生成绩评价工作 的重要性和重要意义，研究了目前学生成绩评价工作的现状和导致该种现象的原 因。最后将蚁群聚类算法应用于学生成绩分析中，分别研究了我校 100 名学生 7 门公共课的综合成绩分析和 500 名会计专业学生高等数学成绩等级评价。前者分 析公共课具有的特点以说明聚类分析的意义；后者一方面通过实际统计验证算法 的合理性，另一方面根据聚类结果得出学生成绩等级评价的划分，将结果与传统 评价等级比较，说明聚类分析的合理性。 第五章 总结与展望。 合肥工业大学硕士学位论文 12 第二章第二章 蚁群算法蚁群算法 2.1 引言 蚂蚁是一种社会性昆虫，其单个个体行为十分简单，但是整体却表现出了高 度结构化的组织社会性，能够在团队协作中完成非常复杂的任务。每只蚂蚁在寻 找食物过程中对于路径的选择都是随机的，并不知道食物源的具体位置。当其中 一只蚂蚁发现食物源后，会搬运一部分的食物返回蚁穴，途中蚂蚁会散发出一种 随时间推移而逐渐挥发的特殊气味称之为“信息素” ，其他蚂蚁通过感知这种激 素找到食物源，这样越来越多的蚂蚁会找到食物。取得食物的蚂蚁在返回过程中 是随机选择各自路径，在此过程中每只蚂蚁分泌出各自“信息素” ，由于选择路 径不同，返回蚁穴所需时间相应不同，信息素浓度最大的路径恰恰是最短路径。 如此反复，最短路径上的信息素浓度越来越强，而其他较长路径上的信息素随时 间变化逐渐消失，其它蚂蚁选择较长路径的概率大大降低，久之久之，蚁群就出 现了蚁巢与食物源之间的最短路径上了。 蚁群算法（ant colony algorithm）的主要思想就是基于蚁群在寻找食物源时 候的智能行为，通过真实蚁群在觅食机制求解组合优化问题。这是一种群智能的 优化算法，具有很强的全局搜索能力。蚁群算法最早是由意大利学者 dorigo, maniezzod1718等人提出来解决旅行商问题19的。 2.2 群群体智能 自然界中有很多成群的生物：蚂蚁，鸟和鱼等等，这些生物群体中单个个体 的并没有表现出很高的智能性，但是却能依靠群体之间的协作发挥出强大的智能 行为：构建巢穴、迁徙、觅食、御敌等。仿真行为就是基于自然界中昆虫的智能 行为而衍生出来的一门学科，并借此解决了较为复杂的问题。这些研究称之为群 体智能2021。群体智能有五大基本原则2223： （1）邻近原则：群体个体具有简单的计算运动空间和时间的能力。 （2）品质原则：环境中的品质因子对群体行为会产生影响。 （3）多样性原则：群体活动范围较大。 （4）稳定性原则：群体中的单体不会因为环境变化而变化。 （5）适应性原则：群体能够适当改变自身行为以适应环境变化。 群体智能具有以下几个特点： （1）无中心控制，不会因为系统中一个或几个个体故障而影响全局 （2）系统中相互合作的个体之间独立分布，适合在网络环境下工作。 第二章 蚁群算法 13 （3）个体之间不直接通信，通过介质进行数据交流，有更好的扩充性。 （4）个体能力简单，个体执行时间较短，系统的实现较为简单。 2.3 蚁群算法的基本原理 2.3.1 蚂蚁的觅食行为蚂蚁的觅食行为 蚁群算法的原理是基于自然界中真实的蚂蚁觅食机制，因此简要介绍蚂蚁觅 食的基本过程。科学家通过大量观察发现：蚂蚁总是能在食物源与蚁穴之间找到 一条最短的路进行觅食。大量的实验研究表明：蚂蚁在运动时候会散发出一种特 殊气味的激素，称之为“信息素” ，蚁群中蚂蚁个体的信息沟通就是通过感知信 息素的强度来交流的。在蚁群觅食过程中，后面的蚂蚁通过感知前面蚂蚁残留在 路径上的信息素决定自己行进方向。当然，也会有蚂蚁寻找其他路线，由于选择 路径不同，返回蚁穴所需时间相应不同，各路径上信息素的浓度也不相同。由于 蚂蚁分泌的激素会随着时间推移逐渐蒸发减弱，所以经过一段时间的往返，较长 路径上的信息素含量会逐渐减弱甚至趋于消失，而较短路径信息素含量会增强并 吸引更多蚂蚁到这条路径上来，这样就形成了一个正反馈的机制24，到最后，整 个蚁群就找到了食物源与蚁穴之间的最短路径。 deneubourg 为了研究蚂蚁在可控条件下通过信息素来选择路径的觅食行为， 做了著名的“双桥实验” 。如图 2.1（a）所示，蚂蚁被两条对称的从蚁穴和食物 源之间隔开，蚂蚁能够在食物源与蚁穴之间自由移