tonglin0325的个人主页

机器学习——支持向量机(SVM)之Platt SMO算法

tonglin0325

**　　Platt SMO算法是通过一个外循环来选择第一个alpha值**的，并且其选择过程会在两种方式之间进行交替：

一种方式是在所有数据集上进行单遍扫描，另一种方式则是在非边界alpha中实现单遍扫描。　　

　　所谓非边界alpha指的就是那些不等于边界0或者C的alpha值。对整个数据集的扫描相当容易，而实现非边界alpha值的扫描时，首先需要建立这些alpha值的列表，然后再对这个表进行遍历。同时，该步骤会跳过那些已知的不会改变的alpha值，即。

　　在选择第一个alpha值后，算法会通过一个内循环来选择第二个alpha值。在优化过程中，会通过最大化步长的方式来获得第二个alpha值。在简化版SMO算发放中，我们会在选择j之后计算错误率Ej。但在这里，我们会建立一个全局的缓存用于保存误差值，并从中选择使得步长或者说Ei-Ej最大的alpha值。

 

完整版的SMO代码及其注释：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
'''#######********************************
以下是没有核函数的版本
'''#######********************************

class optStructK:
    def __init__(self,dataMatIn, classLabels, C, toler):  # Initialize the structure with the parameters 
        self.X = dataMatIn
        self.labelMat = classLabels
        self.C = C
        self.tol = toler
        self.m = shape(dataMatIn)[0]
        self.alphas = mat(zeros((self.m,1)))
        self.b = 0
        self.eCache = mat(zeros((self.m,2))) #first column is valid flag
        
def calcEkK(oS, k):			#计算误差
    fXk = float(multiply(oS.alphas,oS.labelMat).T*(oS.X*oS.X[k,:].T)) + oS.b
    Ek = fXk - float(oS.labelMat[k])
    return Ek
        
def selectJK(i, oS, Ei):        	#用于选择第2个循环（内循环）的alpha值，内循环中的启发式方法
    maxK = -1; maxDeltaE = 0; Ej = 0
    oS.eCache[i] = [1,Ei]  #set valid #choose the alpha that gives the maximum delta E
    validEcacheList = nonzero(oS.eCache[:,0].A)[0]
    if (len(validEcacheList)) > 1:
        for k in validEcacheList:   #loop through valid Ecache values and find the one that maximizes delta E
            if k == i: continue 	#跳过本身
            Ek = calcEk(oS, k)
            deltaE = abs(Ei - Ek)
            if (deltaE > maxDeltaE):	#选取具有最大步长的j
                maxK = k; maxDeltaE = deltaE; Ej = Ek
        return maxK, Ej
    else:   #in this case (first time around) we don't have any valid eCache values
        j = selectJrand(i, oS.m)
        Ej = calcEk(oS, j)
    return j, Ej

def updateEkK(oS, k):		#alpha改变后，更新缓存
    Ek = calcEk(oS, k)
    oS.eCache[k] = [1,Ek]

