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.

编辑 顾逸斐