第一章 K-NN和K-Means算法理论基础

　　1.1 K-NN算法研究的背景和意义

　　随着信息技术的快速发展，大数据时代已经到来，人们迫切需要研究出更加方便有效的工具对收集到的海量信息进行J决速准确的分类，以便从中提取符合需要的、简洁的、精炼的、可理解的知识。口前关于这方而的研究已经取得了很大的进步。现有的分类算法有很多种，比较常用的有K-NN,Native Bayes, Neural Net 、SVM,LLSF 等方法。

　　针对这些算法处理大规模数据时存在的问题，国内外已经进行了很多相关方而的研究。针对传统支持向量机方法处理大规模数据时时间复杂度和空间复杂度随数据量的增加直线上升的缺点，提出了核向量机(core vector machineCVM)方法，大大减小了算法的时间和空间复杂度，对向量机方法进行了进一步研究，提高了核向量机的分类速度和泛化能力，但是其分类精度依然没有得到改善，提出了一种聚簇消减大规模数据的支持向量分类算法，提高了传统算法处理大规模数据时的速度，同时降低了算法的时间复杂度，但是精度也只有在阂值选择适当时才有可能达到既减少训练时间又提高精度的双赢目的。

　　K-NN作为一种经典的统计模式识别方法，也是效果最好的分类方法之一，而且K-NN方法主要靠周围有限的邻近样本，而不是靠判别类域的方法来确定所属类别，因此对于类域的交叉或重叠较多的大数据来说，K-NN方法较其他方法更为适合，但K-NN在分类时主要的不足是该算法只计算最近的邻居样本，某一类的样本数量很大，容易出现误判。现在主要采用权值的方法(与该样本距离小的邻居权值大)来改进，但是权值的设置针对不同的领域又要有不同的要求，实用性不是很高。该方法的另一个不足之处是计算量较大，因为对每一个待分类的文本都要计算它到全体已知样本的距离，才能求得它的K个最近邻点。

　　1.2 K-NN研究现状

　　K-NN文本分类算法：K-NN法由Cover和Hart于1968年提出，是一个理论上比较成熟的方法。该算法的基本思想是:根据传统的向量空间模型，文本内容被形式化为特征空间中的加权特征向量。对于一个测试文本，计算它与训练样本集中每个文本的相似度，找出K个最相似的文本，根据加权距离和判断测试文本所属的类别，具体算法步骤如下:

　　 1. 对于一个测试文本，根据特征词形成测试文本向量。

　　 2. 计算该测试文本与训练集中每个文本的文本相似度，按照文本相似度，在训练文本集中选出与测试文本最相似的k个文本。

　　 3. 在测试文本的k个近邻中，依次计算每类的权重。

　　4. 比较类的权重，将文本分到权重最大的那个类别中。

　　 K-NN算法稳定性好、准确率高、简单易用，针对大数据的分类问题，它存在着如下缺点:a)对每一个待分类的文本都要计算它到全体已知样本的距离，才能求得它的K个最近邻点，而大数据的典型特点就是数据信息海量、价值密度低，这就显然出现了很大的无效计算量，在决定测试样本的类别时，该算法只计算最近邻的样本，而大数据的另一个显著特点是涉及领域繁多、类别界限不明显，对于此类文本容易使判决结果产生偏差;c)随着信息爆炸时代的到来，各种新的事物层出不穷，出现新的类别的概率极大，而K-NN算法的邻居都是已知的类别样本，也就导致了对新样本的无知或者误判。

　　改进的K-NN算法，即分层模型的基本思想是根据所属类别的不同对已知样本进行分层，第一层包含的类别数最少，最后一层包含的类别数最多，然后依层对未知样本进行分类。图1以社区民情民意信息的分层为例，图中共分了三层。

图1-1 K-NN分层模型

　　第一层只有a和b两个类别，如果判断出来未知样本属于a类，那么在第二层时只需在a1,a2,a3类中进行比较，不需要在b类的其他文本进行比较。在第二层判断时，如果判断出来属于a1类，那么在第三层进行比较时只需要在a11,a12类中进行比较，依此类推即可。图1中菱形部分为分层模型需要比较的类别数，而传统的方法是需要对所有的数据进　　行比较。从图1中可见分层模型可以大大减少无效计算量。

　　1.3 K-means算法研究的背景和意义

