一种基于蚁群优化的相似重复记录检测中自动特征加权与选择方法

摘要

一种基于蚁群优化的相似重复记录检测中自动特征加权与选择方法，包括定义了基于属性类型的相似度函数计算公式，方法通过应用属性权重和检测阈值综合考虑的同步优化策略，将基于相对权重的特征选择方案，属性权重归一化的约束转换策略，以及蚁群算法求解过程中在不同变量间启发式信息的作用平衡策略，有机地整合起来，使整个方法更加系统、全面，加之整个方法基于领域无关的设计理念，适用范围更加广泛，体现了方法极大的健壮性和良好的可扩展性。

主权项

1.一种基于蚁群优化的相似重复记录检测中自动特征加权与选择方法，该方法用于领域无关数据清洗中检测和消除相似重复记录，其特征是建立了召回率、准确率和属性集规模综合最优的特征加权和选择数学模型；两记录的相似度函数通过下述公式计算：$S_{\mathrm{ij}}=F(s_{0\mathrm{ij}},s_{1\mathrm{ij}},···,s_{(n-1)\mathrm{ij}})=\underset{k=0}{\overset{n-1}{\Sigma }}{w}_k{s}_{\mathrm{kij}}$w₀，w₁，...，w_(n-1)≥0，且其中，s_kij＝f_k(v_ki，v_kj)＝f_k(v_kj，v_ki)表示两记录r_i和r_j的第k个属性的相似度，假设共有n个属性，v_ki，k＝0，1，...，n-1表示记录r_i的第k个属性，w₀，w₁，...，w_(n-1)表示各属性的权重，S_ij为两记录的相似度函数值，通过设定检测阈值δ∈[0，1]，当S_ij＞δ时，记录r_i，r_j相似重复，否则不相似重复；给定待检记录，用其中的q(1≤q≤n)个属性进行相似重复记录检测，对属性重新编号，属性集为A^q＝{α₀，α₁，...，α_q-1}，相似度向量为建立特征加权数学模型如下：max R(w₀，w₁，...，w_q-1；δ)max P(w₀，w₁，...，w_q-1；δ)max W(w₀，w₁，...，w_q-1)s.t.w₀，w₁，...，w_q-1≥0，且δ∈[0，1]其中，R表示召回率，表示检测出的相似重复记录数占相似重复记录总数的百分比，P表示准确率，表示检测出的真正相似重复记录数占检测出的相似重复记录总数的百分比，表示属性权重能量和，且此式说明，属性权重能量和的值域为[1/q，1]，其值越大，说明大权重属性越少，即能量越向少数属性集中，此时更多的属性权重接近0，易于进行特征选择；通过上述特征加权数学模型，得到一组属性权重和检测阈值，使召回率和准确率达到综合最优，同时使权重能量向少数属性的权重集中，上述特征加权数学模型的三个目标函数的优先级由高到低；其中，定义了基于相对权重的特征选择方法，通过去除相对权重为零的那些属性完成特征选择，公式如下：${\chi }_k=\frac{w_k}{\max \{w_0,w_1,···,w_{q-1}\}},$k＝0，1，...，q-1其中，χ_k∈[o，1]反映了属性α_k在相似重复记录检测中与权重最大的属性相比较的相对重要程度，若χ_k→0，则说明属性α_k的贡献很小；事实上，χ_k→0的属性还有可能对相似重复记录检测没有贡献，甚至会通过与其它属性竞争权重产生负面影响，将χ_k→0，即w_k＝0的属性删除，利于将权重向更好的属性集中，提高检测效果和精度，特征选择的过程即将w_k＝0的属性α_k从属性集A^q中删除；综合上述特征加权与特征选择，建立了特征加权和选择数学模型：max R(w₀，w₁，...，w_q-1；δ)max P(w₀，w₁，...，w_q-1；δ)min qs.t.0≤q≤n-1δ∈[0，1]通过上述特征加权与选择数学模型，获得属性集A^q的各属性权重和检测阈值，使召回率和准确率最优，同时使A^q的规模最小，上述特征加权和选择数学模型的三个目标函数的优先级由高到低，该特征加权和选择数学模型的求解依赖于对上述特征加权数学模型的求解；其中，通过模型分析和约束条件转化，设计了求解特征加权数学模型的基于平移搜索窗口的蚁群优化算法：特征加权数学模型是多目标多约束优化问题，利用蚁群算法对其进行求解，必须首先对属性权重归一化的约束条件进行转化，通过给属性α_k定义等级l_k∈[0，+∞)，k＝0，1，...，q-1，l_k是连续的，即可以有0等级，等级越高，表示属性越重要，等级划分由蚁群优化实现，然后，将等级值做归一化求取权重，计算公式如下：$w_k=\frac{l_k}{\underset{k=0}{\overset{q-1}{\Sigma }}{l}_k}$通过上述转换，将求解特征加权数学模型转化为了间接求取属性等级和检测阈值；所述基于平移搜索窗口的蚁群优化算法需要进行搜索窗口的设定，记属性等级变量l_k的第D组搜索窗口为D＝0，1，2，...，k＝0，1，...q-1，L_kDB，L_kDE分别为第D组第k个窗口的起点和终点，则记初始搜索窗口为L_k0＝[L_k0B，L_k0E]，即基准区域，再记网格宽度为Δl，即搜索精度，窗口的网格数为M，每个窗口包含M+1个网格点，根据属性等级的实际意义，q个初始窗口均设定为以L_k0C＝1为中心，既基准点，等级值相等，即属性重要程度相同，各属性权重均为即算法从等权重邻近区域开始搜索，设Δl＝0.1，M＝10，则L_k0＝[0.5，1.5]，每个窗口含11个网格点；记检测阈值变量δ的第D组搜索窗口为D＝0，1，2，...，Φ_kB，Φ_kE分别为第D组窗口的起点和终点，相应的，记初始窗口为Φ₀＝[Φ_0B，Φ_0E]，网格宽度为Δδ，为了方便处理，并使不同类型的变量构成的解空间得到同等遍历，窗口网格数同样为M，根据相似重复记录检测阈值设定经验，最优阈值靠近其取值范围的上界，所以将初始窗的基准点设置为定义域的上边界，即Φ_0E＝1，设Δδ＝0.01，则Φ₀＝[0.90，1.00]，每个窗口含11个网格点，为了平衡算法求解过程中不同变量的启发式信息，以使蚁群在不同变量的搜索空间内启发信息对转移概率的作用一致，需要将启发式信息对两类变量的作用进行平衡，启发式信息矩阵η_xy由下式计算：${\eta }_{\mathrm{xy}}=\left\{\begin{array}{cc}|L_{\mathrm{xDB}}+\mathrm{y\Delta l}-L_{x0C}|& x=\mathrm{0,1},...,q-1\\ ({\Phi }_{0E}-({\Phi }_{\mathrm{DB}}+\mathrm{y\Delta \delta }))\frac{\mathrm{\Delta l}}{\mathrm{\Delta \delta }}& x=m-1\end{array}\right.$通过启发式信息矩阵的计算表达式，优先选择离初始窗基准点远的网格点，即每次窗口更新有较远平移，以快速到达更优区域；用网格宽度比平衡不同类型变量的启发式信息；启发式信息随窗口平移具有动态自适应性，离基准区域越远，各网格点的启发式信息差异越小，启发式信息的作用也相对减弱。