EdmondFrank's 时光足迹

この先は暗い夜道だけかもしれない それでも信じて進むんだ。星がその道を少しでも照らしてくれるのを。
或许前路永夜,即便如此我也要前进,因为星光即使微弱也会我为照亮前途。
——《四月は君の嘘》

Python在Spark上的机器学习(三)之统计分析



Python在Spark上的机器学习(三)之统计分析

背景

通常来说,一个完整使用机器学习建模解决问题的过程包含一下步骤:

  • 数据获取
  • 数据预处理
  • 数据统计分析
  • 算法建模
  • 训练
  • 预测/分类

这就意味着,在我们进行一般的数学建模或者挑选机器学习训练算法之前,应该先对数据进行清洗以及简单的统计分析,以便了解数据中显著的特征或者规律(虽然现在的机器学习方法,很多情况下根本不需要了解数据的意义,仅仅是通过堆叠特征就能获得一个可行的结果,但这显然离一个优秀的结果还是有一段距离的)。为了得到更加鲁棒的模型,以及了解数据背后的含义,我们这篇文章就来讲讲如何在PySpark上进行简单的统计分析。

概念介绍

描述性统计分析
这是一个统计学的概念,描述性统计是以揭示数据分布特性的方式汇总并表达定量数据的方法。主要包括数据的频数分析、数据的集中趋势分析、数据离散程度分析、数据的分布、以及一些基本的统计图形。特征括并表示定量数据,揭示数据分布的特征。
描述性统计是一类统计方法的汇总,作用是提供了一种概括和表征数据的有效且相对简便的方法。通常用图示法来表述,易于看懂,能发现质量特性值(总体)的分布状况、趋势走向的一些规律,便于采取措施。用于汇总和表征数据,通常是对数据进一步定量分析的基础,或是对推断性统计方法的有效补充。

数据读取

本文使用的是一个信用欺诈检测的一个数据集,具体下载地址:这里

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
import PySpark.sql.types as typ
fraud = sc.textFile('data/ccFraud.csv')
header = fraud.first()
fraud = fraud.filter(lambda row:row!=header)\
.map(lambda row:[int(elem) for elem in row.split(',')])
fields = [
    *[
        typ.StructField(h[1:-1],typ.IntegerType(),True)
        for h in header.split(',')
    ]
]
schema = typ.StructType(fields)
fraud_df = spark.createDataFrame(fraud,schema=schema)
fraud_df.printSchema()
fraud_df.head()

输出结果
root
|– custID: integer (nullable = true)
|– gender: integer (nullable = true)
|– state: integer (nullable = true)
|– cardholder: integer (nullable = true)
|– balance: integer (nullable = true)
|– numTrans: integer (nullable = true)
|– numIntlTrans: integer (nullable = true)
|– creditLine: integer (nullable = true)
|– fraudRisk: integer (nullable = true)
Out:
Row(custID=1, gender=1, state=35, cardholder=1, balance=3000, numTrans=4, numIntlTrans=14, creditLine=2, fraudRisk=0)

在上面的代码中,我们读入了我们的数据集,以及创建了一个DataFrame,下面我们再进行一些简单的分析操作。

简单统计分析

1
2
3
4
5
6
7
8
9
10
11
fraud_df.groupby('gender').count().show() #按照性别分类汇总


numerical = ['balance', 'numTrans', 'numIntlTrans']
desc = fraud_df.describe(numerical)
##对balance,numTrans,numIntTrans进行描述性分析
desc.show()


# 计算balance值分布的偏度
fraud_df.agg({'balance': 'skewness'}).show()

输出结果
+——+——-+
|gender| count|
+——+——-+
| 1|6178231|
| 2|3821769|
+——+——-+
+——-+—————–+——————+—————–+
|summary| balance| numTrans| numIntlTrans|
+——-+—————–+——————+—————–+
| count| 10000000| 10000000| 10000000|
| mean| 4109.9199193| 28.9351871| 4.0471899|
| stddev|3996.847309737258|26.553781024523122|8.602970115863904|
| min| 0| 0| 0|
| max| 41485| 100| 60|
+——-+—————–+——————+—————–+
+——————+
| skewness(balance)|
+——————+
|1.1818315552993839|
+——————+

