跳到主要内容

京都大学 情報学研究科 知能情報学専攻 2023年8月実施 専門科目 S-3

Author

祭音Myyura, itsuitsuki

Description

Suppose that samples are given in a 2-dimensional feature space as shown in Table 1. The samples are denoted by xi=(xi1,xi2)Tx_i = (x_{i1}, x_{i2})^T, (i=1,,n)(i = 1, \ldots, n), where TT represents the transpose of a vector or a matrix. Answer the following questions.

(1) Suppose that a classification of the samples in Table 1 (a) is given by

Class(xi)={C1(i=1,3,5)C2(i=2,4,6) \text{Class}(x_i) = \begin{cases} C_1 & (i = 1, 3, 5) \\ C_2 & (i = 2, 4, 6) \end{cases}

where C1C_1 and C2C_2 represent two classes. Find the linear classifier function that classifies a new sample xjx_j into the class whose center is closer to the sample in Euclidean distance than the other class’s center.

(2) Suppose that another classification of the samples in Table 1 (a) is given by

Class(xi)={C3(i=3,5,6)C4(i=1,2,4) \text{Class}(x_i) = \begin{cases} C_3 & (i = 3, 5, 6) \\ C_4 & (i = 1, 2, 4) \end{cases}

where C3C_3 and C4C_4 represent two classes. Explain how we can compare the discriminability of the classifications given in (1) and (2) by using the within-class variance concerning the distribution of the samples within a class and the between-class variance concerning the distribution of the classes.

(3) For each class given in (1), give the formula for calculating Mahalanobis distance for xix_i.

(4) Explain which class given in (1) is suitable for the sample in Table 1 (b). The assumption on the sample distribution required for the discussion must be clearly stated.

题目描述

题图表 1 给出二维样本 xi=(xi1,xi2)x_i=(x_{i1},x_{i2})^\topi=1,,ni=1,\ldots,n):

二维样本表
  1. 对表 1(a) 的分类 C1={x1,x3,x5}C_1=\{x_1,x_3,x_5\}C2={x2,x4,x6}C_2=\{x_2,x_4,x_6\},求线性分类函数:把新样本分到 Euclidean 距离更近的类中心。
  2. 另有分类 C3={x3,x5,x6}C_3=\{x_3,x_5,x_6\}C4={x1,x2,x4}C_4=\{x_1,x_2,x_4\}。说明如何用类内方差和类间方差比较第 1 问与该分类的可分性。
  3. 对第 1 问的每一类,写出计算样本 xix_i 的 Mahalanobis 距离的公式。
  4. 说明表 1(b) 的样本更适合第 1 问中的哪一类,并明确说明讨论所需的样本分布假设。

考点

  • 最近类中心线性分类器:展开两个到均值向量的平方距离差,得到线性判别函数。
  • Fisher 线性判别准则:用类间散布相对类内散布的比值比较两种标注的可分性。
  • Mahalanobis 距离与 Gaussian 分类:用各类协方差逆矩阵度量距离,并说明在 Gaussian 及先验/协方差假设下作分类。

Kai

(1)

Let c1c_1 and c2c_2 denote the center of classes C1C_1 and C2C_2, respectively. Then we have

{c1=(1+023,4+8+63)=(1,6)c2=(1+4+43,1+2+63)=(3,3)\begin{aligned} \begin{cases} \displaystyle c_{1} = \left(\frac{-1+0-2}{3},\frac{4+8+6}{3}\right) =(-1,6)\\ \displaystyle c_{2} = \left(\frac{1+4+4}{3},\frac{1+2+6}{3}\right) =(3,3) \end{cases} \end{aligned}

Let the point (x,y)(x,y) be where the Euclidean distance from c1c_1 and c2c_2 are equal. Then we define a linear classifier with the decision boundary as follows:

(x+1)2+(y6)2=(x3)2+(y3)2(x+1)^{2}+(y-6)^{2} = (x-3)^{2}+(y-3)^{2}

i.e.,

8x6y+19=08x-6y+19 = 0

The classifier is

f((x,y))={C1,8x6y+19>0,C2,8x6y+19<0.f((x,y))=\begin{cases} C_1,&8x-6y+19>0,\\C_2,&8x-6y+19<0. \end{cases}

(2)

Let cˉ\bar{c} denote the mean of all the data

cˉ=(1,92).\bar{c} = \left(1,\frac{9}{2}\right).

Since a larger ratio of between-class variance (sum of squared class center-overall center distances) to within-class variance (sum of squared data-class center distances) is considered a better classification, we compare the ratio r1r_1 and r2r_2 of Q1 and Q2.

Let cic_i denote the center of class CiC_i. Then we have

r1=i=1,2(cicˉ)T(cicˉ)i=1,2xCi(xci)T(xci)=12.5300.416r_1 = \frac{\sum_{i=1,2}(c_{i} - \bar{c})^{T}(c_{i}-\bar{c})}{\sum_{i=1,2}\sum_{x \in C_{i}}(x-c_{i})^{T}(x-c_{i})} = \frac{12.5}{30} \approx 0.416

Similarly,

r2=173/18116/30.248r_2 = \frac{173/18}{116/3} \approx 0.248

Since r1>r2r_1 > r_2, the classifier in Q1 is better than Q2.

(3)

For j=1,2j=1,2, let Σj\Sigma_j denote the covariance matrix of CjC_j. Then, the Mahalanobis distance for xix_i corresponding to CjC_j is

Lj=(xicj)TΣj1(xicj)L_{j} = \sqrt{(x_{i}-c_{j})^{T}\Sigma_{j}^{-1}(x_{i}-c_{j})}

where

Σ1=(1114),Σ2=(3337)\Sigma_{1} = \begin{pmatrix} 1 & 1\\ 1 & 4 \end{pmatrix},\quad \Sigma_{2} = \begin{pmatrix} 3 & 3\\ 3 & 7 \end{pmatrix}

and by the inversion

(abcd)1=1adbc(dbca),\begin{pmatrix} a&b\\c&d \end{pmatrix}^{-1}=\frac1{ad-bc} \begin{pmatrix} d&-b\\-c&a \end{pmatrix},
Σ11=(43131313),Σ21=(712141414).\Sigma_1^{-1}=\begin{pmatrix}\frac43&-\frac13\\-\frac13&\frac13\end{pmatrix},\qquad \Sigma_2^{-1}=\begin{pmatrix}\frac7{12}&-\frac14\\-\frac14&\frac14\end{pmatrix}.

(4)

Assume that each sample follows a multivariate normal distribution. Based on the form of the probability density function of the multivariate normal distribution (assuming the samples of each class form a multivariate normal distribution respectively), it is better to classify the sample into the class with the smaller Mahalanobis distance calculated using the method in Q3.

Following the formula given in Q3, the Mahalanobis distances L1L_1 and L2L_2 for x7x_7 are

L1=283<2=L2\begin{aligned} L_1 = \sqrt{28\over 3}<2= L_2 \end{aligned}

Hence class C2C_2 is suitable for x7x_7.