Posts

一、引子——双色球 我们知道，双色球每注投注号码由 6 个红色球号码和 1 个蓝色球号码组成。红色球号码从 1—33 中选择；蓝色球号码从 1—16 中选择。现在要求写出一个程序，模拟双色球的抽奖过程。 我们很容易想到使用某种方法生成一定范围内的随机数。蓝色球很好解决，但对于红色球，需要的是随机生成 6 个号码不同的数，可一定范围内的随机数总可能出现相同的情况，这样要如何解决？ 也就是说：对于 $1, 2, ..., m$ 这 m 个数字，随机抽取其中 $n(n \lt m)$ 个数。要采取怎样的算法？ 二、两种思路 其一 : 暴力方法 的确，随机数总有可能出现相同的情况，但是我们知道，同一个数多次出现的概率很小，以至于我们可以将其忽略。因此，我们只需要不断地取范围内的随机数，遇到重复的舍弃，直到取得的数字数目达到 n 即可。 void rand1(int m, int n, int rands[]) { char* hasSelect = calloc(m+1, sizeof(char)); for (int i = 0; i < n; ) { int r = randomInt(1, m); if (!hasSelect[r]) { rands[i++] = r; hasSelect[r] = 1; } } free(hasSelect); } 但这种算法是有缺陷的。问题在于，概率达到多小才算作可以忽略？ 考虑 $m=100, n=99$ 的情况。首先，取得第一个球，一定只需要选取 1 次；但是，我们再计算一下取得最后一个球的选取次数。为了取得第 99 个数，选中的概率为 $p_{99} = \frac{1}{50}$。我们设离散型随机变量 $X$ 表示为了取得第 99 个数所需的选取次数，则 $P\{X = k\} = (1-p)^{k-1}p$ 服从几何分布。因此 $E(X) = \frac{1}{p} = 50$。从期望上看，需要整整 50 次才能取到第 99 个数！！这中间的差距说明了，在 m 一定时，随着 n 的增大，随机的效率明显降低。...

一、信号简介 （1）信号含义 软中断信号(signal，又简称为信号)用来通知进程发生了异步事件。在软件层次上是对中断机制的一种模拟；在原理上，一个进程收到一个信号与处理器收到一个中断请求可以说是一样的。信号是进程间通信机制中唯一的异步通信机制，一个进程不必通过任何操作来等待信号的到达，事实上，进程也不知道信号到底什么时候到达。进程之间可以互相通过系统调用 kill 发送软中断信号。内核也可以因为内部事件而给进程发送信号，通知进程发生了某个事件。信号机制除了基本通知功能外，还可以传递附加信息。 （2）信号分类 可以使用kill -l命令查看当前系统支持的所有信号： 信号值小于 SIGRTMIN（<=34）的信号都是不可靠信号。它的主要问题是信号可能丢失。 信号值位于 SIGRTMIN 和 SIGRTMAX 之间的信号都是可靠信号，这些信号支持排队，不会丢失。 （3）信号的产生 信号可以由一下几种方式产生： 键盘事件：ctrl+c ctrl+\ ctrl+Z 等 非法内存：如果内存管理出错，系统就会发送一个信号进行处理 硬件检测到异常：如段错误，除 0，总线错误等 环境切换：比如说从用户态切换到其他态，状态的改变也会发送一个信号，这个信号会告知给系统 系统调用：如调用kill，raise，sigsend ，sigqueue函数等 （4）信号处理 进程可以通过三种方式响应信号： 接受默认处理 忽略信号（某些信号不能被忽略，如 SIGKILL 和 SIGSTOP） 捕捉信号并执行信号处理程序 二、信号操作 （1）信号发送 系统调用中用于发送信号的函数有 kill() raise() abort() 等。 kill() 函数 #include <signal.h> int kill(pid_t pid, int sig); //第一个参数pid代表接受信号的进程PID，第二个参数代表要发送的信号 参数 pid 会影响 kill()函数的作用，取值分为以下四种情况 若 pid>0，则发送信号 sig 给进程号为 pid 的进程。 若 pid=0，则发送信号 sig 给当前进程所属进程组的所有进程。 若 pid=-1，则发送信号 sig 给除 1 号进程和当前进程外的所有进程。 若 pid<-1，则发送信号 sig 给属于进程组 pid 的所有进程。 segqueue() 函数 sigqueue()函数支持发送信号的同时传递参数，需要配合 sigaction() 函数一起使用。...