上面我们使用了一些常用的统计分析函数,以及简单地了解了一下PySpark 聚合函数agg()的使用。通常地,常用的聚合函数还有avg() , count(), countDistinct() , max() 等。

相关分析

相关分析(correlation analysis),相关分析是研究现象之间是否存在某种依存关系,并对具体有依存关系的现象探讨其相关方向以及相关程度,是研究随机变量之间的相关关系的一种统计方法。通常两个变量之间存在的相关关系有:正相关、完全正相关、负相关、完全负相关、无相关。

相关系数是最早由统计学家卡尔·皮尔逊设计的统计指标,是研究变量之间线性相关程度的量,一般用字母 r 表示。由于研究对象的不同,相关系数有多种定义方式,较为常用的是皮尔逊相关系数。简单来说,相关系数是衡量两个变量间相关关系的指标。

在PySpark中计算两个变量之间的相关系数是非常简单的,往往只需要一条代码:

fraud_df.corr(‘balance’, ‘numTrans’)#计算balance和numTrans的相关系数

输出

Out:0.0004452314017265385

我们还可以通过下面的方法来创建一个相关矩阵。

1
2
3
4
5
6
7
n_numerical = len(numerical)
corr = []
for i in range(0, n_numerical):
    temp = [None] * i
    for j in range(i, n_numerical):
        temp.append(fraud_df.corr(numerical[i], numerical[j]))
    corr.append(temp)

输出结果;
[[1.0, 0.0004452314017265387, 0.0002713991339817875], [None, 1.0, -0.00028057128198165555], [None, None, 1.0]]

正如输出结果所示,这个信用欺诈检测的数据集中的特征之间不存在过大的相关关系,基本全部都为相互独立关系。因此,在选择特征代入机器学习算法训练时,可以采用全部的变量。正也是统计分析的用处,可以帮助我们了解变量之间的线性相关关系,有利于帮住我们选取训练的特征变量。

Python在Spark上的机器学习(二)之数据操作



Python在Spark上的机器学习(二)之数据操作

PySpark

PySpark 是 Spark 为 Python 开发者提供的 API。
Spark是用Scala语言写成的,Scala把要编译的东西编译为Java虚拟机(JVM)的字节码(bytecode)。Spark的开源社区开发了一个叫PySpark的工具库。它允许使用者用Python处理RDD。这多亏了一个叫Py4J的库,它让Python可以使用JVM的对象(比如RDD)。
Pyspark Internals这篇wiki里介绍了pyspark的实现机制,大体是下面这张图就可以表示:

enter image description here

Resilient Distributed Datasets

说到Spark上的数据模式,一定不能少的就是Spark中的核心:RDD了。与许多专有的大数据处理平台不同,Spark建立在统一抽象的RDD之上,使得它可以以基本一致的方式应对不同的大数据处理场景,包括MapReduce,Streaming,SQL,Machine Learning以及Graph等。这即Matei Zaharia所谓的“设计一个通用的编程抽象(Unified Programming Abstraction)。这正是Spark让人着迷的地方。

RDD 具体是什么呢?
RDD,全称Resilient Distributed Datasets,又称弹性分布式数据集。是一个可容错的、并行的数据结构,可以让用户显示地将数据储存到磁盘和内存当中,并能控制数据的分区。

RDD本质上是一个内存数据集,在访问RDD时,指针只会指向与操作相关的部分。例如存在一个面向列的数据结构,其中一个实现为Int的数组,另一个实现为Float的数组。如果只需要访问Int字段,RDD的指针可以只访问Int数组,避免了对整个数据结构的扫描。

RDD将操作分为两类:transformation与action。无论执行了多少次transformation操作,RDD都不会真正执行运算,只有当action操作被执行时,运算才会触发。而在RDD的内部实现机制中,底层接口则是基于迭代器的,从而使得数据访问变得更高效,也避免了大量中间结果对内存的消耗。

