机器学习 | 无监督聚类K-means和混合高斯模型

机器学习 | 无监督聚类K-means和混合高斯模型

1. 实验目的

实现一个K-means算法和混合高斯模型,并用EM算法估计模型中的参数。

2. 实验内容

用高斯分布产生 k k k个高斯分布的数据(不同均值和方差)(其中参数自己设定)。

  1. 用K-means聚类,测试效果;

  2. 用混合高斯模型和你实现的EM算法估计参数,看看每次迭代后似然值变化情况,考察EM算法是否可以获得正确的结果(与你设定的结果比较)。

  3. 可以UCI上找一个简单问题数据,用你实现的GMM进行聚类。

3. 实验环境

Windows11; Anaconda+python3.11; VS Code

4. 实验过程、结果及分析(包括代码截图、运行结果截图及必要的理论支撑等)

4.1 算法理论支撑

4.1.1 K-means聚类算法

K-means聚类算法的核心思想为假定聚类内部点之间的距离应该小于数据点与聚类外部的点之间的距离。即使得每个数据点和与它最近的中心之间距离的平方和最小

假设数据集为 X = { x 1 , … , x N } , x i ∈ R D X = \left\{ x_{1},\ldots,x_{N} \right\},x_{i} \in \mathbb{R}^{D} X={x1,,xN},xiRD,我们的目标是将数据集划分为 K K K个类别 Y Y Y。令 μ k ∈ R D , k = 1 , … , K \mu_{k} \in \mathbb{R}^{D},k = 1,\ldots,K μkRD,k=1,,K表示各类别的中心。聚类问题等价于求概率分布:

P ( Y | X ) = P ( X | Y ) ∙ P ( Y ) P ( X ) P\left( Y \middle| X \right) = \frac{P\left( X \middle| Y \right) \bullet P(Y)}{P(X)} P(YX)=P(X)P(XY)P(Y)

K-means聚类相当于假设 P ( X | Y ) P\left( X \middle| Y \right) P(XY)服从多元高斯分布(特征之间相互独立,协方差矩阵 Σ = λ I \Sigma\mathbf{=}\lambda\mathbf{I} Σ=λI),且 P ( Y ) P(Y) P(Y)为等概率均匀分布。而 P ( X ) P(X) P(X)为已知数据分布,从似然的角度看,极大化 P ( Y | X ) P\left( Y \middle| X \right) P(YX)即等价于极大化 P ( X | Y ) ∼ − 1 2 ( x − μ ) T Σ − 1 ( x − μ ) P\left( X \middle| Y \right)\sim - \frac{1}{2}(x - \mu)^{T}\Sigma^{- 1}(x - \mu) P(XY)21(xμ)TΣ1(xμ),即最小化各数据点到其类别的均值。

多元正态分布: N ( x ∣ μ , Σ ) = 1 ( 2 π ) D / 2 1 ∣ Σ ∣ 1 / 2 exp ⁡ { − 1 2 ( x − μ ) T Σ − 1 ( x − μ ) } 多元正态分布:\mathcal{N(}x|\mu,\Sigma) = \frac{1}{(2\pi)^{D/2}}\frac{1}{\mid \Sigma \mid^{1/2\ }}\exp\{ - \frac{1}{2}(x - \mu)^{T}\Sigma^{- 1}(x - \mu)\}\ 多元正态分布:N(xμ,Σ)=(2π)D/21Σ1/2 1exp{21(xμ)TΣ1(xμ)} 

引入二值指示变量 r n k ∈ { 0 , 1 } r_{nk} \in \{ 0,1\} rnk{0,1}表示数据点的分类情况,则可定义目标函数为

min ⁡ r , μ J = ∑ n = 1 N ∑ k = 1 K r n k ∥ x n − μ k ∥ 2 \min_{r,\mu}{J = \sum_{n = 1}^{N}{\sum_{k = 1}^{K}{r_{nk}\left\| x_{n} - \mu_{k} \right\|^{2}}}} r,μminJ=n=1Nk=1Krnkxnμk2

