基于Ismap的手写体字聚类研究毕设答辩

《基于Ismap的手写体字聚类研究毕设答辩》由会员分享，可在线阅读，更多相关《基于Ismap的手写体字聚类研究毕设答辩（15页珍藏版）》请在装配图网上搜索。

1、LOGO指指导教师导教师：马马勇勇基于基于ISOMAP的手的手写写体体数数字聚字聚类研类研究究n班班级级：10电电信（信（2）n学学生：生：吴吴昆昆伦伦n学号学号：108326218n背景 如今国内外学者在手写体数字方面的研究重点是脱机手写数字识别，面临两大难题：1、精度 2、速度 美国已经建立了适合自己国人书写习惯的数字数据库，里面包含6万个标注样本，我们还没有Hilditch提出的细化算法Roweis S.和Saul L.提出的LLE算法Tenenbaum等提出的NLDR方法Kouropteva O.和Okun O.及Pietikainen M.LLE和SVM改进n意义 应用前景非常广阔

2、极大便利人民生活 推进科技快速进步 课题的背景及意义课题的背景及意义论文的结构和主要内容论文的结构和主要内容u第一部分第一部分 简单阐述了手写数字聚类技术研究的现状及意义简单阐述了手写数字聚类技术研究的现状及意义。u第二部分第二部分 主要介绍流形学习的基本原理、优点和主要应用主要介绍流形学习的基本原理、优点和主要应用u第三部分第三部分 介绍聚类的主要方法介绍聚类的主要方法u第四部分第四部分 介绍基于介绍基于ISOMAP的手写体数字的聚类研究及改的手写体数字的聚类研究及改 进之处，通过实验进行分析进之处，通过实验进行分析u第五部分第五部分 总结本文的研究方法，对以后的研究进行展望总结本文的研究方

3、法，对以后的研究进行展望ISOMAP原理分析原理分析对于按照某种复杂结构分布在高维空间的样对于按照某种复杂结构分布在高维空间的样本，如果我们直接计算样本点与样本点之间的欧本，如果我们直接计算样本点与样本点之间的欧式距离，那么就无法获得样本的结构分布信息。式距离，那么就无法获得样本的结构分布信息。在样本分布较密集的情况下，可以采用欧式空间在样本分布较密集的情况下，可以采用欧式空间去近似代替被分为无数个局部小样本的样本集。去近似代替被分为无数个局部小样本的样本集。计算相邻两个样本之间的欧式距离，对于两个不计算相邻两个样本之间的欧式距离，对于两个不相邻的样本，可以通过一系列两两相邻的样本来相邻的样本

4、，可以通过一系列两两相邻的样本来构成连接这两个样本的路径，然后把每两个样本构成连接这两个样本的路径，然后把每两个样本间最短路径上的局部距离相加作为这两个样本的间最短路径上的局部距离相加作为这两个样本的距离。我们把这个距离叫做测地距离。通过这个距离。我们把这个距离叫做测地距离。通过这个样本间的距离矩阵，就可以采用度量型样本间的距离矩阵，就可以采用度量型MDS等映等映射到低维空间。射到低维空间。ISOMAP算法的主要步骤算法的主要步骤ISOMAP算法的主要步骤如下：算法的主要步骤如下：u 1、构造近邻图。首先计算任意两个样本向量、构造近邻图。首先计算任意两个样本向量xi与与xj的的欧氏距离欧氏距离

5、dXxixj然后用全部的样本向量然后用全部的样本向量 xi1=i=N构构造无向图造无向图G。对于样本向量。对于样本向量xi在图在图G中将它与离它最近的中将它与离它最近的n个样本向量个样本向量n是可调参数连接起来设置连接线的长度分别为是可调参数连接起来设置连接线的长度分别为它们各自的距离。它们各自的距离。u 2、计算任意两个样本向量之间的最短路径。在图、计算任意两个样本向量之间的最短路径。在图G中中设置任意两个样本向量设置任意两个样本向量xi与与xj之间的最短距离为之间的最短距离为dGij。如。如果果xi与与xj之间存在连线之间存在连线dGij的初始值设为的初始值设为 dXij否则令否则令dXi