一、引言 进程是操作系统中的重要概念，是对执行一定功能的程序的过程的抽象。这篇文章将简要说明进程的相关知识。介绍进程管理相关的函数，并通过这些函数实现重定向和进程间通信等功能。 二、进程简介 1. 程序执行原理 程序在编译后以二进制方式存在于外存上，执行的时候被操作系统载入内存。以 Linux 系统上的 C 语言编译出来的程序为例，载入的过程简单来说就是把编译完成的 ELF （Executable and Linkable Format 可执行与可链接格式） 文件的几个段的内容读取到内存指定位置，然后初始化寄存器的内容，将指令寄存器（比如cs:ip）指向程序入口，再初始化一些进程相关内容就完成了。 在某一次时钟中断发生的时候，进程主动陷入内核态，进行进程切换的系统调用，CPU 将切换到另一个进程工作。总而言之，整个计算机从开机到关机，就是一个不断创建、切换、终止进程的过程。 2. 进程概念的用途 早期的计算机一次只能执行一个程序，这种程序完全控制系统，并且访问所有系统资源。相比之下，现代计算机系统允许“同时”加载多个应用程序到内存，以便并发（轮流）执行。 这种改进要求对各种程序提供更严的控制和更好的划分。这些需求导致了进程概念的诞生。 进程是现代分时操作系统的工作单元，是操作系统向运行中的程序进行资源分配的单位。进程包括程序代码(文本)，当前活动(程序计数器，寄存器的值)，堆栈，数据端，堆。 需要注意区分程序和进程的概念。程序是被动实体，如存储在磁盘上的可执行文件；进程是活动实体，具有一个程序计数器用于表示下个执行命令和一组相关资源。 当一个可执行文件被加载到内存时，这个程序就成为进程。 两个进程可以与同一程序相关联，但当作两个单独的执行序列，虽然文本段相同，但是数据、堆、堆栈不同。 三. 进程管理 接下来介绍使用操作系统 API 进行进程管理的方法。 1. 使用 fork 创建新进程 #include <unistd.h> pid_t fork(); fork 无参数，返回一个用于指示子进程的 pid（对于子进程，返回值为 0）。其作用是创建一个子进程，共享父进程所有内容，并且这个子进程会接着 fork 下面的代码继续执行。fork有以下两种用法： 一个父进程希望复制自己，使父进程和子进程同时执行不同的代码段。 一个进程要执行一个不同的程序。在这种情况下，子进程从fork返回后立即调用exec。 如果在调用 fork 后子进程先于父进程结束，则子进程就会变为僵尸进程，虽然结束，却依然占据了进程表中的一个位置。为了避免这种情况，需要调用 wait 或 waitpid 来使父进程等待子进程结束，并释放子进程的信息。 #include <sys/wait.h> pid_t wait(int *status); pid_t waitpid(pid_t pid,int *status,int options); 下面将以一个程序作为例子。该程序由父进程创建两个子进程，父进程打印字符 B ，两个子进程分别打印 A 和 C ，并且要使最终的输出为 ABC 。...