　　K-mean聚类算法在机器学习中属于无监督学习。所谓“无监督学习”即是指训练样本的标记信息是未知的，目标是通过对无标记训练样本的学习来揭示数据的内在性质及规律，为进一步的数据分析提供基础。在此类学习任务中研究最多、最广的是“聚类”。

　　聚类也就是将数据集中的点划分为几个一般情况下不相交的子集、每个子集称为一个“簇”。如下图，在未上色前是一个散点图，通过这些点的位置分布情况，我们可以将他们分为红、绿、蓝三类也就是三个簇。

　　kmeans算法又名k均值算法,K-means算法中的k表示的是聚类为k个簇，means代表取每一个聚类中数据值的均值作为该簇的中心，或者称为质心，即用每一个类的质心对该簇进行描述，那么也就是会有k个质心。在该算法中k值的选择一般是按照实际需求进行决定，或在实现算法时直接给定 k 值。在k-means算法执行结束后，在划分的k个族中同一聚类中的对象相似度较高；而不同聚类中的对象相似度较低。

优点：速度快，简单

缺点：最终结果跟初始点选择相关，容易陷入局部最优，需直到k值

　　1.4 K-means研究现状

　　K-means算法操作简单、运算速度较快，能够有效处理中小型数据集。但同时K-means算法也有不足之处，包含以下几点：

　　(1) 聚类结果不确定

　　K-means算法初始聚类中心是随机选择的，初始中心点选取的好坏会导致最终聚类效果。选取不同初始聚类中心，会使得最终聚类得到的类簇发生变化。除此之外，K-means算法一般采用准则函数为目标函数，准则函数中只存在一个全局最小值和N个极小值，这使得算法运算过程中，会陷入局部极小值，导致最终得到的不是全局最优解。

　　(2) 聚类个数不确定

　　K-means算法中K表示聚簇个数，K的取值决定聚类结果。K值的选取需要根据实际的需求来确定，但通常情况下我　　　　们并不知道需将数据集聚为多少个类簇最合适，所以针对K值的选取依然有待解决。

　　(3) 数据量大、算法时间复杂度较高

　　K-Means算法的计算过程是一个不断迭代的过程，为寻找合适的聚类中心，需要不断的计算和调整才能对数据对象进行有效的聚类。这个过程中反复进行大量的对象间距离的计算，所以K-Means聚类过程会消耗大量时间，降低聚类运算效率。

　　1.5 癌症样本检验研究的背景和意义

　　在医学上可以通过样本数量的结果来判断病情和医疗处理，所以可以通过机器学习来进行高效精确的分析和判断，再根据样本数量的多少来确定判断结果的科学性，本实验的意义在于用K-NN和K-means算法来实现癌症样本检测的功能，并验证数据的科学性和准确性。能对判断病情和预测发展的分析做出有力的数据支撑。

　　1.6 癌症样本检验研究现状

　　精确的癌症检测包括成像和体外诊断产品和程序，直接检测病人样本或病人本身的恶性肿瘤。而本程序在于对检测后的数据进行分析、处理，将数据进行可视化处理，将对样品检测，样品分析，趋势分析和行为变化提供数据支撑。由于我国预后较差的肺癌、胃癌、肝癌等肿瘤高发，肿瘤患者整体生存情况远差于西方国家，肿瘤防治形势严峻。作为癌症大国，更需要更先进的医学技术和理念来对抗强敌，此外，由于国内政策的推动，未来基因检测用于肿瘤防治渗透率将越来越高，随着人们对于基因检测的深入了解，

　　1.7 癌症样本检验研究内容

　　本研究将对前列腺癌症（Prostate_Cancer）检测数据进行数据分析，样品分类，行为测试，测试正确率来进行研究，其中重要对表格数据的肿瘤直径（radius）和结构大小（texture）进行分析和计算处理。

图1-2 癌症检测测试数据

第二章 K-NN和K-Means算法相关技术综述　　

　　2.1机器学习算法K-NN

　　K-NN（K-Nearest Neighbor）最邻近分类算法是数据挖掘分类（classification）技术中最简单的算法之一，其指导思想是”近朱者赤，近墨者黑“，即由你的邻居来推断出你的类别。

