基于多类支持向量机的恒星光谱分类方法

引用本文

张静, 刘忠宝, 宋文爱, 富丽贞, 章永来. 基于多类支持向量机的恒星光谱分类方法[J]. 光谱学与光谱分析, 2018,38(7): 2307-2310.
ZHANG Jing, LIU Zhong-bao, SONG Wen-ai, FU Li-zhen, ZHANG Yong-lai. Stellar Spectra Classification Method Based on Multi-Class Support Vector Machine[J]. Spectroscopy and Spectral Analysis, 2018,38(7): 2307-2310.
Doi:10.3964/j.issn.1000-0593(2018)07-2307-04 复制到剪切板

Permissions

《光谱学与光谱分析》期刊社所有

基于多类支持向量机的恒星光谱分类方法

张静, 刘忠宝^*, 宋文爱, 富丽贞, 章永来

中北大学软件学院, 山西太原 030051

*通讯联系人　　e-mail: liz_zhongbao@hotmail.com

作者简介: 张静, 1980年生, 中北大学软件学院博士研究生 e-mail: enty_ren@126.com

收稿日期: 2017-07-30

基金: 山西省自然科学基金项目(201601D011042), 山西省高等学校创新人才支持计划, 中北大学杰出青年基金支持计划资助

摘要

支持向量机作为一种经典的分类方法被广泛应用于恒星光谱分类领域。该方法在实际应用中取得了较为理想的分类效果, 但其面临无法解决多分类问题的挑战。在支持向量机的基础上, 提出多类支持向量机, 建立基于多类支持向量机的恒星光谱分类模型。该方法的最大优势是经过一次分类过程, 可以确定多类样本的类属。 SDSS DR8恒星光谱数据上的比较实验表明, 本研究所提的方法较之已有多分类方法在分类性能上有一定的提升。

关键词: 支持向量机; 多类支持向量机; 恒星光谱; 自动分类

中图分类号:TP391 文献标志码:A

Stellar Spectra Classification Method Based on Multi-Class Support Vector Machine

ZHANG Jing, LIU Zhong-bao^*, SONG Wen-ai, FU Li-zhen, ZHANG Yong-lai

School of Software, North University of China, Taiyuan 030051, China

*Corresponding author

Abstract

Support vector machine (SVM), a typical classification method, has been widely used in stellar spectra classification. It performs well in practice, while it encounters the multi-class classification challenge. In order to solve the problem above, multi-class support vector machine (MCSVM) was proposed in this paper based on the in-depth analysis of SVM. Meanwhile, the stellar spectra classification model based on multi-class support vector machine was constructed. The advantage of the proposed method is that the samples’ class can be determined by a classification process. Comparative experiments with the existed multi-class classification method on the SDSS DR8 datasets verify the effectiveness of the proposed method.

Keyword: Support vector machine; Multi-class support vector machine; Stellar spectra; Automatic classification

文章图片

引言

随着天文观测设备的持续改进, 人类获得的天体光谱数据量呈指数级增长的态势。基于人工方式的光谱分析和处理方法已经不能满足实际需要。鉴于此, 数据挖掘技术受到人们的广泛关注, 如何利用数据挖掘技术快速有效地从海量光谱中发现有用的信息成为广大研究人员面临的一大挑战。其中, 天体光谱分类问题是重中之重, 该问题的解决为天体演化、密度分布、宇宙结构等方面的研究提供有力的技术支持, 也为进一步探究银河系的形成与演化奠定坚实的理论基础。

目前, 众多研究人员从事天体光谱分类方面的研究工作, Xue等利用自组织特征映射(self-organization feature mapping, SOFM)对恒星光谱进行自动分类^[1]; Alejandra等综合利用信号处理、专家系统以及模糊逻辑等技术对恒星光谱进行分类^[2]; Malyuto将最大似然法应用到模板匹配中用于恒星光谱分类^[3]; Bu等利用等距特征映射(Isometric feature map, Isomap)以及支持向量机(support vector machine, SVM)对恒星光谱进行自动分类^[4]; Du等提出贝叶斯支持向量机(Bayesian support vector machine, BSVM)并基于此, 提出自适应的恒星光谱分类方法^[5]; 赵梅芳等将K近邻方法应用于光谱自动分类^[6]; 孙士卫等将数据仓库应用于星系光谱分类^[7]; 潘景昌等针对海量光谱数据, 提出利用Hadoop并行处理平台解决恒星光谱分类问题^[8]。