一、引言 另一种常用的非监督学习应用场景是异常检测。异常检测会学习正常情况下的样本数据，并在应用时检测出现的异常数据。 异常检测会运用正态分布等知识，这里先介绍一下正态分布（同时也作为自己对概率统计中的相关知识的一点总结）。 二、正态分布 对于连续型随机变量 X，若其概率密度函数为如下的形式 $$ f(x) = \frac{1}{\sqrt{2\pi}\sigma} e^{-\frac{(x-\mu)^2}{2\sigma^2}} $$ 其中 $\sigma > 0, \mu \in R$ 则称 X 服从正态分布（Normal distribution），记 $X \sim N(\mu, \sigma^2)$。 取 $\mu = 0, \sigma = 1$，此时 $X \sim N(0, 1)$，称 X 服从标准正态分布。记标准正态分布的概率密度为 $\phi(x)$，分布函数为 $\Phi(x)$，则任意的服从正态分布的随机变量 X，其分布函数为 $F(x) = \Phi(\frac{x - \mu}{\sigma})$。 标准正态分布的分布函数数值有表可查。 任意正态分布的分布函数等式中的 $\frac{x - \mu}{\sigma}$ 是不是有点熟悉？在特征放缩那一篇文章中的 Z score 标准化部分有出现。 Z score 标准化似乎就是假定特征数值服从正态分布，并将其转化为标准正态分布形式。 三、算法 我们假设不同训练样本的每一个特征服从服从正态分布。那么，对每一个特征 x_j，求其期望 $\mu_j$ 和方差 $\sigma_j^2$，则该特征对应的概率密度为 $p(x_j, \mu_j, \sigma_j^2) = \Phi(\frac{x - \mu}{\sigma})$。我们假设各个特征之间相互独立，则对于任意的 $\vec{x}=(x_1, x_2, ....

一、引言——非监督学习 之前介绍的算法都是监督学习算法。需要样本中包含各特征信息以及结果标签来让模型学习特征与结果的对应关系。但是，如果我们此时只有特征信息，而不指明具体结果是什么，又需要什么样的算法和模型才能得知哪些样本会有同样的标签呢？ 这种从原始数据中探索样本间联系的学习方式称为非监督学习。其中非监督意指，模型不需要人来告知他 “什么是什么”，而能自己从数据中挖掘信息。 二、聚类算法 非监督学习中的一种算法为聚类算法。它的目的是将数据按照一定特征进行分组。 最广泛使用的聚类算法称为 K 均值（K-means）算法。 三、K均值算法 假设我们要将所有数据分成 k 组，并称在一组中的数据为一个簇。那么对于每一簇内的数据，我们就希望他们之间的距离相对较小，而他们与其他簇中的数据的距离较大。直观上讲，就是同簇的数据点形成一个较为密集的区域，不同簇之间则有较大的空隙（这或许就是聚类的含义）。 我们用簇内的数据的平均作为对簇的描述，相当于指示了簇在特征空间中的位置。这一平均后得到的点称为簇质心。假设我们现在已经得到了一种分组，那么这种分组现在是否有优化的可能呢？要回答这个问题就要查看每一数据点相对于各个簇质心的距离，如果某个数据点相对于其他簇质心的距离要小于其相对于当前所在的簇的质心的距离，就说明该点被错分类了。我们就要将其重新划分为与其距离最小的簇质心所对应的簇内。 但是，这种重新划分又会使得簇质心的位置发生变化，这又导致一些之前是距离该质心位置最小的数据点不再是距离该质心位置最小，又需要再次调整分类。就这样，不断地调整，直到最终所有的点距离当前所在簇的质心距离都为最小，就代表了分类完成。 经过了上面的分析，我们现在给出 K 均值算法的流程： 初始化 k 个簇质心位置，分别对应 k 个簇 对每个数据点，选择与其距离最近的簇质心对应的簇作为其当前分组 对所有同一簇的数据点，计算其平均值，作为新的当前簇的簇质心 不断重复 2、3，直到所有簇的簇质心不再发生变化，即代表分组完成 可以看出，该算法具有很简单的流程，且没有复杂的数据结构。 算法中还需要明确两个点： 如何初始化簇质心： 一般是随机选取点作为质心，或者在样本数据中随机选取 k 个点 怎么计算数据点到簇质心的距离 该算法使用二范数，或者说欧氏距离作为距离 四、K均值算法的损失函数 这里我们要更理论化地解释为什么这样的算法可以将数据成功分类 假设总共有 m 个样本数据 $x^{(1)}, x^{(2)}, ..., x^{(m)}$，需要将其分为 k 类（k < m）。我们用 $c^{(i)}$ 表示第 i 个数据点选择第几个簇。用 $\mu_{j}$ 表示第 j 个簇的簇质心。 要衡量当前分组，按照之前所说的 “同簇的数据点形成一个较为密集的区域，不同簇之间则有较大的空隙”，很容易采用簇中数据点相对于质心的距离的平均作为标准。这里直接给出损失函数 $$ J(c^{(1)}, ..., c^{(m)}, \mu_{1}, ..., \mu_{k}) = \frac{1}{m}\sum_{i=1}^m \Vert x^{(i)} - \mu_{c^{(i)}} \Vert^2 $$ 该损失函数在这里又叫做失真函数。很明显，失真函数是所有数据点到其对应的簇质心的距离的平方的平均。距离取平方是因为这样并不影响损失函数的衡量效果，而又方便计算。...

一、引言 决策树是另一种十分有效的机器学习模型。该模型采取树状分支结构，能够很快地进行模型训练，并具有较高的准确率。 本文将以决策树的最简单形式开始，即特征只包括真值特征，或只有两种选择的特征，且结果也只有两种的情况。 二、决策树基本模型 决策树是一个二叉树，树的非叶节点存储需要区分的特征，叶节点存储预测的分类。对于每一个要进行预测的数据，从根节点开始，根据当前节点所对应的特征，选择移动到左子节点或右子节点。直到最终移动到一个叶节点，返回预测结果。 可以认为决策树的预测过程就是通过不同特征将当前数据分组归类的过程。决策树的构建过程，或者更一般地说，该模型的学习过程，也就是不断确定如何分类的过程。 三、决策树的构建 总体上讲，对于我们已有的样本数据，构建决策树的过程时这样的。 选择一个特征，将该特征作为当前节点的特征 根据该特征将样本数据分为两组 对于两组被分类的数据，分别递归执行如上操作，从而确定当前节点的左右子节点。直到当前数据已经全部是要预测的某个结果了、或者所有特征都被用完、又或者递归进行到了最大层数。 可以看到，决策树构建的过程中大部分过程都可以用简单的程序逻辑实现。现在唯一要解决的就是在每个节点时，如何选择一个特征了。 当然，对于神经网络来说也是这样的。唯一要解决的是如何选择权重。 四、特征的选择 我们要衡量选择不同特征对训练样本的区分效果。这点类似于损失函数。 我们区分的目标是使得所有当前组的样本属于同一个预测结果。那么我们就要找到一种衡量纯度的指标，数据越纯指标越小，数据越不纯指标越大。这种指标就是熵。假设某一种类在数据总体中的占比为 $p_1$，则熵 $H(p_1)$ 为 $$ p_0 = 1 - p_1 \\ H(p_1) = -p_1log_2(p_1) - p_0 log_2(p_0) $$ 即 $$ H(p_1) = -p_1log_2(p_1) - (1-p_1) log_2(1 - p_1) $$ 当 $p_1 = 0$ 或 $p_1 = 1$ 时 $$ H(0) = H(0+0) = 0 \\ H(1) = H(1-0) = 0 $$ 可以看出熵与交叉熵损失函数之间有联系。确实，交叉熵损失函数也是用来衡量预测的纯度的。对于一个预测，我们总希望它接近 0 或者 1，也就是纯度最大的比例。...