使用Pyspark

在按照系列的上一个教程搭建好环境后,在终端中直接输入pyspark就可以运行Python与Spark的交互式的shell了。

那么,下面我们就以一些简单的例子来使用pyspark。

创建RDD

1
2
3
4
data = sc.parallelize(
    [('Amber', 22), ('Alfred', 23), ('Skye',4), ('Albert', 12),
     ('Amber', 9)])
data

输出:

ParallelCollectionRDD[3] at parallelize at PythonRDD.scala:475

RDD对象转换成Python对象

1
2
data_heterogenous = sc.parallelize([('Ferrari', 'fast'), {'Porsche': 100000}, ['Spain','visited', 4504]]).collect()
data_heterogenous

输出:

[(‘Ferrari’, ‘fast’), {‘Porsche’: 100000}, [‘Spain’, ‘visited’, 4504]]

读取文件及统计词频

首先word.txt文件内容如下:

The dynamic lifestyle
people lead nowadays
causes many reactions
in our bodies and
the one that is the
most frequent of all
is the headache. However so good

1
2
3
4
5
6
7
8
9
from operator import add
lines = sc.textFile('word.txt')
counts = lines.flatMap(lambda x: x.split(' '))\
.map(lambda x : (x, 1))\
.reduceByKey(add)
output = counts.collect()
print(output)
for (word, count) in output:
    print("%s: %i" %(word, count))

输出:

[(”, 4), (‘good’, 1), (‘in’, 1), (‘is’, 2), (‘However’, 1), (‘of’, 1), (‘causes’, 1), (‘lifestyle’, 1), (‘The’, 1), (‘headache.’, 1), (‘reactions’, 1), (‘most’, 1), (‘frequent’, 1), (‘that’, 1), (‘all’, 1), (‘our’, 1), (‘dynamic’, 1), (‘nowadays’, 1), (‘so’, 1), (‘the’, 3), (‘people’, 1), (‘bodies’, 1), (‘many’, 1), (‘one’, 1), (‘and’, 1), (‘lead’, 1)]

DataFrame

DataFrameDataFrame是Spark推荐的统一结构化数据接口,是一个不可变的分布式数据集合,它结构与关系数据库中的表类似。

类似于Python Pandas DataFrame或R DataFrame,它能够让用户轻松处理结构化数据。

DataFrame还允许用户通过Spark SQL数据库或者采用一些函数式的方法查询及操作结构数据,下面我们就通过一些例子来了解和使用DataFrame。

创建DataFrames

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
stringJSONRDD = sc.parallelize(("""
{ "id": "123",
"name": "Katie",
"age": 19,
"eyeColor": "brown"
}""",
"""{
"id": "234",
"name": "Michael",
"age": 22,
"eyeColor": "green"
}""",
"""{
"id": "345",
"name": "Simone",
"age": 23,
"eyeColor": "blue"
}""")
)
swimmersJSON = spark.read.json(stringJSONRDD)
swimmersJSON.show()
swimmersJSON.createOrReplaceTempView("swimmersJSON") #这里创建了临时表

输出:

+—+——–+—+——-+
|age|eyeColor| id| name|
+—+——–+—+——-+
| 19| brown|123| Katie|
| 22| green|234|Michael|
| 23| blue|345| Simone|
+—+——–+—+——-+

DataFrame的简单内容及类型查询

1
2
spark.sql("select * from swimmersJSON").collect()
swimmersJSON.printSchema() #显示表数据的类型

输出:

[Row(age=19, eyeColor=’brown’, id=’123’, name=’Katie’),
Row(age=22, eyeColor=’green’, id=’234’, name=’Michael’),
Row(age=23, eyeColor=’blue’, id=’345’, name=’Simone’)]
root
|– age: long (nullable = true)
|– eyeColor: string (nullable = true)
|– id: string (nullable = true)
|– name: string (nullable = true)

