毕业设计（论文）-数据挖掘K-均值算法实现.doc

本科生毕业论文（设计）册学院：数学与信息科学学院专业：计算机科学与技术班级：2009级计算机班学生：指导教师： 河北师范大学本科毕业论文（设计）任务书论文（设计）题目： 数据挖掘K-均值算法实现 学 院： 数学与信息科学学院 专业： 计算机科学与技术 班级： 2009级计算机班 学生姓名： 郝蓓 学号： 2009010915 指导教师： 郭瑞强 职称： 副教授 1、论文（设计）研究目标及主要任务本文主要研究聚类分析K-均值算法，并对该算法的优缺点进行分析，并通过该算法的缺点通过实验验证，这些敏感的因素对聚类结果具有哪些影响。本文的主要任务是实现K-均值算法，并通过改变不同的初始条件得出算法聚类结果，并对结果进行比对，得出结论。2、论文（设计）的主要内容本文主要介绍了聚类分析，包括它各个方面的性能指标测量函数和常见的聚类方法，着重介绍了基于划分的聚类算法中的K-均值算法，详细分析了该算法的基本思想，算法流程和算法本身的特点，并通过实验实现了该算法，在实现该算法的基础上，对影响聚类结果的两方面因素初始点和数据输入顺序的不同分别进行实验。3、论文（设计）的基础条件及研究路线本文是在C+的基础上实现的K-均值算法，数据集是从数据堂下载的c-fat500-10.txt数据集，在运行实现该算法的基础上，改变初始点和数据输入顺序，进行了六次试验，分别进行实验这两个初始条件的不同会对聚类结果有哪些影响。4、主要参考文献1 T ZhangRRamakrishnan and MogiharaAn efficient data clustering method for very largedatabasesIn Pror1996 ACM-SlGMOD hatConfManagement of Data，Montreal。Canada，June 1996：103114.2Sambasivam S，Theodosopoulos NAdvanced data clustering methods ofmining web documentsIssues in Informing Science and Information Technology，2006，8(3)：563579.3 ZHuangExtensions to the K-means algorithm for clustering large data sets with categorical valuesData Mining and Knowledge discovery,1998，(2)：283-304.Applied Math，1999，90：3265、计划进度阶段起止日期1确定题目2012年12月2013年01月2查阅资料2013年01月2013年02月3论文撰写2013年02月2013年04月4论文修改2013年04月2013年05月5论文答辩2013年05月指 导 教师: 年 月 日教研室主任: 年 月 日河北师范大学本科生毕业论文（设计）开题报告书 数学与信息科学 学院 计算机科学与技术 专业 2013 届学生姓名郝蓓论文（设计）题目数据挖掘K-均值算法实现指导教师郭瑞强专业职称副教授所属教研室软件研究方向数据库课题论证：本文主要是实现K-均值算法，在实现K-均值算法的基础上，对影响聚类结果的初始值选取问题和数据输入顺序的不同，分别通过实验进行验证，并从实验结果得出一般选取数据集开始的几个连续数作为初始中心，有助于提高聚类结果的迭代次数，适当的改变数据的输入顺序也可以改变聚类结果和迭代次数的结论，这些结论可以为我们改变聚类效率提供参考。方案设计：本文主要是用C+语言实现K-均值算法，在实现的基础上，并改变初始簇中心点和数据集的输入顺序的方式，分别实现出不同的结果，并对这些聚类结果进行分析，得出本文需要验证的结论。进度计划：1.确定题目：2012年12月2013年01月；2.查阅资料：2013年01月2013年02月；3.论文撰写：2013年02月2013年04月；4.论文修改：2013年04月2013年05月；5.论文答辩：2013年05月指导教师意见：指导教师签名： 年 月 日教研室意见： 教研室主任签名： 年 月 日河北师范大学本科生毕业论文（设计）文献综述 目前，国内对于数据挖掘聚类分析的研究的集中部门还是科研单位和各大高校，国内还没有公司企业专门从事聚类分析的研究，相对于外国来说起步较晚。各大科研机构与高校对聚类的研究主要是对其算法设计并实现，以此为基础对算法改进。目前人们已经在统计分析软件中应用一些聚类分析工具，如SAS等软件。为大型的数据库寻求有效的聚类分析方法是目前聚类分析的主要研究工作，目前研究方向包括以下几个方向：可伸缩性：目前的聚类算法针对小型数据库，数据量是几百范围内的，对于有很庞大数据量的数据库会造成结果的不稳定性，可伸缩性强的算法就亟待的研发出来。属性不同情况下的处理能力：现在开发出来的聚类算法所针对的数据类型都是数值型，但实际上的聚类类型的信息是不确定的，如二元数据、序数型、分类型等或者是各种类型的混合。聚类形状：基于欧几里得距离发现所得的簇的形状是球状簇，它们有相近的距离与密度，形成一个簇，但是我们更希望能够有一种算法实现各种形状的簇。决定结果的输入参数：聚类算法的视线中很多是需要用户输入所要聚类出来的簇数K，当前的算法对这些K的值是相当敏感的，大型的数据流对这些要求很严格，对结果的影响很明显，使用户在输入时加大了分析的工作难度，很难与控制。输入数据的顺序问题：有的聚类算法对输入数据的顺序是有要求的，不同的输入次序会有不同的聚类结果，这就特别需要对数据顺序不敏感的算法开发出来，更好的适应人们的要求。高维数据的处理：含有若干维数据属性的数据库是很常见的，但是擅长处理两维或三维的聚类算法才是目前成熟的应用的算法，一旦高维数据需要聚类处理，这就是一个难题，这就需要算法有很强的实用性。污染数据的发现：数据是一个不确定而且无限性的群体，我们不能保证数据集中的数据是完全集中的，难免会有个别的孤立点造成污染数据，影响整个结果，应该开发出能智能识别这些孤立点的数据的算法，来优化聚类结果，这要通过对目前算法进行改进来实现。有约束条件的聚类：实际的聚类情况是有很多限制的条件的，在实现这些聚类时，既要按约束条件又要按聚类要求实现，是很有压力和挑战的一项任务。可用性和可解释性：大多情况下的聚类结果，对于客户来说都希望它们简单易懂，一目了然，所以我们要优化聚类结果界面的研究，选择适合每个客户需求的聚类方法来满足他们的需求。同时聚类分析算法主要有着手于眼下的几个问题的解决3：(1)初始值的选取及输入顺序对结果有何影响在数据挖掘的学科范围内寻找最优解的过程是通过迭代不同的初始值实现，但是这个办法不是很可靠，也就是说不能完全确定找到最优解。其实寻找最优解就是在优化原来的聚类的结果，通过重复聚类找到所设计的目标函数的最优解，但是这个目标函数一般都不是有最值得函数，所以它的最小值并不是很容易确定，因为它并不唯一，有可能找到的这个只是局部最小值，而不是全局最小，所以这种非完全单调函数的全局最小值得查找是目前最亟待解决的问题。(2)小波变换聚类算法因为当前主要是对均值算法与模糊算法的研究改进而得到的研究成果，这些研究成果使得目前的聚类分析算法提高了它的性能属性。小波变换聚类算法同样符合好的聚类算法的各项要求，目前对小波聚类的研究还有很大程度的空白，如果花大的精力进一步研究会有更加深入的突破。(3)算法的效率改进问题聚类的效率问题是目前一个很棘手的问题，因为人类在进步，数据量会越来越庞大，应该增强目前聚类算法对更大数据库的处理能力，即增量聚类，是聚类算法在聚类的数量上有更好的弹性，尽量减少在工作时对庞大数据库的扫描次数，进一步提高它的工作效率。(4)数据库类型目前，基于聚类算法的数据库比较单一，仅仅包括关系或事务数据库，应该着眼于其他数据库类型应用算法的研究，比如面向属性数据库、文本数据库、时态数据库、地理数据库多维数据库等的算法开发，这是一项非常艰巨而且有意义的研究方向。聚类分析中的算法有很多种，详细分析比较了个算法的优缺点，本文着力介绍了K-均值算法，分析它本身的算法优点与不足，并用算法实现，着力于对该算法不足进行改进，以更好地适应现在的生活。K-均值算法是聚类分析最常用的算法之一。K-均值算法的应用范围非常广泛，因为它的操作简单，适合处理庞大的数据集，但是它同时也暴露出自身的不足，如易陷入局部最优解的结果里面、需要用户提前输入参数、发现簇的形状比较单一等，已经有很多专家对这些问题进行了改进，文献4作者通过最大最小距离和DBI聚类指标解决了K-均值算法对初始值K得选择问题，能够确定出最佳的聚类数目。文献5的作者用K-均值算法与层次聚类算法进行混合出一种新的聚类算法，充分发挥了层次聚类的精确性和K-均值的高效性。文献6的作者对遗传算法提出一种改进，基于比变长编码，是这种算法与K-均值结合解决了对初值选择的敏感问题等等。已经有很多被发表出来的对K-均值的改进的算法已经被提出来的K均值聚类算法的具体改进措施还有很多。河北师范大学本科生毕业论文（设计）翻译文章SQL Server 管理工作室SQL Server 管理工作室是一个与微软SQL Server协作的管理和脚本工具的集合。这个工作室与商业智能开发工作室的不同在于，你是在一个联机的环境下工作，一旦你保存工作，你的行为就被传送到服务器上。在数据被清理并为数据挖掘准备好后，大多数和创建苏局挖掘解决方案相关联的工作都在商业智能开发工作室中工作。通过使用商业智能开发工作室，你可以利用迭代过程确定的给定情况下的最佳模式来发布和测试数据挖掘解决方案。一旦开发商对解决方案满意，就可以将其发布到分析服务服务器。从这点来看，重点从SQL Server管理工作室的开发转移到了维护和应用。在SQL Server管理工作室中，您可以管理您的数据库和执行一些在商业智能开发工作室中的相同的职能，比如在挖掘模式中查看、创建预测。数据转换服务在SQL Server 2005中数据转换服务（ DTS ）包括抽取，转换和加载（简称ETL ）工具 。这些工具可用于执行一些数据挖掘中最重要的任务，为数据模型的建立清理和准备数据。在数据挖掘，您通常可以执行重复数据转换清理数据，然后利用这些数据组成挖掘模型。利用DTS中的任务和转移，您可以把数据准备和模型建立结合为一个单一的DTS包。DTS公司还提供了DTS设计器，以帮助您轻松地建立和运行的包含了所有的任务和转变的软件包。利用DTS设计器，您可以将包发布到服务器上并定期的运行他们。这是非常有用例如，你每周收集数据资料，并向要每次自动执行相同的清洁转换工作。你可以通过向商业智能开发式的解决方案中分别增加项目来将数据转换项目和分析服务项目结合起来工作，作为商务智能解决方案的一部分。挖掘模式算法数据挖掘算法是挖掘模型的创建的基础。SQL Server 2005中各种各样的算法可以让你执行多种类型的执行。欲了解更多有关算法及其参数调整的信息，请参看SQL Server联机丛书中的“数据挖掘算法”。决策树决策树算法支持分类与回归并且对预测模型也行之有效。利用该算法，你可以预测离散和连续这两个属性。在建立模型时，该算法检查每个数据集的输入属性是怎样的影响预测属性的结果，以及使用最强的关系的输入属性制造了一系列的分裂，称为节点。随着新节点添加到模型中，树状结构开始形成。顶端节点树描述了大多数预测属性的统计分析。每个节点建立把预测属性比作投入的属性的分布情况上。如果输入的属性被视为导致预测属性有利于促成比另一个更好的状态，于是一个新的节点添加到模型。该模型继续增长，直到没有剩余的属性制造分裂提供了一个更好的预测在现有节点。该模型力图找到一个结合的属性和引起在预测属性不成比例分配的状态，因此，您可以预测预测属性的结果。簇簇算法采用迭代技术组从包含相似特性的数据及中进行分类。利用这些组合，您可以探讨的数据，更多地了解存在的关系，这在理论上可能不容易通过偶然的观察获得。此外，您也可以从算法创建的簇建立预测模型。例如，考虑那些住在同一社区，驱动器相同的车，吃同样的食物，买了类似的版本的产品的那一个群体的人。这是一组数据。另一组可能包括去相同的餐厅，也有类似的薪金，休假和每年两次以外的地区的人。观测这些集合是如何的分布，可以更好地了解预测属性的结果是如何相互影响的。传统贝叶斯传统贝叶斯算法迅速的建立挖掘模型，可用来做分类和预测。它适合各个输入属性情况的可能情况，并考虑到每种预测属性的情况，以后可以在已知的输入属性的基础上来预测预测属性的结果。概率用来生成计算和储存加工过程中的立方体的模型。该算法只支持分立或离散属性，以及它认为所有输入的属性是独立的。传统贝叶斯算法产生一个简单的挖掘模型，可以被视为在数据挖掘过程中的一个起点。由于大多数的计算结果是立方体处理的过程中生成的，结果很快返回。这使得该模型成为探索数据和发现各种不同的输入属性在不同预测属性的情况下是如何分布的一个很好的选择。时间系时间系算法创建可以用来预测连续变量随着时间的推移从联机分析处理和关系数据源的模式，。例如，您可以使用时间系预测算法历史数据立方体的基础上来预测销售额和利润。利用该算法，您可以选择一个或多个变量来预测，但他们必须是继续的。对每个模式您只能有一系列案例。一系列的案例等同于一系列位置，诸如寻求销售的长度的日期超过几个月或几年。一个例子可能包含了一套变量（例如，销售不同的商店） 。时间系算法可以在预测中使用跨变量。例如，在一个商店的先售可能在预测另一个商店的当前销售时也有用。联结联结算法是专门设计用于市场篮子分析。该算法认为每个属性/值配对（如产品/自行车）作为一个项目。一个相集是在单一事务的项目上的一个组合。该算法通过扫描数据集试图找到往往出现在许多交易的项目集。出现在很多交易项面前的支持参数确定被认为是重要的。例如，频繁项目集可能包含（性别= “男性” ，婚姻状况= “已婚” ，年龄= “ 30-35 ” ） 。每个项目集包含项目的数量都有个大小。在这种情况下，大小是3 。往往联结模式在包含嵌套表的数据集之后工作，如客户名单在一个嵌套的购买列表后。如果一个嵌套表中存在数据集，每个嵌套的建制（如在购买表的产品）被认为是一个项目。算法同时找到项目集之间的联系。关联模型的规则看起来像A，B= C （发生概率的联系） ，其中有A，B ，C都是频繁项目集。 = 意味着C是通过A和B预测的。概率阈值是一个在被深思考虑的规则之前确定了最低概率参数。这些概率在数据挖掘文献中也被称为“信任”。联结模式同样对交叉销售或协同过滤有用。例如，您可以使用联结模式在他们购物篮项目上来预测一个用户可能希望购买的产品。序列簇序列簇分析算法分析有关联导向的包含离散值系列的数据。通常串联的一连串属性拥有特定的命令（如点击路径）的一组事件。通过分析有关联的事物之间的情况的转变，该算法可以预测有关联的事务将来的情况。序列簇算法是一种混合型的序列和聚类算法。该算法根据这些关系的相似性将有关系属性的的多重案例分组成片段。该算法的一个典型的使用情况是一个门户网站的网络客户分析。一个门户网站拥有一套附属领域，如新闻，天气，金钱，邮件，和体育。每个网站的客户通过在这些领域中网页点击的 顺序联系起来。序列簇算法可以根据他们的导航模式将这些网页客户分组成差不多同质的团体。这些团体是视化的，提供了详细的了解客户如何使用该网站。神经网络在Microsoft SQL Server 2005分析服务中，神经网络算法通过构建多层感知神经元网络建立分类与回归挖掘模型。类似微软决策树算法的供应商，考虑到每个可预测属性的情况，该算法为马格可能输入属性的情况计算概率。该算法提供案例的过程，反复比较预测分类的情况和已知的实际分类的案件。这些来自第一代的整套案件中从最初的分类错误，被反馈到网络，用来修改网络性能的下一代，等等。以后您可以在输入属性的基础上使用这些概率来预测那些预测属性的结果。然而，该算法和决策树算法其中一个主要区别，是其学习的过程是朝着尽量减少错误的方向优化网络参数，而决策树算法的分裂规则，以求最大限度地发挥信息增益。该算法支持预测的离散和连续属性。线性回归线性回归算法是决策树算法的一种特殊的构造，获得了无效的分裂（整个回归公式是建立在一个单一根节点） 。该算法支持预测连续属性。逻辑回归逻辑回归算法是神经网络算法的一种特殊的构造，得到了消除隐蔽层。该算法支持预测的离散和连续属性。翻译原文：SQL Server Management StudioSQL Server Management Studio is a collection of administrative and scripting tools for working with Microsoft SQL Server components. This workspace differs from Business Intelligence Development Studio in that you are working in a connected environment where actions are propagated to the server as soon as you save your work. After the data has been cleaned and prepared for data mining, most of the tasks associated with creating a data mining solution are performed within Business Intelligence Development Studio. Using the Business Intelligence Development Studio tools, you develop and test the data mining solution, using an iterative process to determine which models work best for a given situation. When the developer is satisfied with the solution, it is deployed to an Analysis Services server. From this point, the focus shifts from development to maintenance and use, and thus SQL Server Management Studio. Using SQL Server Management Studio, you can administer your database and perform some of the same functions as in Business Intelligence Development Studio, such as viewing, and creating predictions from mining models. Data Transformation ServicesData Transformation Services (DTS) comprises the Extract, Transform, and Load (ETL) tools in SQL Server 2005. These tools can be used to perform some of the most important tasks in data mining: cleaning and preparing the data for model creation. In data mining, you typically perform repetitive data transformations to clean the data before using the data to train a mining model. Using the tasks and transformations in DTS, you can combine data preparation and model creation into a single DTS package.DTS also provides DTS Designer to help you easily build and run packages containing all of the tasks and transformations. Using DTS Designer, you can deploy the packages to a server and run them on a regularly scheduled basis. This is useful if, for example, you collect data weekly data and want to perform the same cleaning transformations each time in an automated fashion.You can work with a Data Transformation project and an Analysis Services project together as part of a business intelligence solution, by adding each project to a solution in Business Intelligence Development Studio.Mining Model AlgorithmsData mining algorithms are the foundation from which mining models are created. The variety of algorithms included in SQL Server 2005 allows you to perform many types of analysis. For more specific information about the algorithsm and how they can be adjusted using parameters, see Data Mining Algorithms in SQL Server Books Online.Microsoft Decision TreesThe Microsoft Decision Trees algorithm supports both classification and regression and it works well for predictive modeling. Using the algorithm, you can predict both discrete and continuous attributes. In building a model, the algorithm examines how each input attribute in the dataset affects the result of the predicted attribute, and then it uses the input attributes with the strongest relationship to create a series of splits, called nodes. As new nodes are added to the model, a tree structure begins to form. The top node of the tree describes the breakdown of the predicted attribute over the overall population. Each additional node is created based on the distribution of states of the predicted attribute as compared to the input attributes. If an input attribute is seen to cause the predicted attribute to favor one state over another, a new node is added to the model. The model continues to grow until none of the remaining attributes create a split that provides an improved prediction over the existing node. The model seeks to find a combination of attributes and their states that creates a disproportionate distribution of states in the predicted attribute, therefore allowing you to predict the outcome of the predicted attribute.Microsoft ClusteringThe Microsoft Clustering algorithm uses iterative techniques to group records from a dataset into clusters containing similar characteristics. Using these clusters, you can explore the data, learning more about the relationships that exist, which may not be easy to derive logically through casual observation. Additionally, you can create predictions from the clustering model created by the algorithm. For example, consider a group of people who live in the same neighborhood, drive the same kind of car, eat the same kind of food, and buy a similar version of a product. This is a cluster of data. Another cluster may include people who go to the same restaurants, have similar salaries, and vacation twice a year outside the country. Observing how these clusters are distributed, you can better understand how the records in a dataset interact, as well as how that interaction affects the outcome of a predicted attribute.Microsoft Nave BayesThe Microsoft Nave Bayes algorithm quickly builds mining models that can be used for classification and prediction. It calculates probabilities for each possible state of the input attribute, given each state of the predictable attribute, which can later be used to predict an outcome of the predicted attribute based on the known input attributes. The probabilities used to generate the model are calculated and stored during the processing of the cube. The algorithm supports only discrete or discretized attributes, and it considers all input attributes to be independent. The Microsoft Nave Bayes algorithm produces a simple mining model that can be considered a starting point in the data mining process. Because most of the calculations used in creating the model are generated during cube processing, results are returned quickly. This makes the model a good option for exploring the data and for discovering how various input attributes are distributed in the different states of the predicted attribute.Microsoft Time SeriesThe Microsoft Time Series algorithm creates models that can be used to predict continuous variables over time from both OLAP and relational data sources. For example, you can use the Microsoft Time Series algorithm to predict sales and profits based on the historical data in a cube.Using the algorithm, you can choose one or more variables to predict, but they must be continuous. You can have only one case series for each model. The case series identifies the location in a series, such as the date when looking at sales over a length of several months or years. A case may contain a set of variables (for example, sales at different stores). The Microsoft Time Series algorithm can use cross-variable correlations in its predictions. For example, prior sales at one store may be useful in predicting current sales at another store.Microsoft AssociationThe Microsoft Association algorithm is specifically designed for use in market basket analyses. The algorithm considers each attribute/value pair (such as product/bicycle) as an item. An itemset is a combination of items in a single transaction. The algorithm scans through the dataset trying to find itemsets that tend to appear in many transactions. The SUPPORT parameter defines how many transactions the itemset must appear in before it is considered significant. For example, a frequent itemset may contain Gender=Male, Marital Status = Married, Age=30-35. Each itemset has a size, which is number of items it contains. In this case, the size is 3. Often association models work against datasets containing nested tables, such as a customer list followed by a nested purchases table. If a nested table exists in the dataset, each nested key (such as a product in the purchases table) is considered an item. The Microsoft Association algorithm also finds rules associated with itemsets. A rule in an association model looks like A, B=C (associated with a probability of occurring), where A, B, C are all frequent itemsets. The = implies that C is predicted by A and B. The probability threshold is a parameter that determines the minimum probability before a rule can be considered. The probability is also called confidence in data mining literature. Association models are also useful for cross sell or collaborative filtering. For example, you can use an association model to predict items a user may want to purchase based on other items in their basket.Microsoft Sequence ClusteringThe Microsoft Sequence Clustering algorithm analyzes sequence-oriented data that contains discrete-valued series. Usually the sequence attribute in the series holds a set of events with a specific order (such as a click path). By analyzing the transition between states of the sequence, the algorithm can predict future states in related sequences.The Microsoft Sequence Clustering algorithm is a hybrid of sequence and clustering algorithms. The algorithm groups multiple cases with sequence attributes into segments based on similarities of these sequences. A typical usage scenario for this algorithm is Web customer analysis for a portal site. A portal Web site has a set of affiliated domains such as News, Weather, Money, Mail, and Sport. Each Web customer is associated with a sequence of Web clicks on these domains. The Microsoft Sequence Clustering algorithm can group these Web customers into more-or-less homogenous groups based on their navigations patterns. These groups can then be visualized, providing a detailed understanding of how customers are using the site.Microsoft Neural NetworkIn Microsoft SQL Server 2005 Analysis S