无监督特征选择在多特征表示的时间序列数据挖掘中的应用

第xx卷第x期仪器仪表学报VoxxxNo.xxxxx年x月ChineseJournalofScientificInstrument无监督特征选择在多特征表示的时间序列数据挖掘中的应用郑宝芬，苏宏业，罗林，张均峰（浙江大学控制科学与工程系，浙江杭州310027；浙江大学智能系统与控制研究所，浙江杭州310027）摘要：疲劳驾驶是交通事故发生的主要原因之一，为了精确预测驾驶员疲劳程度，提出一种基于度量学习的无监督特征选择与识别方法。首先，在对脑电图（EEG）进行特征提取时，多特征表示的方法克服了传统方法相对单一、往往不能完整表达时间序列信息的缺陷。然后，基于度量学习的特征选择方法对变换之后的特征进行选择，有效降低了预测工作；最后引入SVM分类器对其进行分类。通过在公开数据集和真实数据集上对各种过滤式特征选择方法进行的比较实验说明了该方法的有效性。关键词：脑电图;多特征表示;特征选择;预测Unsupervisedfeatureselectioninamulti-featurerepresentationoftimeseriesdataminingapplicationZHENGBaofen，SUHongye，LUOLin，ZHANGJunfeng(DepartmentofControlScienceandEngineering,ZhejiangUniversity,Hangzhou310027,ChinaInstituteofCyber-SystemsandControl,ZhejiangUniversity,Hangzhou310027,China)Abstract：Mentalfatigueisamajorcauseoftrafficaccidents,inordertopredictdriver’sfatiguestatusaccurately,weproposeanunsupervisedfeatureselectandrecognizedmethodbasedonmetriclearning.First,weusemulti-featurerepresentationmethodinfeatureextractionofelectroencephalography(EEG),whichovercomessomeweaknessoftraditionalmethods,suchastoosimpletocompletelyexplaintimesequenceinformation.Then,weusethemetric-learningbasedfeatureselectionmethodonthetransformeddata,whichsignificantlyincreasingtheefficiencyofsuccessprediction;Finally,theSVMclassifierisusedonclassifyingtheprocesseddata.Comparingtheperformanceofexperimentsonpubliclyavailabledatasetsandrealdatasetsusingmultiplefilteringfeatureselectionmethods,ourproposedmethodturnsouttobeeffective.Keywords：EEG;multi-featurerepresentation;featureselection;forecast1引言随着近年来互联网和信息行业的发展，时间序列的数据量增长越来越快。如何在时间序列中发现潜在的有用信息已经成为了数据挖掘领域的一个主要研究方向，并取得了大量的研究成果，广泛应用于经济、金融[1]、电子信息、医学[2]、气象[3]、教育和工业工程[4]等各个领域。EEG信号是一类常见的时间序列，具有小样本高维度的特点，主要研究方向包括脑电数据预处理、相似性度量方法、特征表示、特征选择及分类预测等[5]。其中特征表示、相似性度量方法和特征选择是本文关注的重点。时间序列的特征表示将原时间序列映射到另一域中，同时使映射后低维空间下的数据能尽可能地反映原时间序列信息[4]。目前，时间序列的特征表示主要分为数据自适应方法和数据非自适应方法两大类[6]。但无论哪种方法，通常都使用单一的时域、频域等信息来提取时间序列的特征，使得特征表示的信息不全，影响了特征识别的精度。相似性度量用来表征数据之间的二元关系，大部分时间序列数据挖掘工作都需要进行相似性比较。目前相似性度量方法主要有欧式距离、曼哈顿距离、夹角余弦、信息熵等，但是传统的方法往往很难对具体问题都适用，因此在过去十年中，很多机器学习及相关领域的研究者展开了度量学习的研究，如Chopra用第xx卷第x期仪器仪表学报VoxxxNo.xxxxx年x月ChineseJournalofScientificInstrument度量学习的方法提高了kNN的分类精度，Paramveer等将度量学习应用到了基于图形的域适应。特征选择可以去除和挖掘主题不相关的或者冗余的属性，是数据挖掘过程的一个关键步骤。根据算法和分类器的关系，特征选择方法大致可以分为过滤式、封装式和嵌入式模型。过滤式模型通过某个适应函数的值来估计某个特征子集的有效性，与具体的分类器无关；封装式模型是用某个特定分类器的性能作为特征子集选择的准则，这种直接优化分类器的策略可改进分类器的泛化性，但计算代价相对较高，且不具有通用性；嵌入式模型同时进行特征选择和学习器设计。本文提出了一种新的基于度量学习的无监督特征选择算法（SBFS），具有以下三个特点：1）利用多种特征抽取方法对时间序列进行特征表示，更全面地保留了原始数据的信息；2）基于谱聚类的特征选择方法，同时适用于监督数据和非监督数据，克服了类标签无法取得或者获取代价大的困难；3）将度量学习应用于相似图的矩阵生成，使得相似性矩阵表达更精确。实验结果表明：相对于传统的过滤式算法，本文提出的SBFS算法在精确度方面表现出了明显的优势，并且在实验室数据处理中达到了90%以上的准确度，达到了预期目标。2一种新的无监督特征选择方法本文采用多种特征表示的方法提取EEG信息，基于谱聚类算法，用度量学习的方法生成相似矩阵，求得前k个特征向量，并通过学习稀疏系数向量，得到最能表达原始数据信息的d个属性，以实现降维的目的。2.1时间序列的多特征表示随着信息化技术的不断发展，时间序列包含的信息量越来越多，传统的时频域单特征表示已无法满足日益增长的识别精确度需求。表1对本文引入的特征表示方法进行了汇总。本文采用时频域、信息论和混沌理论中的多种特征表示方法来综合提取特征，尽可能多地保留了时间序列的信息。时频域的特征表示方法有时域均值、频域功率、离散傅里叶变换（DFT）和离散小波变换（DWT）等，本文引入了实用性较强的小波变换，利用Harr小波变换[7]来表示和重构时间序列，得到了小波包频带能量比（WPFBER）[8]。信息论特征表示方法有近似熵、样本熵Renyi熵、Tsallis熵和多尺度熵等。熵（entropy）指的是体系的混乱程度，在控制论、概率论、数论、天体物理、生命科学等领域都有重要应用。熵值越大，代表混乱程度越大。本文引入了最常用的近似熵和样本熵来表征EEG的无序性。混沌理论是一种兼具质性思考与量化分析的方法，用以探讨动态系统中必须用整体、连续的数据关系才能加以解释及预测的行为。基于混沌理论的特征表示方法主要有连续功率谱、饱和分维数、Lyapunov指数和Kolmogorov熵等。本文引入了最大Lyapunov指数。表1.本文引入的特征表示方法方法类别方法名称时频域特征表方法小波变换信息论特征表示方法示近似熵样本熵混沌理论特征表示方法最大Lyapunov指数2.2基于度量学习的特征选择方法在多特征表示下的时间序列中的应用无监督特征选择算法通常是根据给定的属性集123[,,,,]nXxxxx和限定的特征数目d，选出一个最能反映原样本集信息的属性子集。如何选择这个属性子集是算法的核心部分，现有文献通常是以一种聚类算法为核心，找到最能代表原始属性集的一个簇，常用的聚类方法有层次聚类、谱聚类等。本研究基于谱聚类，提出一种基于度量学习的无监督特征选择方法SBFS，具备了以下两个特点：（1）尽可能地保持数据的原有结构；（2）尽可能多地保留样本数据的信息。2.2.1度量学习比较两个对象的相似性或者计算他们之间的距离是许多机器学习算法的基本要求之一。传统的方法有欧式距离、曼哈顿距离以及余弦相似度等，它们分别在不同的研究领域中取得了良好的效果。然而，随着数据挖掘对象日益增多，固定的距离公式已经越来越不能满足实际的需求。近年来，度量学习成为了机器学习领域的一个重要研究方向。其中，马氏距离因其原理简单、泛化能力优异得到了广泛的应用[9]。它通过线性变换，把数据映射到另一个空间，在新空间中用欧式距离公式进行计算，其参数数目与数据维度的平方成正比。在该过程中，往往要使用核学习，以克服马氏距离在处理高维数据和非线性数据时的缺陷。核学习算法根据样本数据是否含类标签可以分为第xx卷第x期仪器仪表学报VoxxxNo.xxxxx年x月ChineseJournalofScientificInstrument有监督、弱监督和半监督三种，根据变换方法来分可以分为线性、非线性和局部度量（localmetrics）三类，包括NCA、ITML、LRML等多种算法。其中，ITML引入了LogDet散度正规化，在许多马氏距离学习算法中得到了运用[10]。LogDet散度的定义如下，11000(,)()logdet()ldDMMtrMMMMd(1)其中d为输入空间的维度，0M为我们要保持接近的一些PSD矩阵。事实上，0M通常设定为I，此时的正规化目标为使得学习得到的距离尽可能地接近欧氏距离。LogDet散度的特点是当且仅当M是PSD矩阵时它是有限的。因此最小化0(,)ldDMM为保持M的正半定性质提供了一种简便的方法。2.2.2基于度量学习的无监督特征选择谱聚类算法基于谱图理论，能在任意形状的样本空间上聚类并收敛于全局最优解。该算法首先将数据集中的每个对象看作是图的顶点V，将顶点间的相似度量化作相应顶点连接边E的权值，得到一个基于相似度的无向加权图(,)GVE。在这种图中，每个顶点只与k个相似度最高的点连边，大大简化了计算复杂度。首先，需要对相似图的每条边进行量化表示，本文采用度量学习中最常用的马氏距离，其定义如下，(,)()()MdxxxxMxx（2）其中dSM是其关键参数，dS是dd维对称正半定实值矩阵的锥体空间，dSM保证了Md符合伪距离的条件。为了得到M的最佳解，本文引入了一种弱监督的信息理论度量学习算法（ITML）[10]，利用LogDet散度正规化，得到下式，1100,22min()logdet()..(,)(,)S(,)(,)DdijMSijMijijijMijijijtrMMMMdstdxxuxxdxxvxx(3)其中，,uvR是阈值参数，0是权值参数。最小化两个以M和0M为参数的多元高斯分布的KL差，是求解（3）式的有效方法。计算所有连接边E的权值Md即可得到相似图的邻接矩阵，记为W。定义一个对角矩阵D，其对角线上的数为W中对应行的和，即iiijjDW。则相似图的非规格拉普拉斯矩阵定义为LDW。通过LyDy计算得到拉普拉斯矩阵的前k个特征向量，记为1[,,]kYyy，完成了原始样本集到特征向量空间的映射。给定iy（1,2,...,ik），通过下面的最小化拟合误差，找到一个最佳子集，2minkTiiiayXaa(4)其中ia为M维向量，X是原始数据矩阵，是权重系数。,1Miijjaa是ia的L1范式。在逼近iy的时候，ia代表了不同属性的相关系数，其中,ija代表第j个属性的系数。求解式（