指定数据储存及处理的类型

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# Import types
from pyspark.sql.types import *
# Generate comma delimited data
stringCSVRDD = sc.parallelize([
(123, 'Katie', 19, 'brown'),
(234, 'Michael', 22, 'green'),
(345, 'Simone', 23, 'blue')
])
# Specify schema
schema = StructType([
StructField("id", LongType(), True),
StructField("name", StringType(), True),
StructField("age", LongType(), True),
StructField("eyeColor", StringType(), True)
])
# Apply the schema to the RDD and Create DataFrame
swimmers = spark.createDataFrame(stringCSVRDD, schema)
# Creates a temporary view using the DataFrame
swimmers.createOrReplaceTempView("swimmers")
swimmers.printSchema()

输出:

root
|– id: long (nullable = true)
|– name: string (nullable = true)
|– age: long (nullable = true)
|– eyeColor: string (nullable = true)

明明可以自动匹配储存类型,为什么我们还要手动指定类型呢?
因为,在自动匹配类型的情况下,有时会将ID,Age等我们未来将要用来计算的数据以String的方式存储,这样就不利于我们对这些数据进行加减等运算,所以手动指定储存类型还是很有必要的。

使用SQL语句查询及操作数据

1
2
3
4
spark.sql("select count(1) from swimmers").show()
spark.sql("select id, age from swimmers where age = 22").show()
spark.sql(
"select name, eyeColor from swimmers where eyeColor like 'b%'").show()

输出:

+——–+
|count(1)|
+——–+
| 3|
+——–+

+—+—+
| id|age|
+—+—+
|234| 22|
+—+—+

+——+——–+
| name|eyeColor|
+——+——–+
| Katie| brown|
|Simone| blue|
+——+——–+

小结

在这篇文章中我们可以看出,通过Pyspark结合RDD与DataFrames让我们可以用Python用上Spark平台上的分布式优势,也能够进一步加速和优化我们平时的数据操作。通过Spark导出的抽象层的API我们无需学过过于复杂和繁多的语法就能操作RDD上的数据。这篇文章的内容主要是为了后面用在用Python在Spark进行数据建模和机器学习所铺路,但受限于文章篇幅,还有十分多的函数和API无提及。所以有兴趣的读者可以阅读下Spark DataFrame的官方文档深入了解一下。

Python在Spark上的机器学习(一)之环境搭建



Python在Spark上的机器学习(一)之环境搭建

前面已经介绍了不少机器学习的算法了,那么机器学习又该如何结合大数据一起使用么?

常言道:工欲善其事,必先利其器

既然来结合大数据与机器学习,我们就不得不提Spark了。

首先,Apache Spark 是专为大规模数据处理而设计的快速通用的计算引擎。Spark是UC Berkeley AMP lab (加州大学伯克利分校的AMP实验室)所开源的类Hadoop MapReduce的通用并行框架,Spark,拥有Hadoop MapReduce所具有的优点;但不同于MapReduce的是Job中间输出结果可以保存在内存中,从而不再需要读写HDFS,因此Spark能更好地适用于数据挖掘与机器学习等需要迭代的MapReduce的算法。

Spark 是一种与 Hadoop 相似的开源集群计算环境,但是两者之间还存在一些不同之处,这些有用的不同之处使 Spark 在某些工作负载方面表现得更加优越,换句话说,Spark 启用了内存分布数据集,除了能够提供交互式查询外,它还可以优化迭代工作负载。

讲了这么多Spark的优点,那么现在我们就先开始来搭建一个Spark 集群环境吧!

安装基础环境

1. Java1.8环境搭建(下载JDK1.8的):

下载页面:
http://www.oracle.com/technetwork/java/javase/downloads/jdk8-downloads-2133151.html

安装过程可以参考Linux公社给出的教程

Ubuntu用户:
Ubuntu用户可以通过添加PPA源再通过Apt来进行安装

$ sudo add-apt-repository ppa:webupd8team/java
$ sudo apt-get update
$ sudo apt-get install oracle-java8-installer

2. Scala环境搭建

下载scala安装包:

