$$\mathbf{x} = \begin{bmatrix} \mathbf{x_B} \ \mathbf{0} \end{bmatrix} = \mathbf{B}^{-1}\mathbf{b}$$
时间: 2023-06-11 11:07:10 浏览: 56
这个公式很有意思,可以解释为:向量 $\mathbf{x}$ 是由向量 $\mathbf{b}$ 经过矩阵 $\mathbf{B}^{-1}$ 的逆变换得到的结果。其中,$\mathbf{x_B}$ 是向量 $\mathbf{x}$ 的前 $n$ 个元素,$\mathbf{0}$ 是向量 $\mathbf{x}$ 的后 $m-n$ 个元素,$n$ 是向量 $\mathbf{x}$ 的维度,$\mathbf{B}$ 是一个 $n \times n$ 的矩阵。这个公式在线性代数中非常常见,可以用于解线性方程组等问题。
相关问题
kmeans算法中,记 $\hat{\mathbf{x}}$ 为 $n$ 个样本的中心点, 定义如下变量: \begin{table}[h] \centering \label{table:equation} \begin{tabular}{ l | c } \hline total deviation & $T(X) = \sum_{i=1}^n \lVert \mathbf x_i - \hat{\mathbf x}\rVert^2/n$ \\ intra-cluster deviation & $W_j(X) = \sum_{i=1}^n \gamma_{ij} \lVert\mathbf x_i - \mu_j \rVert^2/\sum_{i=1}^n \gamma_{ij}$ \\ inter-cluster deviation & $B(X) = \sum_{j=1}^k \frac{ \sum_{i=1}^n \gamma_{ij}}{n} \lVert\mu_j -\hat{\mathbf x} \rVert^2$\\ \hline \end{tabular} \end{table} 试探究以上三个变量之间有什么样的等式关系? 基于此, 请证明, $k$-means 聚类算法可以认为是在最小化 intra-cluster deviation 的加权平均, 同时近似最大化 inter-cluster deviation.
根据定义,总偏差 $T(X)$ 可以展开为:
$$
T(X) = \frac{1}{n}\sum_{i=1}^n \lVert \mathbf x_i - \hat{\mathbf x}\rVert^2
$$
注意到 $\hat{\mathbf{x}}$ 是样本 $\mathbf{x}_1,\ldots,\mathbf{x}_n$ 的平均值,所以有:
\begin{align*}
\lVert \mathbf x_i - \hat{\mathbf x}\rVert^2 &= \lVert \mathbf x_i - \frac{1}{n}\sum_{j=1}^n \mathbf x_j \rVert^2 \\
&= \lVert \frac{1}{n}\sum_{j=1}^n (\mathbf x_i - \mathbf x_j) \rVert^2 \\
&= \frac{1}{n^2}\sum_{j=1}^n \lVert \mathbf x_i - \mathbf x_j \rVert^2 \\
\end{align*}
因此,我们可以将总偏差展开为:
$$
T(X) = \frac{1}{n}\sum_{i=1}^n \frac{1}{n}\sum_{j=1}^n \lVert \mathbf x_i - \mathbf x_j \rVert^2
$$
注意到 $\lVert \mathbf x_i - \mathbf x_j \rVert^2$ 表示样本 $\mathbf x_i$ 和 $\mathbf x_j$ 的距离,因此上式相当于计算所有样本对之间的距离的平均值,即总偏差就是所有样本之间距离的平均值。
接下来,我们来看 intra-cluster deviation $W_j(X)$ 和 inter-cluster deviation $B(X)$。
首先考虑 intra-cluster deviation $W_j(X)$。根据定义,$W_j(X)$ 是第 $j$ 个簇内部样本到簇质心的距离的平均值。可以将其展开为:
$$
W_j(X) = \frac{\sum_{i=1}^n \gamma_{ij} \lVert\mathbf x_i - \mu_j \rVert^2}{\sum_{i=1}^n \gamma_{ij}}
$$
注意到 $\gamma_{ij}$ 表示样本 $\mathbf x_i$ 是否属于第 $j$ 个簇,因此 $\sum_{i=1}^n \gamma_{ij}$ 表示第 $j$ 个簇中样本的数量。因此,$W_j(X)$ 可以看做是第 $j$ 个簇内部样本与该簇质心的距离平方和的加权平均值。
接下来考虑 inter-cluster deviation $B(X)$。根据定义,$B(X)$ 是所有簇质心到整个数据集质心的距离的平方和的加权平均值。可以将其展开为:
$$
B(X) = \sum_{j=1}^k \frac{\sum_{i=1}^n \gamma_{ij}}{n} \lVert\mu_j -\hat{\mathbf x} \rVert^2
$$
注意到 $\sum_{i=1}^n \gamma_{ij}$ 表示第 $j$ 个簇中样本的数量,因此 $\frac{\sum_{i=1}^n \gamma_{ij}}{n}$ 表示第 $j$ 个簇在整个数据集中的占比。因此,$B(X)$ 可以看做是所有簇质心与整个数据集质心的距离平方和的加权平均值。
综上所述,我们有以下等式关系:
$$
T(X) = \sum_{j=1}^k \frac{\sum_{i=1}^n \gamma_{ij}}{n} W_j(X) + B(X)
$$
也就是说,总偏差可以看做是所有 intra-cluster deviation 的加权平均值再加上 inter-cluster deviation。
因此,当我们使用 $k$-means 聚类算法时,我们的目标是最小化所有 intra-cluster deviation 的加权平均值,同时近似最大化 inter-cluster deviation,以使得总偏差最小。
设原样本$\mathbf{X}$的协方差矩阵对应的$d'$个特征值组成的投影变换为$\mathbf{W}$. 考虑旋转变换(样本围绕点$\boldsymbol{p}$顺时针旋转$\theta$). 试求解变换后的样本$\hat{\mathbf{X}}$对应的$\hat{\mathbf{W}}$.
设旋转变换矩阵为$\mathbf{R}$,其中:
$$\mathbf{R}=\begin{bmatrix}
\cos \theta & -\sin \theta \\
\sin \theta & \cos \theta
\end{bmatrix}$$
样本点$\mathbf{x}=[x_1,x_2]$绕点$\boldsymbol{p}=[p_1,p_2]$顺时针旋转$\theta$后,变为$\hat{\mathbf{x}}=[\hat{x_1},\hat{x_2}]$,其中:
$$\begin{pmatrix} \hat{x_1} \\ \hat{x_2} \end{pmatrix} = \mathbf{R} \begin{pmatrix} x_1-p_1 \\ x_2-p_2 \end{pmatrix} + \begin{pmatrix} p_1 \\ p_2 \end{pmatrix}$$
将原样本点矩阵$\mathbf{X}$中每个样本点对应的坐标向量$\mathbf{x}$代入上式,得到变换后的样本点矩阵$\hat{\mathbf{X}}$:
$$\hat{\mathbf{X}} = \mathbf{R}(\mathbf{X}-\boldsymbol{p}\boldsymbol{1}^T) + \boldsymbol{p}\boldsymbol{1}^T$$
其中$\boldsymbol{1}$为全1列向量。
我们知道,样本的协方差矩阵可以表示为$\mathbf{X}$的特征向量矩阵$\mathbf{V}$与特征值矩阵$\boldsymbol{\Lambda}$的乘积,即$\mathbf{X}\mathbf{X}^T=\mathbf{V}\boldsymbol{\Lambda}\mathbf{V}^T$。而变换后的样本的协方差矩阵$\hat{\mathbf{X}}\hat{\mathbf{X}}^T$,则可以表示为变换后的样本矩阵$\hat{\mathbf{X}}$的特征向量矩阵$\hat{\mathbf{V}}$与特征值矩阵$\hat{\boldsymbol{\Lambda}}$的乘积,即$\hat{\mathbf{X}}\hat{\mathbf{X}}^T=\hat{\mathbf{V}}\hat{\boldsymbol{\Lambda}}\hat{\mathbf{V}}^T$。
我们要求的是变换后的特征向量矩阵$\hat{\mathbf{V}}$,即:
$$\hat{\mathbf{V}} = [\hat{\mathbf{v_1}}, \hat{\mathbf{v_2}}]$$
其中$\hat{\mathbf{v_1}}$和$\hat{\mathbf{v_2}}$分别是$\hat{\mathbf{X}}\hat{\mathbf{X}}^T$的两个最大特征值对应的特征向量。
将$\hat{\mathbf{X}}\hat{\mathbf{X}}^T$带入上式:
$$\hat{\mathbf{V}} = [\hat{\mathbf{v_1}}, \hat{\mathbf{v_2}}] = \begin{bmatrix} \hat{\mathbf{v_1}} & \hat{\mathbf{v_2}} \end{bmatrix} = \begin{bmatrix} \hat{\mathbf{X}}\hat{\mathbf{X}}^T\hat{\mathbf{v_1}} & \hat{\mathbf{X}}\hat{\mathbf{X}}^T\hat{\mathbf{v_2}} \end{bmatrix} \hat{\boldsymbol{\Lambda}}^{-1/2}$$
其中$\hat{\boldsymbol{\Lambda}}^{-1/2}$为特征值矩阵$\hat{\boldsymbol{\Lambda}}$的逆平方根。
将$\hat{\mathbf{X}}$代入上式,得到变换后的特征向量矩阵$\hat{\mathbf{V}}$:
$$\hat{\mathbf{V}}= \begin{bmatrix} \cos \theta & -\sin \theta \\ \sin \theta & \cos \theta \end{bmatrix} \begin{bmatrix} \mathbf{V_1} & \mathbf{V_2} \end{bmatrix} \boldsymbol{\Lambda}^{-1/2}$$
其中$\mathbf{V_1}$和$\mathbf{V_2}$分别是协方差矩阵$\mathbf{X}\mathbf{X}^T$的两个最大特征值对应的特征向量。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)