精华内容
下载资源
问答
  • 支持向量模型

    2019-05-20 17:18:00
    支持向量模型(SVM)是一个二分类模型基本思想是求解能够正确划分训练数据集并且几何间隔最大的分离超平面,其学习策略便是间隔最大化,最终化为一个凸二次规划问题的求解。 SVM可分为线性可分支持向量机、线性...

    支持向量机模型(SVM)是一个二分类模型,基本思想是求解能够正确划分训练数据集并且几何间隔最大的分离超平面,其学习策略便是间隔最大化,最终化为一个凸二次规划问题的求解。
    SVM可分为线性可分支持向量机、线性支持向量机和非线性支持向量机。

    算法推导

    1. 线性可分支持向量机

    • 引入函数间隔和几何间隔

    线性向量机的基本思想是硬间隔最大化,即:

    \[ \begin{aligned} \max_{w,b} \ \ \ \ &γ\\ s.t.\ \ \ \ \ &y_i·\frac{1}{||w||} ·(w·x_i+b)≥γ,i=1,2,…,N \end{aligned} \]
    即:
    \[ \begin{aligned} \max_{w,b} \ \ \ \ &\frac{ŷ}{||w||}\\ s.t.\ \ \ \ \ &y_i·(w·x_i+b)≥ŷ,i=1,2,…,N \end{aligned} \]
    \(ŷ=1\),得
    \[ \begin{aligned} \min_{w,b} \ \ \ \ &\frac{1}{2}{||w||}^2\\ s.t.\ \ \ \ \ &y_i·(w·x_i+b)-1≥0,i=1,2,…,N \end{aligned} \]

    这是一个凸二次规划问题,通过引入拉格朗日乘子法,构建拉格朗日对偶函数,通过求其对偶函数的解,从而得到原始问题的最优解。

    • 定义拉格朗日函数:

    \[ L(w,b,α)= \frac{1}{2}{||w||}^2-\sum_{i=1}^N{α_iy_i (w·x_i+b)}+\sum_{i=1}^N{α_i} \]
    其中,\(α={(α_1,α_2,…,α_N)}^T\)为拉格朗日乘子向量,\(α_i≥0,i=1,2,…,N\)

    原始问题的对偶问题是极大极小问题

    \[ \max_α{\min_{w,b} L(w,b,α)} \]

    • 求解对偶问题
      • \(\min_{w,b} L(w,b,α)\)

      分别对w,b求偏导数并令其为0:

      \[ \begin{aligned} \nabla_w L(w,b,α)=w-\sum_{i=1}^N{α_i y_i x_i}=0 \\ \nabla_b L(w,b,α)=\sum_{i=1}^N{α_i y_i}=0 \end{aligned} \]

      \[ \begin{aligned} w=\sum_{i=1}^N{α_i y_i x_i} \\ \sum_{i=1}^N{α_i y_i}=0 \end{aligned} \]

      代入拉格朗日函数,得

      \[ L(w,b,α)= \frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N α_i α_j y_i y_j (x_i·x_j+b)-\sum_{i=1}^N{α_i y_i ((\sum_{j=1}^N{α_j y_j x_j})·x_i+b)}+\sum_{i=1}^Nα_i \]

      \[ = -\frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N α_i α_j y_i y_j (x_i·x_j)+\sum_{i=1}^Nα_i \]

      \[ \min_{w,b} L(w,b,α) = -\frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N α_i α_j y_i y_j (x_i·x_j)+\sum_{i=1}^Nα_i \]

      • \(\min_{w,b} L(w,b,α)\)\(α\)的极大:

      \[ \max_{α}\ \ \ -\frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N α_i α_j y_i y_j (x_i·x_j)+\sum_{i=1}^Nα_i \]

      \[ s.t.\ \ \ \sum_{i=1}^N{α_i y_i}=0 \]

      \[ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ α_i≥0,i=1,2,…,N \]

      即:

      \[ \min_{α}\ \ \ \frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N α_i α_j y_i y_j (x_i·x_j)-\sum_{i=1}^Nα_i \]

      \[ s.t.\ \ \ \sum_{i=1}^N{α_i y_i}=0 \]

      \[ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ α_i≥0,i=1,2,…,N \]

      求得最优解1

      \[ \alpha^x={({\alpha_1}^x,{\alpha_2}^x,…,{\alpha_N}^x)}^{T} \]

      计算

      \[ w^*=\sum_{i=1}^N {α_i}^x y_i x_i \]

      并选择\(α^x\)的一个正分量\({α_j}^x>0\),计算

      \[ b^x=y_i-\sum_{i=1}^N {α_i}^x y_i (x_i·x_j) \]

      求得分类决策函数:

      \[ f(x)=sign(w^x·x+b^x) \]

      可知\(w^x\)\(b^x\)只依赖训练数据中对应于\({α_i}^x>0\)的样本点\((x_i,y_i)\),而其他样本点对\(w^x\)\(b^x\)没有影响。将训练样本中对应于\({α_i}^x>0\)的实例点称为支持向量。

    2. 线性支持向量机

    对于线性不可分训练集,引入松弛变量,采用软间隔最大化策略

    • 其原始问题为:

    \[ \begin{aligned} \min_{w,b} \ \ \ \ &\frac{1}{2}{||w||}^2+C\sum_{i=1}^{N}{ξ_i} \\ s.t.\ \ \ \ \ &y_i·(w·x_i+b)≥1-ξ_i,i=1,2,…,N \\ &ξ_i≥0,i=1,2,…,N \end{aligned} \]

    构建拉格朗日函数:

    \[ L(w,b,ξ,α,μ)=\frac{1}{2}{||w||}^2+C\sum_{i=1}^{N}{ξi}-\sum_{i=1}^N{α_i(y_i (w·x_i+b)-1+ξi)}-\sum_{i=1}^N{μ_i ξ_i} \]

    求导后代入,得

    \[ min_{w,b} {L(w,b,ξ,α,μ)}=-\frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N α_i α_j y_i y_j (x_i·x_j)+\sum_{i=1}^Nα_i \]

    得其对偶问题:

    \[ \max_{α}\ \ \ -\frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N α_i α_j y_i y_j (x_i·x_j)+\sum_{i=1}^Nα_i \\ \]

    \[ s.t.\ \ \ \sum_{i=1}^N{α\_i y_i}=0\\ \]

    \[ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ α_i≥0,i=1,2,…,N \]

    \[ \ \ \ \ \ \ \ \ \ \ \ \ \ C-α_i-μ_i=0 \]

    \[ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ μ_i≥0,i=1,2,…,N \]

    可以看做最小化以下目标函数:
    \[ \sum_{i=1}^N[1-y_i (w·x_i+b)]_++λ||w||^2 \]
    目标函数第一项是经验风险,称为合页损失函数(hinge loss function)

    3. 非线性支持向量机

    核函数:我们可以使用核函数,将原始输入空间映射到新的样本空间,从而使原来线性不可分得变成高维的线性可分。
    在线性支持向量机的对偶问题中,无论是目标函数还是决策函数都只涉及输入实例与实例之间的内积。在对偶问题的目标函数中内积可以用核函数来代替,此时对偶问题的目标函数成为:

    \[ W(α)=\frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N α_i α_j y_i y_j K(x_i·x_j)+\sum_{i=1}^Nαi \]

    同样,分类决策函数中的内积也可以用核函数代替,而分类决策函数成为:

    \[ f(x)=sign(\sum{i=1}^{N_s}α_i^x y_i·ϕ(x_i)·\phi(x)+b^x) \ \ \ =sign(\sum_{i=1}^{N_s}α_i^x y_i K(x_i,x)+b^x) \]

    SMO

    SMO是用于快速求解SVM的
    它选择凸二次规划的两个变量,其他的变量保持不变,然后根据这两个变量构建一个二次规划问题,这个二次规划关于这两个变量解会更加的接近原始二次规划的解,通过这样的子问题划分可以大大增加整个算法的计算速度,关于这两个变量:

    1. 其中一个是严重违反KKT条件的一个变量
    2. 另一个变量是根据自由约束确定,求剩余变量的最大化来确定的。

    相关问题

    SVM如何解决多分类问题?

    1. 直接法
      直接在目标函数上进行修改,将多个分类面的参数求解合并到一个最优化问题中,通过求解该优化就可以实现多分类(计算复杂度很高,实现起来较为困难)
    2. 间接法
      1) 一对多
      其中某个类为一类,其余n-1个类为另一个类,比如A,B,C,D四个类,第一次A为一个类,{B,C,D}为一个类训练一个分类器,第二次B为一个类,{A,C,D}为另一个类,按这方式共需要训练4个分类器,最后在测试的时候将测试样本经过这4个分类器\(f1(x)\),\(f2(x)\),\(f3(x)\)\(f4(x)\),取其最大值为分类器(这种方式由于是1对M分类,会存在偏置,很不实用)
      2) 一对一(libsvm实现的方式)
      任意两个类都训练一个分类器,那么n个类就需要n_(n-1)/2个svm分类器。
      还是以A,B,C,D为例,那么需要{A,B},{A,C},{A,D},{B,C},{B,D},{C,D}为目标共6个分类器,然后在预测的将测试样本通过这6个分类器之后进行投票选择最终结果。(这种方法虽好,但是需要\(n_(n-1)/2\)个分类器代价太大,不过 可以使用循环图来进行改进)

    KKT条件及其物理意义

    KKT条件可以总结成:约束条件(原始约束和引入拉格朗日乘子后的约束)、对x偏导为0、对偶互补条件
    针对问题:
    \[ \begin{aligned} \min\ & {f(x)} \\ s.t.\ \ &h(x)=0 \\ &g(x)≤0 \end{aligned} \]
    对于这个问题先不看等式约束,画出不等式约束和目标函数关系图:

    不等式约束

    其中,阴影部分就是可行域,也就是说可行域从原来的一条线变成了一块区域。那么能取到极值点的地方可能有两种情况:
    1、还是在 \(h(x)\)和等值线相切的地方
    2、\(f(x)\)的极值点本身就在可行域里面。

    两种情况

    因为如果不是相切,那么,对任意一个在可行域中的点,如果在它附近往里走或者往外走,\(f(x)\)一般都会变大或者变小,所以绝大部分点都不会是极值点。除非这个点刚好在交界处,且和等值线相切;或者这个点在可行域内部,但是本身就是\(f(x)\)的极值点。
    对于第一种情况,不等式约束就变成等式约束了,定义拉格朗日函数:
    \[ L(x,λ,μ)= f(x)+λh(x)+μg(x) \]
    使用拉格朗日乘子法:
    \[ ∇_x L(x,λ,μ)=0 \\ h(x)=0 \\ g(x)=0 \\ μ≥0 \]
    这里需要解释一下,为什么是\(μ≥0\)。在“不等式约束”图中,问题的可行域是在$ g(x)≤0\(一侧,而\)g(x)$ 的梯度是指向大于 0 的一侧,也就是不是可行域的一侧。而求的问题是极小值,所以 \(f(x)\) 在交点处的梯度是指向可行域的一侧,也就是说两个梯度一定是相反的。所以也就可以确定这里的系数一定是大于等于0的。而等式约束由于不知道\(h(x)\) 的梯度方向,所以对它没有约束。
    对于第二种情况,不等式约束就相当于没有,定义拉格朗日函数
    \[ L(x,λ)= f(x)+λh(x) \]
    使用拉格朗日乘子法:
    \[ ∇_x L(x,λ)=0 \\ h(x)=0 \\ g(x)≤0 \\ μ=0 \\ \]
    不同的是第一种情况有\(g(x)=0\)\(μ≥0\),第二种情况\(g(x)≤0\)\(μ=0\),综合两个问题可得:
    \[ ∇_x L(x,λ,μ)=0 \\ μg(x)=0 \\ μ≥0 \\ h(x)=0 \\ g(x)≤0 \\ \]
    这个就是 KKT 条件。它的含义是这个优化问题的极值点一定满足这组方程组。(不是极值点也可能会满足,但是不会存在某个极值点不满足的情况)它也是原来的优化问题取得极值的必要条件。

    LR与SVM的区别和联系

    相同点:
    1、都是有监督的分类算法;
    2、如果不考虑核函数,LR和SVM都是线性分类算法。它们的分类决策面都是线性的。
    3、LR和SVM都是判别式模型。
    不同点:
    1、本质上是loss函数不同,或者说分类的原理不同。LR模型找到的那个超平面,是尽量让所有点都远离他,而SVM寻找的那个超平面,是只让最靠近中间分割线的那些点尽量远离,即只用到那些支持向量的样本。SVM只考虑分界面附近的少数点,而LR则考虑所有点。
    2、SVM是结构风险最小化,LR则是经验风险最小化。
    结构风险最小化就是在训练误差和模型复杂度之间寻求平衡,防止过拟合,减小泛化误差。为了达到结构风险最小化的目的,最常用的方法就是添加正则项。SVM的loss函数具有L2正则项;LR需要加入正则化项。
    3、SVM不能产生概率,LR可以产生概率。
    4、在解决非线性问题时,SVM可采用核函数的机制,而LR通常不采用核函数的方法。
    5、SVM计算复杂,但效果比LR好,适合小数据集;LR计算简单,适合大数据集,可以在线训练。

    转载于:https://www.cnblogs.com/hellojamest/p/10895276.html

    展开全文
  • 这些专业的硕士论文中所表现出了的数据条数基本保持在200~300条左右,数据量并不高,相比较于线性回归模型而言,SVM模型在小样本的分类预测上精度更明显(但是SVM的缺点是运行速度慢),所以本文对支持向量模型...

    写在前面:

    目前许多专业在做分类问题时都选择线性回归模型进行研究,比如技术经济与管理专业、工商管理专业、会计等。

    这些专业的硕士论文中所表现出了的数据条数基本保持在200~300条左右,数据量并不高,相比较于线性回归模型而言,SVM模型在小样本的分类预测上精度更明显(但是SVM的缺点是运行速度慢),所以本文对支持向量机模型进行介绍。

    什么是支持向量机SVM?

    支持向量机(Support Vector Machine, SVM)是一类按监督学习(supervised learning)方式对数据进行二元分类的广义线性分类器(generalized linear classifier),其决策边界是对学习样本求解的最大边距超平面(maximum-margin hyperplane)。

    SVM与SVR的区别

    很多人也有听过SVR(Support Vector Regression)模型即支持向量机回归,那么二者的区别是什么?

    区别就是:一个是分类,一个是回归啊!没错,就是这么浅显的区别。

    分类和回归的区别是什么?

    很多童鞋对这方面应该很清楚,分类模型输出类别,回归输出数值。

    f8694c2e42d5d86a578efc5eedc15f4b.png

    ▲SVM

    cf4d26b0c98dcc3f27c0f9db09b44a3b.png

    如上图所示,分类目的是寻求一条线或面把两类数据分开,后续预测时可以按照预测集的数据决定把它划为绿色类还是蓝色类,而回归是根据已有数据得到一条线,这条线通过方程表述出来,预测时我们知道x(质量)的值,就可以预测出y(用户满意度)的值。

    SVM与逻辑回归的区别

    那么有人又会问分类模型不还有逻辑回归吗?它跟支持向量机模型的区别是什么?

    首先,两者都是线性分类器,本章都是求最佳分类平面,且都是监督学习算法,都是判别模型。但是,两者的区别还是挺大的

    (1) 分类依据不同

    SVM是基于距离分类的,逻辑回归是基于概率分类的。SVM依赖数据表达的距离测度,所以需要对数据先做标准化处理,逻辑回归不受其影响。

    且SVM受数据量影响严重,大量数据一般选择用逻辑回归。

    (2) 敏感性不同

    SVM考虑分类边界线附近的样本(决定分类超平面的样本)。在支持向量外添加或减少任何样本点对分类决策面没有任何影响。

    逻辑回归受所有数据点的影响。直接依赖数据分布,每个样本点都会影响决策面的结果。

    如果训练数据不同类别严重不平衡,则一般需要先对数据做平衡处理,让不同类别的样本尽量平衡。

    (3) 算法差异

    SVM与逻辑回归的损失函数不同,且SVM的损失函数自带正则,逻辑回归需要再添加正则项。SVM可以选择核函数机制,逻辑回归不可以。

    SVM中的线性可分、线性不可分、非线性可分与非线性不可分

    SVM模型按性质可以划分为四种,线性可分、线性不可分,非线性三种。

    首先,线性与非线性指的是两变量之间的关系是否是一条直线,比如y=kx就是线性,而y=kx2就是非线性模型。

    其次,可分与不可分指的是两类数据点是否有完全分界线或者面,如果是“你中有我,我中有你”,那么就是不可分,如果是“泾渭分明”,那么就是可分的。

    1. 线性可分SVM

    e2f2b3fc8a962f9c74df9c007436d76d.png

    ▲线性可分SVM模型的图例

    如上图所示,黑点和空心圆两种数据可以由一条红色虚直线完全分离,那么这种情况就是SVM模型的线性可分类型

    2. 线性不可分SVM

    f3f56bab2fb3b82264f6117fe7683807.png

    ▲线性不可分SVM示例图

    如上图所示,当有两种数据存在“你中有我,我中有你”的类型,比如有一个空心圆与黑点掺在一起,那么我们选择H1,H2和MMH都是不合理的。

    此时我们在拟合SVM模型时需要调整约束条件,即增加松弛变量和惩罚因子,但是更好的方法是通过核方法来对特征向量进行映射,将他们转化到更高维的空间,使得数据在高维空间是线性可分的。

    这种方法也适合用在数据存在异常值时的SVM模型的拟合。

    3. 非线性SVM

    e15afc1abc880adc3decea380666375e.png

    ▲非线性可分SVM示例图

    如上图,蓝色方块和绿色三角形之间存在明显界限,但是这条界线是非线性的,这就对应SVM中的非线性可分情况。

    这种情况我们也是通常选取核方法进行研究,该类型可以选取多项式核,高斯RBF核等。

    展开全文
  • 文本表示+向量空间模型

    千次阅读 2017-10-11 15:28:24
    模型向量空间模型;概率模型;概念模型向量空间模型 1、主要步骤 (1)将文本的基本语言单位(字、词、词组、短语)抽取,组成特征项,用tn表示 (2)将tn按在文本中的重要性给出权重wn (3)将文本抽象为...

    概念:文本挖掘算法不能直接在原始文本形式上处理。因此,在预处理阶段,将文本转化为更易计算机识别的信息,即对文本进行形式化处理。

    模型:向量空间模型;概率模型;概念模型;

    向量空间模型

    1、主要步骤

    (1)将文本的基本语言单位(字、词、词组、短语)抽取,组成特征项,用tn表示

    (2)将tn按在文本中的重要性给出权重wn

    (3)将文本抽象为(t1,w1,t2,w2,……,tn,wn)简化为(w1,w2,……,wn)即为文本的向量 空间模型。

    2、权值wn计算

    (1)布尔权值:wn可取值1/0表示该特征是否在文本中出现。

    (2)词频权值:wn用特征在文档中出现的频数表示

    (3)TF/IDF权值:公式有两种,一种考虑文本信息量,另一种不考虑。下面举不考虑信息量的例子。

    有很多不同的数学公式可以用来计算TF-IDF。这边的例子以上述的数学公式来计算。词频 (TF) 是一词语出现的次数除以该文件的总词语数。假如一篇文件的总词语数是100个,而词语“母牛”出现了3次,那么“母牛”一词在该文件中的词频就是3/100=0.03。一个计算文件频率 (IDF) 的方法是测定有多少份文件出现过“母牛”一词,然后除以文件集里包含的文件总数。所以,如果“母牛”一词在1,000份文件出现过,而文件总数是10,000,000份的话,其逆向文件频率就是 log(10,000,000 / 1,000)=4。最后的TF-IDF的分数为0.03 * 4=0.12。

     考虑词长公式及注解:


    词频为频率[0,1],频数为次数,大于等于0.

    地址





    展开全文
  • 向量空间模型(vector space model)

    万次阅读 多人点赞 2017-10-17 20:30:08
    向量空间模型(vector space model) 向量空间模型概念简单,把对文本内容的处理简化为向量空间中的向量运算,并且它以空间上的相似度表达语义的相似度,直观易懂。当文档被表示为文档空间的向量,就可以通过计算向量...

    向量空间模型(vector space model)

    向量空间模型概念简单,把对文本内容的处理简化为向量空间中的向量运算,并且它以空间上的相似度表达语义的相似度,直观易懂。当文档被表示为文档空间的向量,就可以通过计算向量之间的相似性来度量文档间的相似性。文本处理中最常用的相似性度量方式是余弦距离。

    VSM基本概念:

    (1) 文档(Document):泛指一般的文本或者文本中的片断(段落、句群或句子),一般指一篇文章,尽管文档可以是多媒体对象,但是以下讨论中我们只认为是文本对象,本文对文本与文档不加以区别"。

    (2) (Term):文本的内容特征常常用它所含有的基本语言单位(字、词、词组或短语等)来表示,这些基本的语言单位被统称为文本的项,即文本可以用项集(Term List)表示为D(T1,T2,,,,Tn)其中是项,1≤k≤n"

    (3) 项的权重(TermWeight):对于含有n个项的文本D(,………,,项常常被赋予一定的权重表示他们在文本D中的重要程度,即D=(,,,,······,)。这时我们说项的权重为(1≤k≤n)。

    (4) 向量空间模型(VSM):给定一文本D=D(,………,)由于在文本中既可以重复出现又应该有先后次序的关系,分析起来有一定困难。为了简化分析,暂时不考虑的顺序,并要求互异,这时可以把,………,看作是一个n维的坐标,而就是n维坐标所对应的值,所以文档D()就可以被看作一个n维的向量了。

    (5) 相似度(Similarity)两个文本D,和DZ之间的(内容)相关程度(Degree of Relevance)常常用他们之间的相似度Sim(,)来度量,当文本被表示为向量空间模型时,我们可以借助与向量之间的某种距离来表示文本间的相似度"常用向量之间的内积进行计算:
                   Sim(,)=*
    或者用夹角的余弦值表示:
                   Sim(,)=

    可以看出,对向量空间模型来说,有两个基本问题:即特征项的选择项的权重计算

    特征项选择

    用来表示文档内容的项可以是各种类别,对汉语来说,有字、词、短语,甚至是句子或句群等更高层次的单位。项也可以是相应词或短语的语义概念类。

    项的选择必须由处理速度、精度、存储空间等方面的具体要求来决定。特征项选取有几个原则:一是应当选取包含语义信息较多,对文本的表示能力较强的语言单位作为特征项;二是文本在这些特征项上的分布应当有较为明显的统计规律性,这样将适用于信息检索、文档分类等应用系统;三是特征选取过程应该容易实现,其时间和空间复杂度都不太大。实际应用中常常采用字、词或短语作为特征项。

    由于词汇是文本最基本的表示项,在文本中的出现频度较高,呈现一定的统计规律,在考虑到处理大规模真实文本所面临的困难,一般选择词汇或短语作为特征项,但是直接选用文本中的词或词组作为文本特征项也会存在以下问题:
    (1) 文本中存在一些没有实在意义但使用频率很高的虚词和功能词,如中文中“的”、“把”、“了”等,常常把一些真正有分类作用的实词淹没掉了。解决这个问题的方法是把这些词组织成一个禁用词表,或者进行权重计算时,使它们的权重很低,通过取阀值将它们丢弃。采用禁用词表时,词表的选择很关键,很难全面地包括所有的禁用词,并且语言是不断发展的,禁用词表也是随着训练文本集合的不同而不同,某个词在这里不是禁用词,到另外一类文本中可能就成了禁用词。另一方面考虑到,最能代表一篇文章实际意义的词,往往是那些实词,如形容词、动词、名词,而且同一个词,当处于不同词性时,可能分别属于和不属于禁用词表。例如:“他高兴地走了”(副词“地”应是禁用词),“地很不平”(名词“地”不应作为禁用词)"针对这个现象,提出了只提取形容词、动词和名词作为特征项,并尝试着取代禁用词表方法.
    (2) 采用词语作为特征项时还会出现所谓的同义现象,同义现象是指:对于同一个事物不同的人会根据个人的需要、所处的环境、知识水平以及语言习惯有着不同的表达方式,因此所采用的词汇也有很大的不同。所以经常出现两个文本所用的词汇有所不同,但实际上两者是相似的,这就是词的同义现象造成的。例如电脑和计算机是同一个概念,应该属于同一个特征项,目前最常用的解决方案是采用概念词典来解决这个问题。

    分词

    确定了特征项单位以后,接下来要做的就是把文本分割成特征项的表示。我们知道,词是最小的能够独立活动的有意义的语言成分。然而,汉语是以字为基本的书写单位,文本中词与词之间没有明确的分隔标记,而是连续的汉字串,显而易见,自动识别词边界,将汉字串分为正确的词串的汉语分词问题无疑是实现中文信息处理各项任务的基础与关键。中文词语分析一般包括3个过程:预处理过程的词语粗切分、切分排歧与未登陆词识别、词性标注。目前中文词语分析采取的主要步骤是:先采取最大匹配、最短路径、概率统计、全切分等方法,得到一个相对最好的粗分结果,然后进行排歧、未登陆词识别,最后标注词性。在实际系统中,这三个过程可能相互交叉、反复融合,也可能不存在明显的先后次序。可以将现在的分词算法分为3大类:基于字符串匹配的分词方法、基于理解的分词方法和基于统计的分词方法。

    1)基于字符串匹配的分词方法
    这种方法又叫机械分词法,它按照一定的策略将待分析的汉字串与机器字典中的词条进行匹配,若在字典中可以找到某个字符串,则匹配成功(识别出一个词)。按照扫描方向的不同可以分为正向匹配和逆向匹配;按照不同长度优先匹配的情况,又可以分为最大(最长)匹配和最小(最短)匹配;按照是否与词性标注过程相结合,又可分为单纯分词法和分词与标注相结合的一体化方法。具体的方法主要有以下几种:
      (a)最大匹配法(maximum matching method, MM)

    在计算机中存放一个已知的词表,这个词表叫底表,从被切分的语料中,按给定的顺序截取一个定长的字符串,通常为6-8个汉字,这个字符串的长度叫做最大词长,把这个具有最大词长的字符串与底表中的词相匹配,如匹配成功,则可确定这个字符串为词,然后指针向给定的方向移动与已经识别出的词长相应个数的汉字,继续进行匹配,否则,则把该字符串逐次减一,再与底表中的词长进行匹配,直到成功为止。MM的原理简单,易于在计算机上实现,实现复杂度比较低。缺点是最大词长难以确定,如果定得过长,则算法复杂度显著提高,如果定得太短,则不能切分长度大于它的词,导致切分正确率降低。

    b)逆向最大匹配法(reverse maximum matching method, RMM)

    这种方法的原理与MM相同,不同的是切词的扫描方向,如果MM的方向是从左到右取字符串进行匹配,则RMM的切词方向就是从右到左取字符串进行匹配。试验证明RMM的切词正确率较MM更高一些。但是,RMM要求配置逆序的切词字典,这种词典与人们的语言习惯不同。

    c)逐词遍历匹配法

    这种方法把辞典中的词按由长到短的顺序,逐个与待切词的语料进行匹配,直到把语料中所有的词都切分出来为止。由于这种方法要把辞典中的每个词都匹配一遍,需要花费很多时间,算法的时间复杂度相应增加,效率不高。

    d)双向扫描法

    这种方法是分别用MM和RMM进行正向和逆向扫描完成初步的切分,并将用MM初步切分的结果与用RMM初步切分结果进行比较,如果两种结果一致,则判定正确,否则定为疑点,此时或者结合上下文信息,或进行人工干预,选取一种切分为正确结果,由于要进行双向扫描,时间复杂度增加,而且为了使切分词典能同时支持正向与逆向两种顺序的匹配和搜索,词典的结构比一般的切词词典复杂。

    e)最佳匹配法(optimum matching method,0M)

    这是在切词词典中按词出现频率的大小排列词条,高频词在前,低频词在后,从而缩短了查询切词词典的时间,加快切词的速度,使切词达到最佳的效率。这种切词方法对于分词算法没有什么改进,只是改变了分词词典的排列顺序,它虽然降低了切词的时间复杂度,却没有提高分词的正确率。

    f)设立切分标记法

    在书面语中,存在的切分标记有两种:一种是自然的切分标志,如标点符号,词不能跨越标点符号而存在,标点符号则是词的边界之所在;另一种是非自然的切分标志,如只能在词首出现的词首字,只能在词尾出现的词尾字,没有构词能力的单音节单纯词、多音节单纯词、拟声词等,词显然也不能跨越这些标志而存在,它们也必然是词的边界。如果收集了大量的这种切分标志,切词时,先找到切分标志,就可以把句子切分成一些较短的字段,然后再用MM或RMM进行进一步切分。使用这种方法切词,要额外消耗时间,并扫描切分标志,还要花费存储空间来存储非自然的切分标志,使切词算法的时间复杂度和空间复杂度都大大增加了,而切词的正确率却提高的有限,所以采用这种方法的自动切词系统不多。

    g)有穷多级列举法

    这种方法把现代汉语中的全部词分为两大类:一类是开放词,如名词、动词、形容词等,它们的成员几乎是无穷的,另一类是闭锁词,如连词、助词、叹词等,它们的成员是可以一一枚举的。切词时,先切出词的特殊标志的字符串,如阿拉伯数字、拉丁字母等,再切出可枚举的闭锁词,最后在逐级切出开放词。这是完全立足于语言学的切词方法,在计算机上实现起来还是很有困难。
      

    由于汉语很少单字成词的特点,正向最小匹配和逆向最小匹配一般很少使用。一般说来,逆向匹配的切分精度略高于正向匹配,遇到的歧义现象也很少。统计结果表明,单纯使用正向最大匹配的错误率为1/169,单纯使用逆向最大匹配的错误率为1/245(这可能是因为汉语的中心语靠后的特点)。但这种精度还远远不能满足实际的需要。由于分词是一个智能决策过程,机械分词方法无法解决分词阶段的两大基本问题:歧义切分问题未登陆词识别问题。实际使用的分词系统,都是把机械分词作为一种切分手段,还需通过利用各种其他的语言信息来进一步提高切分的正确率。

    对于机械分词方法,可以建立一个通用模型,形式化地表示为ASM(d,a,m)即Automatic Segmentation Model"其中:

    d:匹配方向,+1表示正向,一1表示逆向。

    a:每次匹配失败后增加/减少字符串长度(字符数),+1为增字,一1为减字。

    m:最大/最小匹配标志,+1为最大匹配,一1为最小匹配。

    例如,ASM(+,-,+)就是正向减字最大匹配法(即MM),ASM(-,-,

    +)就是逆向减字最大匹配法(即RMM),等等。对于现代汉语来说,只有m=+1是实用的方法。

    2)基于理解的分词方法

    通常的分词系统,都力图在分词阶段消除所有歧义切分现象,有些系统则在后续过程中来处理歧义切分问题,其分词过程只是整个语言理解过程的一个小部分。其基本思想就是在分词的同时进行句法、语义分析,利用句法信息和语义信息来处理歧义现象。它通常包括3个部分:分词子系统、句法语义子系统、总控部分。在总控部分的协调下,分词子系统可以获得有关词、句子等的句法和语义信息来对分词歧义进行判断,即它模拟了人对句子的理解过程。这种分词方法需要使用大量的语言知识和信息。由于汉语语言知识的笼统、复杂性,难以将各种语言信息组织成机器可直接读取的形式,因此,目前基于理解的分词系统还处于试验阶段,联想回溯法就是其中的一种。

    联想-回溯法(association-backtracking method ,AB):要求建立知识库-特征词词库、实词词库和规则库。首先将待切分的汉字字符串序列分割为若干子串,子串可以是词,也可以是由几个词组合成的词群,然后就利用实词词库和规则库将词群细分为词。切词时,要利用一定的语法知识,建立联想机制和回溯机制。联想机制由联想网络和联想推理构成,联想网络描述每个虚词的构词能力,联想推理利用相应的联想网络来判定所描述的虚词究竟是单独的词还是作为其他词中的构成成分。回溯机制主要用于处理歧义句子的切分。联想回溯算法虽然增加了算法的时间复杂度和空间复杂度,但是这种方法的切词正确率得到了提高,是一种行之有效的方法。

    3)基于统计的分词方法

    从形式上看,词是稳定的字的组合,因此在上下文中,相邻的词同时出现的次数越多,就越有可能构成一个词"因此字与字相邻共现的频率或概率能够较好地反映成词的可信度。可以对语料中相邻共现的各个字的组合的频度进行统计,计算它们的互现信息。定义两个字的互现信息为:
                  M(X,Y)=log(P(X,Y)/P(X)*P(Y))

    其中P(X,Y)是汉字X,Y的相邻共现频率,P(X)、P(Y)分别是X、Y在语料中出现的概率。互现信息体现了汉字之间结合关系的紧密程度。当紧密程度高于某一个阐值时,便可认为此字组可能构成一个词。这种方法只需要对语料中字组频度进行统计,不需要切分词典,因而又称为无词典分词法或统计取词方法。但这种方法也有一定的局限性,会经常抽出一些共现频度高,但并不是词的常用字组,例如“这一”、“之一”、“有的”、“我的”、“许多的”等,并且对常用词的识别精度差,时空开销大。实际应用的统计分词系统都要使用一部基本分词词典(常用词词典)进行串匹配分词,同时使用统计方法识别一些新词,即将串频统计和串匹配结合起来,既发挥匹配分词切分速度快、效率高的特点,又利用了无词典分词结合上下文识别生词、自动消除歧义的优点。常用的有基于词频统计的切词法基于期望的切词法
      a)基于词频统计的切词法

    这种方法利用词频统计的结果帮助在切词过程中处理歧义切分字段.这种方法的缺点是:由于只考虑词频,出现频率较低的词总是被错误地切分.

    (b) 基于期望的切词法

    这种方法认为一个词的出现,它后面紧随的词就有一种期望,据这种期望,在词典中找到所有的词从而完成切分.这种方法增加了切词的空间复杂度,但在一定程度上提高了切词的正确率。

    中文文本自动分词技术一般以词典作为分词依据,使用专门的分词算法将文本中出现于词典中的词识别出来。通过这种方法获得的文本特征只能是词典中出现的词汇,但是自然语言领域相关性和随时间变化的特性,词典中不可能包含文本中所有词汇,因此,对不同类型文本进行分类时,就需要不断修整和扩充词典并改进分词技术,才能获得良好的分类性能。

    针对基于词典分词的分类系统存在的弊端,人们提出了一种基于n-gram信息的文本特征提取技术,使文本自动分类系统摆脱了对复杂分词处理程序对庞大词库的依赖,实现了中文文本自动分类的领域无关性和时间无关性。N-gram信息的概念是信息论创始人C.E.Shannon在研究信源编码时提出来的,常被用来表示信源输出的连续n个字符所组成的字符串。Shannon曾用它来研究英文文本中字符或字符串的统计特性,即信息嫡,随后,n一gram信息被广泛应用于文本压缩、字符识别与纠错等领域,是一种直接面向代码的技术。采用n-gram信息作为文本特征具有以下特点:第一:无需任何词典支持;第二:对输入文本所需的先验知识少;第三:无需进行分词处理;但是n-gram信息获取技术的领域无关性和时间无关性的实现是有代价的.首先,n-gram信息的提取对系统资源的要求比较高,因为进行任何n-gram信息提取时,都会产生大量的数据冗余,占用很大的内存空间。相比较于词典的分词技术,其实现效率低,获取n一gram信息将花费较长的时间。

    特征值抽取
    一篇文章在经过了分词处理之后,会产生很多词条。如果一个文档所有词条都被作为其特征,将会使特征项异常庞大,而且这样的特征项会使得每个特征项所含信息非常平滑,有用信息反而不会突出。因此我们需要进行特征项选取,把词条中最能代表某类文本信息的词条挑选出来,作为文本的特征项。实验结果表明简化特征项不但不会使分类结果准确率降低,而且还会使结果更加准确。特征项选择一般使用统计方法,利用各种计算公式,计算词代表的信息含量,确定一个阀值,将低于阀值的词语过滤掉。或者确定一个特征项数目n,保留处于信息含量在前n位的词条。

    特征抽取算法是文本自动分类中的一项关键技术和瓶颈技术,如何从原始文本特征集合中选择最能表示文本主题内容的特征子集,是文本特征抽取算法的研究目标。目前,有多种特征抽取算法被用于文本自动分类的研究中,但这些算法都有其优点和缺点,没有公认的最优方法,需要针对具体系统进行对比来确定最优方法。

    特征选择可以从两个方面提高系统性能一是分类速度,通过特征选择,可以大大减少特征集合中的特征数,降低文本向量的维数,简化计算,防止过度拟合,提高系统运行速度。二是准确率,通过适当的特征选择,不但不会降低系统准确性,反而会使系统精度提高。

    在文本处理中,一些常用特征提取评估函数有文档频数(document frequency)、信息增益(information gain)、期望交叉熵(expected cross entropy)、互信息(mutual information)、统计(CHI)、文本证据权(the weight of evidence for text)等。

    (1) 文档频数DF

    它是最简单的评估函数,值为训练集合中该单词发生的文本数。DF评估函数的理论假设稀有单词可能不包含有用信息,也可能太少而不足以对分类产生影响,也可能是噪音,因此可以删去。显然它在计算量上比其他评估函数小很多,但是实践运用中它的效果却很好.DF的缺点是稀有单词可能在某一类文本中并不稀有,也可能包含着重要的判断信息,错误的舍弃,可能影响分类器的精度。因此,在实际运用中一般并不直接使用DF。

     

    (2) 信息增益(information Gain)

    信息增益表示文档中包含某一特征值时文档类的平均信息量。它定义为某一特征在文档中出现前后的信息熵之差。假定c为文档类变量,C为文档类的集合,d为文档,f为特征(以下各节同此)。对于特征f,其信息增量记为IG(f),计算公式如下:
           IG(f)=H(C)-H(C|f)

                =

     

    特征项赋权

    为了兼顾查全率和查准率,检索系统在对特征项进行赋权时,应同时包含提高查全率查准率的赋权因子。特征项赋权因子由频率因子(TF)、文档集因子(DF)和规格化因子三部分组成。

    1)在文档中频繁出现的特征项具有较高的权重,因此检索系统常使用频率因子TF(Term Frequency)进行特征项赋权,使用高频特征项进行查询可以提高系统的查全率。

    2)仅使用频率因子并不能保证系统的查询性能,提高查全率时会影响检索系统的查准率。因此需要引入一个与文档集合有关的因子,加大文档之间的区分度。如果特征项在集合中较少的文档中出现,则相应的文档集因子IDF(Inverse Document Frequency)较大。在文档总数为N的集合中,如果包含某特征项的文档数为n,则文档集因子是idf=。

    3)当文档较长时,查询式与文档进行匹配的可能性更大,所以长文档比短文档更有可能被提取出来,因此引入规格化因子来消除文档长度对匹配结果的影响。假定代表特征项的权重,最后的规格化因子定义为:

     OR

    向量空间模型

    TF-IDF 权重
    特征项的权重计算是文本相似度计算中的一个非常重要的环节。一篇文本中的特征项数目众多,要想得到比较准确的对文本内容的数学化表示,我们需要对能显著体现文本内容特征的特征项赋予高权重,而对不能可以体现文本内容特征的特征项赋予低权重。从效率方面来说,特征项权重的计算是文本相似度计算中的主要工作,它的效率也直接影响文本相似度计算的整体效率。
    经典的 TF-IDF 权重是向量空间模型中应用最多的一种权重计算方法,它以词语作为文本的特征项,每个特征项的权重由 TF 权值和 IDF 权值两个部分构成。对于文本 中的第 k 个特征项,其对应权重计算方法为:

                  =*

    其中

    (1) TF (Term Frequency)权值:特征项在文本中出现的次数,即如果在文本中出现次,那么

                       

    (2) 在实际应用中,通常需要对 TF 值进行标准化处理,以避免文本太长所导致的的统计偏差:
                        =

    (3)IDF(Inverse Document Frequency)权值:特征项在全局文本集 D 中的出现频率,即:
                  log

    假设全局文本集共有M 篇文本,特征项共在篇文章中出现过,那么
                      =log(M/())

    其中为经验常数,一般取 0.01。

    TF 权值反映了特征项在给定的文本中的概念重要程度(freq importance),体现了信息论中频度的思想。某特征项在文本中的出现次数越多,表示它对于该文本的重要程度越高。IDF 权值则反映了特征项的信息度(informativeness),用于体现一个特征项的“文义甄别能力”。如果一个特征项只出现在一个或少数文本中,那么它很可能是能体现文本内容特征的语义中心词,会被赋予大的 IDF 值以提高权重。而如果一个特征项在很多的文本中出现过,表示它代表文本的“个性特征”的能力很低,IDF 值也就相应地小。

    TF-IDF 权重综合考虑了不同的词在文本中的出现频率(TF 值)和这个词对不同文本的分辨能力(IDF 值),在所有文本中出现次数很少的特征项被赋予高权重,因为它们被认为是文本内容特征的辨别器。例如,在汉语中“是”的出现频率非常高,但由于它在很多文本中都出现,会被赋予一个很低的 IDF 值,以此体现它对于我们分辨文本的特征并没有太大的帮助。而像“偏微分”这种专业词汇由于只会在相关专业文本中才会出现,会被赋予高 IDF 值以体现它的文本特征鉴别能力。

    TF-IDF 是基于统计的权重计算方式,在全局文本集包含的语料特征足够的情况下,这种基于统计学的方法经过实践检验是一种有效的特征项权重衡量方法。其局限性在于它的准确度受全局文本集的影响较大:全局文本集越大,语料越完备,所得的权重也就越准确,但相应地计算效率也会随着全局文本集的增大而降低。

    展开全文
  • 向量空间模型基本思想是把文档简化为以特征项(关键词)的权重为分量的N维向量表示。 这个模型假设词与词间不相关(这个前提造成这个模型无法进行语义相关的判断,向量空间模型的缺点在于关键词之间的线性无关的...
  • 文本向量空间模型

    2018-01-06 00:00:00
    我们需要开始思考如何将文本集合转化为可量化的东西。最简单的方法是考虑词频。...基本词频首先,我们回顾一下如何得到每篇文档中的词的个数:一个词频向量。#examples taken from here: http://stackoverfl
  • 基本步骤 对文档进行分词处理,去除停用词等 计算每个文档中词项的tf值,计算公式: 计算文档集中所有词项的idf值,计算公式: 计算每个文档中词项的tf-idf值,计算公式: 对查询进行上述处理 构造向量,有两种...
  • 首先,我们回顾一下如何得到每篇文档中的词的个数:一个词频向量。   #examples taken from here: http://stackoverflow.com/a/1750187 mydoclist = ['Julie loves me more than Linda loves me', 'Jane likes me...
  • 1.向量空间模型(Vector Space Models) 1.1 基本概念 定义:向量空间模型将单词或文本用向量表示,通过上下文来获取其语义信息 功能:识别两文本/两类文档间的相似度和独立性 例: 单词基本相同的两句话可能...
  • SVM简介 通俗的解释: 给定两组不同类别的数据点,找一个超平面把他们分割开,并希望这个超平面离这两组数据点的距离尽可能大。这样,我们就认为超平面一侧是一个类别。...支持向量机算法的基本流程 代码实现 fro..
  • 向量空间模型中,文本泛指各种机器可读的记录。用D(Document)表示,特征项(Term,用t表示)是指出现在文档D中且能够代表该文档内容的基本语言单位,主要是由词或者短语构成,文本可以用特征项集表示为D(T1,T2...
  • 向量空间模型这是信息检索中的最基本的方法之一。用在向量空间模型(Vector Space Model)中。向量空间模型在信息检索的应用中经常用到。举个列子:例如,现在有一组文档d1, d2, d3, 我们要在其中搜索 “Car ...
  • 文本特征抽取由两组小说,一组是爱情的,另一组是科幻的。我们能否用支持向量机训练一个模型,用来识别小说类型呢?这个并不容易。因为支持向量机这类机器学习算法只能接受数学...向量作为一种基本的数学模型,是文本特
  • 向量空间模型请参照全文检索的基本原理的blog 问题: 在你的文章中提到了: 于是我们把所有此文档中词(term)的权重(term weight) 看作一个向量。  Document = {term1, term2, …… ,term N}  Document ...
  • 1. 基本概念 1. 1 语料库&词典 一般语料库就是很多篇文章(可能一篇文章有好几句话,也可能只有一句话),在实际业务中,每篇文章一般要先进行分词 词典:语料库中词的种类数,即有多少个词,一般用|V|表示 树...
  • 介绍在我们学习机器算法的时候,可以将机器学习算法视为...相反的是,“支持向量机(SVM)”就像一把锋利的刀,它比较适用于较小的数据集,但在较小的数据集上面,它可以构建更加强大的模型。相信在你学习机器学习算...
  • 改进后的向量空间模型(VSM)

    千次阅读 2014-08-04 10:52:09
    除了简单地给出查询词列表外,...基本思想是:不频繁出现的词的权重应该比频繁出现的词的权重更高。文献[Salton,1969;Salton,1970b]分别采用权重自动赋值与人工赋值方法计算相似度,然后进行查询比较。实验结果表
  • 论文研究-强简化流率基本入树模型与枝向量矩阵反馈环分析法.pdf, 首先提出了流率基本人树的强简化方法 ,然后又在枝向量概念及其运算的基础上 ,给出了一个枝向量矩阵反馈...
  • 语言模型与词向量

    2020-10-02 16:32:37
    自然语言处理中一个很核心的基本任务就是语言模型与词向量,这一篇文章我主要回顾了一下自然语言处理中语言模型与词向量的发展历程,总结一下这一条线的一些经典的idea。
  • [支持向量机是机器学习领域里最强的几种分类器之一...其基本原理相当简单,但是模型的求解和优化却十分复杂,很难描述清楚,这里我会一步一步,尽我所能分章节的将它总结完善 · 支持向量机:模型篇1–支持向量与间
  • 训练自己的词向量模型

    千次阅读 2019-03-15 15:55:36
    from:... 一、gensim介绍 gensim是一款强大的自然语言处理工具,里面包括N多常见模型: - 基本的语料处理工具 - LSI - LDA - HDP - DTM - DIM - TF-IDF - word2vec、paragraph2vec...
  • 支持向量机是机器学习领域里最强的几种分类器之一...其基本原理相当简单,但是模型的求解和优化却十分复杂,很难描述清楚,这里我会一步一步,尽我所能分章节的将它总结完善 · 支持向量机:模型篇1–支持向量与间隔
  • 它的基本内容是词以及它们的向量表示,即将词映射为对应的向量,这样就可以被计算机识别和计算。它的文件后缀名是.bin。过程 分词 即将文本分词,分词工具有很多,比如哈工大的分词工具和结巴分词工具,具体如何...
  • 如果问我哪个是最方便、最好用的词向量模型,我觉得应该是...本文讨论了一些大家比较关心的词向量的问题,很多结论基本上都是实验发现的,缺乏合理的解释,包括: 如果去构造一个词向量模型? 为什么用余弦值
  • 支持向量机是机器学习领域里最强的几种分类器之一...其基本原理相当简单,但是模型的求解和优化却十分复杂,很难描述清楚,这里我会一步一步,尽我所能分章节的将它总结完善 · 支持向量机:模型篇1–支持向量与间隔
  • 模型选择问题是支持向量机的基本问题。基于核矩阵近似计算和正则化路径,提出一个新的支持向量模型选择方法。 -α,证明KMA-α的近似偏差界定理,并得到支持矢量机的模型近似误差界。然后,提出近似模型选择算法...
  • R语言实现PVAR(面板向量自回归模型)

    万次阅读 多人点赞 2019-06-05 20:16:00
    这次研究了一个问题,要用PVAR(面板向量自回归模型),在网上找的教程基本上都是Stata或者Eviews的教程,而鲜有R实现PVAR的教程,这里总结分享一下我摸索的PVAR用R实现的整个过程。 ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 3,129
精华内容 1,251
关键字:

向量基本模型