存档

文章标签 ‘算法’

线性回归

2014年11月24日 没有评论

回归的意思就是给定一个训练集合的前提下,找到一个数学函数拟合这些训练集合的过程;线性回归则是需要找的数学函数是一个线性方程。线性回归的算法常用最小二乘法作为损失函数,求解损失函数最小值的方法有:最小二乘法矩阵解法、梯度下降法(批量梯度下降和随机梯度下降)。

 

最小二乘法损失函数,如下式:
costFunction

* 给定训练集合

X = [1 4;2 5;5 1;4 2 ]

y = [19;26;19;20]

1.最小二乘法矩阵解法

normal-eq

上式中theta即是需要求出的线性回归中各项的系数,X是训练集合矩阵,y向量是训练集合中每个的结果。

如果使用Octave计算,则代码为:

theta=pinv(X'*X)*X'*y

需要注意X必须是列满秩,否则(X’*X)得到的矩阵不可逆;不过Octave中pinv对于不可逆的矩阵一样可以计算,是伪逆。

2.梯度下降法

梯度下降法可以分为批量梯度下降法和随机梯度下降法;批量梯度下降法每一次迭代需要把整个训练集合遍历一次;随机梯度则是在每一次迭代中自行指定一条训练集合中的数据不用遍历整个训练集合。

 

要求J(theta)的最小值则求偏导,并对theta进行迭代,至其收敛:

computeTheta

α是学习速率,其作用是避免步长过大时J(theta)无法达到最小值,或步长多短时学习时间较长。另外在实际应用时可以直接另α=α*(1/m),只要给予α恰当的值就不会影响最终结果。

a)批量梯度下降算法 Java版

package com.opsunv.machine.regression;
 
public class BatchGradient {
 
	public static void main(String[] args) {
		//训练集合输入值
		double x[][] = { { 1, 4 }, { 2, 5 }, { 5, 1 }, { 4, 2 } };
		//训练集合期望输出值
		double y[] = { 19, 26, 19, 20 };
		//线性方程参数
		double theta[] = { 0, 0 }; 
		double learningRate = 0.01;
 
		for (int i = 0; i < 100 ; i++) {
			double err_sum = 0;
 
			double[] tmp = new double[theta.length];
			System.arraycopy(theta, 0, tmp, 0, theta.length);
 
			for (int j = 0; j < x.length; j++) {
 
				double h = 0;
				for (int k = 0; k < theta.length; k++) {
					h += x[j][k] * theta[k];
				}
 
				err_sum = h - y[j] ;
 
				for (int k = 0; k < theta.length; k++) {
					//梯度下降 ,这里直接另 α=α*(1/m),所以没有乘 1/m
					tmp[k] -= learningRate * err_sum* x[j][k]; 
				}
			}
 
			//批量更新参数
			theta = tmp;
		}
 
		for(int i=0;i<theta.length;i++){
			System.out.println("theta"+i+"="+theta[i]);
		}
 
	}
}

a)批量梯度下降算法 Octave版

X = [1 4;2 5;5 1;4 2 ];
y = [19;26;19;20];
theta = zeros(2,1);
 
m = length(X);
a = 0.01;
 
for i=1:1000
	h = ((X*theta)-y)';
	theta = theta - (a*(1/m)*h*X)';
end;
 
theta

c)随机梯度下降算法,以后有空再给出。

矩阵解法和梯度下降法的区别是;矩阵解法对于特征向量较少时可以很快的计算出结果,但是有一定局限性如训练集合X必须满足|X|!=0,并且在特征向量较多时速度会很慢,因为求解矩阵的逆的计算是非常耗时的;对于梯度下降法缺点是需要考虑学习速率参数α的大小,并且梯度下降法是一个迭代的过程在一定情况下比最小二乘法慢,不过梯度下降法可以应对更多的情况。

感知哈希算法

2013年2月9日 2 条评论

一、原理讲解
实现这种功能的关键技术叫做”感知哈希算法”(Perceptual Hash Algorithm), 意思是为图片生成一个指纹(字符串格式), 两张图片的指纹越相似, 说明两张图片就越相似. 但关键是如何根据图片计算出”指纹”呢? 下面用最简单的步骤来说明一下原理:

《1》、第一步 缩小图片尺寸
将图片缩小到8×8的尺寸, 总共64个像素. 这一步的作用是去除各种图片尺寸和图片比例的差异, 只保留结构、明暗等基本信息.

《2》、第二步 转为灰度图片
将缩小后的图片, 转为64级灰度图片.