因此最优化过程可以划分为两步:

  1. 固定 μ \mu μ,优化 r n k r_{nk} rnk。由于 J J J关于 r n k r_{nk} rnk是线性的,因此可以对每个 n n n分别进行最小化,即对 r n k r_{nk} rnk根据与聚类中心的距离进行最优化:

r n k = { 1 , k = a r g m i n j ∥ x n − μ j ∥ 2 0 , 其他情况    r_{nk} = \left\{ \begin{aligned} 1 ,&\ \ \ \ \ \ \ \ \ k = argmin_{j}\left\| x_{n} - \mu_{j} \right\|^{2} \\ 0 ,&\ \ \ \ \ \ \ \ \ 其他情况\ \ \ \end{aligned} \right.\ rnk={1,0,         k=argminjxnμj2         其他情况    

  1. 固定 r n k r_{nk} rnk,优化 μ \mu μ。由于 J J J μ \mu μ的二次函数,对其求导等于零得

∂ J ∂ μ k = 2 ∑ n = 1 N r n k ( x n − μ k ) = 0 ⇒ μ k = ∑ n r n k x n ∑ n r n k \frac{\partial J}{\partial\mu_{k}} = 2\sum_{n = 1}^{N}{r_{nk}(x_{n} - \mu_{k}) = 0} \Rightarrow \mu_{k} = \frac{\sum_{n}^{}{r_{nk}x_{n}}}{\sum_{n}^{}r_{nk}} μkJ=2n=1Nrnk(xnμk)=0μk=nrnknrnkxn

μ k \mu_{k} μk等于类别k的所有数据点的均值。

4.1.2 混合高斯模型

任意连续概率密度都能用多个高斯分布的线性组合叠加的高斯混合概率分布 p ( x ) = ∑ k = 1 K π k N ( x ∣ μ k , Σ k ) p(x) = \sum_{k = 1}^{K}{\pi_{k}\mathcal{N}(x|\mu_{k},\Sigma_{k})} p(x)=k=1KπkN(xμk,Σk)来描述。引入 " 1 o f K " "1\ of\ K" "1 of K"编码的二值随机变量 z \mathcal{z} z,满足 z k ∈ { 0 , 1 } \mathcal{z}_{k} \in \{ 0,1\} zk{0,1} ∑ k = 1 K z k = 1 \sum_{k = 1}^{K}\mathcal{z}_{k} = 1 k=1Kzk=1

由右图模型定义联合概率分布 p ( x , z ) = p ( z ) ∙ p ( x ∣ z ) p\left( x,\mathcal{z} \right) = p\mathcal{(z) \bullet}p\left( x|\mathcal{z} \right) p(x,z)=p(z)p(xz) z \mathcal{z} z的边缘先验概率分布设为 p ( z k = 1 ) = π k ( 0 ≤ π k ≤ 1 且 ∑ k = 1 K π k = 1 ) p(\mathcal{z}_{k} = 1) = \pi_{k}(0 \leq \pi_{k} \leq 1且\sum_{k = 1}^{K}{\pi_{k} = 1}) p(zk=1)=πk(0πk1k=1Kπk=1),也可写作 p ( z ) = ∏ k = 1 K π k z k p(\mathcal{z}) = \prod_{k = 1}^{K}\pi_{k}^{\mathcal{z}_{k}} p(z)=k=1Kπkzk

那么, x x x的条件概率分布为:
p ( x ∣ z k = 1 ) = N ( x ∣ μ k , Σ k ) ⇔ p ( x ∣ z ) = ∏ k = 1 K N ( x ∣ μ k , Σ k ) z k p(x|\mathcal{z}_{k} = 1) = \mathcal{N(}x|\mu_{k},\Sigma_{k}) \Leftrightarrow \ p(x|\mathcal{z}) = \prod_{k = 1}^{K}{\mathcal{N(}x|\mu_{k},\Sigma_{k})^{\mathcal{z}_{k}}} p(xzk=1)=N(xμk,Σk) p(xz)=k=1KN(xμk,Σk)zk

于是可以给出 p ( x ) = ∑ z p ( z ) ∙ p ( x ∣ z ) = ∑ k = 1 K π k N ( x ∣ μ k , Σ k ) p(x) = \sum_{\mathcal{z}}^{}{p\mathcal{(z) \bullet}p\left( x\mathcal{|z} \right)} = \sum_{k = 1}^{K}{\pi_{k}\mathcal{N(}x|\mu_{k},\Sigma_{k})} p(x)=zp(z)p(xz)=k=1KπkN(xμk,Σk),同时, z \mathcal{z} z的条件后验概率 γ ( z k ) \gamma(\mathcal{z}_{k}) γ(zk)由贝叶斯定理得(已知为 x x x,类别为 z k \mathcal{z}_{k} zk的概率):

γ ( z k ) ≡ p ( z k = 1 | x ) = p ( z k = 1 ) p ( x | z k = 1 ) ∑ j = 1 K p ( z j = 1 ) p ( x ∣ z j = 1 ) = π k N ( x ∣ μ k , Σ k ) ∑ j = 1 K π j N ( x ∣ μ j , Σ k ) \begin{array}{r} \gamma(z_{k}) \equiv p\left( \mathcal{z}_{k} = 1 \middle| x \right) \end{array} = \frac{p\left( z_{k} = 1 \right)p\left( x \middle| z_{k} = 1 \right)}{\sum_{j = 1}^{K}{p\left( z_{j} = 1 \right)p\left( x\mid z_{j} = 1 \right)}}\ = \frac{\pi_{k}\mathcal{N}\left( x\mid\mu_{k},\Sigma_{k} \right)}{\sum_{j = 1}^{K}{\pi_{j}\mathcal{N}\left( x\mid\mu_{j},\Sigma_{k} \right)}} γ(zk)p(zk=1x)=j=1Kp(zj=1)p(xzj=1)p(zk=1)p(xzk=1) =j=1KπjN(xμj,Σk)πkN(xμk,Σk)

于是此聚类过程可以看做将概率分布 p ( x ) p(x) p(x)解耦成 K K K个高斯分布,对应 K K K个类别。对于数据集 X = { x 1 , … , x N } , x i ∈ R D , X ∈ R N × D X = \left\{ x_{1},\ldots,x_{N} \right\},x_{i} \in \mathbb{R}^{D},X \in \mathbb{R}^{N \times D} X={x1,,xN},xiRD,XRN×D,对应隐变量表示为 Z ∈ R N × K Z \in \mathbb{R}^{N \times K} ZRN×K

则对数似然函数为
ln ⁡ p ( X ∣ π , μ , Σ ) = ∑ n = 1 N ln ⁡ { ∑ k = 1 K π k N ( x n ∣ μ k , Σ k ) } \ln p(X \mid \pi,\mu,\Sigma) = \sum_{n = 1}^{N}{\ln\left\{ \sum_{k = 1}^{K}{\pi_{k}\mathcal{N}\left( x_{n}\mid\mu_{k},\Sigma_{k} \right)} \right\}} lnp(Xπ,μ,Σ)=n=1Nln{k=1KπkN(xnμk,Σk)}

将此似然函数关于 μ k \mu_{k} μk求导(假设 Σ k \Sigma_{k} Σk非奇异),令 N k = ∑ n = 1 N γ ( z n k ) , γ ( z n k ) ≡ p ( z k = 1 | x n ) N_{k} = \sum_{n = 1}^{N}{\gamma\left( z_{nk} \right),\ \gamma\left( z_{nk} \right) \equiv p\left( z_{k} = 1 \middle| x_{n} \right)} Nk=n=1Nγ(znk), γ(znk)p(zk=1xn)为能被分配到聚类 k k k的有效数量,可以得到:

∑ n = 1 K π k N ( x n ∣ μ k , Σ k ) ∑ j π j N ( x n ∣ μ j , Σ j ) ⏟ γ ( z n k ) Σ k − 1 ( x n − μ k ) = 0 ⇒ μ k = 1 N k ∑ n = 1 N γ ( z n k ) x n \sum_{n=1}^{K}\frac{\pi_{k}\mathcal{N}(x_{n}\mid\mu_{k},\Sigma_{k})}{\underbrace{\sum_{j}\pi_{j}\mathcal{N}(x_{n}\mid\mu_{j},\Sigma_{j})}_{\gamma({z}_{nk})}}\Sigma_{k}^{-1}(x_{n}-\mu_{k})=0\Rightarrow\mu_{k}=\frac{1}{N_{k}}\sum_{n=1}^{N}\gamma(z_{nk})x_{n} n=1Kγ(znk) jπjN(xnμj,Σj)πkN(xnμk,Σk)Σk1(xnμk)=0μk=Nk1n=1Nγ(znk)xn

由此式 μ k \mu_{k} μk可视为当前所有点数据为第 k k k类的概率加权平均。

同样地,将此函数关于 Σ k \Sigma_{k} Σk求导等于0可以得到:

Σ k = 1 N k ∑ n = 1 N γ ( z n k ) ( x n − μ k ) ( x − μ k ) T \Sigma_{k} = \frac{1}{N_{k}}\sum_{n = 1}^{N}{\gamma(z_{nk})(x_{n} - \mu_{k})(x - \mu_{k})^{T}} Σk=Nk1n=1Nγ(znk)(xnμk)(xμk)T

最后使用拉格朗日乘子法关于 π k \pi_{k} πk优化 ln ⁡ p ( X ∣ π , μ , Σ ) + λ ( ∑ k = 1 K π k − 1 ) \ln{p\left( X\mid\pi,\mu,\Sigma \right)} + \lambda(\sum_{k = 1}^{K}{\pi_{k} - 1}) lnp(Xπ,μ,Σ)+λ(k=1Kπk1) π k \pi_{k} πk需要满足和为1的条件)得到:

∑ n = 1 N N ( x n ∣ μ k , Σ k ) ∑ j π j N ( x n ∣ μ j , Σ j ) + λ = 0 ⇒ π k = N k N \sum_{n = 1}^{N}{\frac{\mathcal{N(}x_{n} \mid \mu_{k},\Sigma_{k})}{\sum_{j}^{}{\pi_{j}\mathcal{N(}x_{n} \mid \mu_{j},\Sigma_{j})}} + \lambda} = 0 \Rightarrow \pi_{k} = \frac{N_{k}}{N} n=1NjπjN(xnμj,Σj)N(xnμk,Σk)+λ=0πk=NNk

使用EM算法优化 ln ⁡ p ( X ∣ π , μ , Σ ) \ln p(X \mid \pi,\mu,\Sigma) lnp(Xπ,μ,Σ)即可总结为以下步骤:


ALGORITHM 1 EM for Gaussian Mixture Models

  1. input X ← X \leftarrow X数据集, K ← K \leftarrow K类别数目, i t e r ← iter \leftarrow iter迭代次数;
  2. 初始化均值 μ k \mu_{k} μk、协方差 Σ k \Sigma_{k} Σk和混合系数 π k \pi_{k} πk
  3. 计算对数似然 ln ⁡ p ( X ∣ π , μ , Σ ) ← ∑ n = 1 N ln ⁡ { ∑ k = 1 K π k N ( x n ∣ μ k , Σ k ) } \ln p(X \mid \pi,\mu,\Sigma) \leftarrow \sum_{n = 1}^{N}{\ln\left\{ \sum_{k = 1}^{K}{\pi_{k}\mathcal{N}\left( x_{n}\mid\mu_{k},\Sigma_{k} \right)} \right\}} lnp(Xπ,μ,Σ)n=1Nln{k=1KπkN(xnμk,Σk)}
  4. while i < i t e r i < iter i<iter do
  5. γ ( z n k ) ← π k N ( x n ∣ μ k , Σ k ) ∑ j = 1 K π j N ( x n ∣ μ j , Σ j ) \gamma(z_{nk}) \leftarrow \frac{\pi_{k}\mathcal{N}\left( x_{n}\mid\mu_{k},\Sigma_{k} \right)}{\sum_{j = 1}^{K}{\pi_{j}\mathcal{N}\left( x_{n}\mid\mu_{j},\Sigma_{j} \right)}} γ(znk)j=1KπjN(xnμj,Σj)πkN(xnμk,Σk); (E步)
  6. μ k n e w ← 1 N k ∑ n = 1 N γ ( z n k ) x n \mu_{k}^{new} \leftarrow \frac{1}{N_{k}}\sum_{n = 1}^{N}{\gamma(z_{nk})x_{n}} μknewNk1n=1Nγ(znk)xn
  7. Σ k n e w ← 1 N k ∑ n = 1 N γ ( z n k ) ( x n − μ k n e w ) ( x − μ k n e w ) T \Sigma_{k}^{new} \leftarrow \frac{1}{N_{k}}\sum_{n = 1}^{N}{\gamma(z_{nk})(x_{n} - \mu_{k}^{new})(x - \mu_{k}^{new})^{T}} ΣknewNk1n=1Nγ(znk)(xnμknew)(xμknew)T; (M步)
  8. π k n e w ← N k N \pi_{k}^{new} \leftarrow \frac{N_{k}}{N} πknewNNk
  9. end while
  10. return μ k , Σ k , π k \mu_{k},\Sigma_{k},\pi_{k} μk,Σk,πk //返回最优参数;

4.2 实验设计

4.2.1 随机数据生成

在这里插入图片描述
如上图代码,使用np.random.multivariate_normal方法按给定的协方差矩阵和均值按多元高斯分布初始化 k k k个类别的数据点。

4.2.2 K-means聚类

首先初始化 k k k个类的中心,这里采取的是从数据集中随机选取 k k k个样本作为初始的 k k k类中心。

在这里插入图片描述

而后是更新中心的算法,主要是分为两步:

  1. 通过计算每个样本到 k k k个中心的距离(欧式距离),然后选取最小的距离对应的那个聚类中心作为样本标签,将该样本划分到这个类中,

  2. 根据更新后的类别计算类内均值,作为新的中心。

在这里插入图片描述

重复上述过程,直至中心更新距离较之上次变化较小时退出迭代。

在这里插入图片描述

4.2.3 混合高斯模型GMM

首先初始化 k k k个类的均值、协方差和混合系数,可以有随机生成和采用K-means聚类的结果两种方式进行初始化。

在这里插入图片描述

根据对数似然计算公式 l n p ( X ∣ π , μ , Σ ) ← ∑ n = 1 N ln ⁡ { ∑ k = 1 K π k N ( x n ∣ μ k , Σ k ) } lnp(X \mid \pi,\mu,\Sigma) \leftarrow \sum_{n = 1}^{N}{\ln\left\{ \sum_{k = 1}^{K}{\pi_{k}\mathcal{N}\left( x_{n}\mid\mu_{k},\Sigma_{k} \right)} \right\}} lnp(Xπ,μ,Σ)n=1Nln{k=1KπkN(xnμk,Σk)}以及 关于 μ k \mu_{k} μk Σ k \Sigma_{k} Σk π k \pi_{k} πk的导数进行EM更新:

  1. E步:计算 γ ( z n k ) ← π k N ( x n ∣ μ k , Σ k ) ∑ j = 1 K π j N ( x n ∣ μ j , Σ j ) \gamma(z_{nk}) \leftarrow \frac{\pi_{k}\mathcal{N}\left( x_{n}\mid\mu_{k},\Sigma_{k} \right)}{\sum_{j = 1}^{K}{\pi_{j}\mathcal{N}\left( x_{n}\mid\mu_{j},\Sigma_{j} \right)}} γ(znk)j=1KπjN(xnμj,Σj)πkN(xnμk,Σk),即各数据点的类别概率;

  2. M步:计算新的均值 μ k n e w = 1 N k ∑ n = 1 N γ ( z n k ) x n , 混合系数 π k n e w ← N k N 以及 协方差 Σ k n e w = 1 N k ∑ n = 1 N γ ( z n k ) ( x n − μ k n e w ) ( x − μ k n e w ) T \mu_{k}^{new} = \frac{1}{N_{k}}\sum_{n = 1}^{N}{\gamma(z_{nk})x_{n}},\ 混合系数\pi_{k}^{new} \leftarrow \frac{N_{k}}{N}以及{协方差\Sigma}_{k}^{new} = \frac{1}{N_{k}}\sum_{n = 1}^{N}{\gamma(z_{nk})(x_{n} - \mu_{k}^{new})(x - \mu_{k}^{new})^{T}} μknew=Nk1n=1Nγ(znk)xn, 混合系数πknewNNk以及协方差Σknew=Nk1n=1Nγ(znk)(xnμknew)(xμknew)T

在这里插入图片描述

重复上述过程,直至似然函数较之上次变化较小时退出迭代。

在这里插入图片描述

4.3 实验结果及分析

4.3.1 自己生成数据结果比较

设置均值为 ( − 2 , − 2 ) , ( 2 , − 2 ) , ( 2 , 2 ) , ( − 2 , 2 ) ( - 2, - 2),(2, - 2),(2,2),( - 2,2) (2,2),(2,2),(2,2),(2,2),协方差矩阵均为 [ 1 0 0 1 ] \begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix} [1001],生成1000组数据,而后先后使用K-means和GMM进行聚类,聚类结果如下:

K-means正确率为96.7%,GMM正确率为96.9%(在使用K-means的结果作为GMM初始化的条件下)。

在这里插入图片描述

同时,经过反复实验发现,K-means和GMM的聚类结果严重依赖于初始化的结果,当初始化中心(或均值)选取区分度不高时,结果往往会比较差。

而GMM以K-means的结果初始化,能够一定程度上优化K-means的聚类结果(特别是当分类结果不好时)。
在这里插入图片描述

而特征之间不相互独立时,GMM聚类结果明显优于K-means。这是由于K-means假设数据呈球状分布,不能够区分开具有不相互独立的特征。

下图为均值为 ( − 2 , − 2 ) , ( 2 , − 2 ) , ( 2 , 2 ) , ( − 2 , 2 ) ( - 2, - 2),(2, - 2),(2,2),( - 2,2) (2,2),(2,2),(2,2),(2,2),协方差矩阵均为 [ 1 0.36 0.36 1 ] \begin{bmatrix} 1 & 0.36 \\ 0.36 & 1 \end{bmatrix} [10.360.361],生成1000组数据,先后使用K-means和GMM进行聚类的聚类结果如下:

此时K-means正确率为91.8%,GMM正确率为97.6%。

在这里插入图片描述

4.3.2 UCI-Iris数据集结果比较

而后使用Iris数据集进行聚类,K-means分类正确率为88%,GMM的分类正确率为96.7%,将聚类结果按第一个特征和第二个特征进行可视化结果如下:

在这里插入图片描述

5. 实验结论

K-means和GMM都是EM算法的体现。两者共同之处都有隐变量,遵循EM算法的E步和M步的迭代优化。

K-means其实就是一种特殊的高斯混合模型,提出了强假设,假设每一类在样本数据中出现的概率相等均为 1 k \frac{1}{k} k1,每个特征间相互独立,且满足变量间的协方差矩阵为单位对角阵。在此条件下,可以直接用欧氏距离作为K-means的协方差去衡量相似性。

而GMM用混合高斯模型来描述聚类结果,且假设多个高斯模型对总模型的贡献是有权重的,且样本属于某一类也是由概率的,从而相似度也由离散的 0 , 1 0,1 0,1变成了需要通过全概率公式计算的值,分类效果一般好于K-means。

实验发现,初值的选取对K-means和GMM的效果影响较大,初始化较差可能会导致陷入局部最优解而得不到较好的聚类结果。可以使用GMM对K-means的分类结果进行进一步优化。

6. 参考文献

[1]李航. 统计学习方法[M]. 清华大学出版社, 2012.

[2]周志华. 机器学习[M]. 清华大学出版社, 2016.

[3]Bishop C .Pattern Recognition and Machine Learning[M]. 2006.

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/238215.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

2023年全国职业院校技能大赛软件测试赛题—单元测试卷⑩

单元测试 一、任务要求 题目1&#xff1a;根据下列流程图编写程序实现相应处理&#xff0c;程序根据两个输入参数iRecordNum和IType计算x的值并返回。编写程序代码&#xff0c;使用JUnit框架编写测试类对编写的程序代码进行测试&#xff0c;测试类中设计最少的测试数据满足基路…

shp文件与数据库(创建shp文件)

前言 前面把shp文件中的内容读取到数据库&#xff0c;接下来就把数据库中的表变成shp文件。 正文 简单的创建一个shp文件 暂时不读取数据库的表&#xff0c;先随机创建一个shp文件。既然是随机的&#xff0c;这就需要使用到faker这个第三方库&#xff0c;代码如下。 impor…

【排序】快速排序(C语言实现)

文章目录 前言1. Hoare思想2. 挖坑法3. 前后指针法4. 三路划分5. 快速排序的一些小优化5.1 三数取中常规的三数取中伪随机的三数取中 5.2 小区间优化 6. 非递归版本的快排7. 快速排序的特性总结 前言 快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法&#xff0c;其…

格密码基础:SIS问题的困难性

目录 一. SIS问题的困难性 二. SIS问题归约的性质 2.1 2004年 [MR04] 2.2 2008年 【GPV08】 2.3 2013年【MP13】 三. 归约证明 3.1 核心理解 3.2 归约步骤 3.3 性质理解 一. SIS问题的困难性 推荐先阅读&#xff1a; 格密码基础&#xff1a;SIS问题的定义与理解-CSD…

【Linux】应用与驱动交互及应用间数据交换

一、应用程序与 Linux 驱动交互主要通过以下几种方式&#xff1a; 1. 系统调用接口&#xff08;System Calls&#xff09;: 应用程序可以通过系统调用&#xff0c;如 open(), read(), write(), ioctl(), 等来与设备驱动进行交互。这些调用最终会通过内核转发到相应的驱动函数…

感染嗜肺军团菌是什么感觉?

记录一下最近生病的一次经历吧&#xff0c;可能加我好友的朋友注意到了&#xff0c;前几天我发了个圈&#xff0c;有热心的朋友还专门私信了我说明了他自己的情况和治疗经验&#xff0c;感谢他们。 ​ 那么关于这次生病的经历&#xff0c;给大家分享一下。 首先&#xff0c;这次…

解锁 JavaScript 数组的强大功能:常用方法和属性详解(上)

&#x1f90d; 前端开发工程师&#xff08;主业&#xff09;、技术博主&#xff08;副业&#xff09;、已过CET6 &#x1f368; 阿珊和她的猫_CSDN个人主页 &#x1f560; 牛客高级专题作者、在牛客打造高质量专栏《前端面试必备》 &#x1f35a; 蓝桥云课签约作者、已在蓝桥云…

70.网游逆向分析与插件开发-角色数据的获取-自动化助手UI显示角色数据

内容参考于&#xff1a;易道云信息技术研究院VIP课 上一个内容&#xff1a;利用技能点属性分析角色数据基址-CSDN博客 码云地址&#xff08;ui显示角色数据 分支&#xff09;&#xff1a;https://gitee.com/dye_your_fingers/sro_-ex.git 码云版本号&#xff1a;367aa71f60b…

C++ 完成Client分页显示log

分页显示t_log 1、获取用户的输入 1.1、写一个Input成员函数&#xff0c;处理输入进来的语句 std::string XClient::Input() {//清空缓冲//cin.ignore(4096, \n);string input "";for (;;){char a getchar();if (a < 0 || a \n || a \r)break;cout <<…

蓝桥杯准备

书籍获取&#xff1a;Z-Library – 世界上最大的电子图书馆。自由访问知识和文化。 (zlibrary-east.se) 书评&#xff1a;(豆瓣) (douban.com) 一、观千曲而后晓声 别人常说蓝桥杯拿奖很简单&#xff0c;但是拿奖是一回事&#xff0c;拿什么奖又是一回事。况且&#xff0c;如果…

LeetCode讲解篇之78. 子集

文章目录 题目描述题解思路题解代码 题目描述 题解思路 初始化一个start变量记录当前从哪里开始遍历搜索nums 搜索过程的数字组合加入结果集 然后从start下标开始遍历nums&#xff0c;更新start&#xff0c;递归搜索 直到搜索完毕&#xff0c;返回结果集 题解代码 class …

wxWidgets实战:使用mpWindow绘制阻抗曲线

选择模型时&#xff0c;需要查看model的谐振频率&#xff0c;因此需要根据s2p文件绘制一张阻抗曲线。 如下图所示&#xff1a; mpWindow 左侧使用mpWindow&#xff0c;右侧使用什么&#xff1f; wxFreeChart https://forums.wxwidgets.org/viewtopic.php?t44928 https://…

npm run dev,vite 配置 ip 访问

启动项目通过本地 ip 的方式访问 方式一.通过修改 package.json "scripts": {"dev": "vite --host 0.0.0.0",}, 方式二.通过修改 vite.config.ts export default defineConfig({plugins: [vue(), vueJsx()],server: { // 配置 host 与 port 方…

AI大模型学习笔记二

文章目录 一、Prompt Engineering1&#xff09;环境准备 二、LangChain&#xff08;一个框架名字&#xff09;三、Fine-tuning&#xff08;微调&#xff09; 一、Prompt Engineering 1&#xff09;环境准备 ①安装OpenAI库 pip install --upgrade openai附加 安装来源 pyth…

DDNS-GO配置使用教程

环境&#xff1a;openwrt 下载地址&#xff1a;Releases jeessy2/ddns-go GitHub 下载 ssh至openwrt根目录&#xff0c;根据你的处理器选择要下载的版本&#xff0c;我是路由器&#xff0c;选择的是 ddns-go_5.7.1_linux_arm64.tar.gz wget github链接 安装 tar -zxvf…

基于STM32的CMT液晶屏控制器驱动程序设计与优化

本文以STM32微控制器为基础&#xff0c;设计并优化了一个用于控制CMT液晶屏的驱动程序。在设计过程中&#xff0c;我们首先介绍了液晶屏的基本工作原理&#xff0c;包括CMT液晶屏的结构和信号传输机制。然后&#xff0c;我们详细讨论了STM32微控制器的GPIO、SPI和DMA模块的特性…

Windows下面基于pgsql15的备份和恢复

一、基础备份 1.创建一个文件用来存储备份数据 2.备份指令 $CurrentDate Get-Date -Format "yyyy-MM-dd" $OutputDirectory "D:\PgsqData\pg_base\$CurrentDate" $Command "./pg_basebackup -h 127.0.0.1 -U postgres -Ft -Pv -Xf -z -Z5 -D $O…

分布形态的度量_峰度系数的探讨

集中趋势和离散程度是数据分布的两个重要特征,但要全面了解数据分布的特点&#xff0c;还应掌握数据分布的形态。 描述数据分布形态的度量有偏度系数和峰度系数, 其中偏度系数描述数据的对称性,峰度系数描述与正态分布的偏离程度。 峰度系数反映分布峰的尖峭程度的重要指标. 当…

书生·浦语大模型实战营笔记(四)

Finetune模型微调 直接使用现成的大语言模型&#xff0c;在某些场景下效果不好&#xff0c;需要根据具体场景进行微调 增量预训练&#xff1a;投喂垂类领域知识 陈述形式&#xff0c;无问答&#xff0c;即只有assistant 指令跟随&#xff1a;system-user-assistant XTuner …

【Git】本地仓库管理远程库(GitHub)——clone(下载)、commit(添加到本地仓库)、push(提交到远程仓库)、pull(拉取)操作

目录 使用远程仓库的目的将本地仓库同步到git远程仓库 1.克隆远程仓库(clone)2.新建一个文件3.将工作区的文件添加到暂存区4.将暂存区的文件添加到本地仓库(commit)5.提交(同步)到远程仓库(push)6.远程库拉取到本地库(pull)7.团队协作开发和跨团队协作开发(开源项目) 使用远程…