
第
30
卷第
4
期
2010
年
4
月
计算机应用
Vo
l. 30 No.4
Apr.20
1O
loumal
of Computer Applications
文章编号:
1001 - 9081
(2010
)04
- 1004 - 04
非线性降维算法及其在医院绩效考核上的应用
李
凯黄添强
1
,
2
余养强郭躬德
l
(
1
福建师范大学数学与计算机科学学院,福州
350007;
2.
清华大学信息科学技术学院,北京
100084
)
(LkLLi@
163.
com)
摘
要:流形学习算法中的等
Z
巨嵌入算法
(ISOMAP)
具有对离群点敏感的瑕疵,针对此问题,提出利用基于共享
近邻的距离度量方式,并充分利用了流形上对象的局部密度信息,有效改善了算法的性能,提高了算法的健壮性。同
时,首次尝试将该改进的流形学习算法应用于医院绩效考核。人工数据与真实数据上的实验表明,改进的算法健壮
且有效,在绩效考核上应用成功。
关键词:非线性降维;共享近邻;等距嵌入算法;离群点;绩效考核
中图分类号:
TP181
文献标志码
:A
Nonlinear dimensionality reduction algorithm and application to
hospital performance evaluation
LI
Kai
1
,
HUANG
Tian-qiang
I
,2 ,
YU
Yang-qiang
1
,
GUO
Gong-de
I
(1. Sc/wol
0/
Mathematics
αnd
Computer
Sc
阳时
'e
,
Fujian Normal
Universi
妙
,
F
,
四
/W
U
Fuj
皿
n
350007
, China;
2. Sc
/wol
o/Informat
归
n
Sc
阳
nce
α
nd
Technology, Tsinghua
Univers
町
,
Be古
;ing
100084
, China)
Abstract:
Manifold leaming algorithm ISOMAP is sensitiveto the outliers.
To
solve this problem, the paper employed
the distance measurement based
on
shared nearest neighbor and made a full use
of
the local density information of points on the
manifold
, which resulted in an effective improvement
on
the robustness of the algorithm. Meanwhile, the paper first attempted
to apply the improved manifold leaming algorithm to the hospital performance evaluation. The experiments
on
the artificial data
and real-world data show that the improved algorithm is robust and effective, and the application
to
the performance evaluation
is successful.
Key
words:
nonlinear dimensionality reduction; shared nearest neighbor; Isometric Mapping
(ISOMAP);
outlier;
performance evaluation
。
引言
随着信息技术的广泛应用,数据库中堆积了大量的高维
数据,如商业记录、气候模式、恒星光谱、人类基因分布等。在
处理这些数据时,会碰到降维问题,尤其是非线性降维问题,
降维的目的就是找出隐藏在高维数据中有意义的低维结构,
它是人们做分类决策前的重要步骤。
流形学习算法是非线性降维的重要工具之→,目前已有
的代表性工作包括:等距嵌入算法
(Isometric
Mapping ,
ISOMAP)
[1]
、局部线性嵌入法(Lo
cally
Linear Embedding,
LLE)
[2]
、拉谱拉斯特征映射
(Laplacian
Eigenmaps ,
LE)
[3]
及
局部切空间排列法(Lo
cal
Tangent Space Alignment , LTSA)
[4]
等。这类算法在处理非线性降维方面有较大优势,但也存在
内在缺陷:算法对噪声非常敏感,少量的噪声点将对流形拓扑
结构造成极大破坏。因此,研究健壮的流形学习算法已成为
当前研究的热点和难点之一。
本文主要关注
ISOMAP
算法,针对算法对离群点敏感的
问题,提出利用基于共享近邻的距离度量方法,尽可能地排除
了对象与离群点相连接的可能性,保证测地钱沿着流形连接,
使得原来对离群点敏感的算法更加健壮。传统的绩效考核方
法有精权法[町、相关系数法
[6]
和主成分分析法
[7]
等,这些算
法在处理非线性数据时具有明显局限性,本文利用流形学习
收稿日期
:2009
-10
-15
;修回日期
:2009
-12
-30
。
算法适合处理非线性数据的特点,将它应用于绩效考核领域,
取得了良好的效果。首先对经典
ISOMAP
算法作简要介绍,
然后分析算法的内在缺陷及问题根源,最后提出一种改进的
算法。
1
流形学习算法
1.1
ISOMAP
算法及其缺陷
ISOMAP
是基于流形学习的非线性降维算法的代表作之
一。它利用测地线距离代替欧式距离,测地线距离表现为流
形上任意两点之间的最短距离,可近似为一系列邻近点之间
距离之和。因为在数据的全局几何结构未知(通常呈非线
性)的情况下,欧式距离只在很小的领域内才有意义。
ISOMAP
通过数据间的测地线距离,保留了数据固有的几何
分布结构,具有揭示非线性数据流形的内在特性的能力。
ISOMAP
算法在处理非线性降维方面具有明显优势,但
它也存在内在局限性:
ISOMAP
算法对噪声点非常敏感,噪声
点的存在会造成流形的"短路影响测地线距离的计算,进
而影响到非线性降维的效果。
噪声点之所以会造成流形的"短路其本质原因如下:
如图
1
所示
,
X
1
与
X
2
分别为流形上的两个点
,
X
,
。为噪声点,它
造成
X
1
与几之间的"短路"现象。根据
ISOMAP
算法原理,流
形上的每个点将与其
K
个最近邻连接构成近邻图,当
X
1
或
X
2
作者简介:李凯
(1984
- )
,男,福建甫田人,硕士研究生,主要研究方向:数据挖掘;
黄添强(1
971
- )
,男,福建青田人,博士,主要研究方
向:人工智能、机器学习、数据挖掘;
余养强(1
985
- )
,男,福建古回人,硕士研究生,主要研究方向:数据挖掘;
郭躬德(1
965
- )
,男,福建龙
岩人,博士,主要研究方向:人工智能、机器学习、数据挖掘。