Renns' Blog

聚类(clustering)是一种无监督学习技术 聚类算法试图将数据集中的样本划分为若干个不相交的子集，每个子集称为一个簇(cluster)，每个簇中的样本间包含潜在的联系，也即可能属于同一类 形式化的说，给定样本集$D\in R^{m\times n}$，其中每个样本$x$是一个$m$维向量，聚类算法将$D$划分为$k$个不相交的簇$C1,C_2,…,C_k$，即$C_i\cap{i\neq j}Cj=\emptyset,\ D=\cup{i=1}^kC_i$ 显然聚类的目标是使得簇内相似度高，簇间相似度低 如图所示，聚类的算法很多，下面挑选几个比较基础的进行说明 K-MeansK-Means属于基于划分的聚类，其基本思想为把相似的点划分为同一类，不相似的点划分到不同类 K-Means算法的目标是最小化如下平方误差 E=\sum_{i=1}^k\sum_{x\in C_i}\|x-\mu_i\|_2^2其中 $\mui=\frac{1}{|C_i|}\sum{x\in C_i}x$ 为簇$C_i$的均值向量 该误差表示簇内样本围绕均值向量的紧密程度，$E$越小簇内样本相似度越高 ...

决策树分类基本原理对于分类任务，使用树形结构进行判断是一件很自然的事情 例如我们要判断一个目标是苹果、梨还是香蕉，我们会依次判断其形状、颜色、……每一次判断都会把目标划分到原类别集合的一个子集内，如果我们把这个过程画出来，就会形成一棵树，这就是决策树分类的原理 形式化的说，决策树包含一个根节点、若干个内部节点和若干个叶节点每个内部节点表示一次划分决策，每个叶节点表示一个决策（分类）结果，从根出发到达某个叶子的路径就代表完成了一个完整的分类过程 假设样本属性均为离散型，如下图所示为构建决策树的伪码其中如何选择划分标准使得决策树时空消耗更小、泛化能力更强，就是不同决策树算法所探讨的问题 ID3ID3算法使用信息增益（information gain）作为划分标准 假设当前样本集合$D$中属于第$k$类样本的集合为$D_k$，则$D$的信息熵，也即不确定度为 H(D)=-\sum_{k=1}^{C}\frac{|D_k|}{|D|}\log_2 \frac{|D_k|}{|D|}若使用某属性$A$作为划分标准且$A$有$V$个可能取值，则该次划分将产生$V$个分支 记第$i$个分支包含 ...

参数估计简介在 贝叶斯分类器 中我们提到，对于类条件概率$P(x|c)$，可以通过假设其服从某一分布来计算该概率 例如，假设$P(x|c)\sim N(\mu_c,\Sigma_c)$，则只要知道了参数$\mu_c,\Sigma_c$的值，$P(x|c)$的值也就确定了 因此，参数估计的目标就是根据训练样本来尽可能正确的估计已假设的概率分布的参数 $\theta$ 注意参数估计是先假设概率密度函数，再根据样本估计参数，与之相对的概念称为非参数估计，非参数估计不对分布函数做任何假设，而是直接根据样本估计各区域概率密度，对非参数估计此处不展开说明 极大似然估计和贝叶斯估计是参数估计中两种最常用的方法，他们分别来自频率主义学派和贝叶斯学派 频率主义学派认为待估计的参数虽然未知，但却是客观存在的固定值，因此最佳估计值就是使得产生已有样本（训练集）的概率最大的那个值 而贝叶斯学派则认为待估计的参数是符合某种先验概率分布的随机变量，他们先假设参数服从一个已知的先验分布，再根据已有样本计算参数的后验分布来修正假设 极大似然估计原理假设已知数据集D，其中每一个样本$x$都是根据已知形式的概率密度函数$ ...