《3》、第三步 计算灰度平均值
计算图片中所有像素的灰度平均值

《4》、第四步 比较像素的灰度
将每个像素的灰度与平均值进行比较, 如果大于或等于平均值记为1, 小于平均值记为0.

《5》、第五步 计算哈希值
将上一步的比较结果, 组合在一起, 就构成了一个64位的二进制整数, 这就是这张图片的指纹.

《6》、第六步 对比图片指纹
得到图片的指纹后, 就可以对比不同的图片的指纹, 计算出64位中有多少位是不一样的. 如果不相同的数据位数不超过5, 就说明两张图片很相似, 如果大于10, 说明它们是两张不同的图片.

分类: 高级民工 标签:

位掩码

2013年1月3日 没有评论

位掩码的作用主要是想通过与或运算快速的判断是否选择了某个选项,常见的如在J2SE的弹窗中常用到给窗口加按钮,某个参数里有类似于BTN_OK|BTN_CANCEL|BTN_NO这样的代码,这个就是使用了位掩码。
位掩码的原理比较简单按8bit的一个例子。
0 0 0 0  0 0 0 1   –>1
0 0 0 0  0 0 1 0   –>2
0 0 0 0  0 1 0 0   –>4
0 0 0 0  1 0 0 0   –>8

位掩码总是2的n次方,如果上面的值分别对应a1,a2,a3,a4.
那么a1|a2 –>0 0 0 0  0 0 1 1
这个参数被传入方法中后一个判断可能是这样

if( state&(a1|a2) ==1)  {//state&a1
//当state为a1或a2时。。to do something
//假设state=1则,00000001&00000011=1

}

 

通过与运算如果是0则未设置,如果是1则设置

上面的代码如果不用位掩码可能的代码会是这样

if( state==a1||state==a2 ){

}

位掩码的好处是在一定程度上减少代码量,并可以使得一个变量可以表示多种状态,只需通过与运算即可知道是否带有某个状态。

分类: 高级民工 标签:

QQ安全管家安全飞人flash游戏破解

2012年8月22日 5 条评论

  安全飞人游戏是由QQ安全管家奥运会期间推出的一个活动游戏,地址是:http://guanjia.qq.com/act/brand/olympic/?ADTAG=WEB.AOYUN.GJ.GW 。做为flash游戏而言游戏最后得分一般都是会加密后发送到服务器。安全飞人这个游戏也不例外,当然作为flash游戏破解的方式很多,最直接的方式就是反编译找到加密算法直接计算出符合要求的字符串即可。
  安全飞人这个游戏的flash根据检测是通过doSwf加密的,doSwf其加密方式主要有两点:第一点对原始flash中的as代码进行混淆,主要体现在变量名称,类名,方法名的替换,根据破解的流程上看主要是就是把这些名称替换成特殊字符,形成乱码以达到代码不好阅读,不过这种方式通过简单的字符替换就可以让as代码变得易读;第二点是在第一点的基础上对flash进行加壳处理,这个有点类似于一般exe文件的加壳。 针对doswf的破解而言我在网上还没找到现成的工具,不过通过对exe的脱壳的理解,一般来说最后原始文件都将会在内存中被还原。所以抓住这一点就可以在内存中找到原始的flash.下面先介绍一下步骤。
  1.浏览器打开游戏flash。即访问到游戏页面即可。
  2.用winhex打开浏览器进程的内存,直接把整个浏览器分配的内存区域全部dump出来。
  3.用winhex搜索flash文件的特征码。根据adobe的swf文档 描述:

并结合本游戏的flash版本可以得到一个得到特征码:46 57 53 09,直接用winhex搜索特征码,并结合特征码后4字节是文件长度,经过排除和测试后最终可以找到原始的swf文件,通过winhex dump出来。这里所说的原始swf文件其实是被doswf混淆as后的,所以在反编译得到的swf将出现乱码。如图。


阅读全文…

求1+2+…+n

2010年12月1日 没有评论

题目:求1+2+…+n,
要求不能使用乘除法、for、while、if、else、switch、case等关键字以及条件判断语句(A?B:C)。

一种java的实现方式,主要是使用异常来控制。

public class  T{
	//存放结果
	public static int rs=0;
 
	public static int sum(int n){
		try{
			//除0错误
			int i=1/n;
		}catch (Exception e) {
			return rs;
		}
		rs+=n;
		return sum(--n);
 
	}
 
	public static void main(String[] agrs){
		System.out.println(sum(100));
	}
}
分类: 高级民工 标签: ,