L1范数正则化SVM聚类算法
上传者:曹计昌|上传时间:2015-04-15|密次下载
L1范数正则化SVM聚类算法
内容需要下载文档才能查看
为Γ2:minw2+Cξi, s.t.yi (xi,w+b)≥1 ξi,i=1,2, ,m。
2
ni=1
d≤∑(wTφ(xi)+b)≤d
L1-SVM求解的问题为Γ1[2]:
min∑ 1 yi (xi,w+b) s.t.
i=1
+
m
问题Γ3等价于问题Γ4:
minw+Cξ (2) s.t. d≤∑(wTφ(xi)+b)≤d (3)
i=1n
w
1
≤s
L1-SVM能同时实现分类和特征选择,即选择样例的一些分量参与模型的训练,构造低维模型(w∈Rd,d<<n),这样在对高维样例分类时,可以剔出噪声变量。L2-SVM用于
聚类研究成为热点之一,已提出了CPMMC[3] MMC[4-5]、IterSVR[6-7]等算法,与当前主流聚类算法,如K-Means聚类(KM)和Normalized Cut(NC)谱聚类算法相比有较大优势[8]。L2-SVM用于聚类时,同样是求解问题Γ2,只是Γ2中各样例xi的类标签yi的值是不知道的,目标是求解出w、b和yi的值,由于yi∈{±1},因此这是一个组合优化问题,当前求解的方法是使用割平面方法,把原问题的m个约束条件依次加入目标函数,依次求近似解,从而逐次逼近原问题的解。
基于混合模型聚类特征选择问题已引起重视,说明无监督的学习,运用特征选择技术可以改进聚类算法的性能。SVM分类学习特征选择问题已有文献讨论,但SVM用于聚类的特征选择问题尚未见文献报道。
本文提出L1范数正则化SVM聚类算法,该算法在实现聚类的过程中能够同时进行特征选择。
1n1nT
wTφ(xi)+b ∑ci ξ ∑cisign(wφ(xi)+b) ≤0 i11=i=nn
(4) ci∈ , ξ≥0
其中,ci∈{0,1}; 为约束集;sign( )为符号函数。对约束不等式式(3)写成矩阵形式得:
T
d≤ w
n×1
φ(x1) φ(x2) φ(xn) ×1 ≤d b
n
wT 11×n× φ(x) φ(x) φ(x) ,n d≤ 2n 1 b ≤d
1×n ,则得: 令u1= φ(x1) φ(x2) φ(xn) ,n 1×
T
w
d≤u1× ≤d
b
对约束式(2)进行等价变换处理得:
1n1nT
wTφ(xi)+b ≤0, ci∈ ∑ci ξ ∑cisign(wφ(xi)+b)
ni=1ni=1
φ(x1) φ(x2) φ(xn) 1n
∑ci [wb] ×
ni=111×n diag(sign(wT[φ(x1) φ(x2) φ(xn)]+b))diag(ST)×1n×1≤0
2 L1范数正则化SVM聚类问题解
2.1 L1范数正则化SVM聚类原问题解
L1范数正则化SVM聚类问题原问题Γ3可表示为:
cn
minw+∑ξi (1)
ni=1
基金项目:基金项目:中国石油大学(北京)基础学科研究基金资助项目 作者简介:作者简介:刘建伟(1966-),男,副研究员、博士,主研方向:机器学习;李双成、付 捷,硕士研究生;罗雄麟,教授、博士 收稿日期:收稿日期:2011-08-01 E-mail:liujw@http://wendang.chazidian.com
186 计 算 机 工 程 2012年6月20日 其中,S=[c1 c2 cn],令:
u φ(x1) φ(x2) φ(xn) 11×n
diag(sign(wT
2=[φ(x1) φ(x2) φ(xn)]+ b))×diag(ST)×1
n×1
则有:
[w
T
b]uξ≤ 1∑n
cT w 1n
2 ni u2 ξ
≤i=1 b
n∑ci=1
i
整理得问题Γ5:
min ||w||11+Cξ (5) s.t. d≤u w w 1 ≤d, uT2 ≤ b b ξ
1n
n∑ci=1
i
记 w b
=a,则minw+Cξ问题等价于min ||a||1+Cξ问
题。||a||1在0点不连续,
不可导。设ai=a+i a i,a+i>0,a i>0,则非平滑问题Γ5等价于以下平滑问题Γ6。
min1Ta++1Ta +Cξ (6)
+
a+
s.t.
[u1
u1
0] a
a
≤d, [ uu 1
1
0] a
≤d, ξ
ξ
a+
[ uT2u2
1] a
≤ 1∑nc ξ ni=1
i
其中,uT
1= 11×n × φ(x1) φ(x2) φ(xn) ,n ;S=[c1 c2 cn];u= φ(x1)φ(x2) φ(xn) 11×n
diag(sign(wT
2[φ(x1)φ(x2) φ(xn)]+ b))×diag(ST)×1n×1
2.2 L1范数正则化SVM聚类对偶问题解
根据表示理论,w=∑n
λi=1iφ(xi),其中,λi为拉格朗日乘
子。因此,问题Γ3可等价表示为问题Γ7:
min ||λ||11
+Cξ (7) s.t. d≤∑n(wTφ(xi)+b)≤d (8)
i=11n∑nc1nwT
i ξ ∑cisign(φ wTφi=1ni=1
(xi)+b)
(xi)+b ≤0 c≥0
(9)
i∈ , ξ其中,w=∑n
λiφ(xi)。对约束式(8)进行等价变换处理得:
i=1
d≤ φ wTb
(x1) φ(x2) φ(xn) ×1n×1 n ≤ d
d≤ 11×n× φ(x1) φ(x2) φ(xn) T,n w ≤ b d
d≤ T
11×n× φ(x1) φ(x2) φ(xn) ,n
[φ(x1) φ(x2) φ(xn)]×λ ≤ b
d
令:
u 1×n
(1)φ(x2) φ(xn) T1= 1× φx,n
[φ(x
1)φ(x2) φ(xn)]0
01
则 d≤u w
1× b ≤
d
对约束式(9)进行等价变换处理得:
1n∑nc1∑ncT
i=1i ξ n wTφi=1
isign(wtφ(xi)+bt)
(xi)+b ≤0, ci∈ 1nT
φ(xφ(x
1) 2) φ(xn) n∑ci [wb]i=1 11×n
diag(sign(wTTn×1t[φ(x1) φ(x2) φ(xn)]+bt))diag(S)×1≤0 1n∑ncT[φTb] 1
i [λ(x1) φ(x2) φ(xn)]i= φ(x1) φ(x2) φ(xn)
11×n
×diag(sign(wT(xTn×1
t[φ1) φ(x2) φ(xn)]+bt))diag(S)×1≤0其中,S=[c1 c2 cn]。令:
u [φ(x1) φ(x2) φ(xn)]T0 φ(x1) φ(x2) φ(xn) 2=
01 11×n
diag(sign(wTt[φ(x1)φ(x2) φ(xn)]+bt))diag(ST)×1n×1
则有:
[λT
b]×u12 ξ
≤
n∑ncT λ
i u2 ξ≤
1i=1 b
n∑n
ci=1
i 整理问题Γ8,得:
min ||λ||11+Cξ (10) s.t. d λ T λ≤u ≤d, u 12≤ b b
ξ
1n∑n
ci=1
i 其中:
u 11×n× φ(x) φ(x) φ(x) T,n [φ(x1) φ(x2) φ(xn)]0 1= 12n
01 u [φ(x1) φ(x2) φ(xTn)]0 φ(x1) φ(x2) φ(xn) 2= 01
11×n
× diag(sign(wT[φ(xT1) φ(x2) φ(xn)]+b))diag(S)×1n×1S=[cn
1 c2 cn], w=∑λ=1iφ(xi)
i令λ+ + i=λi
λi
,λi
>0,λi>0,问题Γ8等价问题Γ9。
min1Tλ++1Tλ +Cζ s.t.
[u0] λ+ λ+ 1
u1
λ ≤d, [ u
1u10] λ ≤d, ξ ξ
λ+[ uT2u2
1]
λ
≤ 1∑nci ξ n
i=1
3 L1范数正则化}SVM聚类算法实现
由于ci∈{0,1,S=[c1 c2 cn],原问题Γ6和对偶问题
Γ9均为0-1规划问题,当样例个数大时,无法求解。把a+、
a (原问题)或λ+、λ (对偶问题)看做一个变量,则S为另一
个变量,前者为连续向量,后者为0-1离散变量,因此,原问题Γ6和对偶问题Γ9实为双变量混合0-1规划问题。本文提出的算法类似于文献[7],算法初始随机设定S的值,然后在给定的S值处,求解原问题Γ6或对偶问题Γ9得到a+、a (原问题)或λ+、λ (对偶问题)的值。接着,算法按坐标依次
置换向量S的值,并计算置换后前目标函数值的差是否大于某个预设的阈值。如果大于,则保留变换值,继续置换下一位,否则,取消当前的改变,这样对S的每一步改变保证目标函数呈下降趋势。当S的每一个分量均测试完后,也就是经过一大轮测试后,此时用一大轮测试后的S值,求解原问题Γ6或对偶问题Γ9得到新的a+、a (原问题)或λ+、λ (对偶问题)的值,用符号+、(原问题)或、(对偶问题)表示该值,计算+、(原问题)或+、 (对偶问题)处的
第38卷 第12期 刘建伟,李双成,付 捷,等: L1 范数正则化 SVM 聚类算法 187 目标函数值与a+、a (原问题)或λ+、λ (对偶问题)处的目标函数值的差,如果小于某个预设的阈值,算法结束,否则重复上述过程。L1范数SVM聚类算法伪代码如下:
输入 样例集(x1,x2, ,xn),算法迭代步数T,迭代停止阈值τ
输出 预测样例集(x1,x2, ,xn)的类标签(y1,y2, ,yn)和模型权值
随机设置S∈{0,1}n
的起始值,固定S求解原问题Γ6或
对偶问题Γ+ 9,得到a、a (求解原问题)或λ+、λ(求解对偶问题)的值。
for i=1 to T
for j=1+(i-1) mod n to n if Sj,j=1 then Sj,j=0 else Sj,j=1
计算Sj,j改变前后,原问题Γ6或对偶问题Γ9目标函数的值,如果改变前后目标函数的值下降大于τ,则Sj,j改变保留,否则Sj,j恢复原来值∑=∑+Sj,j改变前后,原问题Γ6或对偶问题Γ9目标函数的值。
j=1+j end
if ∑≤τ then
{求解原问题Γ6或对偶问题Γ9,得到a+、a (求解原问题)或λ+、λ 求解对偶问题)的值,如果改变前后目标函数的值下降大于τ}
break end
4 实验结果与分析实验结果与分析
实验采用UCI数据库中的ionosphere和satellite数据、
mnist数据、USPS数据、Letter数据和20个新闻组文本数据。
其中mnist数据是Google实验室的Corinna Cortes和纽约大
学柯朗研究所建立的一个手写数字数据库,训练库有 60 000张手写数字图像,测试库有10 000张。USPS数据是
美国国家邮政局收集的手写体数据库,有0~9共10个类别,
每个类有1 100个样例。Letter数据是手写体英文字母的数据
库。数字识别选用比较困难聚类的3和8、1和7、2和7、8
和9数字。8组数据集的特性如表1所示。
表1 8组数据集的特性
数据集名 样例个数 样例维数
ionosphere 351 34 Letter 1 555 16 Text1 1 980 8 014 Text2 1 989 8 014 USPS 1 100 256 mnist 5 000 784 satellite 2 236 36 UCI digits
1 797
64
L1范数正则化SVM聚类原问题求解算法用L1SVMC-P表示,L1范数正则化SVM聚类对偶问题求解算法用L1SVMC-D表示。表2给出了8种实际数据集上CPMMC、
L1SVMC-P和L1SVMC-D算法的聚类错误情况比较,表中错误率为100次的平均值。括号中的数字表示选择的特征数。该表显示:在平均预测错误率方面,本文提出的L1SVMC-P和L1SVMC-D算法与CPMMC相当,但是本文算法实现了特征选择。
表2 算法的聚类错误率算法的聚类错误率比较 (%)
数据集名 CPMMC L1SVMC-P L1SVMC-D ionosphere 28.65 24.20(24) 23.20(26) Letter 5.78 5.90(7) 4.80(7) satellite 1.54 1.60(23) 1.40(21) Text1 6.45 6.34(6 034) 5.16(5 456) Text2 4.61 3.67(5 631) 0.10(4 879) USPS 0.89 0.69(136) 0.72(178) mnist
4.34
4.10 (234)
3.41(159)
5 结束语
能够同时实现特征选择的无监督的聚类学习算法是当前新兴的机器学习热点问题,本文使用L1范数正则化技术,实现SVM聚类问题,给出了L1范数正则化SVM聚类问题的原问题和对偶问题统一表示形式。在算法实现上,提出了一种目标下降的混合整数规划算法,在8组实际数据集上的实验验证了该算法能够实现特征选择。
参考文献
[1] Vapnik V. Statistical Learning Theory[M]. New York, USA: [s. n.],
1998.
[2] Zhu Ji, Rosset S, Hastie T, et al. Neural Information Processing
Systems[M]. [S. l.]: MIT Press, 2003.
[3] Zhao Bin, Wang Fei, Zhang Changshui. Efficient Maximum
Margin Clustering via Cutting Plane Algorithm[C]//Proc. of SIAM
International Conference on Data Mining. [S. l.]: ACM Press,
2008.
[4] Neufeld J, Larson B, Schuurmans D, et al. Maximum Margin
Clustering[C]//Proc. of the 17th Annual Conference on Neural
Information Processing Systems. [S. l.]: MIT Press, 2004.
[5] Xu Linli, Schuurmans D. Unsupervised and Semi-supervised
Multi-class Support Vector Machines[C]//Proc. of the 20th
National Conference on Artificial Intelligence. [S. l.]: MIT Press, 2005: 904-910.
[6] Valizadegan H, Jin Rong. Generalized Maximum Margin Cluster-
ing and Unsupervised Kernel Learning[C]//Proc. of the 21st Annual Conference on Neural Information Processing Systems. [S. l.]: MIT Press, 2007: 1417-1424.
[7] Mangasarian O L, Wild E W. Feature Selection for Nonlinear
Kernel Support Vector Machines[C]//Proc. of the 7th IEEE International Conference on Data Mining. [S. l.]: IEEE Press, 2007: 231-236.
[8] Shi Jianbo, Malik J. Normalized Cuts and Image Segmentation[J].
IEEE Trans. on Pattern Analysis and Machine Intelligence, 2000, 22(8): 888-905.
编辑 顾逸斐
下载文档
热门试卷
- 2016年四川省内江市中考化学试卷
- 广西钦州市高新区2017届高三11月月考政治试卷
- 浙江省湖州市2016-2017学年高一上学期期中考试政治试卷
- 浙江省湖州市2016-2017学年高二上学期期中考试政治试卷
- 辽宁省铁岭市协作体2017届高三上学期第三次联考政治试卷
- 广西钦州市钦州港区2016-2017学年高二11月月考政治试卷
- 广西钦州市钦州港区2017届高三11月月考政治试卷
- 广西钦州市钦州港区2016-2017学年高一11月月考政治试卷
- 广西钦州市高新区2016-2017学年高二11月月考政治试卷
- 广西钦州市高新区2016-2017学年高一11月月考政治试卷
- 山东省滨州市三校2017届第一学期阶段测试初三英语试题
- 四川省成都七中2017届高三一诊模拟考试文科综合试卷
- 2017届普通高等学校招生全国统一考试模拟试题(附答案)
- 重庆市永川中学高2017级上期12月月考语文试题
- 江西宜春三中2017届高三第一学期第二次月考文科综合试题
- 内蒙古赤峰二中2017届高三上学期第三次月考英语试题
- 2017年六年级(上)数学期末考试卷
- 2017人教版小学英语三年级上期末笔试题
- 江苏省常州西藏民族中学2016-2017学年九年级思想品德第一学期第二次阶段测试试卷
- 重庆市九龙坡区七校2016-2017学年上期八年级素质测查(二)语文学科试题卷
- 江苏省无锡市钱桥中学2016年12月八年级语文阶段性测试卷
- 江苏省无锡市钱桥中学2016-2017学年七年级英语12月阶段检测试卷
- 山东省邹城市第八中学2016-2017学年八年级12月物理第4章试题(无答案)
- 【人教版】河北省2015-2016学年度九年级上期末语文试题卷(附答案)
- 四川省简阳市阳安中学2016年12月高二月考英语试卷
- 四川省成都龙泉中学高三上学期2016年12月月考试题文科综合能力测试
- 安徽省滁州中学2016—2017学年度第一学期12月月考高三英语试卷
- 山东省武城县第二中学2016.12高一年级上学期第二次月考历史试题(必修一第四、五单元)
- 福建省四地六校联考2016-2017学年上学期第三次月考高三化学试卷
- 甘肃省武威第二十三中学2016—2017学年度八年级第一学期12月月考生物试卷
网友关注
- 食品雕刻
- 临沂第二十九中学饮用水污染事件责任追究制度
- 机械运动
- 2010下期末考试
- 《中和反应》综合练习一
- 空气与生命
- 2.7 元素符号表示的量
- 初中物理实验方法
- 浙教版科学八年级上第1章水和水的溶液
- 常见的酸和碱学案3
- 九年级科学期末专题训练
- 临沂第二十九中学饮用水水质送检制度
- 初二上科学期中试卷
- 《学生体质健康标准》测试工作管理制度
- 小记者档案
- 食品雕刻34
- 常见的酸和碱教案2--2
- 微课程在信息技术教学中的有效应用
- 第二章微粒的模型和符号复习
- 浙教版七年级科学下册第三章1-3节测试题
- 浙教版八年级科学下册第二章 粒子的模型与符号 测试题2
- 2015年热点雾霾
- 第2章粒子的模型与符号综合复习
- 2011年温州市中考科学试题及答案
- 2010年浙江省萧山中学提前自主招生推荐生文化考试卷科学 (word版有答案)
- 七环结(两课时)
- 七年级下科学第一章代代相传的生命知识点
- 2013年温州市中考科学试题及答案
- 《6.1_怎样认识力》教学设计
- 初中化学教学设计和反思
网友关注视频
- 【部编】人教版语文七年级下册《过松源晨炊漆公店(其五)》优质课教学视频+PPT课件+教案,江苏省
- 北师大版八年级物理下册 第六章 常见的光学仪器(二)探究凸透镜成像的规律
- 冀教版小学数学二年级下册第二单元《有余数除法的简单应用》
- 8 随形想象_第一课时(二等奖)(沪教版二年级上册)_T3786594
- 河南省名校课堂七年级下册英语第一课(2020年2月10日)
- 【部编】人教版语文七年级下册《泊秦淮》优质课教学视频+PPT课件+教案,辽宁省
- 沪教版八年级下册数学练习册21.4(1)无理方程P18
- 二年级下册数学第二课
- 冀教版英语三年级下册第二课
- 沪教版八年级下册数学练习册20.4(2)一次函数的应用2P8
- 外研版英语七年级下册module1unit3名词性物主代词讲解
- 第五单元 民族艺术的瑰宝_16. 形形色色的民族乐器_第一课时(岭南版六年级上册)_T1406126
- 沪教版牛津小学英语(深圳用)五年级下册 Unit 1
- 沪教版牛津小学英语(深圳用) 四年级下册 Unit 3
- 每天日常投篮练习第一天森哥打卡上脚 Nike PG 2 如何调整运球跳投手感?
- 二年级下册数学第三课 搭一搭⚖⚖
- 30.3 由不共线三点的坐标确定二次函数_第一课时(市一等奖)(冀教版九年级下册)_T144342
- 冀教版小学数学二年级下册第二单元《余数和除数的关系》
- 青岛版教材五年级下册第四单元(走进军营——方向与位置)用数对确定位置(一等奖)
- 七年级英语下册 上海牛津版 Unit5
- 沪教版牛津小学英语(深圳用) 五年级下册 Unit 7
- 沪教版牛津小学英语(深圳用) 六年级下册 Unit 7
- 19 爱护鸟类_第一课时(二等奖)(桂美版二年级下册)_T502436
- 冀教版小学数学二年级下册第二周第2课时《我们的测量》宝丰街小学庞志荣
- 北师大版数学四年级下册3.4包装
- 【部编】人教版语文七年级下册《老山界》优质课教学视频+PPT课件+教案,安徽省
- 【获奖】科粤版初三九年级化学下册第七章7.3浓稀的表示
- 外研版英语三起6年级下册(14版)Module3 Unit2
- 人教版历史八年级下册第一课《中华人民共和国成立》
- 六年级英语下册上海牛津版教材讲解 U1单词
精品推荐
- 2016-2017学年高一语文人教版必修一+模块学业水平检测试题(含答案)
- 广西钦州市高新区2017届高三11月月考政治试卷
- 浙江省湖州市2016-2017学年高一上学期期中考试政治试卷
- 浙江省湖州市2016-2017学年高二上学期期中考试政治试卷
- 辽宁省铁岭市协作体2017届高三上学期第三次联考政治试卷
- 广西钦州市钦州港区2016-2017学年高二11月月考政治试卷
- 广西钦州市钦州港区2017届高三11月月考政治试卷
- 广西钦州市钦州港区2016-2017学年高一11月月考政治试卷
- 广西钦州市高新区2016-2017学年高二11月月考政治试卷
- 广西钦州市高新区2016-2017学年高一11月月考政治试卷
分类导航
- 互联网
- 电脑基础知识
- 计算机软件及应用
- 计算机硬件及网络
- 计算机应用/办公自动化
- .NET
- 数据结构与算法
- Java
- SEO
- C/C++资料
- linux/Unix相关
- 手机开发
- UML理论/建模
- 并行计算/云计算
- 嵌入式开发
- windows相关
- 软件工程
- 管理信息系统
- 开发文档
- 图形图像
- 网络与通信
- 网络信息安全
- 电子支付
- Labview
- matlab
- 网络资源
- Python
- Delphi/Perl
- 评测
- Flash/Flex
- CSS/Script
- 计算机原理
- PHP资料
- 数据挖掘与模式识别
- Web服务
- 数据库
- Visual Basic
- 电子商务
- 服务器
- 搜索引擎优化
- 存储
- 架构
- 行业软件
- 人工智能
- 计算机辅助设计
- 多媒体
- 软件测试
- 计算机硬件与维护
- 网站策划/UE
- 网页设计/UI
- 网吧管理