第2期 林耀进，等：融合邻域信息的k近邻分类 .241 几里德一重叠度量(heterogeneous euclidean--overlap 上分析，可以得出准则1。 metric,.HEOM)等[4s]。另外，许多学者考虑了样本 准则1考虑样本邻域信息的影响能更加精确 之间的权重以增强样本之间的相似性。H山等6)提 地刻画样本之间的距离。 出一种通过梯度下降的方法估计样本之间的权重进 行改进KNN的分类算法：Wang等)提出一种简单 的自适应距离度量来估算样本的权重。同时，一些 学者通过属性加权或属性选择途径改进距离度 量8。在局部距离度量方面，许多方法利用局部 自适应距离处理全局优化问题，如：ADAMENN中的 自适应距离，WAKNN中的权重校正度量方法及 图1样本邻域图 Fig.1 Neighborhood of sample DANN中的差异化自适应度量方法[c-) 上述方法虽能有效地度量样本之间的距离，但 2.2样本邻域的定义 基本上都是从单一的距离进行考虑，存在着以下缺 据2.1节分析可知，考虑样本邻域之间的距离可 点：1)并未考虑样本之间的邻域结构：2)易受噪声 以更加精确地刻画样本之间的距离△，因此，寻找样 的影响：3)不能处理多模态分布问题。因此，本文 本邻域对提高k-近邻分类算法具有重要的影响。本 受推荐中的用户群体影响概念的启发以)，提出了一 节中给出样本的度量空间及样本邻域的定义。 种融合样本邻域信息的k-近邻分类算法。 定义13]给定一个m维的样本空间2，△： Xm×Xm→X,称△是Xm上的一个度量，如果△满 1k-近邻分类法 足：1)△(x1,x2)≥0,4(x1,x2)=0,当且仅当 k-近邻分类法是一种非常简单有效的用于分类 x1=x2,x1,x2∈X;2)4(x1,x2)=△(x2,x1), 学习和函数逼近的算法。给定由n个样本标签对组 Vx1,x2∈Xm;3)△(x1,x3)≤△(x1,x2)+△(x2, 成的数据集D,D={(x1,c1),(x2,C2),…,(xn,Cn)}, x3),x1,x2,3∈X;称〈D,△〉为度量空间。 其分类的任务在于获取映射函数∫，使得能正确预测 在N维欧氏空间中，给定任意2点x:=(x1,x2, 无标签样本。设N,(x)为测试样本x的k-近邻集合， …,)和考=(2，…，x),其距离为 k-近邻分类法在于通过测试样本x的k-近邻进行大 (2)） 众数投票进行确定x的标签，其公式为 4=(点内 另外，为了处理异构特征，许多学者提出了多种 c=argmax∑∑1(g=c,) (1) 距离函数。如VDM、HVDM和HEOM。其中，VDM EieCIjEN(x) 式中：c为样本x,的类标签，I()为指示函数，当c:与 定义为VDM(x:,x)= 立d-,且 9一样时，1(c=c)=1,否则，1(c=c)=0。 d(xa,x)=(P(x1,x)2,P(x)表示样本x在特征 2融合邻域信息的k-近邻分类算法 1下的分布概率。 定义2给定样本空间上的非空有限集合X= 2.1 邻域信息的影响 {x1,x2,…,xm},对于X上的任意样本x,定义其6 传统的k-近邻分类算法本质上是利用样本个 邻域为6(x)={xlx∈X,△(x,x:)≤8}，其中，0≤ 体与个体之间的距离（寻找对测试样本影响最大的 6≤1.8(x)称为样本x,相应的8邻域。 前k个近似邻居)来预测测试样本的类标签，该预测 定义3给定样本空间上的非空有限集合X= 只是简单地考虑样本个体之间的相似性，而忽略了 {x1,x2,…,xm},对于X上的任意样本x:及x,根据 样本的邻域信息。因此，在计算样本个体距离时不 VDM公式，定义样本x:及，之间的邻域距离为 仅要考虑样本个体之间的距离，也要考虑样本邻域 16(x)116,(g)12 信息产生的距离。图1清楚地描述了样本邻域信息 n()=Σ-1）(3) 1=1 产生的影响作用，从图1可以看出，虽然样本x,与 性质1]给定一个度量空间〈2，△〉，一个 x2之间的距离与样本x1与x3之间的距离相等，即 非空有限样本集合X={x1,出2，…，x}。如果6，≤ d(x1,x2)=d(x1,x3),但是样本x1的邻域信息与x3 62,则有 的邻域信息之间包含更多的大量的共同邻居，则从 1)Hx:∈X:δ1(x)≥82(x); 认识论的角度出发，d(x1,x3)≥d(x1,x2)。根据以 2)U8(x)=X。几里德—重叠度量（ ｈｅｔｅｒｏｇｅｎｅｏｕｓ ｅｕｃｌｉｄｅａｎ⁃ｏｖｅｒｌａｐ ｍｅｔｒｉｃ， ＨＥＯＭ）等［４⁃５］ 。 另外，许多学者考虑了样本 之间的权重以增强样本之间的相似性。 Ｈｕ 等［６］ 提 出一种通过梯度下降的方法估计样本之间的权重进 行改进 ＫＮＮ 的分类算法；Ｗａｎｇ 等［７］ 提出一种简单 的自适应距离度量来估算样本的权重。 同时，一些 学者通过属性加权或属性选择途径改进距离度 量［８⁃９］ 。 在局部距离度量方面，许多方法利用局部 自适应距离处理全局优化问题，如：ＡＤＡＭＥＮＮ 中的 自适应距离， ＷＡＫＮＮ 中的权重校正度量方法及 ＤＡＮＮ 中的差异化自适应度量方法［１０⁃１１］ 。 上述方法虽能有效地度量样本之间的距离，但 基本上都是从单一的距离进行考虑，存在着以下缺 点：１）并未考虑样本之间的邻域结构；２） 易受噪声 的影响；３） 不能处理多模态分布问题。 因此，本文 受推荐中的用户群体影响概念的启发［１２］ ，提出了一 种融合样本邻域信息的 ｋ⁃近邻分类算法。 １ ｋ⁃近邻分类法 ｋ⁃近邻分类法是一种非常简单有效的用于分类 学习和函数逼近的算法。 给定由 ｎ 个样本标签对组 成的数据集 Ｄ， Ｄ ＝ ｛（ｘ１ ，ｃ１ ），（ｘ２ ，ｃ２ ），…，（ｘｎ ，ｃｎ ）｝， 其分类的任务在于获取映射函数 ｆ， 使得能正确预测 无标签样本。 设 Ｎｋ（ｘ） 为测试样本 ｘ 的 ｋ⁃近邻集合， ｋ⁃近邻分类法在于通过测试样本 ｘ 的 ｋ⁃近邻进行大 众数投票进行确定 ｘ 的标签，其公式为 ｃ ＝ ａｒｇｍａｘ ｃｉ ∑ｃｉ∈Ｃ ｘ ∑ ｊ∈Ｎｋ （ｘ） Ｉ（ｃｊ ＝ ｃｉ） （１） 式中： ｃｊ 为样本 ｘｊ 的类标签， Ｉ（·） 为指示函数，当 ｃｉ 与 ｃｊ 一样时， Ｉ（ｃｊ ＝ ｃｉ） ＝ １， 否则， Ｉ（ｃｊ ＝ ｃｉ） ＝ ０。 ２ 融合邻域信息的 ｋ⁃近邻分类算法 ２．１ 邻域信息的影响 传统的 ｋ⁃近邻分类算法本质上是利用样本个 体与个体之间的距离（寻找对测试样本影响最大的 前 ｋ 个近似邻居）来预测测试样本的类标签，该预测 只是简单地考虑样本个体之间的相似性，而忽略了 样本的邻域信息。 因此，在计算样本个体距离时不 仅要考虑样本个体之间的距离，也要考虑样本邻域 信息产生的距离。 图 １ 清楚地描述了样本邻域信息 产生的影响作用，从图 １ 可以看出，虽然样本 ｘ１ 与 ｘ２ 之间的距离与样本 ｘ１ 与 ｘ３ 之间的距离相等，即 ｄ（ｘ１ ，ｘ２ ） ＝ ｄ（ｘ１ ，ｘ３ ）， 但是样本 ｘ１ 的邻域信息与 ｘ３ 的邻域信息之间包含更多的大量的共同邻居，则从 认识论的角度出发， ｄ（ｘ１ ，ｘ３ ） ≥ ｄ（ｘ１ ，ｘ２ ）。 根据以 上分析，可以得出准则 １。 准则 １ 考虑样本邻域信息的影响能更加精确 地刻画样本之间的距离。 图 １ 样本邻域图 Ｆｉｇ．１ Ｎｅｉｇｈｂｏｒｈｏｏｄ ｏｆ ｓａｍｐｌｅ ２．２ 样本邻域的定义 据 ２．１ 节分析可知，考虑样本邻域之间的距离可 以更加精确地刻画样本之间的距离 Δ， 因此，寻找样 本邻域对提高 ｋ⁃近邻分类算法具有重要的影响。 本 节中给出样本的度量空间及样本邻域的定义。 定义 １ ［１３］ 给定一个 ｍ 维的样本空间 Ω， Δ： Ｘ ｍ ×Ｘ ｍ → Ｘ， 称 Δ 是 Ｘ ｍ 上的一个度量，如果 Δ 满 足： １ ） Δ（ｘ１ ，ｘ２ ） ≥ ０，Δ（ｘ１ ，ｘ２ ） ＝ ０， 当 且 仅 当 ｘ１ ＝ｘ２ ，∀ｘ１ ，ｘ２ ∈ Ｘ ｍ ； ２ ） Δ（ｘ１ ，ｘ２ ） ＝ Δ（ｘ２ ，ｘ１ ）， ∀ｘ１ ，ｘ２ ∈ Ｘ ｍ ； ３） Δ（ｘ１ ，ｘ３ ） ≤ Δ（ｘ１ ，ｘ２ ） ＋ Δ（ｘ２ ， ｘ３ ），∀ｘ１ ，ｘ２ ，ｘ３ ∈ Ｘ ｍ ； 称 〈Ω，Δ〉 为度量空间。 在 Ｎ 维欧氏空间中，给定任意 ２ 点 ｘｉ ＝ （ｘｉ１ ，ｘｉ２ ， …，ｘｉＮ） 和 ｘｊ ＝ （ｘｊ１ ，ｘｊ２ ，…，ｘｊＮ）， 其距离为 Δ（ｘｉ，ｘｊ） ＝ （∑ Ｎ ｌ ＝ １ （ｘｉｌ － ｘｊｌ） ２ ） １ ２ （２） 另外，为了处理异构特征，许多学者提出了多种 距离函数。 如 ＶＤＭ 、ＨＶＤＭ 和 ＨＥＯＭ。 其中，ＶＤＭ 定 义 为 ＶＤＭ（ｘｉ，ｘｊ） ＝ ∑ Ｎ ｌ ＝ １ ｄｌ（ｘｉｌ － ｘｊｌ）， 且 ｄｌ（ｘｉｌ，ｘｊｌ） ＝ （Ｐ（ｘｉｌ，ｘｊｌ）） ２ ， Ｐ（ｘｌ） 表示样本 ｘ 在特征 ｌ 下的分布概率。 定义 ２ 给定样本空间上的非空有限集合 Ｘ ＝ ｛ｘ１ ，ｘ２ ，…，ｘｍ ｝， 对于 Ｘ 上的任意样本 ｘｉ， 定义其 δ 邻域为 δ（ｘｉ） ＝ ｛ｘ ｜ ｘ ∈ Ｘ，Δ（ｘ，ｘｉ） ≤ δ｝， 其中， ０ ≤ δ ≤ １。 δ（ｘｉ） 称为样本 ｘｉ 相应的 δ 邻域。 定义 ３ 给定样本空间上的非空有限集合 Ｘ ＝ ｛ｘ１ ，ｘ２ ，…，ｘｍ｝， 对于 Ｘ 上的任意样本 ｘｉ 及 ｘｊ， 根据 ＶＤＭ 公式，定义样本 ｘｉ 及 ｘｊ 之间的邻域距离为 ｎ（ｘｉ，ｘｊ） ＝ ∑ Ｎ ｌ ＝ １ （ ｜ δｌ（ｘｉ） ｜ Ｘ － ｜ δｌ（ｘｊ） ｜ Ｘ ） ２ （３） 性质 １ ［１３］ 给定一个度量空间 〈Ω，Δ〉， 一个 非空有限样本集合 Ｘ ＝ ｛ｘ１ ，ｘ２ ，…，ｘｍ ｝。 如果 δ１ ≤ δ２ ， 则有 １） ∀ｘｉ ∈ Ｘ：δ１（ｘｉ） ≥ δ２（ｘｉ）； ２） ∪ ｍ ｉ ＝ １ δ（ｘｉ） ＝ Ｘ。 第 ２ 期 林耀进，等：融合邻域信息的 ｋ⁃近邻分类 ·２４１·