算法原理 Logistic回归虽然名字叫”回归” ,但却是一种分类学习方法。 Sigmoid函数: f ( X ) = 1 1 + e − ( W X + b ) f(X)=\frac{1}{1+e^{-(WX+b)}} f(X)=1+e−(WX+b)1 其类别y属于正例和负例的概率分别为: p ( y = 1 ∣ X , W , b ) = σ ( W X + b ) = 1 1 + e − ( W X + b ) p(y=1|X,W,b)=\sigma (WX+b)=\frac{1}{1+e^{-(WX+b)}} p(y=1∣X,W,b)=σ(WX+b)=1+e−(WX+b)1 p ( y = 0 ∣ X , W , b ) = 1 − σ ( W X + b ) = e − ( W X + b ) 1 + e − ( W X + b ) p(y=0|X,W,b)=1-\sigma (WX+b)=\frac{e^{-(WX+b)}}{1+e^{-(WX+b)}} p(y=0∣X,W,b)=1−σ(WX+b)=1+e−(WX+b)e−(WX+b) 因此对于上述算法,其属于类别y的概率为: p ( y ∣ X , W , b ) = σ ( W X + b ) y σ ( W X + b ) 1 − y p(y|X,W,b)=\sigma (WX+b)^{y}\sigma (WX+b)^{1-y} p(y∣X,W,b)=σ(WX+b)yσ(WX+b)1−y
损失函数 要求上述问题中的参数W和b,可以使用极大似然法(极大似然估计就是在只有概率的情况下,忽略低概率事件直接将高概率事件认为是真实事件的思想)对其进行估计,则其似然函数为: L W , b = ∐ i = 1 m [ h W , b X i ( 1 − h W , b X i 1 − y ) ] L_{W,b}=\coprod_{i=1}^{m}[h_{W,b}X_{i}(1-h_{W,b}X_{i}^{1-y})] LW,b=∐i=1m[hW,bXi(1−hW,bXi1−y)] 其中,假设函数 h W , b X i h_{W,b}X_{i} hW,bXi为: h W , b X i = σ ( W X + b ) h_{W,b}X_{i}=\sigma (WX+b) hW,bXi=σ(WX+b) 对于似然函数的极大值的求解,通常使用-log似然函数作为其损失函数。 l W , b = − 1 m l o g L W , b = ∐ i = 1 m [ h W , b X i ( 1 − h W , b X i 1 − y ) ] l_{W,b}=-\frac{1}{m}logL_{W,b}=\coprod_{i=1}^{m}[h_{W,b}X_{i}(1-h_{W,b}X_{i}^{1-y})] lW,b=−m1logLW,b=∐i=1m[hW,bXi(1−hW,bXi1−y)] 此时我们需要求解的问题为: m i n l W , b minl_{W,b} minlW,b
梯度下降法 为了求得损失函数的最小值,可以使用基于梯度的方法进行求解。梯度下降法的含义是通过当前点的梯度方向寻找到新的迭代点,并从当前点移动过程如下: ①随机选择一个初始点 w 0 w_{0} w0; ②重复以下过程 i 决定梯度下降的方向: d i = − ∂ ∂ w f ( w ) ∣ w i d_{i}=-\frac{\partial }{\partial w}f(w)|_{w_{i}} di=−∂w∂f(w)∣wi ii 选择步长 α \alpha α iii 更新: w i + 1 = w i + α ⋅ d i w_{i+1}=w_{i}+\alpha\cdot d_{i} wi+1=wi+α⋅di ③直到满足终止条件 凸优化与非凸优化。凸优化是指只存在一个最优解的优化问题,即任何一个局部最优解即全局最优解。 对损失函数采用梯度下降法进行求解,其梯度为: ▽ w j ( l W , b ) = − 1 m ∑ i = 1 m ( y i − h W , b X i ) x j i \bigtriangledown_{w_{j}}(l_{W,b})=-\frac{1}{m}\sum_{i=1}^{m}(y_{i}-h_{W,b}X_{i})x_{j}^{i} ▽wj(lW,b)=−m1∑i=1m(yi−hW,bXi)xji 其中, x j i x_{j}^{i} xji表示的是样本 X i X^i Xi的第j个分量。 W j = W j + α ▽ w j ( l W , b ) W_{j}=W_{j}+\alpha\bigtriangledown_{w_{j}}(l_{W,b}) Wj=Wj+α▽wj(lW,b)
算法原理 y = b + ∑ i = 1 n w i ⋅ x i y = b + \sum_{i=1}^{n}w_i \cdot x_i y=b+∑i=1nwi⋅xi 令 x 0 x_0 x0=1,则上式可以表示为 y = ∑ i = 0 n w i ⋅ x i y = \sum_{i=0}^{n}w_i \cdot x_i y=∑i=0nwi⋅xi
损失函数 平方误差可以表示为: l = 1 2 ∑ i = 1 m ( y i − ∑ j = 0 n − 1 w j ⋅ x i j ) 2 l = \frac{1}{2}\sum_{i=1}^{m}(y_i - \sum_{j=0}^{n-1}w_j \cdot x_{ij})^2 l=21∑i=1m(yi−∑j=0n−1wj⋅xij)2
线性回归的最小二乘解法 预测函数可以表示为: Y = XW 其损失函数可以表示为: ( Y − X W ) T ( Y − X W ) (Y-XW)^T (Y-XW) (Y−XW)T(Y−XW) 在最小二乘法中,对W求导,即: d d W ( Y − X W ) T ( Y − X W ) = X T ( Y − X W ) \frac{d}{dW}(Y-XW)^T (Y-XW) = X^T(Y-XW) dWd(Y−XW)T(Y−XW)=XT(Y−XW) 令其为0,得到 W ^ = ( X T X ) − 1 X T Y \hat{W} = (X^TX)^{-1}X^TY W^=(XTX)−1XTY
牛顿法 牛顿法的基本思想是利用迭代点 x k x_k xk处的一阶导数(梯度)和二阶导数(Hessen矩阵)对目标函数进行二次函数近似,然后把二次模型的极小点作为新的迭代点,并不断重复这一过程,直至求得满足精度的近似极小值。牛顿法下降的速度比梯度下降的快,而且能高度逼近最优值。牛顿法分为基本的牛顿法和全局牛顿法。 ①基本牛顿法的原理 基本牛顿法是一种基于导数的算法,它每一步的迭代方向都是沿着当前点函数值下降的方向。对于一维的情形,对于一个需要求解的优化函数f(x),求函数的极值的问题可以转化为求导函数f’(x) =0。对函数f(x)进行泰勒展开到二阶,得到 f ( x ) = f ( x k ) + f ′ ( x k ) ( x − x k ) + 1 2 f ′ ′ ( x k ) ( x − x k ) 2 f(x) = f(x_k) + f'(x_k)(x-x_k) +\frac{1}{2}f''(x_k)(x-x_k)^2 f(x)=f(xk)+f′(xk)(x−xk)+21f′′(xk)(x−xk)2 对上式求导并令其为0,则为 f ′ ( x k ) + f ′ ′ ( x k ) ( x − x k ) = 0 f'(x_k) + f''(x_k)(x-x_k) = 0 f′(xk)+f′′(xk)(x−xk)=0 即可得 x = x k − f ′ ( x k ) f ′ ′ ( x k ) x = x_k - \frac{f'(x_k)}{f''(x_k)} x=xk−f′′(xk)f′(xk) 这就是牛顿法的更新公式。 ②基本牛顿法的流程 i) 给定终止误差值 0 ≤ ε ≪ 1 0\leq \varepsilon \ll 1 0≤ε≪1,初始点 x 0 ∈ R n x_0 \in \mathbb{R}^n x0∈Rn,令k = 0; ii) 计算 g k = ▽ f ( x k ) g_k = \bigtriangledown f(x_k) gk=▽f(xk),若 ∥ g k ∥ ≤ ε \left \| g_k \right \| \leq \varepsilon ∥gk∥≤ε,则停止,输出 x ∗ ≈ x k x^* \approx x_k x∗≈xk; iii) 计算 G k = ▽ 2 f ( x k ) G_k = \bigtriangledown^2 f(x_k) Gk=▽2f(xk),并求解线性方程组 G k d = − g k G_kd = -g_k Gkd=−gk得解 d k d_k dk; iv) 令 x k + 1 = x k + d k x_{k+1}=x_k + d_k xk+1=xk+dk,k=k+1,并转2。 ③全局牛顿法 牛顿法最突出的优点是收敛速度快,具有局部二阶收敛性,但是,基本牛顿法初始点需要足够“靠近”极小点,否则,有可能导致算法不收敛,此时就引入全局牛顿法。全局牛顿法的流程为: i) 给定终止误差值 0 ≤ ε ≪ 1 , δ ∈ ( 0 , 1 ) , σ ∈ ( 0 , 0.5 ) 0\leq \varepsilon \ll 1,\delta \in(0,1),\sigma \in(0,0.5) 0≤ε≪1,δ∈(0,1),σ∈(0,0.5),初始点 x 0 ∈ R n x_0 \in \mathbb{R}^n x0∈Rn,令k = 0; ii) 计算 g k = ▽ f ( x k ) g_k = \bigtriangledown f(x_k) gk=▽f(xk),若 ∥ g k ∥ ≤ ε \left \| g_k \right \| \leq \varepsilon ∥gk∥≤ε,则停止,输出 x ∗ ≈ x k x^* \approx x_k x∗≈xk; iii) 计算 G k = ▽ 2 f ( x k ) G_k = \bigtriangledown^2 f(x_k) Gk=▽2f(xk),并求解线性方程组 G k d = − g k G_kd = -g_k Gkd=−gk得解 d k d_k dk; iv) 设 m k m_k mk是不满足下列不等式的最小非负整数m: f ( x k + δ m d k ) ≤ f ( x k ) + σ δ m g k T d k f(x_k + \delta^m d_k) \leq f(x_k) + \sigma \delta^mg_k^Td_k f(xk+δmdk)≤f(xk)+σδmgkTdk v) 令 α k = δ m , x k + 1 = x k + α k d k , k = k + 1 \alpha_k = \delta^m,x_{k+1} = x_k + \alpha_kd_k,k=k+1 αk=δm,xk+1=xk+αkdk,k=k+1,并转2。
Armijo搜索 全局牛顿法是基于Armijo的搜索,满足Armijo准则: 给定 δ ∈ ( 0 , 1 ) , σ ∈ ( 0 , 0.5 ) , 令 步 长 α k = δ m \delta \in(0,1),\sigma \in(0,0.5),令步长\alpha_k = \delta^m δ∈(0,1),σ∈(0,0.5),令步长αk=δm,其中 m k m_k mk是满足下列不等式的最小非负整数: f ( x k + δ m d k ) ≤ f ( x k ) + σ δ m g k T d k f(x_k + \delta^m d_k) \leq f(x_k) + \sigma \delta^mg_k^Td_k f(xk+δmdk)≤f(xk)+σδmgkTdk
局部加权线性回归模型 在线性回归中会出现欠拟合的情况,局部加权线性回归(LWLR)可以解决这类问题,其给预测点附近的每个点赋予一定的权重,此时的回归系数可以表示为: W ^ = ( X T M X ) − 1 X T M Y \hat{W} = (X^TMX)^{-1}X^TMY W^=(XTMX)−1XTMY M为给每个点的权重。 LWLR使用核函数来对附近的点赋予更高的权重,常用的有高斯核,对应的权重为: M ( i , i ) = e ∣ X i − X ∣ − 2 k 2 M(i,i) = e^{\frac{|X^i-X|}{-2k^2}} M(i,i)=e−2k2∣Xi−X∣ 这样的权重矩阵只含对角元素。当k的值逐渐表小,其拟合数据的能力也在变强。当k取得较大值时,会出现欠拟合;当k取得较小时,会出现过拟合。
算法原理 Softmx函数: f ( X i ) = e − ( W X i + b ) ∑ i = 1 m e − ( W X i + b ) f(X_{i})=\frac{e^{-(WX_{i}+b)}}{\sum_{i=1}^{m} e^{-(WX_{i}+b)}} f(Xi)=∑i=1me−(WXi+b)e−(WXi+b) 则对于每一个样本估计其所属的类别的概率为: P ( y i ) = j ∣ X i ; Θ ) = e Θ j T X i ∑ l = 1 k e Θ j T X l P(y_{i})=j|X_{i};\Theta)=\frac{e^{\Theta_{j}^{T}}X_{i}}{\sum_{l=1}^{k}e^{\Theta_{j}^{T}}X_{l}} P(yi)=j∣Xi;Θ)=∑l=1keΘjTXleΘjTXi
损失函数 略过
1.4 因子分解机(FM)
算法原理 对于因子分解机FM模型,引入度的概念。对于度为2的因子分解机FM的模型为: y ˘ = w 0 + s u m i = 1 n w i x i + ∑ i = 1 n − 1 ∑ i = 1 n < V i , V j > x i x j \breve{y}=w_{0}+sum_{i=1}^{n}w_{i}x_{i}+\sum_{i=1}^{n-1}\sum_{i=1}^{n}<V_{i},V_{j}>x_{i}x_{j} y˘=w0+sumi=1nwixi+∑i=1n−1∑i=1n<Vi,Vj>xixj 其中, < V i , V j > <V_{i},V_{j}> <Vi,Vj>表示的是两个大小为k的向量 V i 和 V j V_{i}和V_{j} Vi和Vj的点积: < V i , V j > = ∑ f = 1 k v i , f ⋅ v j , f <V_{i},V_{j}>=\sum_{f=1}^{k}v_{i,f}\cdot v_{j,f} <Vi,Vj>=∑f=1kvi,f⋅vj,f 其中, V i V_{i} Vi表示的是系数矩阵V的第i维向量,且 V i = ( v i , 1 , v i , 2 , . . . , v i , k ) , k ϵ N + 称 为 超 参 数 V_{i}=(v_{i,1},v_{i,2},...,v_{i,k}),k\epsilon N^{+}称为超参数 Vi=(vi,1,vi,2,...,vi,k),kϵN+称为超参数,且k的大小称为因子分解机FM算法的度。前面两部分是传统的线性模型,最后一部分将两个互异特征分量之间的相互关系考虑进来。
解决的问题 ①回归问题 ②二分类问题 ③排序 上述的FM模型可以直接处理回归问题,对于二分类问题,其最终形式为: h ( X ) = σ ( y ˘ ) h(X)=\sigma(\breve{y}) h(X)=σ(y˘) 其中, σ \sigma σ是阈值函数,通常取为Sigmoid函数: σ ( x ) = 1 1 + e − x \sigma(x)=\frac{1}{1+e^{-x}} σ(x)=1+e−x1
损失函数 使用逻辑损失作为优化的标准: l o s s C ( y ˘ i ⋅ y i ) = ∑ i = 1 m − l n σ ( y ˘ i ⋅ y i ) loss^{C}({\breve{y}_{i}\cdot y_{i}})=\sum_{i=1}^{m}-ln\sigma({\breve{y}_{i}\cdot y_{i}}) lossC(y˘i⋅yi)=∑i=1m−lnσ(y˘i⋅yi)
FM算法中的交叉项处理 这种直接在交叉项的前面加上交叉项系数 w i , j w_{i,j} wi,j的方式,在稀疏数据的情况下存在一个很大的缺陷,即在对于观察样本中未出现交互的特征分量时,不能对相应的参数进行估计。对交叉项的求解,可以采用 ( ( a + b + c ) 2 − a 2 − b 2 − c 2 ) ) / 2 ((a+b+c)^{2}-a^{2}-b^{2}-c^{2}))/2 ((a+b+c)2−a2−b2−c2))/2 对每一个特征分量 x i x_{i} xi引入辅助向量 V i V_{i} Vi,即利用 V i V j T V_{i}V_{j}^{T} ViVjT对交叉项的系数 w i , j w_{i,j} wi,j,这就对应了一种矩阵的分解。对k值的限定、FM的表达能力均有一定的影响。 y ˘ = w 0 + s u m i = 1 n w i x i + ∑ i = 1 n − 1 ∑ i = 1 n w i , j x i x j \breve{y}=w_{0}+sum_{i=1}^{n}w_{i}x_{i}+\sum_{i=1}^{n-1}\sum_{i=1}^{n}w_{i,j}x_{i}x_{j} y˘=w0+sumi=1nwixi+∑i=1n−1∑i=1nwi,jxixj
FM算法流程 随机梯度下降(SGD)在每次迭代的过程中,仅根据一个样本对模型中的参数进行调整。而梯度下降法中,在每一个迭代过程中,利用全部的数据进行模型参数的学习,对于数据量特别大的情况,每次迭代求解需要花费大量的计算成本。: ①初始化权重 w 0 , w 1 , . . . , w n w_{0},w_{1},...,w_{n} w0,w1,...,wn和V ②对每一个样本: w 0 = w 0 − α [ 1 − σ ( y ˘ y ) ] ⋅ y w_{0}=w_{0}-\alpha[1-\sigma(\breve{y}y)]\cdot y w0=w0−α[1−σ(y˘y)]⋅y 对每一个特征: w i = w i − α [ 1 − σ ( y ˘ y ) ] ⋅ y ⋅ x i w_{i}=w_{i}-\alpha[1-\sigma(\breve{y}y)]\cdot y\cdot x_{i} wi=wi−α[1−σ(y˘y)]⋅y⋅xi ③重复步骤2,直到满足终止条件
1.5 支持向量机(SVM)
感知机算法 在感知机算法中直接使用通误分类的样本到分隔超平面之间的距离S作为其损失函数,并利用梯度下降法求得误分类的损失函数的极小值,得到最终的分隔超平面。 感知机算法的损失函数为: J ( W , b ) = − ∑ i = 1 m y i ( W ⋅ X i + b ) J(W,b)=-\sum_{i=1}^{m}y_{i}(W\cdot X_{i}+b) J(W,b)=−∑i=1myi(W⋅Xi+b) 通过求解损失函数的最小值 m i n W , b J ( W , b ) min_{W,b}J(W,b) minW,bJ(W,b)求得最终的分隔超平面 ①感知机算法存在的问题 对于感知机算法来说,分隔超平面参数W和b的初始值和选择误分类样本的顺序对最终的分隔超平面的计算都有影响,采用不同的初始值或者不同的误分类点,最终的分隔超平面是不同的。无法判断是否存在最好的分隔超平面。 ②函数间隔 当预测值 W ⋅ X i + b W\cdot X_{i}+b W⋅Xi+b和样本标签 y i y_{i} yi同号时,则表明最终的分类是正确的。 i 样本点到分隔超平面的函数间隔为: d i = y i ˘ ( W ⋅ X i + b ) d_{i} = \breve{y_{i}}(W\cdot X_{i}+b) di=yi˘(W⋅Xi+b) ii 同时分隔超平面到训练集中所有样本点的函数间隔的最小值: m i n i = 1 , . . , m ( d i ) min_{i=1,..,m}(d_{i}) mini=1,..,m(di) ③几何间隔 在函数间隔的基础上进行归一化就是几何间隔
支持向量机 与感知机算法不同,在支持向量机中,求解出的分隔超平面不仅能够正确划分训练数据集,而且几何间隔最大。它使用一种非线性映射,把原训练数据映射到较高的维上。在新的维上,它搜索最佳分离超平面。使用到足够高维上的、合适的非线性映射,两个类的数据总可以被超平面分开。 在m个训练样本中,与分隔超平面距离最近的样本称为支持向量。支持向量 X i X_{i} Xi对应着约束条件为: y i ( W ⋅ X i + b ) − 1 = 0 y_{i}(W\cdot X_{i}+b)-1=0 yi(W⋅Xi+b)−1=0 得到的两个超平面被称为间隔边界,我们的目标就是选择最大间隔: a r g max w , b ( m i n ( y ( w T x + b ) ) ⋅ 1 ∥ w ∥ ) arg\max_{w,b} (min(y(w^{T}x+b))\cdot \frac{1}{\left \| w \right \|}) argmaxw,b(min(y(wTx+b))⋅∥w∥1) 通过设置边界间隔为1,上述公式可以等价为为: m i n W , b 1 2 ∥ w ∥ 2 min_{W,b} \frac{1}{2}\left \|w \right \|^{2} minW,b21∥w∥2 ①线性支持向量机 对于线性不可分的某些样本点,意味着其不能满足函数间隔大于或等于1的约束条件,为了解决这个问题,可以对每个样本点引进一个松弛变量 ξ i > = 0 \xi_{i}>=0 ξi>=0,使得函数间隔加上松弛变量大于或等于1,这样约束条件变为: y i ( W ⋅ X i + b ) + ξ i > = 1 y_{i}(W\cdot X_{i}+b)+\xi_{i}>=1 yi(W⋅Xi+b)+ξi>=1 同时,对每个松弛变量 ξ i \xi_{i} ξi,支付一个代价C,此时,优化的目标函数变为: m i n W , b 1 2 ∥ w ∥ 2 + C ∑ i = 1 m ξ i min_{W,b} \frac{1}{2}\left \|w \right \|^{2}+C\sum_{i=1}^{m}\xi_{i} minW,b21∥w∥2+C∑i=1mξi
选最佳划分标准 在决策树算法中,通常有这些标准:信息增益(Information Gain)、增益率(Gain Ratio)和基尼指数(Gini Index)。 熵(Entropy)是度量样本集合纯度最常用的一种指标,信息熵表示的数据集中的不纯度,信息熵越小表明数据集纯度提升了。在数据集D中,第k类的样本所占的比例为 p k p_{k} pk,则数据集D的信息熵为: E n t r o p y ( D ) = − ∑ k = 1 K p k l o g 2 p k Entropy(D) = -\sum_{k=1}^{K}p_{k}log_{2}p_{k} Entropy(D)=−∑k=1Kpklog2pk 其中,K表示的是数据集D中类别的个数。 ①信息增益:对于给定的数据集,划分前后信息熵的减少量称为信息增益。(ID3决策树算法) i g a i n ( D , A ) = E n t r o p y ( D ) − ∑ p = 1 P ∣ D p ∣ D E n t r o p y ( D p ) igain(D,A) = Entropy(D) - \sum_{p=1}^{P}\frac{\left |D_{p} \right |}{D} Entropy(D_{p}) igain(D,A)=Entropy(D)−∑p=1PD∣Dp∣Entropy(Dp) ②增益率:例如考虑充当唯一标识符的属性,如product_ID,划分会导致大量分区(与值一样多),每个只包含一个元组,此时Entropy(D)=0,信息增益最大,显然这种划分对分类没有用。鉴于这点,增益率用“分裂信息”值将信息增益规范化。(C4.5决策树算法) I V ( A ) = − ∑ p = 1 P ∣ D p ∣ ∣ D ∣ l o g 2 ∣ D p ∣ ∣ D ∣ IV(A) = -\sum_{p=1}^{P}\frac{|D_{p}|}{|D|}log_{2}\frac{|D_{p}|}{|D|} IV(A)=−∑p=1P∣D∣∣Dp∣log2∣D∣∣Dp∣ 其中,IV(A)被称为特征A的“固有值”。增益率的计算方法为: g a i n _ r a t i o ( D , A ) = i g a i n ( D , A ) I V ( A ) gain\_ratio(D,A) = \frac{igain(D,A)}{IV(A)} gain_ratio(D,A)=IV(A)igain(D,A) ③基尼指数:对于数据集D,假设有K个分类,则样本属于第k个类的概率为 p k p_{k} pk,则此概率分布的基尼指数为:(CART分类树算法) G i n i ( p ) = ∑ k = 1 K p k ( 1 − p k ) = 1 − ∑ k = 1 K p k 2 Gini(p) = \sum_{k=1}^{K}p_{k}(1-p_{k}) = 1 - \sum_{k=1}^{K}p_{k}^2 Gini(p)=∑k=1Kpk(1−pk)=1−∑k=1Kpk2 停止划分的标准主要有:i)结点中的样本数小于给定阈值;ii)样本集的基尼指数小于给定阈值(样本基本属于同一类);iii)没有更多特征。
随机森林算法(RF)(Bagging) 随机森林(RF)算法是一种重要的基于Bagging的集成学习方法,可以用来做分类、回归问题。随机森林算法是由一系列的决策树组成,它通过自助法(Bootstrap)重采样技术,从原始训练样本集中有放回地重复随机抽取m个样本,生成新的训练样本集合,然后根据自助样本集生成k个分类树组成随机森林,新数据的分类结果按分类树投票多少形成的分数而定。特征选择采用随机的方法去分裂每一个节点,然后比较不同情况下产生的误差。 随机森林算法是通过训练多个决策树,生成模型,然后综合利用多个决策树进行分类。随机森林算法只需要两个参数:构建的决策树的个数 n t r e e n_{tree} ntree,在决策树的每个节点进行分裂时需要考虑的输入特征的个数k,通常k可以取为 l o g 2 n log_{2}n log2n,其中n表示的是原数据集中特征的个数。对于单棵决策树的构建,可以分为如下步骤: ①假设训练样本的个数为m,则对于每一棵决策树的输入样本的个数都为m,且这m个样本是通过从训练集中有放回地随机抽取得到的。 ②假设训练样本特征的个数为n,对于每一棵决策树的样本特征是从该n个特征中随机挑选k个,然后从这k个输入特征里选择一个最好的进行分裂。 ③每棵树都一直这样分裂下去,直到该节点的所有训练样例都属于同一类。在决策树分裂过程中不需要剪枝。
GBDT算法(Gradient-Boosting) GBDT主要由三个概念组成:Regression Decistion Tree(即DT),Gradient Boosting(即GB),Shrinkage (算法的一个重要演进分枝,目前大部分源码都按该版本实现)。搞定这三个概念后就能明白GBDT是如何工作的,要继续理解它如何用于搜索排序则需要额外理解RankNet概念,之后便功德圆满。下文将逐个碎片介绍,最终把整张图拼出来。 ①DT:回归树 Regression Decision Tree GBDT中的树都是回归树,不是分类树。回归树的运行流程与分类树基本类似,但有以下两点不同之处: i)第一,回归树的每个节点得到的是一个预测值而非分类树式的样本计数,假设在某一棵树的某一节点使用了年龄进行分枝(并假设在该节点上人数>1),那么这个预测值就是属于这个节点的所有人年龄的平均值。 ii)第二,在分枝节点的选取上,回归树并没有选用最大熵值来作为划分标准,而是使用了最小化均方差,即 ∑ i = 1 n ( x i − x ˉ ) 2 n \frac{\sum_{i=1}^{n}{} (x_i-\bar{x} )^2}{n} n∑i=1n(xi−xˉ)2。这很好理解,被预测出错的次数越多,错的越离谱,均方差就越大,通过最小化均方差也就能够找到最靠谱的分枝依据。 ②GB:梯度迭代 Gradient Boosting GB本身是一种理念而非一个具体的算法,其基本思想为:沿着梯度方向,构造一系列的弱分类器函数,并以一定权重组合起来,形成最终决策的强分类器。 举一个简单的例子:同样使用年龄进行分枝,假设我们A的真实年龄是18岁,但第一棵树的预测年龄是12岁,即残差为6岁。那么在第二棵树里我们把A的年龄设为6岁去学习,如果第二棵树真的能把A分到6岁的叶子节点,那累加两棵树的结论就是A的真实年龄;如果第二棵树的结论是5岁,则A仍然存在1岁的残差,第三棵树里A的年龄就变成1岁……以此类推学习下去,这就是梯度提升在GBDT算法中的直观意义。 ③Shrinkage Shrinkage是GBDT的第三个基本概念,中文含义为“缩减”。它的基本思想就是:每次走一小步逐渐逼近结果的效果,要比每次迈一大步很快逼近结果的方式更容易避免过拟合。换句话说缩减思想不完全信任每一个棵残差树,它认为每棵树只学到了真理的一小部分,累加的时候只累加一小部分,只有通过多学几棵树才能弥补不足。Shrinkage仍然以残差作为学习目标,但由于它采用的是逐步逼近目标的方式,导致各个树的残差是渐变的而不是陡变的。 最后小结一下GBDT算法的优缺点。 优点: 预测精度高;适合低维数据;能处理非线性数据 缺点: 并行麻烦(因为上下两棵树有联系);如果数据维度较高时会加大算法的计算复杂度
XGBoost算法 GBDT是一种基于集成思想下的Boosting学习器,并采用梯度提升的方法进行每一轮的迭代最终组建出强学习器,这样的话算法的运行往往要生成一定数量的树才能达到令我们满意的准确率。当数据集大且较为复杂时,运行一次极有可能需要几千次的迭代运算,这将对我们使用算法造成巨大的计算瓶颈。可以说,XGBoost是Gradient Boosting的高效实现。XGBoost最大的特点在于它能够自动利用CPU的多线程进行并行计算,同时在算法上加以改进提高了精度。 ①目标函数:损失与正则 在监督学习中,我们通常会构造一个目标函数和一个预测函数,使用训练样本对目标函数最小化学习到相关的参数,然后用预测函数和训练样本得到的参数来对未知的样本进行分类的标注或者数值的预测。在XGBoost中,目标函数的形式为: O b j ( Θ ) = L ( θ ) + Ω ( Θ ) Obj(\Theta) = L(\theta) + \Omega(\Theta) Obj(Θ)=L(θ)+Ω(Θ) i) L ( θ ) L(\theta) L(θ):损失函数,常用损失函数有: 平方损失: L ( θ ) = ∑ i ( y i − y ^ i ) 2 L(\theta) = \sum_i (y_i-\hat{y}_i)^2 L(θ)=∑i(yi−y^i)2 L o g i s t i c 损 失 : L ( θ ) = ∑ i [ y i ln ( 1 + e − y ^ i ) + ( 1 − y i ) ln ( 1 + e y ^ i ) ] Logistic损失:L(\theta) = \sum_i[ y_i\ln (1+e^{-\hat{y}_i}) + (1-y_i)\ln (1+e^{\hat{y}_i})] Logistic损失:L(θ)=∑i[yiln(1+e−y^i)+(1−yi)ln(1+ey^i)] ii) Ω ( Θ ) \Omega(\Theta) Ω(Θ):正则化项,之所以要引入它是因为我们的目标是希望生成的模型能准确的预测新的样本(即应用于测试数据集),而不是简单的拟合训练集的结果(这样会导致过拟合)。所以需要在保证模型“简单”的基础上最小化训练误差,这样得到的参数才具有好的泛化性能。而正则项就是用于惩罚复杂模型,避免预测模型过分拟合训练数据,常用的正则有 L 1 L_1 L1正则与 L 2 L_2 L2正则。 ②目标函数的迭代与泰勒展开
如果移除掉常数项,我们会发现这个目标函数有一个非常明显的特点,它只依赖于每个数据点的在误差函数上的一阶导数和二阶导数( ∑ i = 1 n [ g i f t ( x i ) + 1 2 h i f t 2 ( x i ) ] + Ω ( f t ) \sum_{i=1}^n [g_i f_t(x_i) + \frac{1}{2} h_i f_t^2(x_i)] + \Omega(f_t) ∑i=1n[gift(xi)+21hift2(xi)]+Ω(ft)) ③决策树的复杂度
当给定一个未知的元组时,k-最近邻分类法搜索模式空间,找出最接近未知元组的k个训练元组。这k个训练元组时未知元组的k个“最近邻”。 “邻近性”用距离度量,如欧几里得距离: d i s t ( X 1 , X 2 ) = ∑ i = 1 n ( x 1 i − x 2 i ) 2 dist(X_1,X_2) = \sqrt{\sum_{i=1}^{n}(x_{1i}-x_{2i})^2} dist(X1,X2)=∑i=1n(x1i−x2i)2 通常在上述操作之前会把每个属性的值规范化,通过最小-最大规范化把数值属性A的值v变换到[0,1]区间中的v’ v ′ = v − m i n A m a x A − m i n A v' = \frac{v-min_A}{max_A-min_A} v′=maxA−minAv−minA KNN特点: ①原理简单。 ②保存模型需要保存全部样本集。 ③训练过程很快,预测速度很慢。 使用KNN模型时请注意一下几点: ①发扬KNN模型的特性。如果一个数据任务类别清晰,可以考虑运用KNN(如一段文本是新闻还是娱乐)。反之,如果任务类别不清晰则模型效果不会太好(如点击事件预测或股票等混沌市场预测) ②规避工程执行的短处。对于稀疏特征值的数据,如词文本,可以考虑做索引表,记录词的出现位置,拿存储代价换计算代价;密集特征值数据可以考虑kd-tree等数据结构。
岭回归 岭回归是在平方误差的基础上增加L2正则项: l = ∑ i = 1 m ( y i − ∑ j = 0 n − 1 w j ⋅ x i j ) 2 + λ ∑ j = 0 n w j 2 l =\sum_{i=1}^{m}(y_i - \sum_{j=0}^{n-1}w_j \cdot x_{ij})^2 + \lambda \sum_{j=0}^{n}w_j^2 l=∑i=1m(yi−∑j=0n−1wj⋅xij)2+λ∑j=0nwj2 其中, λ > 0 \lambda > 0 λ>0。通过确定 λ \lambda λ的值可以使得方差和偏差之间达到平衡:随着 λ \lambda λ的增大,模型方差减小而偏差增大。 与线性回归模型一样,在利用最小二乘法求解岭回归模型的参数时,首先对W求导,结果为: 2 X T ( Y − X W ) − 2 λ W 2X^T(Y-XW)-2\lambda W 2XT(Y−XW)−2λW 令其为0,可求得W的值为: W ^ = ( X T X + λ I ) − 1 X T Y \hat{W} = (X^TX+\lambda I)^{-1}X^TY W^=(XTX+λI)−1XTY 其中I是单位对角矩阵。
Lasso回归 Lasso采用的则是L1正则,即Lasso是在平方误差的基础上增加L1正则: l = ∑ i = 1 m ( y i − ∑ j = 0 n − 1 w j ⋅ x i j ) 2 + λ ∑ j = 0 n ∣ w j ∣ l =\sum_{i=1}^{m}(y_i - \sum_{j=0}^{n-1}w_j \cdot x_{ij})^2 + \lambda \sum_{j=0}^{n}|w_j| l=∑i=1m(yi−∑j=0n−1wj⋅xij)2+λ∑j=0n∣wj∣
2 聚类算法
聚类算法是对事物自动归类的一类算法,是一种典型的无监督的学习算法,通过定义不同的相似性的度量方法,将具有相似属性的事物聚集到同一个类中。通常在机器学习算法中使用到的距离函数主要有: 假设有两个点,分别为点P和点Q,其对应的坐标分别为: P = ( x 1 , x 2 , . . . , x n ) ∈ R n P = (x_1,x_2,...,x_n)\in \mathbb{R}^n P=(x1,x2,...,xn)∈Rn Q = ( y 1 , y 2 , . . . , y n ) ∈ R n Q = (y_1,y_2,...,y_n)\in \mathbb{R}^n Q=(y1,y2,...,yn)∈Rn ①闵可夫斯基距离 d ( P , Q ) = ( ∑ i = 1 n ( x i − y i ) p ) 1 p d(P,Q) = (\sum_{i=1}^{n}(x_i-y_i)^p)^{\frac{1}{p}} d(P,Q)=(∑i=1n(xi−yi)p)p1 ②曼哈顿距离 d ( P , Q ) = ∑ i = 1 n ∣ x i − y i ∣ d(P,Q) = \sum_{i=1}^{n}|x_i-y_i| d(P,Q)=∑i=1n∣xi−yi∣ ③欧氏距离 d ( P , Q ) = ∑ i = 1 n ( x i − y i ) 2 d(P,Q) = \sqrt {\sum_{i=1}^{n}(x_i-y_i)^2} d(P,Q)=∑i=1n(xi−yi)2
K-Means++算法 为了解决因为初始化的问题带来K-Means算法的问题,K-Means++算法被提出。其思想是:在聚类中心的初始化过程中的基本原则是使得初始的聚类中心之间的相互距离尽可能远,这样可以避免出现上述的问题。初始化过程如下: ①在数据集中随机选择一个样本点作为第一个初始化的聚类中心; ②选择出其余的聚类中心: i) 计算样本中的每一个样本点与已经初始化的聚类中心之间的距离,并选择其中最短的距离,记为 d i d_i di; ii) 以概率选择距离最大的样本作为新的聚类中心,重复上述过程,直到k个聚类中心都被确定。 ③对k个初始化的聚类中心,利用K-Means算法计算最终的聚类中心。
2.2 均值漂移算法(Mean Shift)
与K-Means算法一样,都是基于聚类中心的聚类算法,不同的是,Mean Shift算法不需要事先指定类别个数k。在Mean Shift算法中,聚类中心是通过在给定区域中的样本的均值来确定的,通过不断更新聚类中心,直到最终的聚类中心不再改变为止。其在聚类,图像平滑、分隔和视频跟踪等方面有广泛的应用。 M h ( X ) = 1 k ∑ X i ∈ S h ( X i − X ) M_h(X) = \frac{1}{k}\sum_{X_i \in S_h}(X_i-X) Mh(X)=k1∑Xi∈Sh(Xi−X) 其中, S h S_h Sh指的是一个半径为h的高维球区域。定义为: S h ( x ) = ( y ∣ ( y − x ) ( y − x ) T ≤ h 2 ) S_h(x) = (y|(y-x)(y-x)^T\leq h^2) Sh(x)=(y∣(y−x)(y−x)T≤h2) 在Mean Shift算法中引入核函数的目的是使得样本与被漂移点的距离不同,其漂移量对均值漂移向量的贡献也不同。 K ( x 1 − x 2 h ) = 1 2 π h e − ( x 1 − x 2 ) 2 2 h 2 K(\frac{x_1-x_2}{h})=\frac{1}{\sqrt {2π}h}e^{-\frac{(x_1-x_2)^2}{2h^2}} K(hx1−x2)=2πh1e−2h2(x1−x2)2 由高斯核函数的图像可以看出,当带宽h一定时,样本点之间的距离越近,其核函数的值越大;当样本点之间的距离相等时,随着高斯核函数的带宽h的增大,核函数的值在减小。
算法原理 向基本的Mean Shift向量形式中增加核函数,得到如下的改进的Mean Shift向量形式: M h ( X ) = ∑ X i ∈ S h [ K ( X i − X h ) ( X i − X ) ] ∑ X i ∈ S h [ K ( X i − X h ) ] M_h(X) = \frac{\sum_{X_i \in S_h}[K(\frac{X_i-X}{h})(X_i-X)]}{\sum_{X_i \in S_h}[K(\frac{X_i-X}{h})]} Mh(X)=∑Xi∈Sh[K(hXi−X)]∑Xi∈Sh[K(hXi−X)(Xi−X)] 在Mean Shift算法中,通过迭代的方式找到最终的聚类中心,即对每一个样本点计算其漂移均值,以计算出来的漂移均值点作为新的起始点,重复以上的步骤,直到满足终止的条件,得到的最终的均值漂移点即为最终的聚类中心。
算法的解释 在Mean Shift算法中,实际上利用了概率密度,求得概率密度的局部最优解。 偏移向量 M h ( X ) M_h(X) Mh(X)与概率密度函数 f ( X ) f(X) f(X)的梯度成正比,因此Mean Shift向量总是指向概率密度增加的方向。
2.3 密度聚类算法(DBSCAN)
与基于距离的聚类算法不同的是,基于密度的聚类算法可以发现任意形状的聚类(包括非球状的数据)
算法原理 在DBSCAN算法中,有两个基本的邻域参数,分别为 ε \varepsilon ε邻域和MinPts。其中 ε \varepsilon ε邻域表示的是在数据集D中与样本点 x + i x+i x+i的距离不大于 ε \varepsilon ε的样本。MinPts表示的是在样本点 x i x_i xi的 ε \varepsilon ε邻域内最少样本点的数目。基于这两个参数,在DBSCAN算法中将数据点分为以下三类: ①核心点。若 x i x_i xi的邻域内至少包含了MinPts个样本,则称样本点 x i x_i xi为核心点。 ②边界点。若样本 x i x_i xi的邻域内包含的样本数目少于MinPts,但是它在其他核心点的邻域内,则称该样本点 x i x_i xi为边界点。 ③噪音点。指既不是核心点也不是;边界点的点。 几个概念: ①直接密度可达。在邻域内的两点。 ②密度可达。两点虽然不在同一个邻域内,但是存在一中间点直接密度可达 ③密度连接。两点都从某点密度可达,则两点密度连接。
Ada-Boosting:核心思想是使序列的下一个模型更关注之前的错误样本。具体的执行步骤如下: ①为整个数据集的每个样本分配一个权重 s 1 , s 2 . . . , s m s_{1},s_{2}...,s_{m} s1,s2...,sm,直观理解:权重代表模型在训练时对样本的“重视度”。 ②在整个数据集上训练模型 m i m_{i} mi,并执行分类预测,对应的正确率为 a c c i acc_{i} acci。 ③评估模型 M i M_{i} Mi对每个样本j的分类正确与否,如果分错该样本,则增大样本对应的权重 s j s_{j} sj,即让下一个模型更关注之前的错误样本。 ④重复步骤2至3,直至构造出n个模型个体。 ⑤归一化序列 [ a c c 1 , a c c 2 , . . . , a c c n ] [acc_{1},acc_{2},...,acc_{n}] [acc1,acc2,...,accn],使其累加和等于1,得到新的序列 [ w 1 , w 2 , . . . , w n ] [w_{1},w_{2},...,w_{n}] [w1,w2,...,wn],最终模型对某个类别的预测概率值等于每个模型预测的加权和: M ( M 1 , M 2 , . . . , M n ) = ∑ i w i ⋅ M i M(M_{1},M_{2},...,M_{n}) = \sum_{i}w_{i}\cdot M_{i} M(M1,M2,...,Mn)=∑iwi⋅Mi。 对于回归问题,替换第2步的评估指标,最终模型按每个模型个体预测值加权和得出即可。从上面的流程可以想象得到,因为每个模型对样本的关注权重不同,所以保证了模型个体的差异。同时,这个执行流程越往后执行,训练出的模型就越会在意那些前面模型容易出错(权重高)的样本。
Gradient-Boosting:核心思想是:序列的后续模型不再直接预测数据集的预测值,而是预测之前模型的预测值和真实值的差值。 ①训练模型 M 1 M_{1} M1,得出预测值,这时模型的整体预测值为y_pred = y _ p r e d 1 y\_pred_{1} y_pred1。 ②计算上一步预测值和真实值的差值: d y 1 = y _ p r e d 1 − y dy_{1}=y\_pred_{1}-y dy1=y_pred1−y,将这个值作为模型 M 2 M_{2} M2待预测的目标值,模型转而开始预测之前模型的预测值和真实值的差值。这时,总模型的预测值为y_pred = y _ p r e d 1 + d y _ p r e d 2 y\_pred_{1} + dy\_pred_{2} y_pred1+dy_pred2。 ③模型 M i + 1 M_{i+1} Mi+1预测前i个模型预测值之和和真实值之间的差值,这一步用到了梯度下降和模型前i个模型中的预测值和真实值的差值: d y 1 , . . . , d y i dy_{1},...,dy_{i} dy1,...,dyi,获得预测值 d y _ p r e d i + 1 dy\_pred_{i+1} dy_predi+1。 ④重复第二步,得到多个预测数值序列 [ d y 1 , d y 2 , . . . , d y n ] [dy_{1},dy_{2},...,dy_{n}] [dy1,dy2,...,dyn],最终的融合预测为: y _ p r e d = y _ p r e d 1 + ∑ i d y _ p r e d i y\_pred = y\_pred_{1} + \sum_{i}dy\_pred_{i} y_pred=y_pred1+∑idy_predi
自编码器(无监督学习算法)是一种用于训练相邻两层网络模型的一种方法。 自编码器首先将输入X映射到一个隐含层(非线性映射)输出H: H = σ ( W 1 X + b 1 ) H = \sigma(W_1X+b_1) H=σ(W1X+b1) 然后利用H重构输出Z,输出层Z可以看成是利用特征H对原始数据X的预测: Z = σ ( W 2 X + b 2 ) Z = \sigma(W_2X+b_2) Z=σ(W2X+b2) 对于解码过程中的权重矩阵W_2可以看成是编码过程的逆过程,即 W 2 = W 1 T W_2 = W_1^T W2=W1T
降噪自编码器 输入样本为X,降噪自编码器以概率p将输入层节点的值置为0,得到含有噪音的输入样本 X ^ \hat{X} X^。利用含有噪音的输入样本 X ^ \hat{X} X^训练自编码器模型,通过编码encode过程得到隐含层的输出H,并通过解码decode过程得到最终的重构样本Z,最终通过度量重构样本Z和不含噪音的样本X之间的误差L(X,Z)。 利用降噪自编码器构建深度网络中,主要包括两个过程:z ①无监督逐层训练,即依次训练多个降噪自编码器,这样逐层训练的过程被称为预训练; ②有监督的微调,即将训练好的多个降噪自编码器Encoder层组合,利用样本标签对训练好的降噪自编码器的编码Encoder层的参数。 其训练过程为: ①初始化各层网络的权重W和偏置b; ②利用损失函数,调整各层网络的权重和偏置。 对权重和偏置调整的过程 被称为有监督的微调。
细想BP算法,CNN(卷积神经网络)我们会发现, 他们的输出都是只考虑前一个输入的影响而不考虑其它时刻输入的影响, 比如简单的猫,狗,手写数字等单个物体的识别具有较好的效果. 但是, 对于一些与时间先后有关的, 比如视频的下一时刻的预测,文档前后文内容的预测等, 这些算法的表现就不尽如人意了.因此, RNN就应运而生了。 RNN是一种特殊的神经网络结构, 它是根据"人的认知是基于过往的经验和记忆"这一观点提出的。它与DNN,CNN不同的是::它不仅考虑前一时刻的输入,而且赋予了网络对前面的内容的一种“记忆”功能。 RNN之所以称为循环神经网路,即一个序列当前的输出与前面的输出也有关。具体的表现形式为网络会对前面的信息进行记忆并应用于当前输出的计算中,即隐藏层之间的节点不再无连接而是有连接的,并且隐藏层的输入不仅包括输入层的输出还包括上一时刻隐藏层的输出。 RNN的应用领域有很多, 可以说只要考虑时间先后顺序的问题都可以使用RNN来解决.这里主要说一下几个常见的应用领域: ① 自然语言处理(NLP): 主要有视频处理, 文本生成, 语言模型, 图像处理 ② 机器翻译, 机器写小说 ③ 语音识别 ④ 图像描述生成 ⑤ 文本相似度计算 ⑥ 音乐推荐、网易考拉商品推荐、Youtube视频推荐等新的应用领域.
4.7 长短期记忆网络(LSTM)
遗忘门 在我们 LSTM 中的第一步是决定我们会从细胞状态中丢弃什么信息。这个决定通过一个称为忘记门层完成。该门会读取 h t − 1 h_{t-1} ht−1和 x t x_t xt ,输出一个在 0到 1之间的数值给每个在细胞状态 C t − 1 C_{t-1} Ct−1中的数字。1 表示“完全保留”,0 表示“完全舍弃”。其中 h t − 1 h_{t-1} ht−1表示的是上一个cell的输出, x t x_t xt 表示的是当前细胞的输入。σ 表示sigmod函数。
现在是更新旧细胞状态的时间了, C t − 1 C_{t-1} Ct−1更新为 C t C_t Ct。前面的步骤已经决定了将会做什么,我们现在就是实际去完成。我们把旧状态与 f t f_t ft相乘,丢弃掉我们确定需要丢弃的信息。接着加上 i t ∗ C ~ t i i_t * \tilde{C}_ti it∗C~ti。这就是新的候选值,根据我们决定更新每个状态的程度进行变化。
相似度的度量方法 相似性的度量方法必须满足拓扑学中的度量空间的基本条件: ①非负性。 d ( x , y ) ⩾ 0 d(x,y) \geqslant0 d(x,y)⩾0,当且仅当两者相等时为0 ②对称性。 d ( x , y ) = d ( y , x ) d(x,y) = d(y,x) d(x,y)=d(y,x) ③三角不等性。 d ( x , z ) ≤ d ( x , y ) + d ( y , z ) d(x,z) \leq d(x,y) +d(y,z) d(x,z)≤d(x,y)+d(y,z) 下文主要介绍三种相似性度量方法: ①欧氏距离(根号差平方),受特征量级影响。 ②皮尔逊相关系数 C o r r ( X , Y ) = < X − X ˉ , Y − Y ˉ > ∣ ∣ X − X ˉ ∣ ∣ ∣ ∣ Y − Y ˉ ∣ ∣ Corr(X,Y)=\frac{<X-\bar{X},Y-\bar{Y}>}{||X-\bar{X}||||Y-\bar{Y}||} Corr(X,Y)=∣∣X−Xˉ∣∣∣∣Y−Yˉ∣∣<X−Xˉ,Y−Yˉ> 其中 < X , Y > <X,Y> <X,Y>表示两向量的内积, ∣ ∣ X ∣ ∣ ||X|| ∣∣X∣∣表示向量X的范数 ∑ i x i 2 \sqrt{\sum_ix_i^2} ∑ixi2。 ③余弦相似度 C o s S i m ( X , Y ) = < X , Y > ∣ ∣ X ∣ ∣ ∣ ∣ Y ∣ ∣ CosSim(X,Y)=\frac{<X,Y>}{||X||||Y||} CosSim(X,Y)=∣∣X∣∣∣∣Y∣∣<X,Y>
在基于用户或者基于项的协同过滤算法因为要计算用户与用户或者项与项之间的相关性,计算量比价奥达,难以实现大数据量下的实时推荐。 基于模型的协同过滤算法有效地解决了实时推荐的问题,在基于模型的协同过滤算法中,利用历史的用户-商品数据训练得到模型,并利用该模型实现实时推荐。矩阵分解(MF)就是其中一种。 矩阵分解就是把用户-商品矩阵转换成多个矩阵的乘积。 基于矩阵分解的推荐算法过程: ①对用户商品矩阵分解;②利用分解后的矩阵预测原始矩阵中的未打分项。 目标模型: R m × n ≈ P m × k × Q k × n = R ^ m × n R_{m\times n} \approx P_{m\times k} \times Q_{k\times n} = \hat{R}_{m\times n} Rm×n≈Pm×k×Qk×n=R^m×n 损失函数: 原始矩阵与重新构建的评分矩阵之间的误差平方。
5.3 基于图的推荐算法
二分图又称作二部图,是图论中的一种特殊模型。 设G=(V,E)是一个无向图,如果顶点V可分割为两个互不相交的子集(A,B),并且图中的每条边(i,j)所关联的两个顶点i和j分别属于这两个不同的顶点集(i in A,j in B),则称图G为一个二分图。 用户-商品表可以转换成二部图的形式。
PersonalRank算法的流程 PersonaliRank算法通过连接的边为每个节点打分,在PersonaliRank算法中,不区分用户和商品,因此上述的计算用户 U 1 U_1 U1对所有商品的感兴趣的程度,就变成了对用户 U 1 U_1 U1计算各个节点 U 2 U_2 U2,…, U n U_n Un, D 2 D_2 D2,…, D n D_n Dn的重要程度。具体流程如下: ①初始化(除了自己为1,其他全设为0) ②开始在图上游走,每次选择PR值不为0的节点开始,沿着边往前的概率为α,停在当前点的概率为1-α,不断更新PR值,直到收敛为止。
文章浏览阅读443次。1.下载mongodb wget https://fastdl.mongodb.org/linux/mongodb-linux-x86_64-2.6.7.tgz?_ga=1.61439151.2035670845.1415171196解压缩mongodb-linux-x86_64-2.6.7.tgztar -zxvf mongodb-linux-x86_64-2.6.7.tgz m_-bash: mongod--dbpath=/root/data/db/-fork: no such file or directory
文章浏览阅读1.6w次,点赞24次,收藏89次。tnsorflow2.0如何解决ModuleNotFoundError: No module named 'tensorflow.examples'问题_modulenotfounderror: no module named 'tensorflow.examples
文章浏览阅读1.9k次。分布式系统:部署在不同的节点,通过网络通信实现协同工作。CAP理解:C:Consistency, all nodes see the same data at the same time;强一致性就是在客户端任何时候看到各节点的数据都是一致的。A:Availability, reads and writes always succeed;高可用性就是在任何时候都可以读写。P:Par_如何理解分布式系统中的cap定理