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

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

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

本次设计的目的在于实现或改进一种基于负数据库的隐私保护K最近邻分类算法。在查阅负数据库的相关文献时发现，国内对于负数据库方面的研究热度相对国外还是相对欠缺，只找到中国科技大学有相关优秀论文文献。因此，希望此次在基于负数据库方面的研究，对与这种现象是有积极意义的。

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

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

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

3、拟采用的技术方案及措施：

a、抓取大量干净的原始数据，以SQLsever作为工具，利用数据库技术将其存在数据库中备用。

b、使用C 语言，以VisualStudi为开发工具，基于前缀算法和q-hidden算法或者基于q-hidden算法生成难以逆转的单串负数据库。