wget -O "scala-2.12.3.deb" 
https://downloads.lightbend.com/scala/2.12.3/scala-2.12.3.deb
或者
wget -O "scala-2.12.3.rpm" "https://downloads.lightbend.com/scala/2.12.3/scala-2.12.3.rpm"

安装deb/rpm包:

rpm -ivh scala-2.12.3.rpm
dpkg -i scala-2.12.3.deb

增加SCALA_HOME

$ vim /etc/profile

增加如下内容;

export SCALA_HOME=/usr/share/scala

刷新配置

$ source /etc/profile

安装Hadoop

1.下载二进制包:
wget http://www-eu.apache.org/dist/hadoop/common/hadoop-2.7.3/hadoop-2.7.3.tar.gz

2.解压并移动至相应目录:

我的习惯是将软件放置/opt目录下:

tar -xvf hadoop-2.7.3.tar.gz
mv hadoop-2.7.3 /opt

3.修改相应的配置文件:

(1) $ vim /etc/profile

增加如下内容:

#hadoop enviroment 
export HADOOP_HOME=/opt/hadoop-2.7.3/
export PATH="$HADOOP_HOME/bin:$HADOOP_HOME/sbin:$PATH"
export HADOOP_CONF_DIR=$HADOOP_HOME/etc/hadoop
export YARN_CONF_DIR=$HADOOP_HOME/etc/hadoop

(2) $ vim $HADOOP_HOME/etc/hadoop/hadoop-env.sh

修改JAVA_HOME 如下:

export JAVA_HOME=<你的Java安装目录>

-

(3) $ vim $HADOOP_HOME/etc/hadoop/core-site.xml

<configuration>
        <property>
                <name>fs.defaultFS</name>
                <value>hdfs://master:9000</value>
        </property>
        <property>
         <name>io.file.buffer.size</name>
         <value>131072</value>
       </property>
        <property>
                <name>hadoop.tmp.dir</name>
                <value>/opt/hadoop-2.7.3/tmp</value>
        </property>
</configuration>

(4) $ vim $HADOOP_HOME/etc/hadoop/hdfs-site.xml

<configuration>
    <property>
      <name>dfs.namenode.secondary.http-address</name>
      <value>master:50090</value>
    </property>
    <property>
      <name>dfs.replication</name>
      <value>2</value>
    </property>
    <property>
      <name>dfs.namenode.name.dir</name>
      <value>file:/opt/hadoop-2.7.3/hdfs/name</value>
    </property>
    <property>
      <name>dfs.datanode.data.dir</name>
      <value>file:/opt/hadoop-2.7.3/hdfs/data</value>
    </property>
</configuration>

(5) $ vim $HADOOP_HOME/etc/hadoop/mapred-site.xml

复制template,生成xml:

cp mapred-site.xml.template mapred-site.xml

内容:

<configuration>
 <property>
    <name>mapreduce.framework.name</name>
    <value>yarn</value>
  </property>
  <property>
          <name>mapreduce.jobhistory.address</name>
          <value>master:10020</value>
  </property>
  <property>
          <name>mapreduce.jobhistory.address</name>
          <value>master:19888</value>
  </property>
</configuration>

(6) $ vim $HADOOP_HOME/etc/hadoop/yarn-site.xml

<!-- Site specific YARN configuration properties -->
         <property>
          <name>yarn.nodemanager.aux-services</name>
          <value>mapreduce_shuffle</value>
     </property>
     <property>
           <name>yarn.resourcemanager.address</name>
           <value>master:8032</value>
     </property>
     <property>
          <name>yarn.resourcemanager.scheduler.address</name>
          <value>master:8030</value>
      </property>
     <property>
         <name>yarn.resourcemanager.resource-tracker.address</name>
         <value>master:8031</value>
     </property>
     <property>
         <name>yarn.resourcemanager.admin.address</name>
         <value>master:8033</value>
     </property>
     <property>
         <name>yarn.resourcemanager.webapp.address</name>
         <value>master:8088</value>
     </property>

至此master节点的hadoop搭建完毕

再启动之前我们需要

格式化一下namenode

