基于带权多维尺度变换的奇异值挖掘

《基于带权多维尺度变换的奇异值挖掘》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、计算机科学2008Vol.35No.1基于带权多维尺度变换的奇异值挖掘和魏莱王守觉徐菲菲(同济大学计算机科学与技术系上海201804)摘要大童的高维数据在分布上表现为一低维流形，试图从这样的数据集中探测出奇异点，传统的奇异点挖掘算法可能失效。本文提出了一种带权重的多维尺度变化,算法通过局部的高维数据集和其低维重构的误差来设定数据点的局部权空，再利用权重之和得到的数据点置信度,以此来进行奇异值的判定.通过实验验证了算法的有效性。关键词奇异值，多维尺度变换，带权多维尺度变换，流形学习/OutliersMiningviaWei

2、ghtedMultidimensionalityScalingWEILaiWANGShou-JueXUFei-Fei(DepartmentofComputerScienceandTechnology♦TongjiUniversity,Shanghai201804)AbstractMiningoutliersfromthedatasetwhichisdistributedonalowdimensionalmanifoldisahardtaskTheexistingalgorithmmaynotbeeffectivefor

3、thesituation.Soanovelapproachcalledweightedmultidimensionalityscalingisproposedforoutliersmining・Itisbasedonmultidimensionalityscaling・MDS.Everydatapointwillgetareliabilityscorebythealgorithm,thenitcanbedeterminedwhetheritisaoutlierthroughthevalueofitsreliability

4、score.TheexperimentsshowtheefficiencyofthealgorithmKeywordsOutliers,MDS,WeightedMDS,Manifoldlearning1引言在大量的数据中可能包含着一些数据，它们与一般的数据的行为和模型不一致。这些被称为奇异点(outliers)的数据在大部分情况下会被去除，但在一些应用中非正常的事件可能比正常的事件更有趣，因此作为数据挖掘的一个分支，奇异点挖掘也引起了很多学者的关注口~‘】。通过对奇异值表现的分析,大部分挖掘算法可以归为如下四类;基于统计

5、的检测⑶、基于距离的检测〔“】、基于偏差的检测⑹以及基于密度的检测但是随着信息技术的发展，数据的形式和内容与以往有了较大的区别,表现在数据的高维数和数据属性的高度相关。这些高维数据集的分布在高维观测空间形成了一种低维的几何结构,在数学上称为流形,这种几何结构是未知的,且非线性的。因此，以上传统的奇异点检测算法在这种情况下可能失效。为此需要一种新的方法来处理流形上奇异值检测的问题。本文提出了一种带权重的多维尺度变换奇异值挖掘算法(OutliersMiningviaWeightedMultidimensionalScalin

6、g,OMWMDS)。该算法利用多维尺度变换(MultidimensionalScaling)的思想，通过计算数据重构的误差来赋予数据点相应的权值，对于分布成为一低维流形的数据集通过局部的Weighted-MDS得到局部权重，遍历数据集后通过以局部权重的和作为每一数据点的置信度，通过置信度的大小来判定数据点是否为奇异点。实验表明算法能够有效挖掘出当正常数据分布成一低维流形时整体数据中的非正常数据,同时每一数据点相应的置信度也可用于改进流行学习算法的鲁棒2多维尺度变换2.1多维尺度变换(MultidimensionalSc

7、aling,MDS)[9]多维尺度变换同主成分分析(PrincipalComponent)一样是一种应用广泛的线性降维算法，在图像处理、计算机视觉等方面有着广泛的应用。MDS不需要知道数据点的具体坐标,它通过对数据之间的距离矩阵的奇异值分解来获得数据的低维重构坐标，从而有效地对数据集进行降维。经典的MDS算法具体步骤如下：假设数据集为X=｛©,£,・・・“｝其中工疋应,并且我们有任意两数据点之间距离矩阵D=｛必｝,数据点相应的重构坐标为Y—｛yi，护，・••,％｝』€/・STEP1.计算STEP2.取矩阵H=偽｝,满足加

8、=&一国家自然科学基金项目(60495019),教育部博士点专项基金(20060247039)・魏莱博士研究生，研究方向:流形学习、仿生模式识别、信息几何、粗糙集理论.，其中STEP3.(双中心化)计算r(D)=-旦器；STEP4.求矩阵HD)的待征值和其对应的特征向凰，矩阵A是对角阵,对角元索是从大到小排列的特征值