非参数估计基本原理在极大似然估计与贝叶斯估计 中我们提到了参数估计与非参数估计的区别 参数估计先假设概率密度函数的形式，再根据样本估计该概率密度函数的参数 非参数估计不对分布函数做具体的假设，而是直接根据样本估计各区域的概率密度 非参数估计的思想与直方图类似，即将样本空间划分为若干相同大小的区间，统计每个区间包含的的样本数并用柱状图画出，得到对真实概率密度的近似 设$R$是样本空间中的一个小区域，$p(x)$为分布的概率密度函数，则样本$x$落在$R$中的概率为 P=\int_{R}p(x) \text{d}x假设$n$个样本独立同分布地根据$p(x)$抽取，显然落入区域$R$的样本数$k$服从二项分布，即有$E(k)=nP$ 因此$P=\frac{k}{n}$是对$P$的一个很好的估计 当$R$足够小时，我们可以认为这个区间内$p(x)$没有变化，即有 P = \int_{R}p(x) \text{d}x = p(x)V其中$V$是区域$R$的体积，综上可得$p(x)$在区域$R$的估计 p(x)\approx \frac{k/n}{V}当$n$固定时，区域$R$的选定和 ...

线性判别分析 (Linear Discriminant Analysis, LDA) 是一种常用的有监督降维方法 LDA最早是由Fisher提出的用于解决二分类问题的方法，因此也称为FDA，下面我们从二分类开始讲解LDA LDA二分类对于二分类问题，假设给定样本集$D\in R^{2\times m}$，记$D_1,D_2$分别是属于两个类别的样本集合 LDA的目标是将样本投影到一个直线上，使同类样本间尽可能近，异类样本间尽可能远 为了量化评价这个目标，可以定义Fisher判别准则 J(w)=\frac{\|\widetilde{\mu_1}-\widetilde{\mu_2}\|^2_2}{S_1+S_2}其中$\widetilde{\mu_1},\widetilde{\mu_2}$分别为两类样本投影后的均值向量，$S_1，S_2$分别为两类样本投影后各自的方差对于二维向量投影到直线上的情况，$\widetilde{\mu_1},\widetilde{\mu_2}$为实数 显然$J(w)$越大，则投影点的类别可分性越强 记$\mu_1,\mu_2$分别为两类样本投影前的均值向量，投 ...