上述分类方法主要是针对于二分类问题提出的。但在实际应用中, 往往面临多分类问题, 即在一个分类问题中, 同时要将几类分开。在处理上述问题时, 传统分类器的做法是将多个二类分类器进行某种组合, 从而解决多分类问题。然而这样的做法存在复杂度过高的问题, 因而无法处理海量高维光谱数据。本研究在支持向量机的基础上, 引入多类支持向量机(multi-class support vector machine, MCSVM), 该方法有效地解决光谱分类中的多分类问题。 SDSS DR8恒星光谱数据上的验证实验表明本研究所提方法是有效的。

1 支持向量机

假设X={(x₁, y₁), (x₂, y₂), …, (x_n, y_n)}表示样本集合, 其中, x_i(1≤ i≤ n)表示样本, y_i(1≤ i≤ n)∈ {-1, 1}表示类别标签。支持向量机的基本原理是在样本空间中找到一个最优分类超平面将两类分开, 即支持向量机是用来确定样本x_i(1≤ i≤ n)的类别标签。支持向量机的最优化问题可表示为

$\begin{array}{l} \min_{w, b} \frac{1}{2} w^{T} w + c \overset{n}{\sum_{i = 1}} ξ_{i} (1) \\ s.t. y_{i} (w^{T} x_{i} + b) \geq 1 - ξ_{i} (2) \\ ξ_{i} \geq 0, i = 1, 2, \dots, n (3) \end{array}$

其中, w表示分类超平面的法向量; b表示分类超平面的偏置项; c为惩罚因子, 用于表示训练误差的重要性; ξ _i为松弛因子。

由拉格朗日定理可以将上述优化问题转化为如下对偶形式

$\begin{array}{l} \min_{α} \frac{1}{2} \overset{n}{\sum_{i, j}} α_{i} α_{j} y_{i} y_{j} {x^{T}}_{i} x_{j} - \overset{n}{\sum_{i = 1}} α_{i} (4) \\ s.t. \overset{n}{\sum_{i = 1}} y_{i} α_{i} = 0 (5) \\ α_{i} \geq 0, i = 1, 2, \dots, n (6) \end{array}$

其中α _i为拉格朗日乘子。求解上述优化问题可得到的最优解为α ^*=[ $α_{1}^{*}$ , $α_{2}^{*}$ , …, $α_{n}^{*}$ ]^T。最优分类超平面可由下式计算得到

$y (x) = \overset{n}{\sum_{i = 1}} α_{i} y_{i} x^{T} x_{i} + b (7)$

其中 $b = y_{j} - \overset{n}{\sum_{i = 1}} y_{i} α_{i}^{*} {x^{T}}_{i} x_{j} 。$

支持向量机的决策函数定义如下

$f (x) = sign (y (x)) (8)$

其中sign(· )为符号函数。

2 基于多类支持向量机的恒星光谱分类方法

2.1 多类支持向量机

与传统的支持向量机相比, 多类支持向量机可以一次性地将不同类别的样本分开。从建模角度看, 多类支持向量机试图在样本空间中找到若干个分类超平面将各类样本分开。假设在一个多分类问题中, 共有K个分类超平面, 其中w_k(k=1, 2, …, K)表示第k个分类超平面的法向量, l_i(i=1, 2, …, K)表示样本的类别标签。则多类支持向量机的最优化问题可表示为

$\begin{array}{l} \min_{w_{k}, b_{k}} \overset{K}{\sum_{k = 1}} \frac{1}{2} {w^{T}}_{k} w_{k} + c \overset{n}{\sum_{i = 1}} \sum_{k \neq l_{i}} ξ_{i}^{k} (9) \\ s.t. {w^{T}}_{l_{i}} x_{i} + b_{l_{i}} \geq {w^{T}}_{k} x_{i} + b_{k} + 2 - ξ_{i}^{k} (10) \\ ξ_{i}^{k} \geq 0, i = 1, 2, \dots, n (11) \\ k \neq l_{i} (12) \end{array}$

由拉格朗日定理可得

$\begin{array}{l} L (w_{k}, b_{k}, α, β, ξ) = \overset{K}{\sum_{k = 1}} \frac{1}{2} {w^{T}}_{k} w_{k} + c \overset{n}{\sum_{i = 1}} \sum_{k \neq l_{i}} ξ_{i}^{k} - \\ \overset{n}{\sum_{i = 1}} \overset{K}{\sum_{k = 1}} α_{i}^{k} [(w_{l_{i}} - w_{k})^{T} x_{i} + b_{l_{i}} - b_{k} - 2 + ξ_{i}^{k}] - \overset{n}{\sum_{i = 1}} \overset{K}{\sum_{k = 1}} β_{i}^{k} ξ_{i}^{k} (13) \end{array}$

