博客

k最近邻分类器将实例指派到被最多近邻代表的类。它基于这样的想法：实例越类似，它们越可能属于同一类。只要有一个合理的相似性或距离度量，就可以对非类使用相同的方法。

大多数分类算法可以改写为基于距离的分类。例如，在最近均值分类器中(nearest mean classification)，选择











C








i















C

i


$C_i$
，如果

$$D(x, m_i) = \min_{j=1}^K D(x, m_j)$$

在高斯超球的情况下，维是独立的且具有相同的尺度，距离度量是欧氏距离：

$$D(x, m_i) = ||x-m_i||_2$$

否则它是马氏距离：

$$D(x, m_i) = (x-m_i)^T S_i^{-1}(x-m_i)$$

其中











S








i















S

i


$S_i$
是











C








i















C

i


$C_i$
的协方差矩阵。

在半参数方法中，每一个类都表示高斯混合。可以粗略地说，如果在所有类的簇中心中，属于











C








i















C

i


$C_i$
的簇中心是最近的，我们选择











C








i















C

i


$C_i$
：

$$\min_{l=1}^{k_i}D(x, m_{il})=\min_{j=1}^K\min_{l=1}^jD(x, m_{jl})$$

其中











k








i















k

i


$k_i$
是总簇数，











k








j

















k

j


$k_j$
是











C








j

















C

j


$C_j$
的簇数，











m








j




l



















m

j

l


$m_{jl}$
表示











C








j

















C

j


$C_j$
的簇








l












l


$l$
的中心。所使用的距离是欧氏距离还是马氏距离任然是依赖于簇的形状。

非参数方法可以更灵活。不是每类或每簇一个距离度量，而是对于每一个邻域，即输入空间中的每一个小区域，都可以有一个不同的距离度量。换句话说，可以定于局部自适应距离函数(locally adaptive distance function)用于分类，例如Knn。

距离学习(distance learning)的思想是参数化









D


(


x




,





x








t











|




θ




)

$D(x, x^t|\theta)%$
，以监督的方式学习








θ












θ


$\theta$
，然后将它与knn一起使用。最常见的方法是使用马氏距离：

$$D(x, x^t|M)=(x-x^t)^TM(x-x^t)$$

其中参数是正定矩阵M。

当输入维度很高时，为了避免过拟合，一种方法是在M上添加稀疏约束。里一种方法是使用低秩近似，把M分解为











L








T









L












L

T

L


$L^TL$
，而L是








k




×


d












k

×

d


$k \times d$
矩阵，其中








k




<


d












k

<

d


$k<d$
。在这种情况下：

$$D(x, x^t|M) = (x - x^t)^TM(x - x^t) = (x-x^t)L^TL(x-x^t)=(L(x-x^t))^T(L(x-x^T)) = (Lx-Lx^t)^T(Lx - Lx^t)=(z-z^t)^T(z-z^t) = ||z-z^t||^w$$

其中








z


=


L




x












z

=

L

x


$z=Lx$
是x的k维投影，学习L而不是M。我们看到，原始的d维x空间中的马氏距离相当于新的k维空间中的欧氏距离。这意味着距离估计、维度归约、特征提取三者之间的联系：

理想的距离度量是定义在星空间中的欧氏距离，新空间（最少的）维是以尽可能最好的方式从原始输入中提取的

。

对于离散数据，可以使用统计非匹配属性数的汉明距离(Hamming distance)：

$$HD(x, x^t) = \sum_{j=1}^d1(x_j \neq x_j^t)$$
其中








1


(


a


)










1

(

a

)


$1(a)$
取值为0或1.

这个框架也可以用于依赖应用的相似性度量或距离度量。对于视频中的图像匹配、生物信息学中的序列比对的得分，以及自然语言处理中的文档相似性度量，可以有专门的相似度或距离度量。这些都可以使用该框架而不必明确的表示为向量，应使用欧氏距离这样的通用度量。

只要有两个实例之间的相似性度量函数








S




(


x




,





x








t









)










S

(

x

,

x

t

)


$S(x, x^t)$
，就可以把实例x的基于相似性度量的表示(similarity-based representation)











x








′















x

′


$x'$
定义为所有训练实例的











x








t









(


t




=


1


,


2


,


.


.


.


,


N




)










x

t

(

t

=

1

,

2

,

.

.

.

,

N

)


$x^t(t=1, 2, ..., N)$
的N维向量：

$$x' = [s(x, x^1), s(x, x^2), ..., s(x, x^N)]^T$$

这可以作为被任意机器学习算法处理的向量。在核机器中，我们称它为经验核映射。