　　K-NN最邻近分类算法的实现原理：为了判断未知样本的类别，以所有已知类别的样本作为参照，计算未知样本与所有已知样本的距离，从中选取与未知样本距离最近的K个已知样本，根据少数服从多数的投票法则（majority-voting），将未知样本与K个最邻近样本中所属类别占比较多的归为一类。

　　以上就是K-NN算法在分类任务中的基本原理，实际上K这个字母的含义就是要选取的最邻近样本实例的个数，在 scikit-learn 中 K-NN算法的 K 值是通过 n_neighbors 参数来调节的，默认值是5。

如下图所示(图2-1)，如何判断绿色圆应该属于哪一类，如果K=3，由于红色三角形所占比例为2/3，绿色圆将被判定为属于红色三角形那个类，如果K=5，由于蓝色四方形比例为3/5，因此绿色圆将被判定为属于蓝色四方形类。

图2-1 K-NN投票法则

　　由于K-NN最邻近分类算法在分类决策时只依据最邻近的一个或者几个样本的类别来决定待分类样本所属的类别，而不是靠判别类域的方法来确定所属类别的。

　　K-NN算法的关键：

　　(1)样本的所有特征都要做可比较的量化

　　若是样本特征中存在非数值的类型，必须采取手段将其量化为数值。例如样本特征中包含颜色，可通过将颜色转换为灰度值来实现距离计算。

　　(2)样本特征要做归一化处理

　　样本有多个参数，每一个参数都有自己的定义域和取值范围，他们对距离计算的影响不一样，如取值较大的影响力会盖过取值较小的参数。所以样本参数必须做一些 scale 处理，最简单的方式就是所有特征的数值都采取归一化处置。

　　(3)需要一个距离函数以计算两个样本之间的距离

　　一般选欧氏距离作为距离度量，但是这是只适用于连续变量。在文本分类这种非连续变量情况下。欧氏距离和曼哈顿距离计算方法（图2-2）。

图2-2 欧氏距离和曼哈顿距离计算方法

　　(4)确定K的值

　　K值选的太大易引起欠拟合，太小容易过拟合，需交叉验证确定K值。

　　K-NN算法的优点：

简单，易于理解，易于实现，无需估计参数，无需训练；
适合对稀有事件进行分类；
特别适合于多分类问题(multi-modal,对象具有多个类别标签)， K-NN比SVM的表现要好。

　　K-NN算法的缺点：

　　K-NN算法在分类时有个主要的不足是，当样本不平衡时，如一个类的样本容量很大，而其他类样本容量很小时，有可能导致当输入一个新样本时，该样本的K个邻居中大容量类的样本占多数，如下图所示。该算法只计算最近的邻居样本，某一类的样本数量很大，那么或者这类样本并不接近目标样本，或者这类样本很靠近目标样本。无论怎样，数量并不能影响运行结果。可以采用权值的方法(和该样本距离小的邻居权值大)来改进。

　　该方法的另一个不足之处是计算量较大，因为对每一个待分类的文本都要计算它到全体已知样本的距离，才能求得它的K个最近邻点。

　　可理解性差，无法给出像决策树那样的规则。

　　2.2机器学习算法K-means

　　K-Means 是一种非常简单的聚类算法(聚类算法都属于无监督学习)。给定固定数量的聚类和输入数据集，该算法试图将数据划分为聚类，使得聚类内部具有较高的相似性，聚类与聚类之间具有较低的相似性。

算法原理

　　1. 初始化聚类中心，或者在输入数据范围内随机选择，或者使用一些现有的训练样本(推荐)

　　2. 直到收敛，将每个数据点分配到最近的聚类。点与聚类中心之间的距离是通过欧几里德距离测量得到的。

　　通过将聚类中心的当前估计值设置为属于该聚类的所有实例的平均值，来更新它们的当前估计值。目标函数聚类算法的目标函数试图找到聚类中心，以便数据将划分到相应的聚类中，并使得数据与其最接近的聚类中心之间的距离尽可能小。给定一组数据X1，...，Xn和一个正数k，找到k个聚类中心C1，...，Ck

并最小化目标函数：

其中是质心，计算表达式为

图2-6 表达了初始的数据集

