基于局部均值分解和改进小波熵的时序SAX模型

符号聚合近似表示法是提取时间序列特征的重要方式。然而,传统的符号聚合近似表示法存在平均化分段数、同等对待划分区间,以及无法准确反映非平稳序列的突变信息等多项缺陷。鉴于此,通过引入局部均值分解和改进小波熵的分段算法,建立了一种新的时序SAX模型。该模型的基本原理是采用局部均值分解技术对原始序列进行去噪处理,利用滑动窗口阈值法获取分段数,并使用SAX表示法进行符号表示,利用KNN分类器实现分类性能测试。基于这一改进模型,进行了实证检验,实验结果表明,该模型能够有效提取序列的信息特征,具有较高的拟合度,达到了降维的目的,更重要的是,提高了KNN分类算法在SAX表示法中分类的准确率。     

基于SAX的时间序列相似性度量方法*

符号化表示是一种有效的时间序列降维技术,其相似性度量是诸多挖掘任务的基础。基于SAX(sym-bolic aggregate approximation)的距离MINDIST_PAA_iSAX不满足对称性,在时间序列挖掘中具有局限性,提出了对称的度量Sym_PAA_SAX,且下界于欧拉距离。在真实数据集和合成数据集上的实验说明下界紧密性较好,相似搜索错报率较低。     

基于统计特征的时序数据符号化算法

为克服SAX(符号聚合近似)算法对时序信息描述不完整的缺陷,提出基于统计特征的时序数据符号化算法,与SAX不同的是,该算法将时序符号看作矢量,而各时序子段的均值和方差则分别作为描述其平均值及发散程度的分量.由于该算法能够比SAX提供更多的描述信息,因而在时序数据挖掘应用中能够获得比SAX更精确的结果.大量的实验也证实了它的出色表现.     

基于SAX方法的股票时间序列数据相似性度量方法研究

特定数据集上高效的相似性度量方法是目前时间序列数据挖掘领域研究的重点内容之一。针对经过SAX方法降维后的股票数据在相似性度量中缺乏趋势变化的动态信息这一问题,本文提出了一种融合了点距离与模式距离优点的新型相似性度量函数——复合距离函数,并通过实证分析验证了该距离函数在相似性度量中的有效性,为揭示股票数据间相互依赖的规律以及时间序列相似性问题的进一步研究提供了新思路。     

时序数据的矢量化符号方法

针对SAX方法的某些缺陷,提出基于SAX[8]的VSB(矢量化符号)方法,通过引入最大值,最小值这二个极值分量,将原来的SAX符号转化为具有三个分量的符号矢量,其VSB符号值由各分量的加权和最终确定.由于VSB方法能够比SAX提供更多对时序数据的描述信息,因而在时序分析中能够获得比SAX更精确的结果.大量的实验也证实了它的出色表现.     

时序数据的动态有界符号化方法

提出了一种时序符号化方法.根据数据集极值来确定最佳字符集及时序数据的划分基准,通过估算最大压缩比来指导降维,从而实现了与SAX同样的符号化时序转换和相同的距离计算方式.与SAX不同的是,该时序符号化方法可以有效防止极值信息的丢失,因而在一些与极值相关的时序分析中有出色的表现.     

基于数值符号和形态特征的时间序列相似性度量方法

针对传统符号聚合近似方法在特征表示时容易忽略时间序列局部形态特征的局限性,以及动态时间弯曲在度量上的优势,提出一种基于数值符号和形态特征的时间序列相似性度量方法.将时间序列进行符号和形态的特征表示后,提出动态时间弯曲与符号距离结合的时间序列距离度量方法,使所提方法能够较好地反映时间序列数据数值分布和形态特征.实验结果表明,所提出的方法在时间序列数据挖掘中能够得到较好的分类效果,具有一定的优越性.     

基于微局部特征的时序数据二分类算法

在诸多时序数据分类算法中,有一类算法借助时序数据的局部特征对时序数据进行分类,它们取得了不错的分类结果,然而其时间复杂度以及分类精度依旧存在可见的提升空间.本文提出的微局部特征二分类算法,着眼于局部特征本身的性质,对局部特征集进行限制,进而改进现有的基于局部特征的分类算法.新算法通过理论分析支撑,将经典算法的局部特征集大幅缩小,进而显著提升了分类算法的时间性能.另一方面通过重定义局部特征的评价标准,新算法选出性质更为优良的局部特征,提升了分类精度.     