6、j。接下来依次更新。接下来依次更新dGij的数值的数值dGijmin=I=NdGiJdG1j。u 3、经过多次迭代样本向量间最短路径矩阵、经过多次迭代样本向量间最短路径矩阵DGdGij便便可收敛。使用经典可收敛。使用经典MDS将样本向量压缩到将样本向量压缩到d维并使压缩之维并使压缩之后样本向量之间的欧氏距离尽可能接近已求出的最短路径后样本向量之间的欧氏距离尽可能接近已求出的最短路径。K-means算法原理算法原理设我们一共有设我们一共有 N 个数据点需要分为个数据点需要分为 K 个个 cluster，k-means 要做的就是最小化评价指标要做的就是最小化评价指标J 其中其中 rnk 在数据点

7、在数据点 n 被归类到被归类到 cluster k 的时候为的时候为 1，否，否则为则为 0。直接寻找。直接寻找 rnk和和 uk来最小化来最小化J并不容易，不过并不容易，不过我们可以采取迭代的办法：先固定我们可以采取迭代的办法：先固定 uk，选择最优的，选择最优的 rnk，很容易看出，只要将数据点归类到离他最近的那个中心，很容易看出，只要将数据点归类到离他最近的那个中心就能保证就能保证J最小。下一步则固定最小。下一步则固定rnk，再求最优的，再求最优的uk。将。将J对对uk求导并令导数等于零，很容易得到求导并令导数等于零，很容易得到J最小的时候最小的时候uk应应该满足：该满足：亦即亦即 uk

8、的值应当是所有的值应当是所有 cluster k 中的数据点的平中的数据点的平均值。由于每一次迭代都是取到均值。由于每一次迭代都是取到 J的最小值，因此的最小值，因此 J只会不只会不断地减小（或者不变），而不会增加，这保证了断地减小（或者不变），而不会增加，这保证了 k-means 最终会到达一个极小值。最终会到达一个极小值。K-means算法步骤算法步骤u 1、选定、选定 K 个中心个中心 的初值。这个过程通常是针对具体的初值。这个过程通常是针对具体的问题有一些启发式的选取方法，或者大多数情况下采用的问题有一些启发式的选取方法，或者大多数情况下采用随机选取的办法。因为前面说过随机选取的办法。

9、因为前面说过 k-means 并不能保证全并不能保证全局最优，而是否能收敛到全局最优解其实和初值的选取有局最优，而是否能收敛到全局最优解其实和初值的选取有很大的关系，所以有时候我们会多次选取初值跑很大的关系，所以有时候我们会多次选取初值跑 k-means，并取其中最好的一次结果。，并取其中最好的一次结果。u 2、将每个数据点归类到离它最近的那个中心点所代表、将每个数据点归类到离它最近的那个中心点所代表的的 cluster 中。中。u 3、用公式、用公式 计算出每个计算出每个 cluster 的新的中心点。的新的中心点。u 4、重复第二步，一直到迭代了最大的步数或者前后的、重复第二步，一直到迭代

10、了最大的步数或者前后的 的值相差小于一个阈值为止。的值相差小于一个阈值为止。PCA算法简介算法简介u PCA即主成分分析是线性降维方法，全称是即主成分分析是线性降维方法，全称是Principal Components Analysis，在图像处理中是比较流行的降维方法，在图像处理中是比较流行的降维方法，从统计学的角度来说，从统计学的角度来说是一种多元统计方法。是一种多元统计方法。PCA通过将多个变量通过线性变换以选出较少的重通过将多个变量通过线性变换以选出较少的重要变量。它往往可以有效地从过于要变量。它往往可以有效地从过于“丰富丰富”的数据信息中获取最重要的元的数据信息中获取最重要的元素和结构

11、，去除数据的噪音和冗余，将原来复杂的数据降维，揭示隐藏在素和结构，去除数据的噪音和冗余，将原来复杂的数据降维，揭示隐藏在复杂数据背后的简单结构。近年来，复杂数据背后的简单结构。近年来，PCA方法被广泛地运用于计算机领域方法被广泛地运用于计算机领域，如数据降维、图像有损压缩、特征追踪等等。，如数据降维、图像有损压缩、特征追踪等等。PCA方法其实就是将数据空间通方法其实就是将数据空间通过正交变换映射到低维子空间的过程。过正交变换映射到低维子空间的过程。红点代表原始数据点；绿点代表被红点代表原始数据点；绿点代表被映射到低维空间后的点；紫线代表映射到低维空间后的点；紫线代表映射平面。映射平面。模糊模糊

