Machine Learning in Action::Logistic Regression

Logistic Regression 概述

	关键词：最优化算法·监督学习
	
	原理:	根据现有数据对分类边界线建立回归公式,以此进行分类.
		假设现在有一些数据点,我们用一条曲线对这些点进行拟合(该线成为最佳拟合曲线),这个拟合过程就是回归.这里的"回归"一词源于最佳拟合,表示要找的最佳拟合参数集合.
		训练分类器时的做法就是寻找最佳拟合参数,使用的是最优化算法.

LR 核心算法代码实现

[1] LR 梯度下降算法

#便利函数
def loadDataSet():
	
	dataMat = [] #[x1,x2,x3]
	labelMat = []
	fr = open('test.txt','r')
	
	for line in fr.readLines():
		lineArr = line.strip().split('\t')
		dataMat.append([1.0,float(lineArr[0]),float(lineArr[1])])
		labelMat.append(int(lineArr[2]))
	
	return dataMat,labelMat

# sigmoid 函数
def sigmoidFunc(intX):
	
	return 1.0 / (1 + exp( -inX ) )


#LR 梯度下降算法初始版
# REPEAT : {   
#		 w : = 
#			w - α * xT * ( hw( x ) - y ) 
#           }

函数名称:
	gradDescent(dataMatIn,classLabels)
函数功能:
	梯度下降实现(初始版),最优化回归系数,跳出条件,达到最大迭代次数
	学习率硬编码
输入参数:
	dataMatIn : 训练集特征矩阵(m*n m:样本数 n:特征数) : mat or array or list
	classLabels : 训练集标签(m*1 m:样本数) : mat or array or list
输出参数:
	weight : 最优回归系数(n*1  n:特征数) : array

def gradDescent(dataMatIn, classLabels):
	
	#训练集特征matrix化[m*n] 
	#m(样本数量),n(特征数量)
	sampleFeatureDataMatrix = mat(dataMatIn)

	#训练集标签matrix化[m*1]
	sampleLabelDataMatrix = mat(classLabels).transpose()
	
	#获取m,n
	m,n = shape(sampleFeatureDataMatrix)

	#回归系数初始化
	weight = ones((n,1))
	# 学习率
	alpha = 0.0001
	# 迭代次数
	maxCycles = 500
	
	for k in range(maxCycles):
		
		# sigmiod func :note input mat ,return mat
		# h : matrix of (m*1)
		h = sigmoidFunc(sampleFeatureDataMatrix)
		# 误差计算
		# error : matrix of (m*1)
		error = h - sampleLabelDataMatrix
		
		# update weight reference of regression
		weight = weight - alpha * sampleFeatureDataMatrix.transpose()*error
	
	return weight
	
------------------------------------------------------------------------------	

[2] 改进的随机梯度下降算法

	[1]中实现的梯度下降算法在每次更新回归系数时,都要遍历整个数据集合,该方法在处理100个左右的数据集合(这里应该是说针对单机来讲,大型的分布式计算方案能够支撑更大的量级)
	时尚可,但如果有数十亿个样本和成千上万的特征,那么该特征的计算复杂度就太高了.一个改进方法是一次仅用一个样本点来更新回归系数,该方法称为随机梯度上升算法.
	由于可以在样本到来时,对分类器进行增量式更新,因此这是一个在线学习算法.[1]所运用的一次处理所有数据的方式称作是批处理
	

函数名称:
        stocGradDescent(dataMatIn,classLabels)
函数功能:
        梯度下降实现改进1,在线学习，跳出条件，学习完全部样本
        学习率硬编码
输入参数:
        dataMatIn : 训练集特征矩阵(m*n m:样本数 n:特征数) : mat or array or list
        classLabels : 训练集标签(m*1 m:样本数) : mat or array or list
输出参数:
        weight : 最优回归系数(n*1  n:特征数) : array