#内部循环的代码
def innerLK(i, oS):		
    Ei = calcEk(oS, i)
    #判断每一个alpha是否被优化过，如果误差很大，就对该alpha值进行优化，toler是容错率
    if ((oS.labelMat[i]*Ei < -oS.tol) and (oS.alphas[i] < oS.C)) or ((oS.labelMat[i]*Ei > oS.tol) and (oS.alphas[i] > 0)):
        j,Ej = selectJ(i, oS, Ei) 			#使用启发式方法选取第2个alpha，选取使得误差最大的alpha
        alphaIold = oS.alphas[i].copy(); alphaJold = oS.alphas[j].copy();
        #保证alpha在0与C之间
        if (oS.labelMat[i] != oS.labelMat[j]):		#当y1和y2异号，计算alpha的取值范围 
            L = max(0, oS.alphas[j] - oS.alphas[i])
            H = min(oS.C, oS.C + oS.alphas[j] - oS.alphas[i])
        else:						#当y1和y2同号，计算alpha的取值范围
            L = max(0, oS.alphas[j] + oS.alphas[i] - oS.C)
            H = min(oS.C, oS.alphas[j] + oS.alphas[i])
        if L==H: print "L==H"; return 0
        #eta是alpha[j]的最优修改量，eta=K11+K22-2*K12,也是f(x)的二阶导数，K表示内积
        eta = 2.0 * oS.X[i,:]*oS.X[j,:].T - oS.X[i,:]*oS.X[i,:].T - oS.X[j,:]*oS.X[j,:].T
        #如果二阶导数-eta <= 0，说明一阶导数没有最小值，就不做任何改变，本次循环结束直接运行下一次for循环
        if eta >= 0: print "eta>=0"; return 0
        oS.alphas[j] -= oS.labelMat[j]*(Ei - Ej)/eta	#利用公式更新alpha[j]，alpha2new=alpha2-yj(Ei-Ej)/eta
        oS.alphas[j] = clipAlpha(oS.alphas[j],H,L)	#判断alpha的范围是否在0和C之间
        updateEk(oS, j) 				#在alpha改变的时候更新Ecache
        #如果alphas[j]没有调整，就忽略下面语句，本次循环结束直接运行下一次for循环
        if (abs(oS.alphas[j] - alphaJold) < 0.00001): print "j not moving enough"; return 0
        oS.alphas[i] += oS.labelMat[j]*oS.labelMat[i]*(alphaJold - oS.alphas[j])#update i by the same amount as j
        updateEk(oS, i) 				#在alpha改变的时候更新Ecache
        #已经计算出了alpha，接下来根据模型的公式计算b  
        b1 = oS.b - Ei- oS.labelMat[i]*(oS.alphas[i]-alphaIold)*oS.X[i,:]*oS.X[i,:].T - oS.labelMat[j]*(oS.alphas[j]-alphaJold)*oS.X[i,:]*oS.X[j,:].T
        b2 = oS.b - Ej- oS.labelMat[i]*(oS.alphas[i]-alphaIold)*oS.X[i,:]*oS.X[j,:].T - oS.labelMat[j]*(oS.alphas[j]-alphaJold)*oS.X[j,:]*oS.X[j,:].T
        #根据公式确定偏移量b，理论上可选取任意支持向量来求解，但是现实任务中通常使用所有支持向量求解的平均值，这样更加鲁棒
        if (0 < oS.alphas[i]) and (oS.C > oS.alphas[i]): oS.b = b1
        elif (0 < oS.alphas[j]) and (oS.C > oS.alphas[j]): oS.b = b2
        else: oS.b = (b1 + b2)/2.0
        return 1			#如果有任意一对alpha发生改变，返回1
    else: return 0

#无核函数 Platt SMO 的外循环
def smoPK(dataMatIn, classLabels, C, toler, maxIter):    #full Platt SMO
    oS = optStruct(mat(dataMatIn),mat(classLabels).transpose(),C,toler)
    iter = 0
    entireSet = True; alphaPairsChanged = 0
    #有alpha改变同时遍历次数小于最大次数，或者需要遍历整个集合
    while (iter < maxIter) and ((alphaPairsChanged > 0) or (entireSet)):	
        alphaPairsChanged = 0
        #首先进行完整遍历，过程和简化版的SMO一样
        if entireSet:   #go over all
            for i in range(oS.m):        
                alphaPairsChanged += innerL(i,oS)		#i是第1个alpha的下标
                print "fullSet, iter: %d i:%d, pairs changed %d" % (iter,i,alphaPairsChanged)
            iter += 1
        #非边界遍历，挑选其中alpha值在0和C之间非边界alpha进行优化 
        else:#go over non-bound (railed) alphas
            nonBoundIs = nonzero((oS.alphas.A > 0) * (oS.alphas.A < C))[0]	#然后挑选其中值在0和C之间的非边界alpha进行遍历
            for i in nonBoundIs:
                alphaPairsChanged += innerL(i,oS)
                print "non-bound, iter: %d i:%d, pairs changed %d" % (iter,i,alphaPairsChanged)
            iter += 1
        #如果这次是完整遍历的话，下次不用进行完整遍历
        if entireSet: entireSet = False 			#终止完整循环
        elif (alphaPairsChanged == 0): entireSet = True  	#如果alpha的改变数量为0的话，再次遍历所有的集合一次
        print "iteration number: %d" % iter
    return oS.b,oS.alphas

 

