作者简介:邓剑勋(1978-),男,副教授,博士.研究方向:模式识别,图像处理.E-mail:dengjianxun@189.cn
针对传统DNALA算法运行效率低、最终数据挖掘结果精度不理想等问题,提出了一种基于谱聚类矩阵的改进DNALA(DNALA-I)算法,提高了时间效率以及结果精度。该算法通过频谱聚类方法中的计算距离矩阵方法对传统DNALA算法中通过多序列比计算距离矩阵的方法进行改进,在不降低数据挖掘精度的前提下能够有效减少对齐序列所花费的时间,提高算法的运行效率。仿真实验结果表明:本文算法相较传统的DNALA算法不仅提高了时间效率,并且保证了实验结果的计算精度。
Traditional DNALA algorithm has the shortcomings of low efficiency in terms of running time and unsatisfactory accuracy of the data mining results. To overcome these shortcomings, an improved DNALA algorithm is proposed based spectral clustering matrix, called DNALA-I, which can improve the time efficiency and accuracy of the results. The calculation of the distance matrix by multi sequence ratios in the traditional DNALA algorithm is improved by calculation of the spectral clustering distance matrix in the DNALA-I algorithm. Experiment results show that, compared with the traditional DNALA algorithm, the proposed DNALA-I algorithm can effectively reduce the time for sequence alignment meanwhile remain the data mining accuracy.
数据库技术的飞速发展导致数据量呈指数级增长[1]。面对巨量的数据, 单靠人工进行统计分析显然不现实, 这就促进了数据挖掘技术的快速发展[2]。目前, 数据挖掘技术不断由低精度、低深度向高精度、高深度发展, 当人们利用数据挖掘技术对巨量数据进行分析和挖掘时, 不得不面对这些数据的隐私保护问题[3, 4, 5]。
在数据挖掘领域已经有许多专家学者提出了防止用户个人隐私数据泄露的数据挖掘算法, 其中事务型数据隐私保护问题是一个重要的研究方向。Terrovitis等[6]将关系型数据k-匿名化处理算法应用到事务型数据中, 提出了km-匿名化算法。该算法的前提是集合里项目的数目不能大于m, 并且该集合必须被数目不低于k的事务记录所包含。该算法的缺点是:当巨量数据中含有一定量的非正常数据项目时, 数据容易被概化过度, 进而导致数据信息损失过多, 影响最后的信息精度。km-匿名化采用的是全局概化技术[7], 后来一些专家学者对该算法进行了改进, 提出了采用局部概化技术的事务型匿名原则, 该原则要求更为苛刻, 但缺点就是破坏了原始数据的域互斥性[8]。Xu等[9]提出了一种新的采用全消隐技术的
以上几种数据挖掘隐私保护技算法都较为经典, 并且还有很多其他基于聚类算法的隐私保护技术[11]。本文提出了一种基于谱聚类矩阵的改进DNALA(DNALA-improved, DNALA-I)算法, 对传统DNALA算法中距离矩阵的计算方法进行了改进, 提高了时间效率以及结果精度。
DNALA算法通常用来保护个人DNA数据隐私安全, 属于经典的数据挖掘中个人数据隐私保护算法, 原理是在个人的DNA数据维护中融入k-匿名(k-Anonymitya)方法, 从而得到DNALA算法。它的主要攻击方式是路径攻击, 该算法主要是采用模糊化方式处理DNA数据, 进而确保数据库的序列存在与其相一致的序列(这一序列表示为k-1个, 但是在实践中, 一般选择k=2), 这样可以有效杜绝路径的干扰。但是, 该方法保证数据安全的代价是牺牲了数据的准确性[12]。
DNALA算法步骤为:①将数据库的数据逐一展开并进行多序列对比, 运用的算法和工具有多种, 在文献[2]中的计算方法为CLUSTALW; ②距离矩阵由对比结果和DNA单字符表示法的兼容性两部分构成。
DNALA算法能够有效保护DNA数据中的个人隐私, 但也存在明显缺陷[13]。DNALA算法中通过多序列对比来计算距离矩阵, 这种机制属于纯动态规划, 缺点是复杂度极高、计算效率较低。从而导致在DNA数据预处理阶段, 算法时间成本太高, 必须借助别的算法进行额外加速。并且DNALA算法数据预处理阶段采用贪心算法对序列进行分组, 分组效果不是特别理想[14]。
本文算法将传统数据挖掘算法中的数据对象转换为空间数据对象, 利用频谱聚类方法中的计算距离矩阵方法对传统DNALA算法中通过多序列对比计算距离矩阵的方法进行改进。在传统聚类算法的基础上, 通过谱图机制分析出聚类结果, 实现了距离矩阵算法与谱聚类算法的有机结合, 大大降低了数据预处理阶段序列分组的复杂度, 节省了时间, 提高了算法效率。同时, 该算法采用双序列对比, 相较DNALA算法能够进一步减少序列排列所花费的时间, 并且增加了序列对比的灵活性。
谱聚类算法用于处理图像空间最优划分数据, 其机制是将数据向数据点转变之后连接这些数据点, 从而组合成图[15]。DNA序列算法将根据前文介绍的谱聚类算法的特点, 结合DNA序列可以被认为是储存于空间的图像数据这一特征来完善DNALA算法, 有利于提升算法效率, 也有利于完善算法的精准度。本文采用其非对称规范Laplace矩阵的方法计算距离矩阵。
1.2.1 聚类
谱聚类算法是一种基于图论的聚类方法。在谱聚类算法内, 通常用高斯核函数计算相似矩阵
由图1可知, 该图能够视为2个部分构成, 可以将它们分别做聚类泛化处理得到最佳结果。但是由于在实际应用中并非全部数据都是正常数据, 常常会出现难于处理的异常数据, 这时候就会增加划分数据的复杂度。该情况下应当制定标准的数据划分方法, 以确保数据点能够得到有效的划分。
定义(划分) 由于划分代表着各种类包含的2个点连线形成的边的集合。因此, 其公式为:
将以上标准问题归类为获得最小划分问题。结合图1可知其划分所采取的公式为:
全面考虑各类的相互关系, 并对其内部的密度性加以权衡, 以便兼顾类的内、外部状态, 那么可得获取最佳划分的评价标准公式为:
式中:Ncut(· )表示最佳划分;
采用该评价标准有利于获取最佳划分, 其优势为充分借助各种类包含的内、外部关系, 以确保状态得到最优平衡。
1.2.2 基于谱聚类的规范Laplace矩阵
选取
顶点集的度矩阵为:
谱聚类算法一般采用的矩阵如下所示。
Laplace矩阵为:
转移概率矩阵为:
非对称规范Laplace矩阵为:
规范相似矩阵为:
对称规范Laplace矩阵为:
在转移概率矩阵
在谱聚类算法中, 采用高斯核函数对距离矩阵进行转换来计算相似矩阵。一般而言, 相似矩阵
式中:
多路归一化割普聚类方法属于普聚类算法之一, 它的性能优良, 且其普聚类矩阵属于非对称规范Laplace矩阵。因此, 本文围绕扰动理论, 在DNALA算法中积极融合非对称规范Laplace矩阵的优势, 改进其计算距离矩阵的方法, 一方面加强了算法的运行效率; 另一方面提升了信息的安全性, 全面保护个人隐私。
1.3.1 DNALA-I序列对比
序列对比通常是用于汇总、分析各类数据, 并且结合各类方法来寻求规律性, 在模式识别、机器学习以及数据挖掘等领域应用广泛。
双序列对比通常是以DNA序列为基础, 对其相应的元素逐一加以对比, 确保对比结果的正确性和准确性, 保障个人信息安全。因此, 需要事先围绕原始序列做出相应处理, 其具体步骤如下:
(1)插入(Insertion):将字符插入到DNA序列中, 如将几个空格分别插入到序列中, 用“ -” 表示。
(2)删除(Deletion):选择序列里面的字符, 对其进行删除操作, 如选中序列里面包含的空格, 对其进行删除, 用“ -” 表示。
(3)替换(Substitution):选中序列, 将需要的字符进行替换操作。
选取序列
选取
(1)对序列
(2)两个碱基的得分需要根据得分递推公式和替换矩阵进行详细填写。
(3)以得分矩阵为基础, 从矩阵对应的右下方位开始, 由最大分值依次做路线回溯操作。
(4)将回溯路线转化成对比结果, 也就是完成插入空格等相关操作。
这一序列对比的对象是偶数序列, 但是在实际过程中并非只有偶数序列, 也常出现奇数序列。假如原始序列集合的序列全部属于奇数, 则最终一个序列对比包含3条序列, 但是本部分仅是针对双序列为对比对象来进行距离矩阵的计算, 所以, 在多序列对比时, 只要再增加一次对这3个序列的对比即可。由于数量不多, 可以快速获得其对比结果。
1.3.2 DNALA-I距离矩阵计算
就DNALA序列而言, 如果两个字符被泛化, 需要通过距离衡量信息受到的损失。本文基于规范Laplace矩阵全面改进DNALA序列矩阵。字符
用
式中:lev(· )为字符“ · ” 所在的层。
序列
以Laplace矩阵所具备的特点以及扰动原理为中心, 计算DNA序列泛化后距离的新算法详细步骤如下所示。
(1)选取一个矩阵
Step1
式中:
Step2 相似矩阵
式中:
(2)选取
(3)将
(4)当分区序列值全部选取完毕后, 就可以得出一棵进化树。
DNALA-I算法侧重于聚成含有两条序列的类, 如果前置条件是出现奇数条序列, 一个类就会含有3条序列, 每条记录需要得到有效的区分。
本文的实验数据来自文献[16]中的数据I和数据II, 通过Matlab软件实现仿真验证。本文首先将DNA序列中含有的数据流信息放入度量空间; 然后通过弱聚类的数据流匿名化框架实现数据匿名化, 以便维护用户隐私, 其原理是将处于DNA数据集里面的数据流信息视为空间点; 最后对其进行距离矩阵和相似度计算。DNA序列数据经过匿名化处理后, 不会严重影响原始DNA序列的数据信息。
通过双序列以及多序列的对比方法, 将两个数据集中所含有的子序列进行对比, 同时将对齐序列所耗费的时间进行计算, 结果如图2所示。由图2可见, 与多序列对比而言, 双序列对比更加节约时间, 数据集I对该现象的呈现十分显著。
采用不同算法计算原始序列与其泛化序列间的平均距离, 结果如表1和图3所示。即使在同一实验环境中, 得到的值也会有偏差, 因此, 对一个数据进行多次实验, 取3次实验的平均值。
通过多序列、双序列两种方法进行序列对比, 然后计算其距离矩阵。同时对其进行聚类, 并对聚类结果做泛化处理, 取两者的平均距离。由表1可以看出:在确保聚类算法精度的前提下, 若想减少计算距离矩阵平均距离的时间, 可以借助多序列、双序列这两种对比方法来有效对齐序列, 这样还能够进一步提升计算结果的精度。
从上述实验结果可以看出:将DNALA-I距离矩阵计算方法运用到DNA序列集合中, 能够大大提升序列对比的时间效率, 同时也提升了聚类算法的精度。
提出了基于谱聚类矩阵的改进的DNALA算法— — DNALA-I(DNALA-improved)算法。该算法通过频谱聚类方法中的计算距离矩阵方法对传统DNALA算法中通过多序列比来计算距离矩阵的方法进行改进, 在不降低数据挖掘精度的情况下, 本文算法能够有效减小对齐序列所花费的时间, 提高时间效率。仿真实验结果表明:本文算法相较传统的DNALA算法不仅提高了时间效率, 并且保证了实验结果的计算精度。
The authors have declared that no competing interests exist.