其中α 和β 为拉格朗日乘子。

将式(13)分别对w_k, b_k, $ξ_{i}^{k}$ 求偏导, 可得

$\begin{array}{l} \frac{\partial L}{\partial w_{k}} = w_{k} + \overset{n}{\sum_{i = 1}} α_{i}^{k} x_{i} - \overset{n}{\sum_{i = 1}} A_{i} p_{i}^{k} x_{i} (14) \\ \frac{\partial L}{\partial b_{k}} = - \overset{n}{\sum_{i = 1}} A_{i} p_{i}^{k} + \overset{n}{\sum_{i = 1}} α_{i}^{k} (15) \\ \frac{\partial L}{\partial ξ_{i}^{k}} = - α_{i}^{k} - β_{i}^{k} + c (16) \end{array}$

其中 $p_{i}^{k} = \{\begin{array}{l} 1, & l_{i} = k \\ 0, & l_{i} \neq k \end{array}, A_{i} = \overset{K}{\sum_{k = 1}} α_{i}^{k} 。$

令式(14)— 式(16)偏导为0, 则有

$\begin{array}{l} \frac{\partial L}{\partial w_{k}} = 0 \Rightarrow w_{k} = \overset{n}{\sum_{i = 1}} (A_{i} p_{i}^{k} - α_{i}^{k}) x_{i} (17) \\ \frac{\partial L}{\partial b_{k}} = 0 \Rightarrow \overset{n}{\sum_{i = 1}} A_{i} p_{i}^{k} = \overset{n}{\sum_{i = 1}} α_{i}^{k} (18) \\ \frac{\partial L}{\partial ξ_{i}^{k}} = 0 \Rightarrow c = α_{i}^{k} + β_{i}^{k} (19) \end{array}$

将式(17)— 式(19)代入式(13)中, 可得原优化问题的对偶形式

$\begin{array}{l} \min_{α_{k}} \overset{K}{\sum_{k = 1}} \overset{n}{\sum_{i = 1}} \overset{n}{\sum_{j = 1}} (α_{i}^{k} α_{j}^{l_{i}} - \frac{1}{2} α_{i}^{k} α_{j}^{k}) x_{i}^{T} x_{j} + 2 \overset{K}{\sum_{k = 1}} \overset{n}{\sum_{i = 1}} α_{i}^{k} \\ s.t. \overset{n}{\sum_{i = 1}} α_{i}^{k} = \overset{n}{\sum_{i = 1}} p_{i}^{k} α_{i}, k = 1, 2, \dots, K \\ 0 \leq α_{i}^{k} \leq c, α_{i}^{l_{i}} = 0, i = 1, 2, \dots, n, k \neq l_{i} \end{array}$

其中 $α_{i}^{k} (i = 1, 2, \dots, n; k = 1, 2, \dots, K) 为拉格朗日乘子, 且 α_{i} = \overset{K}{\sum_{k = 1}} α_{i}^{k} 。$

多类支持向量机的决策函数为

$f (x, α) = \underset{k}{argmax} [\overset{n}{\sum_{i = 1}} (p_{i}^{k} A_{i} - α_{i}^{k}) {x^{T}}_{i} x + b_{k}] (20)$

2.2 算法流程

在多类支持向量机的基础上, 提出基于多类支持向量机的恒星光谱分类方法。作为一种有监督的学习方法, 恒星光谱分类一般将实验数据集分为训练样本集和测试样本集。训练样本集用于训练多类支持向量机, 得到分类依据; 测试样本集用于检验分类器的分类性能。该方法的输入数据是训练样本集, 输出数据是各测试样本的类属。该方法的具体工作流程是:

第1步: 对恒星光谱数据进行离散化、归一化等预处理;

第2步: 根据光谱分类的一般做法, 将恒星光谱数据集分为训练样本集和测试样本集;

第3步: 在训练样本集上, 利用式(9)— 式(12)表示的最优化问题对多类支持向量机进行训练, 并建立分类模型;

第4步: 利用拉格朗日乘子法求得多类支持向量机优化问题的对偶形式, 并根据式(20)得到多类支持向量机的决策函数;

第5步: 在测试样本集上, 利用多类支持向量机的决策函数确定各测试样本的类属。

3 实验分析

实验采用的数据集来自于美国斯隆望远镜巡天获得的SDSS DR8恒星光谱数据集, 实验对象包括K 型、 F型、 G型和M型四类恒星。鉴于数据规模较大, 随机选取上述恒星数据集的60%作为实验数据集。 K型恒星包括K1, K3, K5和K7四类次型; F型恒星包括F2, F5和F9三类次型; G型恒星包括G0, G2和G5三类次型; M型恒星包括M0— M9次型。这些数据在实验前要做一定的预处理: 选取间隔为20的200个波长作为条件属性; 根据每个波长处的流量、峰宽和形状, 离散化为十三个数值之一; 恒星类别作为判定属性。在实验中, 分别选取实验数据集的40%, 50%, 60%, 70%和80%作为训练样本集, 而剩下的数据分别作为测试样本集。多类支持向量机中的惩罚因子c是一个自由参数, 该参数的选取对于分类器的性能有较大影响。因此, 本实验采用20倍交叉验证法来获取该参数。惩罚因子c在网格{0.1, 0.5, 1, 5, 10}中选取。

以支持向量机为代表的传统二分类方法, 在处理多分类问题时, 一般采用以下两种策略:

(1)一对多策略(one versus rest, 1-v-r)。针对K类分类问题, 可以构建K个二类分类器, 每个类对应一个二类分类器, 用于将其与其他类分开。

(2)一对一策略(one versus one, 1-v-1)。任意两类间训练一个分类器, 因此对于K类分类问题, 共有K(K-1)/2个分类器。在对未知样本进行类属判定时, 各分类器对其类别进行判定并给出相应的得分, 得分高者即为该样本类属。

实验中, 将上述两种分类策略与本研究所提方法进行对比, 得到如表1所示的实验结果。

表1 对比实验结果 Table 1 The comparative experimental results

由表1可以看出: 随着训练样本规模的增大, 三种方法的分类精度均有不同幅度的提升。当训练样本分别取40%, 50%, 60%, 70%和80%时, MCSVM的分类精度均最优, 其次是1-v-1策略, 最后是1-v-r策略。从平均分类能力看, 与1-v-r和1-v-1策略相比, MCSVM的分类精度较之1-v-r策略高出近5%; 较之1-v-1策略高出3.4%。

4 结论

光谱自动分类是天文数据挖掘领域的一大研究热点问题。在众多分类方法中, 支持向量机以其优良的分类性能受到人们的广泛关注。然而, 该方法是针对二分类问题提出的, 其在解决多分类问题时, 常见的做法是将多个二类分类器进行某种组合, 从而达到解决多分类问题的目的。但这种做法的复杂度过高, 无法处理规模较大的光谱数据。在支持向量机的基础上, 深入探讨了多类支持向量机, 提出了基于多类支持向量机的恒星光谱分类方法。该方法经过一次分类过程, 就能将所有类别的样本分开。 SDSS DR8恒星光谱数据上的比较实验表明, 所提的方法较之已有方法在分类精度上具有一定优势。

The authors have declared that no competing interests exist.

参考文献

文献列表

[1]	Xue J Q, Li Q B, Zhao Y H. Chinese Astronomy and Astrophysics, 2001, 25: 120. [本文引用:1]
[2]	Alejand ra R, Bernardino A, Carlos D, et al. Expert Systems with Applications, 2004, 27: 237. [本文引用:1]
[3]	Malyuto V. New Astronomy, 2002, 7: 461. [本文引用:1]
[4]	Bu Y D, Chen F Q, Pan J C. New Astronomy, 2014, 28: 35. [本文引用:1]
[5]	Du C D, Luo A L, Yang H F. New Astronomy, 2017, 51: 51. [本文引用:1]
[6]	ZHAO Mei-fang, WU Chao, LUO A-li, et al(赵梅芳, 吴潮, 罗阿理, 等). Acta Astronomica Sinica(天文学报), 2007, 48(1): 1. [本文引用:1]
[7]	SUN Shi-wei, LUO A-li, ZHANG Ji-fu(孙士卫, 罗阿理, 张继福). Astronomical Research & Technology, 2007, 4(3): 276. [本文引用:1]
[8]	PAN Jing-chang, WANG Jie, JIANG Bin, et al(潘景昌, 王杰, 姜斌, 等). Spectroscopy and Spectral Analysis(光谱学与光谱分析), 2016, 36(8): 2651. [本文引用:1]