ubuntu重启搜狗输入法

tonglin0325
1
2
3
fcitx | xargs kill
sogou-qimpanel | xargs kill

 或者编写Shell脚本restart_sougou.sh，放到/usr/bin目录下，不要忘记chmod修改运行权限，然后就能在终端输入restart_sougou命令来执行重启搜狗输入法

1
2
3
4
5
6
#!/bin/sh
pidof fcitx | xargs kill
pidof sogou-qimpanel | xargs kill
nohup fcitx  1>/dev/null 2>/dev/null &amp;
nohup sogou-qimpanel  1>/dev/null 2>/dev/null &amp;

 

机器学习——支持向量机(SVM)之拉格朗日乘子法，KKT条件以及简化版SMO算法分析

tonglin0325

SVM有很多实现，现在只关注其中最流行的一种实现，即序列最小优化（Sequential Minimal Optimization，SMO）算法，然后介绍如何使用一种核函数（kernel）的方式将SVM扩展到更多的数据集上。

 

1.基于最大间隔分隔数据

几个概念：

1.线性可分（linearly separable）：对于图6-1中的圆形点和方形点，如果很容易就可以在图中画出一条直线将两组数据点分开，就称这组数据为线性可分数据

2.分隔超平面（separating hyperplane）：将数据集分隔开来的直线称为分隔超平面

3.如果数据集是1024维的，那么就需要一个1023维的超平面来对数据进行分隔

4.间隔（margin）：数据点到分隔面的距离称为间隔

5.支持向量（support vector）:离分隔超平面最近的那些点

 

支持向量机的优点：泛化错误率低，计算开销不大，结果易解释

支持向量机的缺点：对参数调节和核函数的选择敏感，原始分类器不加修改仅适用于处理二类问题

适用数据类型：数值型和标称型数据**
**

 

2.寻找最大间隔

如何求解数据集的最佳分隔直线？

分隔超平面的形式可以写成  

其中 w = (w1,w2,w3…wd)为法向量，决定了超平面的方向，其中d等于数据的维度，

全文 >>

广告系统——广告归因

tonglin0325

1.广告归因的概念

在做用户增长的时候需要对各渠道（广告投放平台，如腾讯广告、字节-巨量引擎、百度营销平台等）上的投放效果进行广告归因，归因的作用是判断用户从何渠道下载应用（或打开落地页、小程序），通过匹配用户广告行为，分析是何原因促使用户产生转化。 广告归因的数据结果是衡量广告效果、评估渠道质量的重要依据，可帮助广告主合理优化广告素材，高效开展拉新、促活营销推广。

参考：神策广告归因介绍

2.常用的渠道

3.广告归因原理

1.用户A在app1上点击了app2在渠道方（各种投放平台，比如巨量引擎）投放的广告，这时候渠道方就知道用户A点击了广告

2.第三方归因平台（即下图中的服务端，比如字节穿山甲的增长参谋）会和很多的渠道方进行合作，渠道方支持将数据回传给第三方的归因平台，比如oaid，imei这种的用户ID，一般需要在渠道方的平台上进行配置，参考：appsflyer-巨量引擎广告归因配置 - Bytedance Ads Configuration

3.当用户首次打开APP的时候，会将埋点数据上报给第三方的归因平台（像穿山甲会提供SDK用于上传打点），一般也是在渠道方平台上进行配置，参考：归因结果兼容API使用说明：穿山甲

4.归因平台再将激活的数据回传给各个渠道方，用于优化投放的点击率（CTR）

5.归因平台完成渠道归因

6.上报数据到数据仓库中

7.app内部打点统计次留，播放，付费的时间，上报给归因平台

8.归因再将这些转化数据回传给各个渠道方，用于优化投放的转化率（CVR）

全文 >>

机器学习——Logistic回归

tonglin0325

 

1.基于Logistic回归和Sigmoid函数的分类

 

2.基于最优化方法的最佳回归系数确定

 

2.1 梯度上升法

参考：机器学习——梯度下降算法

 