一种基于滑动窗口的数据流相似性查询算法

相似性查询是一种非常重要的数据挖掘应用。由于数据流具有无限、高速等特性,传统的查询算法不能直接应用于数据流。提出了一种基于小波滑动窗口的多数据流相似性查询算法。算法首先将滑动窗口划分成若干等宽基本窗口,然后对每个基本窗口内的数据进行小波分解与系数约简,从而形成小波摘要窗口。执行相似性查询时,直接基于小波摘要进行计算,而无需数据重构。由于利用了小波分解的线性处理优点,算法具有较低的时间复杂度。最后,基于实际数据对算法进行了实验,实验结果证明了算法的有效性。     

基于滑动窗口的数据流连接聚集查询降载策略

基于单个数据流的滑动窗口聚集查询降载技术和数据流连接技术,提出滑动窗口模型下的数据流连接聚集查询降载策略,给出判断系统是否过载的负载方程和使过载系统恢复到轻载状态的降载算法,使降载后的查询结果同时拥有较小的相对误差和最大的元组输出率。实验结果表明,该降载策略具有较好的可行性和适应性。     

基于PAA的时间序列早期分类

在时间序列数据挖掘领域,时间序列的早期分类越来越受到人们的重视,由于时间序列的长度(也称为维数)较大,在早期分类的实际应用中选择合适的维数约简方法非常重要,因此提出一种基于分段聚合近似(PAA)的时间序列早期分类方法。首先运用PAA对时间序列样本进行维数约简,然后在低维空间对样本进行早期分类,在43个时间序列数据集上的实验结果表明, 所提方法 在准确率、早期性、可靠性等方面优于已有方法。     

A Tensor Approximation Approach to Dimensionality Reduction

Dimensionality reduction has recently been extensively studied for computer vision applications. We present a novel multilinear algebra based approach to reduced dimensionality representation of multidimensional data, such as image ensembles, video sequences and volume data. Before reducing the dimensionality we do not convert it into a vector as is done by traditional dimensionality reduction techniques like PCA. Our approach works directly on the multidimensional form of the data (matrix in 2D and tensor in higher dimensions) to yield what we call a Datum-as-Is representation. This helps exploit spatio-temporal redundancies with less information loss than image-as-vector methods. An efficient rank-R tensor approximation algorithm is presented to approximate higher-order tensors. We show that rank-R tensor approximation using Datum-as-Is representation generalizes many existing approaches that use image-as-matrix representation, such as generalized low rank approximation of matrices (GLRAM) (Ye, Y. in Mach. Learn. 61:167–191, 2005), rank-one decomposition of matrices (RODM) (Shashua, A., Levin, A. in CVPR’01: Proceedings of the 2001 IEEE computer society conference on computer vision and pattern recognition, p. 42, 2001) and rank-one decomposition of tensors (RODT) (Wang, H., Ahuja, N. in ICPR ’04: ICPR ’04: Proceedings of the 17th international conference on pattern recognition (ICPR’04), vol. 1, pp. 44–47, 2004). Our approach yields the most compact data representation among all known image-as-matrix methods. In addition, we propose another rank-R tensor approximation algorithm based on slice projection of third-order tensors, which needs fewer iterations for convergence for the important special case of 2D image ensembles, e.g., video. We evaluated the performance of our approach vs. other approaches on a number of datasets with the following two main results. First, for a fixed compression ratio, the proposed algorithm yields the best representation of image ensembles visually as well as in the least squares sense. Second, proposed representation gives the best performance for object classification. A shorter version of this paper was published at IEEE CVPR 2005 (Wang and Ahuja 2005).     

CIS：一种基于迭代扩张的微阵列数据聚类算法

