单标签多分类及多标签多分类算法

一时失言乱红尘 2023-05-28 11:17 22阅读 0赞

## 1、单标签二分类算法 ##

单标签二分类这种问题是我们最常见的算法问题，主要是指label标签的取值只有两种，并且算法中只有一个需要预测的label标签。直白来讲就是每个实例的可能类别只有两种（A or B）。此时的分类算法其实是在构建一个分类线将数据划分为两个类别。常见的算法有：Logistic、SVM、KNN等。  
 y = f ( x ) ,       y ∈ \{ − 1 , + 1 \} y=f(x),\\ \\ \\ \\ \\ y\\in\\\{-1, +1\\\} y=f(x),     y∈\{ −1,\+1\}

###### Logistic算法 ######

s i g m o i d = h θ ( x ) = 1 1 + e − θ T x J ( θ ) = − 1 m \[ ∑ i = 1 m y ( i ) log ⁡ h θ ( x ( i ) ) + ( 1 − y ( i ) ) log ⁡ ( 1 − h θ ( x ( i ) ) ) \] ,       y ( i ) ∈ \{ 0 , 1 \} \\begin\{aligned\} sigmoid&=h\_\{\\theta\}(x) \\\\ &=\\frac\{1\}\{1+e^\{-\\theta^Tx\}\} \\\\ J(\\theta)&=-\\frac\{1\}\{m\}\[\\sum\_\{i=1\}^my^\{(i)\}\\log h\_\{\\theta\}(x^\{(i)\})+(1-y^\{(i)\})\\log(1-h\_\{\\theta\}(x^\{(i)\}))\], \\ \\ \\ \\ \\ y^\{(i)\}\\in\\\{0, 1\\\} \\end\{aligned\} sigmoidJ(θ)=hθ(x)=1\+e−θTx1=−m1\[i=1∑my(i)loghθ(x(i))\+(1−y(i))log(1−hθ(x(i)))\],     y(i)∈\{ 0,1\}  
![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dvbmd4aWZhY2FpX2JlbGlldmU_size_16_color_FFFFFF_t_70_pic_center][]

## 2、单标签多分类算法 ##

单标签多分类问题其实是指待预测的label标签只有一个，但是label标签的取值可能有多种情况。直白来讲就是每个实例的可能类别有K种 ( t 1 , t 2 , … , t k , k ≥ 3 ) (t\_1, t\_2, \\dots, t\_k ,k\\ge3) (t1,t2,…,tk,k≥3)。常见算法：Softmax、KNN等。  
 y = f ( x ) ,        y ∈ \{ t 1 , t 2 , … , t k \} D = \{ ( x 1 , y 1 ) , ( x 2 , y 2 ) , … , ( x n , y n ) \} y i = j ,      i = 1 , 2 , … , n      j = 1 , 2 , … , k \\begin\{aligned\} y&=f(x),\\ \\ \\ \\ \\ \\ y\\in\\\{t\_1, t\_2, \\dots, t\_k\\\} \\\\ D&=\\\{(x\_1, y\_1), (x\_2, y\_2), \\dots, (x\_n, y\_n)\\\} \\\\ y\_i&=j, \\ \\ \\ \\ i=1, 2, \\dots, n \\ \\ \\ \\ j=1, 2, \\dots, k \\end\{aligned\} yDyi=f(x),      y∈\{ t1,t2,…,tk\}=\{ (x1,y1),(x2,y2),…,(xn,yn)\}=j,    i=1,2,…,n    j=1,2,…,k

###### Softmax算法 ######