12、C均值算法简介均值算法简介u 模糊模糊C均值属于聚类的另一种，即模糊聚类，模糊集理论是均值属于聚类的另一种，即模糊聚类，模糊集理论是由由Zadeh在在1965年提出的，模糊年提出的，模糊C均值聚类算法均值聚类算法(FCM Fuzzy C-means)作为基于函数的一种最优方法的聚类作为基于函数的一种最优方法的聚类算法，它采用微积分计算技术的数学原理求最优代价函数算法，它采用微积分计算技术的数学原理求最优代价函数。Fuzzy C-means算法主要是比较算法主要是比较RGB空间的每个像素空间的每个像素值与值与Cluster中的每个中心点值，最终给每个像素指派一中的每个中心点值，最终给每个像素指派

13、一个值个值(01之间之间)说明该像素更接近于哪里说明该像素更接近于哪里Cluster的中心的中心点，模糊规则是该像素对所有点，模糊规则是该像素对所有cluster的值之和为的值之和为1。数字聚类流程数字聚类流程实验数据实验数据Isomap_300_10 Isomap_900_3 实验数据分析实验数据分析0.00%20.00%40.00%60.00%80.00%100.00%Isomap_300_2weiIsomap_300Isomap_300_4wei Isomap_300_5weiIsomap不同维数错误率52.93%48.43%40.60%33.83%0.00%10.00%20.00%30

14、.00%40.00%50.00%60.00%Isomap_300_can_3Isomap_300_can_7Isomap_300_can_9Isomap_300_can_11Isomap不同参数错误率42.33%51.23%47.20%50.37%实验数据分析实验数据分析0.00%20.00%40.00%60.00%80.00%100.00%Isomap_900_2weiIsomap_900Isomap_900_4wei Isomap_900_5weiIsomap降维（900数据）8.52%9.81%10.59%16.51%0.00%50.00%100.00%Pca_300_2weiPca_3

15、00Pca_300_4weiPca_300_5weiPca_300_can_5Pca_300_can_7Pca_300_can_9Pca_300_can_11Pca_900PCA降维错误率统计60.30%61.13%37.73%14.41%58.90%56.63%53.33%16.01%16.24%应用展望应用展望 虽然本文着重讲解的是手写体数字的聚类，但其原理虽然本文着重讲解的是手写体数字的聚类，但其原理和方法在图像处理上都是相通的。在未来这种技术可以应和方法在图像处理上都是相通的。在未来这种技术可以应用在一些安全方面，比如指纹识别、虹膜识别。可以让我用在一些安全方面，比如指纹识别、虹膜识别

16、。可以让我们的生活更便利和安全简洁，具体点讲可以实现门禁身份们的生活更便利和安全简洁，具体点讲可以实现门禁身份识别，保护住所财产的安全；或者是用于汽车的智能识别识别，保护住所财产的安全；或者是用于汽车的智能识别及启动，防止车被盗。还有现今已经广泛应用的车牌识别及启动，防止车被盗。还有现今已经广泛应用的车牌识别技术、快递扫描、指纹签到、钱币防伪等。医学上还有望技术、快递扫描、指纹签到、钱币防伪等。医学上还有望替代人类的眼睛，实现盲人的复明。替代人类的眼睛，实现盲人的复明。u大学本科的学习生活即将结束。在此，我大学本科的学习生活即将结束。在此，我要感谢所有曾经教导过我的老师和关心过要感谢所有曾经教导过我的老师和关心过我的同学，他们在我成长过程中给予了我我的同学，他们在我成长过程中给予了我很大的帮助。本文能够顺利完成，要特别很大的帮助。本文能够顺利完成，要特别感谢我的导师马勇老师，感谢各位系的老感谢我的导师马勇老师，感谢各位系的老师的关心和帮助。师的关心和帮助。u最后向所有关心和帮助过我的人表示真心最后向所有关心和帮助过我的人表示真心的感谢。的感谢。致谢致谢