　　假设k=2。在图b中，我们随机选择了两个k类所对应的类别质心，即图中的红色质心和蓝色质心，然后分别求样本中所有点到这两个质心的距离，并标记每个样本的类别为和该样本距离最小的质心的类别，如图c所示，经过计算样本和红色质心和蓝色质心的距离，我们得到了所有样本点的第一轮迭代后的类别。此时我们对我们当前标记为红色和蓝色的点分别求其新的质心，如图4所示，新的红色质心和蓝色质心的位置已经发生了变动。图e和图f重复了我们在图c和图d的过程，即将所有点的类别标记为距离最近的质心的类别并求新的质心。最终我们得到的两个类别如图f。当然在实际K-Mean算法中，我们一般会多次运行图c和图d，才能达到最终的比较优的类别。

对于K-Means算法，首先要注意的是k值的选择，一般来说，我们会根据对数据的先验经验选择一个合适的k值，可以通过交叉验证选择一个合适的k值.在确定了k的个数后，我们需要选择k个初始化的质心，就像上图b中的随机质心。由于我们是启发式方法，k个初始化的质心的位置选择对最后的聚类结果和运行时间都有很大的影响，因此需要选择合适的k个质心，最好这些质心不能太近。

　　2.3 numpy数据分析

　　2.3.1Numpy

　　一个用python实现的科学计算，包括：1、一个强大的N维数组对象Array；2、比较成熟的（广播）函数库；3、用于整合C/C++和Fortran代码的工具包；4、实用的线性代数、傅里叶变换和随机数生成函数。numpy和稀疏矩阵运算包scipy配合使用更加方便。

　　NumPy（Numeric Python）提供了许多高级的数值编程工具，如：矩阵数据类型、矢量处理，以及精密的运算。专为进行严格的数字处理而产生。多为很多大型金融公司使用，以及核心的科学计算组织如：Lawrence Livermore，NASA用其处理一些本来使用C++，Fortran或Matlab等所做的任务。

　　NumPy 的前身为 Numeric，最早由 Jim Hugunin与其它协作者共同开发，2005 年，Travis Oliphant在Numeric中结合了另一个同性质的程序库Numarray 的特色，并加入了其它扩展而开发了NumPy。NumPy为开放源代码并且由许多协作者共同维护开发。

　　2.3.2Pandas

　　Pandas是python的一个数据分析包，最初由AQR Capital Management于2008年4月开发，并于2009年底开源出来，目前由专注于Python数据包开发的PyData开发team继续开发和维护，属于PyData项目的一部分。Pandas最初被作为金融数据分析工具而开发出来，因此，pandas为时间序列分析提供了很好的支持。 Pandas的名称来自于面板数据（panel data）和python数据分析（data analysis）。panel data是经济学中关于多维数据集的一个术语，在Pandas中也提供了panel的数据类型。

　　2.3.3Matplotlib

　　Matplotlib 是一个 Python 的 2D绘图库，它以各种硬拷贝格式和跨平台的交互式环境生成出版质量级别的图形。

第三章 K-NN算法相关综述

　　3.1 K-NN代码实现

　　K-NN回归算法就是给定数据集与结果，预测后面新出的数据集的结果。与前面K-NN最邻近算法比较类似，最临近算法是求出预测数据集与训练数据集的每个点之间的距离，取前k个数据集的结果集，把结果集中占比大的结果作为预测结果。

　　导入内置库CSV和random

　　3.1.1 CSV

csv 文件格式的本质是一种以文本存储的表格数据（使用 Excel 工具即可读写 csv 文件）。csv 文件的每行代表一行数据，每行数据中每个单元格内的数据以逗号隔开。

　　Python 提供csv模块来读写csv文件。由于 csv 文件的格式本身比较简单（通常第一行是表头，用于说明每列数据的含义，接下来每行代表一行数据），因此使用 csv 模块读取 csv 文件也非常简单。

图3-1 打开CSV文件

　　打开CSV文件，r读取，DictReader以字典形式读取，reader为可迭代对象，遍历循环row打印reader有序字典。

图3-2 遍历结果

　　3.1.2 random.shuffle()

　　Random类主要是生成随机数。random类是专门用于生成一个伪随机数的类，其产生的随机数是根据种子和顺序决定的；ThreadLocalRandom类是Java 7新增的一个类，它是Random的增强版。在并发访问的环境下,保证系统具有更好的线程安全性。Random类有两个构造器：

　　　　1、Random()：创建一个新的随机数生成器。

　　　　2、Random(long seed)：使用单个long种子创建一个新的随机数生成器。