2.2 训练算法：使用梯度上升找到最佳参数

 

Logistic回归梯度上升优化算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
def loadDataSet():
    dataMat = []; labelMat = []
    fr = open('testSet.txt')
    for line in fr.readlines():
        lineArr = line.strip().split()
        dataMat.append([1.0, float(lineArr[0]), float(lineArr[1])])	#加上第0维特征值
        labelMat.append(int(lineArr[2]))
    return dataMat,labelMat	#返回数据矩阵和标签向量

def sigmoid(inX):
    return 1.0/(1+exp(-inX))

def gradAscent(dataMatIn, classLabels):		#Logistic回归梯度上升优化算法
    dataMatrix = mat(dataMatIn)             	#由列表转换成NumPy矩阵数据类型，dataMatrix是一个100&times;3的矩阵
    labelMat = mat(classLabels).transpose() 	#由列表转换成NumPy矩阵数据类型，labelMat是一个100&times;1的矩阵
    m,n = shape(dataMatrix)		    	#shape函数取得矩阵的行数和列数，m=100,n=3
    alpha = 0.001				#向目标移动的步长
    maxCycles = 500				#迭代次数
    weights = ones((n,1))			#3行1列的矩阵，这个矩阵为最佳的回归系数，和原来的100&times;3相乘，可以得到100&times;1的结果
    for k in range(maxCycles):              
        h = sigmoid(dataMatrix*weights)     	#矩阵相乘，得到100&times;1的矩阵，即把dataMat的每一行的所有元素相加
        error = (labelMat - h)              	#求出和目标向量之间的误差
	#梯度下降算法
        weights = weights + alpha * dataMatrix.transpose()* error #3&times;100的矩阵乘以100&times;1的矩阵，weights是梯度算子，总是指向函数值增长最快的方向
    return weights				#返回一组回归系数，确定了不同类别数据之间的分割线

 

1
2
3
dataMat,labelMat = loadDataSet()
print gradAscent(dataMat,labelMat)	#输出回归系数

全文 >>

zk学习笔记——超级用户

tonglin0325

如果遇到auth遗忘，又想删除zknode的情况，可以使用超级用户用来删除zknode

超级用户只能在zkserver启动的时候启用，需要在zkserver的启动命令中添加 -Dzookeeper.DigestAuthenticationProvider.superDigest 参数

 

1
2
-Dzookeeper.DigestAuthenticationProvider.superDigest=super:xQJmxLMiHGwaqBvst5y6rkB6HQs=

 然后就可以使用 super:admin 的auth来删除zknode

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
[zk: localhost:2181(CONNECTED) 15] addauth digest super:admin
[zk: localhost:2181(CONNECTED) 16] get /hbase

cZxid = 0x155e7a
ctime = Wed Oct 20 21:35:34 CST 2021
mZxid = 0x155e7a
mtime = Wed Oct 20 21:35:34 CST 2021
pZxid = 0x15639a
cversion = 40
dataVersion = 0
aclVersion = 0
ephemeralOwner = 0x0
dataLength = 0
numChildren = 12
[zk: localhost:2181(CONNECTED) 17] rmr /hbase

参考：zookeeper acl认证机制及dubbo、kafka集成、zooviewer/idea zk插件配置

 

tonglin0325

标签

标签云

AWS Airbnb Android CDH Doris ELK Flink Git Grafana HAProxy HBase Hadoop Hive Hudi InfluxDB JDBC JMeter JVM Java LaTex Linkedin Linux ML ML Infra MPP Maven MySQL Nexus OpenTSDB Paper Play Prometheus Python React Redis RocksDB Scala Solr Spark SpringBoot SpringMVC Thrift YARN antlr arthas avro cassandra clickhouse confluent docker filebeat flume golang google gradle hexo impala jenkins k8s kafka kerberos kudu ldap mac mongo mybatis nginx nlp open-falcon openwrt parquet presto ranger rocketmq scyllaDB twitter zookeeper 刷题 前端 图存储及计算 多线程 广告系统 开发工具 数据结构 杂谈 算法 系统设计 计算机基础 设计模式

文章归档

最近文章