利用Latex在线工具Overleaf编写分区匹配（PM）、K-Means聚类、MeanShift聚类算法伪代码（附源码）

如题，本文只免费开源研究生课题中所遇到的部分算法伪代码，使用Latex在线工具Overleaf，具体编程教学可参考上篇文章，本文不再过多赘述。使用Overleaf在毕业论文中插入算法伪代码https://blog.csdn.net/jucksu/article/details/123489825?spm=1001.2014.3001.5501

1. K-Means聚类算法

• 事先确定K值，K就是类别数目
• 在给定的数据样本点中随机选取K个点作为初始质心
• 计算所有的点到初始质心的距离，离哪个质心近，就判为该质心的集合
• 重新计算每簇的质心，开始新一轮迭代
• 若前后两次质心之间的距离小于某个阈值或者达到最大迭代次数，停止循环
• 否则，重复以上过程，最终输出分簇类质心

算法伪代码效果：

 附Overleaf编程源码：

%在菜单中，编译器选择XeLaTex\documentclass[11pt]{ctexart}\usepackage[top=2cm, bottom=2cm, left=2.5cm, right=2.5cm]{geometry} %定义页边距\usepackage{algorithm}\usepackage{algorithmicx}\usepackage{algpseudocode}\usepackage{amsmath} %数学公式\usepackage[UTF8]{ctex} %输出中文\floatname{algorithm}{Algorithm} %算法\renewcommand{\algorithmicrequire}{\textbf{Input:}} %输入\renewcommand{\algorithmicensure}{\textbf{Output:}} %输出\begin{document}\renewcommand{\thealgorithm}{1:} %这里用来定义算法1，算法2等    \begin{algorithm} \caption{基于K-Means聚类的盲均衡算法} %标题 \begin{algorithmic}[1] %每行显示行号，1表示每1行进行显示     \Require 输入样本集$D$ = \{$x_1,x_2,...,x_N$\},分簇数$K=2$,最大迭代次数为$M$,从分簇样本中随机选取两点\{$u_1$,$u_2$\}作为初始质心     \Ensure 输出样本分簇质心\{$C_1$,$C_2$\}     \For{$m = 1 \to M$} \quad\quad\quad//$m$表示迭代次数  \State $C_1 \Leftarrow \emptyset, C_2 \Leftarrow \emptyset$ \quad\quad\quad//初始化各簇  \For{$i = 1,2,...,N$}     \quad\quad\quad//$i$表示样本集编号      \State $d_{i1} \Leftarrow {\Vert x_i-u_1 \Vert}^2$, $d_{i2} \Leftarrow {\Vert x_i-u_2 \Vert}^2$ \quad\quad\quad//计算$x_i$到两质心的欧式距离      \If {$d_{i1} \leq d_{i2}$}      \State $C_1 \Leftarrow C_1 \cup \{x_i\}$ \quad\quad\quad//将$x_i$划分到相应的簇      \Else      \State $C_2 \Leftarrow C_2 \cup \{x_i\}$ %有时候需要用\来转译  \EndIf  \EndFor  \State $\tilde{u_1} \Leftarrow \frac{1}{\vert C_1 \vert}\sum\limits_{x \in C_1} x$, $\tilde{u_2} \Leftarrow \frac{1}{\vert C_2 \vert}\sum\limits_{x \in C_2} x$ \quad\quad\quad//重新计算各簇质心  \If{\{$(\tilde{u_1} == u_1) \textbf{\&\&} (\tilde{u_2} == u_2)$\}} \quad\quad\quad//各簇质心未改变，跳出循环      \State \textbf{break} from line 3 %\textbf为加粗      \Else      \State $u_1 \Leftarrow \tilde{u_1}, u_2 \Leftarrow \tilde{u_2}$ \quad\quad\quad//更新各簇质心  \EndIf     \EndFor     \State \Return $C_1, C_2$ \quad\quad\quad//输出结果 \end{algorithmic}    \end{algorithm}\end{document}

2. 分区匹配（PM）算法

• 假设4条初始的簇分界线：x=0, y=0, y=x, y=-x
• 这四条分界线可以通过对数据样本集实部、虚部的正负相对大小来实现初始分类
• 4种分类中至少存在一个最接近正确的分类方法，通过分类重心矢量模值的大小区分
• 挑选出最佳分类后，利用其进行均衡

算法伪代码效果图：

附编程源码 ：