　　　　3、random.shuffle（）用于将一个列表中的元素打乱顺序，值得注意的是使用这个方法不会生成新的列表，减少数据偶然性，使测试结果更具有合理性。

图3-3 random shuffle

　　3.1.3分组

　　测试集和训练集。将数据长度进行划分，把数据分为训练集和测试集两部分。

图3-4 测试集和训练集

　　3.2.算距离

　　拿出每个数据集，将字符串转换成浮点型，并再计算欧式距离。欧几里得度量（欧氏距离）

图3-5 欧氏距离计算

图3-6 欧氏距离代码实现

　　3.3 K-NN算法实现

　　输入一个测试值用于对训练数据进行测试。将算法实现分为以下几个步骤：

算距离，循环训练项，result用来取出肿瘤直径，distance用来测试数据和测试项的距离。

图3-7 循环训练项算距离

　　2.升序排序，取出测试数之前的数据。

图3-8 升序排序

　　3.算加权平均值，离的近权重高，离的远权重低。对于未知类别属性数据集中的点：

　　计算已知类别数据集中的点与当前点的距离。2.按照距离依次排序。3.选取与当前点距离最小的K个点。4,确定前K个点所在类别的出现概率。5,返回前K个点出现频率最高的类别作为当前点预测分类。

图3-9 算加权平均值

　　3.4 进行测试

　　测试并输出测试结果和样本的测试准确率，K-NN分类的计算复杂度和训练集中的文档数目成正比。如训练集中文档总数为n，那么K-NN的分类时间复杂度为O(n)。

　　K-NN算法专注于全局异常检测，所以无法检测到局部异常。首先，对于数据集中的每条记录，必须找到k个最近的邻居。然后使用这K个邻居计算异常分数。最大：使用到第k个邻居的距离作为离群值得分；平均值：使用所有k个邻居的平均值作为离群值得分；中位数：使用到k个邻居的距离的中值作为离群值得分。

图3-10 测试报告输出

　　在实际方法中后两种的应用度较高。然而，分数的绝对值在很大程度上取决于数据集本身、维度数和规范化。参数k的选择当然对结果很重要。如果选择过低，记录的密度估计可能不可靠。（即过拟合）另一方面，如果它太大，密度估计可能太粗略。所以在分类方法中，选择一个合适的K值，可以用交叉验证法。

　　实现k近邻法时，主要考虑的问题是如何对训练数据进行快速k近邻搜索，这点在特征空间的维数大及训练数据容量大时尤其必要。

k近邻法最简单的实现方法是线性扫描（linear scan），这时要计算输入实例与每一个训练实例的距离，当训练集很大时，计算非常耗时。为了提高k近邻法搜索的效率，可以考虑使用特殊的结构存储训练数据，以减少计算距离的次数。

　　3.5 If语句对身体健康进行预测

“表达式”可以是一个单一的值或者变量，也可以是由运算符组成的复杂语句，形式不限，只要它能得到一个值就行。

图3-11 情况输出

　　3.6 运行结果

图 3-12 程序运行结果

第四章 K-means算法相关综述

　　4.1初始化中心点

　　初始化中心点可分为1.选择彼此距离尽可能远的K个点 2.先对数据用层次聚类算法或者Canopy算法进行聚类，得到K个簇之后，从每个类簇中选择一个点，该点可以是该类簇的中心点，或者是距离类簇中心点最近的那个点。本系统则采用最简单的确定初始类簇中心点的方法是随机选择K个点作为初始的类簇中心点。

图4-1初始化中心点

　　4.2样本距离

计算样本点与中心点之间的距离，将样本点归为最近的中心点的类。将对象点分到距离聚类中心最近的那个簇中需要最近邻的度量策略，在欧式空间中采用的是欧式距离，在处理文档中采用的是余弦相似度函数。

图4-2 计算样本距离

　　4.3 创建画布

　　通过matplotlib来实现对kmeans的数据进行可视化处理，matplotlib是一套面向对象的绘图库，图中的所有部件都是python对象。pyplot是matplotlib仿照MATLAB提供的一套快速绘图API，它并不是matplotlib本体。pyplot虽然用起来简单快捷，但它隐藏了大量的细节，不能使用一些高级功能。pyplot模块内部保存了当前图表和当前子图等信息。