基于K-means++算法和支持向量机结合的分类算法教程.doc

 PAGE \* MERGEFORMAT 10 论文题目： 基于K-means++算法和 支持向量机结合的分类算法 摘 要 近年来，随着计算机技术的飞速发展整个社会正在快速向数据化，信息化，智能化方向发展，于是涌现出了各行各业的大量数据。如何使得这些数据变为提高管理水平，发展产业效益与社会保障与信息安全的重要资源，成为当前重要且不得不不解决的重要问题，分析数据和挖掘这些数据的关系。因此，从大量数据信息中抽取有价值的潜在知识的一种新的数据分析技术数据挖掘应运而生。数据挖掘有对大量数据之间聚类和分类相关的学习，而本文主要从以下两个方面进行研究。 １．提出了选取聚类的初始种子点的方法。通过K-means的学习大家知道其方法有两个明显的不足，K值的选定是非常难以估计的和种子点位置的随机选取非常重要。于是本文提出了种子点位置选取的一种方法，首先根据专家经验选取第一个种子点，然后从距离第一个种子点较远的这些数据中根据权重随机选取一个种子点，重复以上步骤直到选取的种子点个数满足要求为止。该方法的主要思想就是初始的聚类中心之间的相互距离要尽可能的远。 ２．以上选取的种子点与支持向量机结合进行分类。支持向量机方法是建立在统计学习理论的VC维理论和结构风险最小原理基础上的分类算法。主要就是建立一个超平面作为决策面，使得正例和反例之间的隔离边缘被最大化，即最优分类超平面等价于最大的间隔。但支持向量机是分类的算法，属于示例式学习，分类之前需要明确各个类别。于是，本文就用聚类选取的种子点和分类方法进行了结合。 关键词：数据挖掘；种子点选取；支持向量机；K－means １　K－means＋＋算法进行聚类 本章提出了一种基于K－means方法的改进的算法，主要思想是：初始的聚类中心之间的相互距离要尽可能的远。首先根据专家经验选取第一个种子点，然后从距离第一个种子点较远的这些数据中根据权重随机选取一个种子点，重复以上步骤直到选取的种子点个数满足要求为止。算法流程图如图3.1所示： 开始 输入数据对象 初始化第一个种子点 根据距离权重??始化K个种子点 计算出各个对象到初始种子点距离 对各个对象按照其到聚类中心距离进行 更新中心 结束 距离 聚类 有变化 聚类中心不变 １.1 算法描述 k-means++算法是k-means算法的改进，是解决初始化种子点的问题，其选择初始seeds的基本思想就是：初始的聚类中心之间的相互距离要尽可能的远。该算法的描述是如下： step.1从输入的数据点集合中随机选择一个点作为第一个聚类中心； step.2对于数据集中的每一个点x，计算它与最近聚类中心(指已选择的聚类中心)的距离D(x)； step.3选择一个新的数据点作为新的聚类中心，选择的原则是：D(x)较大的点，被选取作为聚类中心的概率较大； step.4重复step.2和step.3直到k个聚类中心被选出来； step.5利用这k个初始的聚类中心来运行标准的k-means算法。 2　支持向量机的分类算法 SVM（Support Vector Machine）是从瓦普尼克（Vapnik）的统计学习理论发展而来的，主要针对小样本数据进行学习、分类和预测（有时也叫回归）的一种方法，能解决神 经网络不能解决的过学习问题。支持向量机方法是建立在统计学习理论的VC维理论和结构风险最小原理基础上的分类算法。主要就是建立一个超平面作为决策面，使得正例和反例之间的隔离边缘被最大化，即最优分类超平面等价于最大的间隔。与其他传统的分类方法相比，主要有以下几个方面的特点： 1. 以严格的数学理论为基础，克服了传统神经网络学习中靠经验和启发的先成分等缺点。 2. 采用了结构风险最小化原则，克服了传统神经网络中只靠经验风险最小化来估计函数的缺点，提高了置信水平，克服了过学习等问题。 3. 通过求解凸二次规划问题，可以得到全局最优解，保证了了解的有效性。 4. 用内积的回旋巧妙的构造核函数，克服了特征空间的维数灾难问题，通过非线性映射，只需在原空间中计算样本数据与支持向量的内积。 5. 通过VC维的概念，使网络的收敛速度，样本被差错分的界和风险泛函得到了控制。 2.1 分类问题 设有两类模式和，是从模式和中抽样得到的训练集，其中、。若属于类，则对应有；若属于类，则对应有；。寻求上的一个实函数，对于任给的未知模式，有 或者 式