def stocGradDescent0(dataMatrix,classLabels):
	
	m,n = shape(dataMatrix)
	alpha = 0.001

	#将weight 初始化为行向量	
	weight = ones(n)
	
	for i in range(m):
		# arrary * array = 对应位置相乘 array([a,b,c]) * array([e,d,f]) = array([ae,bd,cf])
		h = sigmoid(sum(dataMatrix[i]*weight)) 
		# error
		error = h - classLabels[i]
		#update weight
		weight = weight - alpha * dataMatrix[i] * error
	
	return weight

	[2]与[1]的区别有两点：
	[1] 中 h 与 error 均为向量，[2]中为数值。这是因为[1]是全部样本的批处理
	[2] 没有矩阵转换（转秩）的过程，所有变量的数据类型都是Numpy数组。

	
	如何判断一个优化算法的优劣呢？
	一个比较靠谱的方法是看它是否收敛（速度）,也就是说参数是否达到了稳定值，是否还会不断的变化。
	所以可以绘图将系数随迭代次数的变化情况展示出来。

 	通过一定程度的不同迭代次数之后，系数达到了稳定值。值得注意的是，在大的波动停止之后，还有一些小的周期波动。产生这种现象的原因是：
	存在一些不能被正确分类的样本点（数据集并非线性可分），在每次迭代时会引发系数的剧烈改变。我们期望算法能够避免来回波动，
	从而收敛到某值。另外，收敛速度也需要加快。
		 
-------------------------------------------------------------------------------

[3] 改进的随机梯度下降算法

函数名称:
        stocGradDescent1(dataMatrix,classLabels,numIter=150)
函数功能:
        梯度下降实现改进2 
        学习率随迭代次数，以及样本选择次数增加而下降（并非严格下降）
	随机选区样本进行学习
输入参数:
        dataMatrix: 训练集特征矩阵(m*n m:样本数 n:特征数) : mat or array or list
        classLabels : 训练集标签(m*1 m:样本数) : mat or array or list
	numIter = 150 : 最大迭代次数 默认为150 : int 
输出参数:
        weights : 最优回归系数(n*1  n:特征数) : array



def stocGradDescent1(dataMatrix,classLabels,numIter=150):
	
	#get number of sample,feature
	m,n = shape(dataMatrix)
	
	#regression reference
	weights = ones(n)	

	#最大迭代次数
	for iter in range(numIter):
		# 样本集标号
		dataIndex = range(m)
		# 迭代整个样本空间 随机
		for i in range(m):
			#学习率 可变
			alpha = 4/(1.0+i+iter) + 0.01       #①
			#样本集标号的list的下标
			randomIndex = int(random.uniform(0,len(dataIndex)))  #②
			# 随机获得的样本集下标
			randomDataIndex = dataIndex[randomIndex]
			
			h = sigmoid(sum(dataMatrix[randomDataIndex]*weights)
			error = h - classLabels[randomDataIndex]
			weights = weights - alpha * error * dataMatrix[randomDataIndex]
	
	return weights
	
	第一处改进在① 处。一方面，alpha 在每次迭代的时候都会调整，这会缓解迭代时的数据波动或者高频波动。另外，虽然alpha会随着迭代次数不断减小，但永远不会减小到0,这是因为① 中还存在一个常数项。
	必须这样做的原因是为了保证在多次迭代之后新数据仍然具有一定影响。如果要处理的问题是动态变化的，那么可以适当加大上述常数项，来确保新的值获得更大的回归系数。另一点值得注意的是，在降低
	alpha的函数中，alpha 每次减少 1/(i+iter) 其中iter 是迭代次数，i 是样本点的下标。当 iter << max(i) 时，alpha就不是严格下降了的。避免参数的严格下降也常见与模拟退火算法等其他优化算法中。
	
	第二处改动在② 处。这里通过随机选取样本来更新回归系数。这种方法将减少周期性的波动。具体实现方法即每次随机从列表中选出一个值，然后从列表中删掉该值，再进行下一次迭代。			



------------------------------------------------------------------------------------------

[4] 上升还是下降?

	最优化的根本是针对代价函数(Cost Function),最小化代价函数推导简化之后,得到的函数,最大化的就要用梯度上升,最小化的话,就要用梯度下降.


------------------------------------------------------------------------------------------

[5] 如何处理样本数据缺失问题 ？

	先给出一些可选的做法：
		·使用可用特征的均值来填补缺失值
		·使用特殊值来填补缺失值，如 -1 ，0
		·忽略有缺失值的样本
		·使用相似样本的均值添补缺失值
		·使用另外的机器学习算法预测缺失值

	
	对于LR，缺失的特征值，用实数0来替换。why ?
		回归系数的迭代更新公式： weights = weights - alpha * error * dataMatrix[randDataIndex]
	因为dataMatrix[randDataIndex]=0 所以 weights = weights 不会进行更新。
	另外 sigmoid(0)=0.5 ,即他对结果的预测不会有任何倾向性，因此上述的做法也不会对误差项造成任何影响。
         
	对于缺失类别标签的数据，直接丢弃。	
	

Welcome to contact me,the friends who like Machine-Learning and Data-Mining.

:)

07 Nov 2014