%在菜单中，编译器选择XeLaTex\documentclass[11pt]{ctexart}\usepackage[top=2cm, bottom=2cm, left=2.5cm, right=2.5cm]{geometry} %定义页边距\usepackage{algorithm}\usepackage{algorithmicx}\usepackage{algpseudocode}\usepackage{amsmath} %数学公式\usepackage[UTF8]{ctex} %输出中文\floatname{algorithm}{Algorithm} %算法\renewcommand{\algorithmicrequire}{\textbf{Input:}} %输入\renewcommand{\algorithmicensure}{\textbf{Output:}} %输出\begin{document}\renewcommand{\thealgorithm}{2:} %这里用来定义算法1，算法2等    \begin{algorithm} \caption{基于PM的盲均衡算法} %标题 \begin{algorithmic}[1] %每行显示行号，1表示每1行进行显示     \Require 输入旋转的BPSK符号样本集$D$ = \{$x_1,x_2,...,x_N$\},序列长度$Length$     \Ensure 输出BPSK符号旋转量的估计值$\rho_s$     \For{$j = 1 \to Length$} \quad\quad\quad//初始的簇分界线:$x=0,y=0,y=x,y=-x$ %\quad表示空格  \State $\rho_x = \sum\limits_{j \in \{ \Re(s_j)>0 \}} s_j - \sum\limits_{j \in \{ \Re(s_j)0 \}} s_j - \sum\limits_{j \in \{ \Im(s_j) \Im(s_j)\}} s_j - \sum\limits_{j \in \{\Re(s_j)  -\Im(s_j)\}} s_j - \sum\limits_{j \in \{\Re(s_j) < - \Im(s_j)\}} s_j$     \EndFor     \State $\rho_s = \textbf{argmax}_{\rho \in \{\rho_x,\rho_y,\rho_{y=x},\rho_{y=-x}\}} \vert \rho \vert$ \quad\quad\quad//挑选最佳分类 % \textbf加粗字体      \State $\theta = \textbf{arctan}{\frac{\Re{\rho_s}}{\Im{\rho_s}}}$ \quad\quad\quad//$\theta$为旋转角度     \State \Return $\theta$ \quad\quad\quad//输出结果 \end{algorithmic}    \end{algorithm}\end{document}

3. MeanShift聚类算法

• 在数据样本集中随机选取一个点作为初始中心点，即圆心
• 找出以center为圆心，r为半径的区域中所有的点，记录其区域内数据点的个数
• 计算均值漂移向量shift
• 根据向量和进行更新圆心位置
• 重复以上过程，直到均值漂移向量很小或者前后两次的圆心位置重合
• 如果收敛时当前簇的center与其他已经存在的簇的center距离小于某个阈值，则将其合并，否则产生新的类别
• 当所有的数据点都被标记访问后，取每个点被访问频率最大的类作为当前点的所属类
• （可加入核函数）

算法伪代码效果图：

 附编程源码：

%在菜单中，编译器选择XeLaTex\documentclass[11pt]{ctexart}\usepackage[top=2cm, bottom=2cm, left=2.5cm, right=2.5cm]{geometry} %定义页边距\usepackage{algorithm}\usepackage{algorithmicx}\usepackage{algpseudocode}\usepackage{amsmath} %数学公式\usepackage[UTF8]{ctex} %输出中文\floatname{algorithm}{Algorithm} %算法\renewcommand{\algorithmicrequire}{\textbf{Input:}} %输入\renewcommand{\algorithmicensure}{\textbf{Output:}} %输出\begin{document}\renewcommand{\thealgorithm}{3:} %这里用来定义算法1，算法2等    \begin{algorithm} \caption{基于MeanShift聚类的盲均衡算法} %标题 \begin{algorithmic}[1] %每行显示行号，1表示每1行进行显示     \Require 输入样本数据集$D$ = \{$x_1,x_2,...,x_N$\},半径$r$,阈值$\xi$,阈值$\delta$,从分簇样本中随机选取一点\{$x$\}作为初始中心     \Ensure 输出样本分簇质心\{$M_1$,$M_2$\}     \For{$i = 1 \to N$} \quad\quad\quad//$N$表示样本集个数，保证其每个点都被标记访问  \While{$True$}      \State $S_k(x) = \{y:(x-x_i)_T (x-x_i) < r^2\}$  \quad//$S_k$表示到x的距离小于半径$r$的数据点集合      \State $M \Leftarrow M_{x_i \in S_k} \cup \{x\}$ \quad\quad\quad//将其划分为集合$M$      \State $f_x = \sum \vert S_k \vert$ \quad\quad\quad//以$x$为中心划分的范围内散点的频数      \State $M_{shift} = \frac{1}{K} \sum\limits_{x_i \in S_k} (x_i - x)$ \quad\quad\quad//MeanShift向量基本形式      \State $x = x + M_{shift}$ \quad\quad\quad//通过漂移向量更新圆心      \If{$\vert M_{{shift}_{new}} - M_{{shift}_{old}} \vert < \xi$} \quad\quad\quad//收敛   \State \textbf{break} from line 2 \quad\quad\quad//前后两次质心相同时停止循环      \EndIf  \EndWhile  \For{$k = 1 \to \vert M \vert$} \quad\quad\quad//$k$为当前分簇聚类种数      \If{$\vert x_{k+1} - x_k \vert < \delta$}   \State $M_k \Leftarrow M_k \cup M_{k+1}$ \quad\quad\quad//合并类别   \State $f_k = f_k + f_{k+1}$ \quad\quad\quad//合并频数      \Else   \State $k++$ \quad\quad\quad//将其作为新的一类      \EndIf  \EndFor     \EndFor     \For{$i = 1 \to N$}  \State $M \Leftarrow M_k (x_i \in { \textbf{Max} (f_k)})$      \quad\quad\quad//根据每个类对每个点的访问频率，取访问频率最大的那个类，作为当前点集的所属类     \EndFor     \State \Return $M_1, M_2$ \quad\quad\quad//输出分簇结果 \end{algorithmic}    \end{algorithm}\end{document}

注：以上算法原理和步骤，在学习参考诸多论文的基础上，包含个人理解，难免有问题和错误，恳请大家指正，欢迎交流！