1. 研究目的与意义（文献综述）

近些年来负数据库以其良好的特性作为一种新型技术被运用到了信息安全以及隐私保护领域上。所谓的信息的负表示，是受人工免疫系统启发而来。与传统的信息表示的区别在于信息的负表示是原始数据以其补集的数据的某种形式来表示。也就是不在数据库的元素被表达，而数据库本身的内容没有被显示表达。由于由负数据库逆转求解出原始数据涉及到不确定性问题，是np难的，因此负数据库作为一种信息负表示的存储形式，在信息安全和隐私保护具有独特的优势。同时，负数据库还保留了传统数据库的一些基本操作，例如：选择、插入、删除、和更新等，保留了传统数据库操作简单的优点。

k最近邻分类算法是一种很成熟的数据分类算法，自1968年由cover和hart提出，以其简单直观、分类准确的特点，受到了各领域关于处理数据挖掘分类工作的广泛应用。同时，knn分类算法的缺点也是十分的明显，例如数据量大运算量大是分类速度慢，等权重分类影响准确率，k值的确定等等。国内外的研究人员对k最近邻分类算法不断地改进，使其不断地适应大数据分析的要求。例如通过粗糙集理论简约训练集后的knn，基于svm的特征加权knn算法和优化了计算方法的knn等等。由此此次使用knn分类算法的决定也是合理的。选择成熟的knn分类算法使课题着重于隐私保护中的分类，而非单纯的分类算法的改良。

传统的knn分类算法是基于原始数据的分类算法。传统的数据大多数是基于实值的，相对来说knn分类算法简单直观，但是基于原始数据和实值分类不利于用户的隐私保护，可能造成数据的泄露。而负数据库还没有基于实值的，都是基于二进制字符串组成的数据库，而且还引入了不确定位。数据由于经过转换变得难以逆转，不再直观甚至意义模糊。因此基于负数据库的knn分类算法是十分具有挑战性的。此次进行的课题意义，并非仅在于负数据库的某方面的深入研究，或者说knn分类算法的在训练集和求近邻算法的优化，而是如何在保护隐私不降低信息安全性的情况下，即保持负数据状态不逆转甚至不了解数据含义的情况下，进行准确而安全的分类。这些尝试将会对负数据库信息安全和隐私保护产生积极地影响。

2. 研究的基本内容与方案

1、基本内容：学习负数据库和knn分类算法基础理论，使用c 来实现将原始数据转化为负数据的算法并熟悉数据库知识以建立负数据库。使用matlab或者c 实现knn分类算法，使之能对负数据库数据进行较快而精确的分类。

2、预期目标：学习负数据库理论以及knn算法知识并尽量完善自身对其的理解。实现一种基于负数据库的隐私保护k最近邻分类算法，并尽量改进优化，使负数据库难以逆转增强隐私保护，使knn算法能较快而精确。同时提升个人科研编程能力及文献编篡能力。

3. 研究计划与安排

①2月26日到3月12日：理解毕业设计要求，收集、查阅相关资料后，完成开题报告。完成负数据库和knn分类算法论文和文献的学习，以及外文翻译工作。

②3月13日到4月12日：完成课题的设计方案，同时按照设计方案，进行基于负数据库隐私保护的knn算法框架的建立与完善。基于负数据库理论以及knn分类算法原理，采用c 和数据库相关工具实现算法。同时深入对算法原理的研究，为算法优化做准备。’

③4月13日到5月31日：进行算法的优化，对算法实现进行编码、调试、测试等工作。撰写并修改毕业论文。

4. 参考文献（12篇以上）

[1] 潘丽芳, 杨炳儒. 基于簇的k最近邻(knn)分类算法研究[j]. 计算机工程与设计, 2009, 30(18):4260-4262.

[2] 闭小梅, 闭瑞华. knn算法综述[j]. 科技创新导报, 2009(14):31-31.

[3] 耿丽娟, 李星毅. 用于大数据分类的knn算法研究[j]. 计算机应用研究, 2014, 31(5):1342-1344.