主成分分析 (Principal Component Analysis, PCA) 是最常用的一种降维方法 PCA寻找一个低维的超平面， 并将所有样本投影到这个超平面上，这个超平面满足 最近重构性：所有样本向量到这个超平面距离都足够近 最大可分性：样本向量在这个超平面上的投影尽可能分开，即投影后方差尽可能大 具体来说，PCA先寻找一组新的正交基，对所有样本进行坐标变换，再删去一部分坐标实现降维 实际上，基于最近重构性和基于最大可分性的推导得到的结果是等价的 PCA推导假设数据集$D\in R^{d\times m}$，即每个样本$x$是一个$d$维向量，共有$m$个样本向量 首先对数据集进行中心化，即$x\leftarrow x - \frac{1}{m}\sum_{i=1}^m x_i$ 当前样本空间的基为自然基，设新的基为规范正交基${w_1,w_2,…,w_d}$ 显然从自然基到该正交基的过度矩阵就是$W=(w_1,w_2,…,w_d)$，其中$w_1,w_2,…,w_d$在$W$中做列向量 设向量$xi=(x{i1};x{i2};…;x{id})$在新的基下坐标为$zi=( ...

贝叶斯决策论贝叶斯决策论（Bayesian decision theory）是基于概率进行分类决策的基本方法 在所有相关概率均已知的理想情况下，贝叶斯决策论假设：决策问题可以用概率来形式化描述 考虑如下多分类问题，假设有$N$个类别$c1,c_2,…,c_N$令$\lambda{ij}$表示将一个真实类别为$c_j$的样本分类为$c_i$所产生的损失那么我们可以基于后验概率$P(c_i|x)$来定义将样本$x$分类为$c_i$产生的期望损失 R(c_i|x)=\sum_{j=1}^N\lambda_{ij}P(c_j|x)其中$R(c_i|x)$称为条件风险 我们的目标是寻找一个分类器$h: X\rightarrow Y$以最小化总体风险 R(h)=E_x[R(h(x)|x)]显然，若分类器$h$能最小化条件风险$R(h(x)|x)$，则总体风险也将最小化 由此即产生了如下贝叶斯判定准则：为最小化总体风险，只需选择使得条件风险$R(c|x)$最小化的类别标签$c$ h^*(x)=\text{argmin}_{c\in Y}R(c|x)此时$h^$称为贝叶斯最优分类器，其对应的最小 ...

分组加密简介分组密码是指将明文消息编码后的数字序列按顺序分成多个长为$n$的分组$P=(p0,p_1,…,p{n-1})$，各分组在密钥$K=(k0,k_1,…,k_t)$的控制下分别变换成等长的密文分组$C=(c_0,c_1,…,c{n-1})$ 理想的分组密码可以定义明密文分组之间的任意可逆变换 若明密文分组为$n$位二进制序列，那么理想的分组密码可以定义$2^n!$种不同变换，当$n$足够大时，密文中明文语言的统计特征将被完全掩盖 然而理想的分组密码显然无法实现，仅仅$n=64$时，要将变换的映射关系存储下来就需要$64\times 2^{64}\approx 10^{21}bit$ 因此密码学家Feistel建议使用乘积密码的概念来近似理想分组密码 扩散与混淆为了对抗统计分析攻击，香农引入了扩散和混淆两个概念 扩散是指使明文的统计特征消散在密文中，通过让每个密文数字受多个明文数字影响可以做到 混淆是指尽可能使密文和密钥间的统计关系更加复杂，以组织攻击者通过密文推出密钥 香农提出交替使用代替和置换（混淆和扩散）的乘积密码思想，其产生的密码强度高于所有单独使用的基本密码系统 Fei ...

数据加密标准DES是迄今为止世界上使用最广泛的分组加密算法直到2001年高级加密标准AES的提出，DES才逐渐被取代 DES原理总体结构如图所示，DES基于Feistel结构其中分组大小为64位，密钥大小为56位，子密钥$K_i$为48位，迭代轮数为16次在Feistel结构之前和之后分别经过一次置换和逆置换 与Feistel一样，DES解密过程与加密过程完全相同，只是密钥和初始置换逆序使用 密钥产生算法56位密钥K首先经过置换1，之后分为等分为左右两份$C,D$，分别为28位每轮子密钥产生中，先将$C,D$分别循环左移1位，将$C,D$拼接起来经过置换2并从中选择48位即为子密钥注意传入下一轮的$C,D$是没有经过置换2的 迭代结构如图所示，DES的迭代结构与Feistel一致，均表示为 \begin{aligned} &LE_{i+1}=RE_i\\ &RE_{i+1}=LE_i\oplus F(K_i,RE_i) \end{aligned}其中轮函数F首先根据扩展表E扩展为48bit，然后与子密钥异或之后经过S盒和P盒分别完成混淆和扩散 扩展表E如图所示，扩展表E实质上 ...

密钥产生ElGamal算法首先选择大素数$q$及其原根$\alpha$ 其公私钥产生过程如下 选择随机整数$1<X_A<q-1$ 计算$Y_A=\alpha^{X_A}\mod q$ 则用户的私钥为$X_A$，公钥为${q,\alpha, Y_A}$ ElGamal加密/解密首先将消息M分组，每块长度不小于$q$ 发送方选择任意整数$k$使得$1\leq k\leq q-1$，并计算一次性密钥$K=(Y_A)^k\mod q$按公式$C_1=\alpha^k\mod q, C_2=KM\mod q$加密，则密文为$(C_1,C_2)$ 接收方计算$K=(C_1)^{X_A}\mod q$恢复密钥按公式$M=C_2K^{-1}\mod q$即可恢复明文 注意每个消息分块都要有随机且唯一的$k$ 椭圆曲线密码下的ElGamal此处以域$Z_p$上的椭圆曲线为例 在$E_p(a,b)$中挑选基点$G$满足$G$的阶很大，其中$G$的阶$n$定义为使得$nG=O$的最小正整数 首先A选择一个整数$n_A<n$作为私钥，然后计算公钥$P_A=n_A\times G$ B要给 ...