p ( y = k ∣ x ; θ ) = e θ k T x ∑ l = 1 K e θ l T x ,       k = 1 , 2 , … , K h θ ( x ) = \[ p ( y ( i ) = 1 ∣ x ( i ) ; θ ) p ( y ( i ) = 2 ∣ x ( i ) ; θ ) … p ( y ( i ) = k ∣ x ( i ) ; θ ) \] = 1 ∑ j = 1 k e θ j T x ( i ) ⋅ \[ e θ 1 T x e θ 2 T x … e θ k T x \] ⟹ θ = \[ θ 11 θ 12 ⋯ θ 1 n θ 21 θ 22 ⋯ θ 2 n ⋯ ⋯ ⋯ ⋯ θ k 1 θ k 2 ⋯ θ k n \] J ( θ ) = − 1 m ∑ i = 1 m ∑ j = 1 k I ( y ( i ) = j ) log ⁡ ( e θ j T x ( i ) ∑ l = 1 K e θ l T x ) I ( y ( i ) = j ) = \{ 1 , y ( i ) = j 0 , y ( i ) ≠ j \\begin\{aligned\} p(y=k|x;\\theta)&=\\frac\{e^\{\\theta\_k^Tx\}\}\{\\sum\_\{l=1\}^Ke^\{\\theta\_l^Tx\}\}, \\ \\ \\ \\ \\ k=1, 2, \\dots, K \\\\ h\_\{\\theta\}(x)&=\\begin\{bmatrix\} p(y^\{(i)\}=1|x^\{(i)\};\\theta) \\\\ p(y^\{(i)\}=2|x^\{(i)\};\\theta) \\\\ \\dots \\\\ p(y^\{(i)\}=k|x^\{(i)\};\\theta) \\end\{bmatrix\} \\\\ &=\\frac\{1\}\{\\sum\_\{j=1\}^ke^\{\\theta\_j^Tx^\{(i)\}\}\}\\cdot\\begin\{bmatrix\} e^\{\\theta\_1^Tx\} \\\\ e^\{\\theta\_2^Tx\} \\\\ \\dots \\\\ e^\{\\theta\_k^Tx\} \\end\{bmatrix\} \\\\ \\Longrightarrow \\theta&=\\begin\{bmatrix\} \\theta\_\{11\} & \\theta\_\{12\} & \\cdots & \\theta\_\{1n\} \\\\ \\theta\_\{21\} & \\theta\_\{22\} & \\cdots & \\theta\_\{2n\} \\\\ \\cdots & \\cdots & \\cdots & \\cdots \\\\ \\theta\_\{k1\} & \\theta\_\{k2\} & \\cdots & \\theta\_\{kn\} \\end\{bmatrix\} \\\\ J(\\theta)&=-\\frac\{1\}\{m\}\\sum\_\{i=1\}^m\\sum\_\{j=1\}^kI(y^\{(i)\}=j)\\log(\\frac\{e^\{\\theta\_j^Tx^\{(i)\}\}\}\{\\sum\_\{l=1\}^Ke^\{\\theta\_l^Tx\}\}) \\\\ I(y^\{(i)\}=j)&=\\begin\{cases\} 1, &y^\{(i)\}=j \\\\ 0, &y^\{(i)\}\\ne j \\end\{cases\} \\end\{aligned\} p(y=k∣x;θ)hθ(x)⟹θJ(θ)I(y(i)=j)=∑l=1KeθlTxeθkTx,     k=1,2,…,K=⎣⎢⎢⎡p(y(i)=1∣x(i);θ)p(y(i)=2∣x(i);θ)…p(y(i)=k∣x(i);θ)⎦⎥⎥⎤=∑j=1keθjTx(i)1⋅⎣⎢⎢⎡eθ1Txeθ2Tx…eθkTx⎦⎥⎥⎤=⎣⎢⎢⎡θ11θ21⋯θk1θ12θ22⋯θk2⋯⋯⋯⋯θ1nθ2n⋯θkn⎦⎥⎥⎤=−m1i=1∑mj=1∑kI(y(i)=j)log(∑l=1KeθlTxeθjTx(i))=\{ 1,0,y(i)=jy(i)=j  
在实际的工作中，如果是一个多分类的问题，我们可以将这个待求解的问题转换为二分类算法的延伸，即将多分类任务拆分为若干个二分类任务求解，具体的策略如下：  
（1）One-Versus-One（ovo）：一对一  
将K个类别中的两两类别数据进行组合，然后使用组合后的数据训练出来一个模型，从而产生K(K-1)/2个分类器，将这些分类器的结果进行融合，并将分类器的预测结果使用多数投票的方式输出最终的预测结果值。  
![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dvbmd4aWZhY2FpX2JlbGlldmU_size_16_color_FFFFFF_t_70_pic_center 1][]  
（2）One-Versus-All / One-Versus-the-Rest（ova/ovr）： 一对多  
在一对多模型训练中，不是两两类别的组合，而是将每一个类别作为正例，其它剩余的样例作为反例分别来训练K个模型。然后在预测的时候，如果在这K个模型中，只有一个模型输出为正例，那么最终的预测结果就是属于该分类器的这个类别。如果产生多个正例，那么则可以选择根据分类器的置信度作为指标，来选择置信度最大的分类器作为最终结果，常见置信度：精确度、召回率。  
![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dvbmd4aWZhY2FpX2JlbGlldmU_size_16_color_FFFFFF_t_70_pic_center 2][]  
（3）Error Correcting Output codes（纠错码机制）：多对多  
将模型构建应用分为两个阶段：编码阶段和解码阶段。编码阶段中对K个类别中进行M次划分，每次划分将一部分数据分为正类，一部分数据分为反类，每次划分都构建出来一个模型，模型的结果是在空间中对于每个类别都定义了一个点。解码阶段中使用训练出来的模型对测试样例进行预测，将预测样本对应的点和类别之间的点求距离，选择距离最近的类别作为最终的预测类别。  
![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dvbmd4aWZhY2FpX2JlbGlldmU_size_16_color_FFFFFF_t_70_pic_center 3][]

## 3、多标签多分类算法 ##

Multi-Label Machine Learning（MLL算法）是指预测模型中存在多个y值，具体分为两类不同情况：

*  多个待预测的y值
 *  在分类模型中，一个样例可能存在多个不固定的类别

根据多标签业务问题的复杂性，可以将问题分为两大类：

*  待预测值之间存在相互的依赖关系
 *  待预测值之间是不存在依赖关系的

对于这类问题的解决方案可以分为两大类：

*  转换策略（Problem Transformation Methods）
 *  算法适应（Algorithm Adaptation）

（1）Problem Transformation Methods  
该方法又叫做策略转换或者问题转换，是一种将多标签的分类问题转换成为单标签模型构造的问题，然后将模型合并的一种方法，主要有以下几种方式：

*  Binary Relevance（first-order）
 *  Classifier Chains（high-order）
 *  Calibrated Label Ranking（second-order）

###### Binary Relevance ######

Binary Relevance的核心思想是将多标签分类问题进行分解，将其转换为q个二元分类问题，其中每个二元分类器对应一个待预测的标签。  
Binary Relevance方式的优点如下：

*  实现方式简单，容易理解
 *  当y值之间不存在相关的依赖关系的时候，模型的效果不错

Binary Relevance方式的缺点如下：

*  如果y之间存在相互的依赖关系，那么最终构建的模型的泛化能力比较弱
 *  需要构建q个二分类器，q为待预测的y值数量，当q比较大的时候，需要构建的模型会比较多

###### Classifier Chains ######

Classifier Chains的核心思想是将多标签分类问题进行分解，将其转换成为一个二元分类器链的形式，其中后链的二元分类器的构建是在前面分类器预测结果的基础上的。在模型构建的时候，首先将标签顺序进行shuffle打乱排序操作，然后按照从头到尾分别构建每个标签对应的模型。  
Classifier Chains方法的优点如下：

*  实现方式相对比较简单，容易理解
 *  考虑标签之间的依赖关系，最终模型的泛化能力相对于Binary Relevance方式构建的模型效果要好

缺点如下：

*  很难找到一个比较适合的标签依赖关系

###### Calibrated Label Ranking ######

Calibrated Label Ranking的核心思想是将多标签分类问题进行分解，将其转换为标签的排序问题，最终的标签就是排序后最大的几个标签值。  
Calibrated Label Ranking 方法的优点如下：

*  考虑了标签两两组合的情况，最终的模型相对来讲泛化能力比较好

Calibrated Label Ranking 方法的缺点如下：

*  只考虑两两标签的组合，没有考虑到标签与标签之间的所有依赖关系

（2）Algorithm Adaptation  
Algorithm Adaptation又叫做算法适应性策略，是一种将现有的单标签的算法直接应用到多标签上的一种方式，主要有以下几种方式：

*  ML-kNN
 *  ML-DT

###### ML-kNN ######

ML-kNN的思想：对于每一个实例来讲，先获取距离它最近的k个实例，然后使用这些实例的标签集合，通过最大后验概率（MAP）来判断这个实例的预测标签集合的值。  
最大后验概率（MAP）：其实就是在最大似然估计（MLE）中加入了这个要估计量的先验概率分布。  
 θ ^ M L E ( x ) = arg ⁡ max ⁡ θ f ( x ∣ θ ) θ ^ M A P ( x ) = arg ⁡ max ⁡ θ f ( x ∣ θ ) g ( θ ) ∫ θ f ( x ∣ θ ′ ) g ( θ ′ ) d θ ′ = arg ⁡ max ⁡ θ f ( x ∣ θ ) g ( θ ) \\begin\{aligned\} \\hat\{\\theta\}\_\{MLE\}(x)&=\\arg\\max\_\{\\theta\}f(x|\\theta) \\\\ \\hat\{\\theta\}\_\{MAP\}(x)&=\\arg\\max\_\{\\theta\}\\frac\{f(x|\\theta)g(\\theta)\}\{\\int\_\{\\theta\}f(x|\\theta')g(\\theta')d\\theta'\} \\\\ &=\\arg\\max\_\{\\theta\}f(x|\\theta)g(\\theta) \\end\{aligned\} θ^MLE(x)θ^MAP(x)=argθmaxf(x∣θ)=argθmax∫θf(x∣θ′)g(θ′)dθ′f(x∣θ)g(θ)=argθmaxf(x∣θ)g(θ)

###### ML-DT ######

ML-DT是使用决策树处理多标签内容，核心在于给予更细粒度的信息熵增益准则来构建这个决策树模型。  
 e n t r y = ∑ j = 1 q \[ − p j log ⁡ p j − ( 1 − p j ) log ⁡ ( 1 − p j ) \] p j = ∑ i = 1 n ∣ ∣ y j ∈ Y i ∣ ∣ n \\begin\{aligned\} entry&=\\sum\_\{j=1\}^q\[-p\_j\\log p\_j-(1-p\_j)\\log(1-p\_j)\] \\\\ p\_j&=\\frac\{\\sum\_\{i=1\}^n||y\_j\\in Y\_i||\}\{n\} \\end\{aligned\} entrypj=j=1∑q\[−pjlogpj−(1−pj)log(1−pj)\]=n∑i=1n∣∣yj∈Yi∣∣

## 4、多标签多分类在Scikit-learn中的实现方式 ##

在Scikit-learn中使用OneVsRestClassifier对多标签进行分类操作，内部其实是将多标签问题转换为多类别的区分问题。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dvbmd4aWZhY2FpX2JlbGlldmU_size_16_color_FFFFFF_t_70_pic_center]: /images/20230528/af25815f4d1c44fe93f4c201f53f394e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dvbmd4aWZhY2FpX2JlbGlldmU_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20230528/9468c4a41fc24cc7b2dbdae3785931b4.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dvbmd4aWZhY2FpX2JlbGlldmU_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20230528/9b1a9bd22aa84039a1d1f7c1ffd3f597.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dvbmd4aWZhY2FpX2JlbGlldmU_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20230528/3361021b031746549bb9d1d312ac849c.png