- 博客(49)
- 收藏
- 关注
RSS订阅
原创 线性判别分析(Linear Discriminant Analysis, LDA）(含类内散度矩阵 类间散度矩阵 全局散度矩阵推导
LDA算法概述：线性判别式分析(Linear Discriminant Analysis, LDA)，也叫做Fisher线性判别(Fisher Linear Discriminant ,FLD)，是模式识别的经典算法，它是在1996年由Belhumeur引入模式识别和人工智能领域的。性鉴别分析的基本思想是将高维的模式样本投影到最佳鉴别矢量空间，以达到抽取分类信息和压缩特征空间维数的效果，投影后...
2020-04-09 13:23:13
8072
3
原创 计算机网络安全(通信机密性、完整性、数字签名、公钥认证、SSL)
1.提供通信机密性1.1. RSARSA有两个互相关联的部分：公钥和私钥的选择加密和解密算法为了生成RSA的公钥和私钥，Bob执行如下步骤：选择两个大素数 ppp 和 qqq 。计算 n=pqn=pqn=pq 和 z=(p−1)(q−1)z=(p-1)(q-1)z=(p−1)(q−1) 。选择小于n的一个数 eee ，且使 eee 和 zzz 没有(非1的)公因数(GCD(e,z)==1GCD(e,z)==1GCD(e,z)==1)。求一个数 ddd ，使得 ed−1ed-1ed−1
2022-01-05 21:35:38
958
原创 Last-Modified / If-Modified-Since / ETag / If-None-Match 的区别
看一圈全都是Last-Modified和HTTP-IF-MODIFIED-SINCE只判断资源的最后修改时间，而ETags和If-None-Match可以是资源任何的属性我: ???(好像说了什么又好像什么也没说修改{资源的任何属性}不会修改{最后修改时间}的吗?下面的我能看懂,但是又有一个小问题,If-None-Match是不是能取代If-Modified-Since啊Last-Modified / If-Modified-SinceLast-Modified是响应头，If-Modifi
2021-11-18 15:58:56
518
原创 A - Axis of Symmetry 2019-2020 ICPC Asia Hong Kong Regional Contest
看着没人发代码,我扔下我的吧我的思路大概就是用一个大的矩形把所有的矩形的围住，然后用四条对称轴去切，判断一个点与对称轴对称的点是否也存在，不存在则不能通过这条对称轴切红色的为对称轴#include<bits/stdc++.h>using namespace std;#define rep(i, a, b) for(int i=(int)(a);i<=(int)(b);i++)const long long MOD = 1e9 + 7;const int MAXN = 5e5
2021-03-27 21:15:00
183
原创 E. Cheap Dinner (multiset 有手就行)
题意给定 n1n_1n1 种第一道菜的价格 aia_iai,n2n_2n2 种第二道菜的价格 bib_ibi,n3n_3n3种饮料的价格 cic_ici,n4n_4n4 种甜点的价格 did_idi有 m1m_1m1 种组合 (xi,yi)(x_i,y_i)(xi,yi), 描述编号为 xix_ixi 的第一道菜与编号为 yiy_iyi 的第二道菜不能搭配有 m2m_2m2 种组合 (xi,yi)(x_i,y_i)(xi,yi), 描述编号为 xix_ixi 的第二.
2021-03-04 11:55:24
226
1
原创 bzoj3533【SDOI2014】向量集 (线段树 凸包 三分)
有一个结论：答案一定会出现在凸包上，而且如果y>0则在上凸包上，否则在下凸包上。简单证明：要计算一个向量a和一些向量的点积的最大值。因为所有向量都是共起点的，所以只要找到这些向量终点中在向量a的方向最靠前的，而这个最靠前点一定在凸包上。然后在一个凸包上答案是单峰的，可以用三分来做。于是问题就变成了如何动态维护区间的凸包，这个可以用线段树。可是问题在于每次新加一个点会修改logn段区间，而凸包合并是O(n)，显然这个复杂度不能接受。有一个比较巧妙的解决方法，包含未插入位置的线段树节点一定不会.
2021-01-22 16:24:13
139
原创 bzoj2300【HAOI2011】防线修建 (动态凸包 平衡树 set)
凸包上删点我不会，那就将删点转成加点。所以我们只要维护一个可以加点的动态凸包就好了。每次加点先判断是否在凸包内，然后用set lowerbound找两边相邻的点，对两边分别进行维护。#include <bits/stdc++.h>#define pb push_back#define memarray(array,val) memset(array,val,sizeof(array))using namespace std;const int mod=1e9+7;const do
2021-01-20 17:47:44
91
原创 2020秦皇岛CCPC 7-2 Bounding Wall(线段树)
维护每个点最左边/右边/上边的’.'位置每次查询建立线段树然后枚举高度查找两边长度即可#include<bits/stdc++.h>using namespace std;#define memarray(a,b) memset(a,b,sizeof(a))#define pb push_backconst long long mod=1e9+7;const int MAXN=1e3+10;const int N=3e2+10;const int INF=0x3f;int n
2020-10-24 01:28:57
157
原创 2019 ICPC 上海 F 题 A Simple Problem On A Tree(树链剖分+线段树 毒瘤题)
A Simple Problem On A Tree令我不解的是在我build()建树的时候long long w=W[pos[l]];如果改成int w=W[pos[l]];就只能正确8.33%，可他一开始W的数据范围不应该爆int的呀不解#include<bits/stdc++.h>using namespace std;#define memarray(a,b) memset(a,b,sizeof(a))#define pb push_backconst lo
2020-09-30 19:46:36
144
原创 P4092 [HEOI2016/TJOI2016]树(树链剖分)
P4092 [HEOI2016/TJOI2016]树树链剖分+线段树#include<bits/stdc++.h>//#define int long long#define pb push_back#define memarray(array, value) memset(array, value, sizeof(array))using namespace std;const double EPS=1e-5;const double PI=acos(-1);const lo
2020-09-15 19:13:55
110
原创 P3629 [APIO2010]巡逻(树的直径 树形dp)
当k=1时答案就是树的直径头尾相连当k=2时答案就是把树的直径上的点标记起来并将相邻的两个直径上的点的距离标记为-1，再用树形dp找树的直径#include<bits/stdc++.h>//#define int long long#define memarray(array, value) memset(array, value, sizeof(array))using namespace std;const double EPS=1e-5;const double PI=aco
2020-08-21 15:52:33
151
原创 局部保留投影(LPP)推导
个人笔记，非教程LPP是拉普拉斯特征图谱的线性近似。它寻求变换P来投影高维输入数据X进入一个低维子空间Y，可以保留输入数据的局部结构。线性变换P可以通过最小化目标函数来获得minP∑i=1N∑j=1N∣∣yi−yj∣∣2S(i,j)\min_P \sum_{i=1}^N\sum_{j=1}^N||y_i-y_j||^2S(i,j)Pmini=1∑Nj=1∑N∣∣yi−yj∣∣2S(i,j)其中S(i,j)S(i,j)S(i,j)的表达式为S(i,j)={e−∣∣xi−xj∣∣2t，当.
2020-08-21 12:47:55
1577
1
原创 核岭回归(Kernel Ridge Regression)推导
个人笔记，非教程最小二乘W=(XXT)−1XYTW=(XX^T)^{-1}XY^TW=(XXT)−1XYT岭回归W=(XXT+λI)−1XYTW=(XX^T+\lambda I)^{-1}XY^TW=(XXT+λI)−1XYT核岭回归W=(XXT+λI)−1XYTW=(XX^T+\lambda I)^{-1}XY^TW=(XXT+λI)−1XYTW=(κ(X,X)+λI)−1XYT=X(λI+κ(X,X))−1YTW=(\kappa(X,X)+\lambda I)^{-1}XY^T=X(\.
2020-08-21 11:16:07
1370
原创 KPCA推导
个人笔记，非教程PCACov(X)w=XXTw=λwCov(X)w=XX^Tw=\lambda wCov(X)w=XXTw=λwKPCA，左乘XTX^TXTXTCov(X)w=XTXXTw=λXTwX^TCov(X)w=X^TXX^Tw=\lambda X^TwXTCov(X)w=XTXXTw=λXTwκ(X，X)XTw=λXTw\kappa(X，X)X^Tw=\lambda X^Twκ(X，X)XTw=λXTw因为投影向量www是样本X的线性组合w=∑i=1Nαixiw=\sum_{i=.
2020-08-21 10:52:48
241
原创 2DPCA、(2D)2PCA公式推导
找到一个投影矩阵W，使数据X不用拉成一维就能投影得到低维表示YY=XWY=XWY=XW投影后的协方差矩阵S(Y)=YTY=WTXTXW=WTS(X)WS(Y)=Y^TY=W^TX^TXW=W^TS(X)WS(Y)=YTY=WTXTXW=WTS(X)W最大化tr(S(Y))maxtr(S(Y))=maxtr(WTS(X)W)\max tr(S(Y))=\max tr(W^TS(X)W)maxtr(S(Y))=maxtr(WTS(X)W)对S(X)特征值分解求前d个最大特征值对应的特征向量组成投
2020-08-15 12:31:51
422
原创 SVR推导
目标函数：minw,b12∣∣w∣∣2+C∑i=1l(ξi+ξi∗)s.t.{yi−<w,xi>−b≤ε+ξi<w,xi>+b−yi≤ε+ξi∗ξi,ξi∗≥0\min_{w,b}\frac12||w||^2+C\sum_{i=1}^l(\xi_i+\xi_i^*) \\ s.t. \begin{cases} y_i-<w,x_i>-b&\leq\varepsilon+\xi_i \\ <w,x_i&g.
2020-08-15 10:50:31
537
4
转载 矩阵的 Frobenius 范数及其求偏导法则
矩阵的迹求导法则1. 复杂矩阵问题求导方法：可以从小到大，从scalar到vector再到matrix2. x is a column vector, A is a matrixd(A∗x)dx=A\frac{d(A∗x)}{dx}=Adxd(A∗x)=Ad(xT∗A)dxT=A\frac{d(x^T∗A)}{dx^T}=AdxTd(xT∗A)=Ad(xT∗A)dx=AT\frac{d(x^T∗A)}{dx}=A^Tdxd(xT∗A)=ATd(xT∗A∗x)dx=xT(AT+A)
2020-08-03 18:14:18
1297
原创 1388C - Uncle Bogdan and Country Happiness(假装拓扑排序)
题意：起初所有人都在1号城市，总共有m个人，每个城市有pi个人，每个城市都有一个幸福指数：快乐的人减去不快乐的人。给出n-1条路：u，v，代表城市u和城市v有一条双向边，每个人回到自己的城市是走最短路，也就是不会经过一个节点两遍，每个人在路途中可能变得不快乐，以后的路不能变得快乐，问给出的数据能不能满足每个城市的幸福指数。思路：我们可以从叶子节点下手，比如现在有一个3号叶子节点，p[3]即该城市人数，因为它是叶子节点，所以也就只有p[3]个人经过，然后我们就可以通过p[3]和h[3]来计算开心人数和不.
2020-08-01 00:27:24
312
原创 2020牛客暑期多校训练营（第二场）[G] Greater and Greater
题意：给定nnn个数的数组AAA，mmm个数的数组BBB，问在AAA中有多少个长度为mmm的子数组SSS满足Si>=Bi,(i=1,...,m)S_i>=B_i,(i=1,...,m)Si>=Bi,(i=1,...,m)题解：我们可以考虑记录合法子数组以数组A中的一个位置代表一个合法子数组（因为长度固定为m）； 设bitset 的ans和tmp，其中tmp为1的位置表示，对于当前的bi ，a数组中有哪些比b[i].val大； 如果某个位置x比当前的b[i].val.
2020-07-27 22:18:10
114
原创 最小二乘支持向量机（LSSVM）推导
LSSVM和SVM的区别就在于，LSSVM把原方法的不等式约束变为等式约束，从而大大方便了Lagrange乘子alpha的求解，原问题是QP问题，而在LSSVM中则是一个解线性方程组的问题。minw,b,eJ(w,e)=12wTw+12γ∑i=1Nek2\min_{w,b,e}J(w,e)=\frac 12 w^Tw+\frac 12\gamma\sum_{i=1}^{N}e_k^2w,b,eminJ(w,e)=21wTw+21γi=1∑Nek2s.t.  .
2020-07-20 20:56:27
2519
2
原创 如何学习算法
写在前面要学习算法首先要理解算法，然后能够通过代码实现对应功能，做题是一种检测你对算法理解度的方法我会列出几个比较主流的在线测题系统，也就是大家说的oj，然后分别介绍它们的侧重点以及使用方法 一、洛谷https://www.luogu.com.cn/我最看重洛谷的是什么呢，它有大量的模板题，一个模板题大概就对应一种算法，如图，用户进入洛谷首页后点击左侧的题库，然后再查找题目里面输入[模板]，就可以得到大量的模板题：这些模板题用户只需理解算法然后将其用代码实现大概就能正确通过了，掌握了基础的模板
2020-07-16 01:23:04
2356
原创 K-Means推导
对于每个样本xix_ixi，将其标记为距离类别中心最近的类别，即labeli=argmin∣∣xi−μj∣∣label_i=\arg \min ||x_i-\mu_j||labeli=argmin∣∣xi−μj∣∣目标minSSE=∑i=1K∑xj∈Ci(xj−μi)2=∑i=1K∑xj∈Ci(xjTxj−xjTμi−μiTxj+μiTμi)=∑i=1K(∑xj∈CixjTxj−∑xj∈CixjTμi−∑xj∈CiμiTxj+∑xj∈CiμiTμi)=∑i=1K(∑xj∈CixjTxj−
2020-07-14 13:44:34
811
原创 SVM推导
将两类样本用以下超平面进行划分wTx+b=0w^Tx+b=0wTx+b=0让所有样本都划分正确wTx++b≥0,x+∈第一类数据,y+=+1w^Tx_++b\geq 0, x_+\in 第一类数据,y_+=+1wTx++b≥0,x+∈第一类数据,y+=+1wTx−+b≤0,x−∈第二类数据,y−=−1w^Tx_-+b\leq 0, x_-\in 第二类数据,y_-=-1wTx−+b≤0,x−∈第二类数据,y−=−1目标：找到最靠近划分超平面的数据xxx，xxx到划分超平面的距离ddd，
2020-07-14 12:54:25
110
原创 最小二乘推导
X:D×NX:D\times NX:D×NY:d×NY:d\times NY:d×NW:D×dW:D\times dW:D×d最小化均方误差min(WTX−Y)2\min (W^TX-Y)^2min(WTX−Y)2min(WTX−Y)(WTX−Y)T\min (W^TX-Y)(W^TX-Y)^Tmin(WTX−Y)(WTX−Y)TL=(WTX−Y)(WTX−Y)T=WTXXTW−WTXYT−YXTW+YYT\begin{aligned}L&=(W^TX-Y)(W^TX-Y)^T \
2020-07-07 16:02:14
144
原创 LDA推导
类内散度矩阵SW=∑i=1C∑j=1Mip(i,j)(xj(i)−μi)2S_W=\sum_{i=1}^{C}\sum_{j=1}^{M_i}p(i,j)(x_j^{(i)}-\mu_i)^2SW=i=1∑Cj=1∑Mip(i,j)(xj(i)−μi)2投影后的类内散度矩阵SW′′′=∑i=1C∑j=1Mip(i,j)(WTxj(i)−WTμi)2=∑i=1C∑j=1Mip(i,j)(WT(xj(i)−μi))2=∑i=1C∑j=1Mip(i,j)(WT(xj(i)−μi)(xj(i)−μ
2020-07-07 15:31:07
212
1
原创 PCA推导
Z:d×nZ: d\times nZ:d×nW:D×dW: D\times dW:D×dX:D×nX: D\times nX:D×nZ=WXZ=WXZ=WX目标：最大化投影后的方差maxw1n∑i=1n(zi−zˉ)2s.t.∣∣W∣∣2=I\max_w \frac1n \sum_{i=1}^n (z_i-\bar z)^2 \\s.t. ||W||^2=I \\wmaxn1i=1∑n(zi−zˉ)2s.t.∣∣W∣∣2=I解Tar=maxw1n∑i=1n(zi−zˉ)2=1
2020-07-06 16:15:37
152
原创 nginx无法加载.woff .eot .svg .ttf等问题解决
最近在django部署到服务器上遇到了贼多问题一开始svg加载不了，在网上乱来找了很多教程都没用，大部分都是这样讲的# vi xx/xx/setting.py在setting文件的最开始添加如下内容：import mimetypesmimetypes.add_type("image/svg+xml", ".svg", True)mimetypes.add_type("image/svg+xml", ".svgz", True)# ：wp 保存退出后重新运行项目，清空浏览器之前缓存即可显示图
2020-07-02 18:56:01
2148
原创 Fuzzy C-Means Clustering(模糊C均值)
算法原理 模糊c-均值聚类算法 fuzzy c-means algorithm (FCMA)或称（FCM）。在众多模糊聚类算法中，模糊C-均值（FCM）算法应用最广泛且较成功，它通过优化目标函数得到每个样本点对所有类中心的隶属度，从而决定样本点的类属以达到自动对样本数据进行分类的目的。 先来讲讲这个算法的名字噢，什么叫Fuzzy，什么叫模糊呢，在经典的集合理论，一个元素是否属于集合，只有真或者假两种情况，也可以说只有0和1两种情况，0为假1为真。比如我们想要定义一个集合表示“年轻人”，那么我们需要设
2020-05-20 20:38:28
5210
2
原创 Simpson积分
几何中的求面积、体积问题，可以用积分的方法，在某个方向上用扫描线或扫描面切过图形，求被覆盖的长度或面积，然后进行积分。 对于这类问题，如果能直接求出面积、体积，或者能列出覆盖长度（面积）关于扫描线（面）的位置的函数，然后手算积分，那当然是再好不过了。但是，如果直接用解析法、公式法比较费时费力，思考难度大，而题目对精度的要求不高（比如精确到0.01，0.001），数据规模不大，可以考虑用积分的方法。 用程序进行积分，一般的方法是矩形（梯形）切割法，但精度比较差。这里用Simpson积分公式，原理.
2020-05-15 21:42:19
1466
原创 快速求n!的质因数及个数
一般要进行质因数分解时，我们是for循环对每个数进行质因数分解，但少数的情况下，数字太大了，题目不允许这样的做法，所以我们需要学会一种更快的方法来求质因数。我们来一个样例说明一下：123456789我们求得在9!中2的个数1234首先我们计算出2的倍数的个数：8/2=412其次我们计算出4的倍数的个数：8/4=21最后我们解出第三层的2的个数：8/8=1 \begin{mat...
2020-04-28 22:10:11
1422
原创 D - Grandpa's Estate POJ - 1228（稳定凸包）
D - Grandpa’s Estate POJ - 1228当凸包上存在一条边上的点只有端点两个点的时候，这个凸包不是稳定的，因为它可以在这条边外再引入一个点，构成一个新的凸包。但一旦一条边上存在三个点，那么不可能再找到一个点使它扩展成一个新的凸包，否则构成的新多边形将是凹的。也就是说只要凸包上的每一条边上至少有三个点就是稳定凸包了, 那就直接求凸包然后对凸包上的每条边的检查一次...
2020-02-13 21:07:00
918
原创 HDU - 546 D - Manors
Some famous theoretical scientists with their wives bought 40952 acres of Prairie Nebraska. They describe it as a square of length 4095. Now they want to build their private manors. Each theoretical ...
2020-02-11 21:08:25
937
原创 周志华西瓜书笔记 2.3 性能度量
2.3 性能度量 ABCDEFGHIJKLMNOPQRSTUVWXYZ\rm {ABCDEFGHIJKLMNOPQRSTUVWXYZ}ABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZ\it {ABCDEFGHIJKLMNOPQRSTUVWXYZ}ABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHI...
2020-02-09 22:47:37
1148
原创 周志华西瓜书笔记 2.2 评估方法
2.2 评估方法 通常, 可以通过实验测试来对学习器的泛化误差进行评估并进而做出选择. 为此, 需使用一个 “测试集”(testing set) 来测试学习器对新样本的判别能力, 然后以测试集上的 “测试误差”(testing error) 作为泛化误差的近似. 通常假设测试样本也是从样本真实分布中独立同分布采样而得. 测试集应尽可能与训练集互斥.只有一个包含mmm个样例的数据集D={(x1...
2020-02-07 22:38:56
1085
原创 周志华西瓜书笔记 2.1 经验误差与过拟合
1:早起时间自选, 不得晚于9:00, 在这个时间点之前以及后15分钟内打卡都算有效, 比如某人定早起时间为8:30, 则6:00-8:45打卡都算成功.2:每天晚上可以选择是否参加第二天的早起打卡, 即想摸鱼了可以睡一天~~(一寒假)~~的懒觉.3:每次押金10人民币,没早起的通过发拼手气红包给对应早起的人,即某人摸鱼了没早起,而当天有5个人按时早起了,就发5个总值10块的红包....
2020-02-07 21:16:35
1269
原创 旋转卡壳
问题:在二维平面上给定n个点，求距离最远的两个点之间的距离是多少？第一反应: n2n^2n2 暴力搞它. 然后瞄一眼范围, woc n=100000, 算了还是摸鱼吧.几个小时月后, 还是学一下怎么求吧.对于上面的问题, 我们进一步思考，这个最远点对一定会出现在这些点集的凸包上. 先求出这个点集的凸包, 然后用下面的算法就能在nlognnlognnlogn 的复杂度求出这个最远距离....
2020-02-06 21:13:51
3073
1
原创 Rotating Scoreboard POJ - 3335 (半平面交)
是是为是是的#include<cstdio>#include<algorithm>#include<cmath>using namespace std;const int MAXN=1e3+5;const double EPS=1e-8;const double PI=acos(-1);inline int sgn(double a){ retu...
2020-02-06 16:37:49
2844
原创 周志华西瓜书笔记 1.4 归纳偏好
1.4 归纳偏好 通过学习得到的模型对应了假设空间中的一个假设. 会有多个与训练集一致的假设.如何选择. 机器学习算法在学习过程中对某种类型假设的偏好, 称为 “归纳偏好”(inductive bias), 或简称为"偏好". e.g.,若算法喜欢 “特殊” 的模型, 则它会选择 "好瓜"↔(色泽=∗)⋀(根蒂=蜷缩)⋀(敲声=浊响)"好瓜"\leftrightarrow(色泽=*)\bi...
2020-02-06 00:11:39
1514
原创 周志华西瓜书笔记 1.3 假设空间
1.2 假设空间 归纳(induction)是从特殊到一般的 “泛化”(generalization)过程, 即从具体的事实归结出一般性规律; 演绎(deduction)是从一般到特殊的 “特化”(specialization)过程, 即从基础原理推演出具体状况. e.g.,在数学公理系统中, 基于一组公理和推理规则推导出与之相洽的定理, 是演绎; 而"从样例中学习"是一个归纳的过程, 因此亦...
2020-02-05 21:14:07
1257
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人