$ hadoop namenode -format

安装Spark

下载文件:

wget -O "spark-2.1.0-bin-hadoop2.7.tgz" "http://d3kbcqa49mib13.cloudfront.net/spark-2.1.0-bin-hadoop2.7.tgz"

解压并移动至相应的文件夹:

tar -xvf spark-2.1.0-bin-hadoop2.7.tgz
mv spark-2.1.0-bin-hadoop2.7 /opt

修改相应的配置文件:

(1) $ vim /etc/profie

#Spark enviroment
export SPARK_HOME=/opt/spark-2.1.0-bin-hadoop2.7/
export PATH="$SPARK_HOME/bin:$PATH"

(2) $ vim $SPARK_HOME/conf/spark-env.sh

-

cp spark-env.sh.template spark-env.sh

#配置内容如下:
export SCALA_HOME=/usr/share/scala
export JAVA_HOME=<你的Java安装目录>
export SPARK_MASTER_IP=master
export SPARK_WORKER_MEMORY=1g
export HADOOP_CONF_DIR=/opt/hadoop-2.7.3/etc/hadoop

至此,我们大部分环境基本安装完毕!

测试Spark

为了避免麻烦这里我们使用spark-shell以及本地的文件(非hdfs),做一个简单的worcount的测试。

val file=sc.textFile("/home/ef/Desktop/Notes/wordcount_test")
val rdd = file.flatMap(line => line.split(" ")).map(word => (word,1)).reduceByKey(_+_)
rdd.collect()
rdd.foreach(println)

展示图:
spark-shell.png

小结

到此,我们在Spark上进行机器学习训练的环境,就搭建完毕了,下章我们再开始讲Spark中的数据结构与Python中的区别,以及结合Pyspark来进行数据处理。

SVM支持向量机



SVM(Support Vector Machines)-支持向量机

曾经很多人都认为SVM是现在的最好的分类器,即:在不加以修改的前提之下,就能够在数据上进行训练并能够对训练集之外的数据点做出很好的分类决策。

基于最大间隔分割数据

支持向量机:
优点:泛化错误率低,计算开销不大,结果容易解释
缺点:对参数调节和核函数的选择策略敏感,原始分类器不加修改仅适用于处理二类问题。
enter image description here

在上图中,我们可以看出:我们可以很容易在图中画出一条直线将两组数据点分开。在这种情况下,这组数据被称为线性可分(linearly separable)数据,而将数据集分割开来的直线我们称为分隔超平面(separating hyperplane)。在上图例子中,由于数据点都在二维平面上,所有此时分隔超平面就只是一条直线而已。但是,如果所给的数据为三维的,那么此时用来分隔数据的就是一个平面。依此类推,如果给出一个N(N>3)维数据集,那么则要用一个N-1维的对象来对数据进行分隔,该对象亦被称为超平面(hyperplane)

我们希望通过这样的方式来构建分类器。即如果数据点离决策边界越远,那么其最后的预测效果就越可信。那么我们继续看回上面的图片,我们可以看到有三条直线(一条实线,两条虚线)它们分别都能将数据分隔开,但是其中哪一条才是最理想的呢?通常,我们可以做过这样的方法来确定一个最佳分隔平面,即:我们先找到离分隔平面最近的点,确保它们离分隔平面的距离尽可能远。

这里我们又要先引入一些新的概念:
首先是,点到分隔面的距离被称为间隔(margin)
支持向量(support vector):就是离分割平面最近的那些点。

接下来,就是最大化支持向量都分隔面的距离,并需要找到此问题的优化求解方法。

寻找最大间隔

Maximum Marginal(最大间隔)是SVM的一个理论基础之一。选择使得间隔最大的函数作为分隔平面是十分容易解释的。从概率的角度上而言,就是使得置信度最小的点置信度最大;从现实意义上而言,两个个体的类别差异越大,我们自然也能够更为准确地分类。

svm.png