DNA微阵列技术使同时监测成千上万的基因表达水平成为可能.直接把传统聚类算法用于高维基因表达数据分析会受到＂维难＂的困扰.特征转换和特征选择是两种常用的降维方式,但前者产生的新特征难以用原来的领域知识解释,后者通常会丢失信息.另外,传统的聚类算法通常由用户指定聚类参数,参数设置不同对聚类结果有很大的影响.针对上述问题,本文提出了一种新的基于迭代扩张的微阵列数据聚类算法-CIS.它不采用特征转换和特征选择的方式,并自动确定聚类参数.CIS反复用最新得到的样本聚簇得到新的聚类基因,然后以新的基因聚簇为特征重新聚类样本,逐步求精,最终的结果容易解释且避免了信息的丢失.该方法降低了由于用户缺少领域知识引起的实验误差.CIS算法被应用于两个真实的微阵列数据集,实验结果证实了算法的有效性.     

Visualization of graphical data in a user-specified 2D space using a weighted Isomap method

We present a visualization system for exploring the high-dimensional graphical data, such as textures or 3D models, in 2D space using the dimensionality reduction method. To arrange high-dimensional data in a meaningful 2D space, we develop a novel semi-supervised dimensionality reduction method that can embed data of high dimension in a user-defined 2D coordinate system that is meaningful in terms of the properties of the data. This is achieved by modifying the Isomap method by weighting the data so that the resulting coordinates have no degeneracies and are orthogonal.     

Kernel approximately harmonic projection

Dimensionality reduction is an important preprocessing procedure in computer vision, pattern recognition, information retrieval, and data mining. In this paper we present a kernel method based on approximately harmonic projection (AHP), a recently proposed linear manifold learning method that has an excellent performance in clustering. The kernel matrix implicitly maps the data into a reproducing kernel Hilbert space (RKHS) and makes the structure of data more distinct, which distributes on nonlinear manifold. It retains and extends the advantages of its linear version and keeps the sensitive to the connected components. This makes the method particularly suitable for unsupervised clustering. Besides, this method can cover various classes of nonlinearities with different kernels. We experiment the new method on several well-known data sets to demonstrate its effectiveness. The results show that the new algorithm performs a good job and outperforms other classic algorithms on those data sets.     

基于主机系统调用的入侵检测方法研究

大多数的入侵行为是由于一系列操作系统内部的非法或异常调用引起的,因此对系统调用序列进行分析是入侵检测的一个重要方法。给出了两种基于系统调用的序列分析方法：基于频繁统计和基于权值树的滑动窗口序列分析方法,并且描述了相应算法的主要过程。并通过试验证明了它们的合理性和有效性。     

Bilinear Lanczos components for fast dimensionality reduction and feature extraction

Matrix-based methods such as generalized low rank approximations of matrices (GLRAM) have gained wide attention from researchers in pattern recognition and machine learning communities. In this paper, a novel concept of bilinear Lanczos components (BLC) is introduced to approximate the projection vectors obtained from eigen-based methods without explicit computing eigenvectors of the matrix. This new method sequentially reduces the reconstruction error for a Frobenius-norm based optimization criterion, and the resulting approximation performance is thus improved during successive iterations. In addition, a theoretical clue for selecting suitable dimensionality parameters without losing classification information is presented in this paper. The BLC approach realizes dimensionality reduction and feature extraction by using a small number of Lanczos components. Extensive experiments on face recognition and image classification are conducted to evaluate the efficiency and effectiveness of the proposed algorithm. Results show that the new approach is competitive with the state-of-the-art methods, while it has a much lower training cost.     

基于形态特征的时间序列符号聚合近似方法

由于形态特征能够较为客观地反映时间序列的变化趋势,在时间序列数据降维过程中,形态特征的提取能够保留较为充分的数据信息,为提高后期的时序数据挖掘的效率提供可靠的保障。文中提出基于形态特征的时间序列符号聚合近似方法,综合考虑分段序列的均值和数据分布的形态特征,并且通过论域转化对它们实现符号转化。在相同的压缩比环境下,与传统符号化表示方法相比,该方法能更好地提供原始时间序列数据信息,进而提高时间序列数据挖掘的效率。     

流数据分类中的概念漂移问题研究

传统的流数据分类算法基于滑动窗口来优化现有分类器或建立多个分类器来跟踪概念的漂移过程,而不能根据概念漂移的强弱程度自适应地进行分类.在结合当前主流的CVFDT和集成分类器算法的基础之上,提出一种新型流数据分类算法:SADT算法.算法动态地判断概念漂移的发生,自动决定是优化还是重建分类器,适用于不同类型的数据的分类.通过分析和实验论证,该算法在处理概念漂移时具有更好的适应性.