上图就是一个对之前所提及的类别间隙的一个描述。其中中间的黑色实线为分隔边界(Classifier Boundary)是我们算法中要求解的f(x),红色和蓝色的线(plus plane 与 minus plane)就是支持变量所在的平面,而红色,蓝色之间的间隙就是我们要最大化的分类间的间隙。

首先,我们可以知道其两个支持向量的所在平面可以表达成如下形式:

enter image description here

enter image description here

然后,这两个超平面的距离可以表达成:enter image description here

因此,为了最大化两个平面的距离,我们只要最小化即可。

综上所述,我们可以将整个原理表示为:

Minimize
subject to
for enter image description here

当支持变量确定的时候,整个分割函数也就确定了下来。除此之外,支持向量的出现还可以让向量后方的样本点不用再参与计算,大大降低了算法的计算复杂度。

再者,有关距离计算的优化。的意思是的二范数,由之前我们得到的最大间隔,最大化这个式子等价于最小化,另外由于是一个单调函数,我们可以对其进行平方,和加上系数。数学经验丰富的朋友可能一眼就看出来,这样做是为了方便求导。

最后我们的式子可以写成:

svmalg.png

s.t的意思是subject to,也就是在后面这个限制条件下的意思,这个词在svm的论文里面非常容易见到。这其实是一个带约束的二次规划(quadratic programming, QP)问题,是一个凸问题,凸问题就是指的不会有局部最优解,可以想象一个漏斗,不管我们开始的时候将一个小球放在漏斗的什么位置,这个小球最终一定可以掉出漏斗,也就是得到全局最优解。s.t.后面的限制条件可以看做是一个凸多面体,我们要做的就是在这个凸多面体中找到最优解。

优化求解

这个优化问题可以用拉格朗日乘子法去解,使用了KKT条件的理论,这里直接作出这个式子的拉格朗日目标函数:
Lagrange.png

由于求解这个式子的过程需要拉格朗日对偶性的相关知识,以及较深入的数学背景知识,在这篇文章中暂且不谈,以后博客再另外写一篇有关具体推导的文章。

在此,我先贴出在该问题在论文中的关键推导步骤:

formulation.png

dual.png

上图就是我们需要最终优化的式子了。整篇文章到这里,我们终于得到了SVM线性可分问题的优化式子。

SVM的使用

由于支持向量机算法的实现涉及过多的数学背景,在本中暂不使用原生程序代码实现,而是选择调用Python sklearn 库现有的SVM算法进行使用的举例。

1
2
3
4
5
6
7
8
9
10
from sklearn import svm
from sklearn import datasets
from sklearn import metrics
clf = svm.SVC()
print(clf)
iris = datasets.load_iris()
X, y = iris.data, iris.target
clf.fit(X, y)
pred = clf.predict(X)
print(metrics.accuracy_score(y,pred))

输出结果
SVC(C=1.0, cache_size=200, class_weight=None, coef0=0.0,
decision_function_shape=None, degree=3, gamma=’auto’, kernel=’rbf’,
max_iter=-1, probability=False, random_state=None, shrinking=True,
tol=0.001, verbose=False)
0.986666666667

本例使用的是sklearn库自带的iris数据集使用SVM算法进行训练,然后再进行回测。首先,我们可以看到在不做任意处理的前提下,SVM模型的预估效果也是相当不错的,其准确率高达98%(其结果主要因为使用的数据集优秀导致的,直接运用于工程上时不会有这么高的准确率)。

当然,上面例子中的算法模型的实现方式是十分简陋的。如果真正要使用SVM进行严格地建模,测试集与训练集的划分问题,数据的归一化处理问题等。都是我们需要考虑的元素。但由于本文主要为了介绍与探讨SVM算法,其他细节问题就不一一处理,详细方法可以参考我写的其他文章。

SVM的其他实现

除了Python的sklearn库外,SVM在其它语言及平台也有实现。其中:
最流行的有

LIBSVM:https://www.csie.ntu.edu.tw/~cjlin/libsvm/
这是经典的svm库支持多种语言调用

再者,在R语言中也有SVM算法的实现:

e1071:
https://cran.r-project.org/web/packages/e1071/index.html