基于新的鲁棒相似性度量的时间序列聚类

针对存在异常值的时间序列数据,提出了一种基于相关系数鲁棒估计的时间序列间的鲁棒广义互相关度量（RGCC）。首先,引入一种鲁棒相关系数代替Pearson相关系数来计算时间序列数据间的协方差矩阵;其次,用新的协方差矩阵的行列式构造两个时间序列间的相似性度量——RGCC;最后,基于该度量计算出序列间的距离矩阵,将其作为聚类算法的输入对数据进行聚类。时间序列聚类仿真实验表明,对存在异常值点的时间序列数据,与基于原始的广义互相关度量（GCC）得到的聚类结果相比,基于RGCC得到的聚类结果明显更接近真实的聚类结果。可见,所提出的新的鲁棒相似性度量完全适用于存在异常值的时间序列数据。     

基于ACF非线性趋势特征的时间序列聚类

在时间序列挖掘工作中,比如聚类和分类,需要计算距离来衡量时间序列样本之间的相似性,有许多研究都致力于时间序列相似性度量的研究.充分利用非线性趋势特征来进行时间序列挖掘.首先计算时间序列的ACF,进而构造ACF的非线性趋势特征,利用该特征作为时间序列相似性度量来进行聚类,它给时间序列平稳性的判定提供了一种新的途径.列举了一个模拟数据和一个实际数据来进行实例验证,实验结果表明,ACF非线性趋势特征作为一种新的相似性度量,相对已有的一些相似性度量而言,ACF非线性趋势特征通常只需计算少量的若干特征值就能更合理地刻画时间序列的平稳性特征.借助K-means进行聚类实验.     

时间序列挖掘中一种新的相似性度量

针对时间序列的全序列聚类展开,提出一种新的相似性度量——全局特征,即从时间序列的统计分布特征、非线性和Fourier频谱转换等3个方面提取11个全局特征构建特征向量。利用特征向量来描述原时间序列,不仅保留了大部分原有的信息,还能加快聚类计算的速度。经过大量的实验验证表明,基于全局特征提取的相似性度量能得到合理的聚类结果,特别是对经济领域的时间序列效果更为明显。例举了2个数据进行实验,并从主观和客观两个角度对聚类结果进行评估。     

符号序列的概率向量聚类方法*

针对符号序列聚类中表示模型及序列间距离度量定义的困难问题,提出一种基于概率向量的表示模型及基于该模型的符号序列聚类算法。该模型引入符号序列的概率分布表示法,定义了一种基于概率分布差异的符号序列距离度量及该模型的目标函数,最后给出了一种符号序列K-均值型聚类算法,并在来自不同领域的实际应用序列集上进行了实验验证。实验结果表明,与基于子序列表示模型的符号序列聚类算法相比,所提方法在DNA序列和语音序列等具有较多符号的实际数据上,有效提高聚类精度的同时降低聚类时间50%以上。     

基于形态相似距离的时间序列相似性度量

时间序列的相似性度量是时间序列分析的基础工作之一,是进行相似匹配的关键。针对欧几里德距离描述分段趋势的不足和各种模式距离对应分段之间距离值的离散化问题,提出一种基于形态相似距离的时间序列相似性度量方法,标准数据集上完成的识别和聚类实验表明了该方法的可行性和有效性。     

辅助信息自动生成的时间序列距离度量学习

对于时间序列聚类任务而言,一个有效的距离度量至关重要.为了提高时间序列聚类的性能,考虑借助度量学习方法,从数据中学习一种适用于时序聚类的距离度量.然而,现有的度量学习未注意到时序的特性,且时间序列数据存在成对约束等辅助信息不易获取的问题.提出一种辅助信息自动生成的时间序列距离度量学习(distancemetric learning based on side information autogeneration for time series,简称SIADML)方法.该方法利用动态时间弯曲(dynamic time warping,简称DTW)距离在捕捉时序特性上的优势,自动生成成对约束信息,使习得的度量尽可能地保持时序之间固有的近邻关系.在一系列时间序列标准数据集上的实验结果表明,采用该方法得到的度量能够有效改善时间序列聚类的性能.     

基于DLT-Kmedoids算法的用电负荷聚类分析

针对高校用电负荷中传统聚类算法直接应用于时间序列聚类效果准确性较低的问题,提出一种融合DTW距离、LB＿Keogh距离以及时间窗口的DLT-Kmedoids算法,以提高聚类算法应用于时间序列的准确性以及算法效率。DLT-Kmedoids算法使用DTW计算时序数据之间的距离取代传统的欧氏距离度量方式,提高了相似性度量算法精度,同时也提高了聚类算法的准确性和复杂度,引入LB＿Keogh距离在计算DTW距离之前过滤掉大部分不可能是最优匹配序列的序列,对于剩下的序列再使用DTW逐个比较,进一步降低算法的复杂度。最后结合高校建筑用电负荷时间序列数据进行分析,通过与主流聚类算法进行比较,表明该算法对于高校用电负荷数据的聚类任务,能够更准确地识别相似的负荷模式,并以更高的效率进行聚类分析。     

有效距离在聚类算法中的应用

聚类分析是数据挖掘领域的重要组成部分之一,而度量学习是聚类分析中的关键性步骤。传统聚类算法中通常使用欧氏距离进行距离度量,但是欧氏距离只关注两两样本之间的距离关系,并没有顾及数据的全局性分布结构。考虑到数据的全局性结构信息,提出了一种新的具有全局性的度量方法——有效距离度量(effective distance metric),其主要思想是通过稀疏重构的方法计算数据样本之间的有效距离。进一步地,将有效距离应用到K-means、K-medoids和FCM(fuzzy C-means)3种经典聚类算法中开发了3种基于有效距离的聚类算法,即EK-means,EK-medoids和EFCM聚类算法。通过与传统聚类算法在UCI标准数据集上的实验结果进行比较,验证了基于有效距离的聚类算法能显著提高聚类效果。     

基于混合距离学习的鲁棒的模糊C均值聚类算法

距离度量对模糊聚类算法FCM的聚类结果有关键性的影响。实际应用中存在这样一种场景,聚类的数据集中存在着一定量的带标签的成对约束集合的辅助信息。为了充分利用这些辅助信息,首先提出了一种基于混合距离学习方法,它能利用这样的辅助信息来学习出数据集合的距离度量公式。然后,提出了一种基于混合距离学习的鲁棒的模糊C均值聚类算法（HR-FCM算法）,它是一种半监督的聚类算法。算法HR-FCM既保留了GIFP-FCM（Generalized FCM algorithm with improved fuzzy partitions）算法的鲁棒性等性能,也因为所采用更为合适的距离度量而具有更好的聚类性能。实验结果证明了所提算法的有效性。     

基于分量属性近邻传播的多元时间序列数据聚类方法

鉴于传统方法不能直接有效地对多元时间序列数据进行聚类分析,提出一种基于分量属性近邻传播的多元时间序列数据聚类方法.通过动态时间弯曲方法度量多元时间序列数据之间的总体距离,利用近邻传播聚类算法分别对数据之间的总体距离矩阵和分量近似距离矩阵进行聚类分析,综合考虑这两种视角下序列数据之间的关联关系,使用近邻传播方法对反映原始多元时间序列数据的综合关系矩阵实现较高质量的聚类.数值实验结果表明,与传统聚类方法相比,所提出方法不仅能够有效地反映总体数据特征之间的关系,而且通过重要分量属性序列之间的关联关系分析能够提高原始时间序列数据的聚类效果.     

Bispectral-based methods for clustering time series

Distinguishing among linear and nonlinear time series or between nonlinear time series generated by different underlying processes is challenging, as second-order properties are generally insufficient for the task. Different nonlinear processes have different nonconstant bispectral signatures, whereas the bispectral density function of a Gaussian or linear time series is constant. Based on this, we propose a procedure to distinguish among various nonlinear time series and between nonlinear and linear time series through application of a hierarchical clustering algorithm based on distance measures computed from the square modulus of the estimated normalized bispectra. We find that clustering using a distance measure computed by averaging the ratio of normalized bispectral periodogram ordinates over the intersection of the principle domain of each pair of time series provides good performance, subject to trimming of extreme bispectral values prior to taking the ratios. Additionally, we show through simulation studies that the distance procedure performs better than a significance test that we derive. Moreover, it is robust with respect to the choice of smoothing parameter in estimating the bispectrum. As an example, we apply the method to a set of time series of intensities of gamma-ray bursts, some of which exhibit nonlinear behavior; this enables us to identify gamma-ray bursts that may be emanating from the same type of astral event.     

Clustering of biological time series by cepstral coefficients based distances

Clustering of stationary time series has become an important tool in many scientific applications, like medicine, finance, etc. Time series clustering methods are based on the calculation of suitable similarity measures which identify the distance between two or more time series. These measures are either computed in the time domain or in the spectral domain. Since the computation of time domain measures is rather cumbersome we resort to spectral domain methods. A new measure of distance is proposed and it is based on the so-called cepstral coefficients which carry information about the log spectrum of a stationary time series. These coefficients are estimated by means of a semiparametric model which assumes that the log-likelihood ratio of two or more unknown spectral densities has a linear parametric form. After estimation, the estimated cepstral distance measure is given as an input to a clustering method to produce the disjoint groups of data. Simulated examples show that the method yields good results, even when the processes are not necessarily linear. These cepstral-based clustering algorithms are applied to biological time series. In particular, the proposed methodology effectively identifies distinct and biologically relevant classes of amino acid sequences with the same physicochemical properties, such as hydrophobicity.     

基于离均差的时间序列相似性度量

 时间序列的相似性度量是数据挖掘领域研究的一个热点,高维多元时间序列数据一般含有大量的噪声不利于相似性的比较。针对现有的时间序列度量方法存在的问题,在改进的时间序列自底向上融合算法的基础上,提出一种新的基于离均差的时间序列相似性度量的夹角余弦算法(Angle Cosine Metric Similarity,ACMS)。ACMS算法将时间序列等价为一个多维度的向量,充分考虑2个向量的方向和大小特征,增强振幅变化的鲁棒性,减少人为干扰,对数据挖掘中的聚类和预测具有帮助作用。     

基于改进RBF网络的多变量序列建模和预测

针对复杂系统多变量序列预测研究中数据样本过多、信息冗余等问题,从学习样本选择和聚类中心优化两方面对径向基函数(RBF)网络进行改进.基于复杂系统多变量时间序列,首先采用一个线性相关函数和一个非线性相关函数分别计算多变量状态间的线性相关性和非线性相关性,确定一个包含系统有效信息的小数据集;然后基于小数据集,采用K均值聚类方法确定RBF网络的隐层聚类中心,并引入局部搜索过程,优化聚类中心结果;输入其它训练样本,确定网络权值.仿真结果表明,与常规RBF网络学习方法比较,在隐层节点数目相同情况下,改进的方法有效地确定了网络的聚类中心,达到更好的预测精度.     

Time series representation and similarity based on local autopatterns

Time series data mining has received much greater interest along with the increase in temporal data sets from different domains such as medicine, finance, multimedia, etc. Representations are important to reduce dimensionality and generate useful similarity measures. High-level representations such as Fourier transforms, wavelets, piecewise polynomial models, etc., were considered previously. Recently, autoregressive kernels were introduced to reflect the similarity of the time series. We introduce a novel approach to model the dependency structure in time series that generalizes the concept of autoregression to local autopatterns. Our approach generates a pattern-based representation along with a similarity measure called learned pattern similarity (LPS). A tree-based ensemble-learning strategy that is fast and insensitive to parameter settings is the basis for the approach. Then, a robust similarity measure based on the learned patterns is presented. This unsupervised approach to represent and measure the similarity between time series generally applies to a number of data mining tasks (e.g., clustering, anomaly detection, classification). Furthermore, an embedded learning of the representation avoids pre-defined features and an extraction step which is common in some feature-based approaches. The method generalizes in a straightforward manner to multivariate time series. The effectiveness of LPS is evaluated on time series classification problems from various domains. We compare LPS to eleven well-known similarity measures. Our experimental results show that LPS provides fast and competitive results on benchmark datasets from several domains. Furthermore, LPS provides a research direction and template approach that breaks from the linear dependency models to potentially foster other promising nonlinear approaches.     

On the granularity and clustering of directed acyclic task graphs

The authors consider the impact of the granularity on scheduling task graphs. Scheduling consists of two parts, the processors assignment of tasks, also called clustering, and the ordering of tasks for execution in each processor. The authors introduce two types of clusterings: nonlinear and linear clusterings. A clustering is nonlinear if two parallel tasks are mapped in the same cluster otherwise it is linear. Linear clustering fully exploits the natural parallelism of a given directed acyclic task graph (DAG) while nonlinear clustering sequentializes independent tasks to reduce parallelism. The authors also introduce a new quantification of the granularity of a DAG and define a coarse grain DAG as the one whose granularity is greater than one. It is proved that every nonlinear clustering of a coarse grain DAG can be transformed into a linear clustering that has less or equal parallel time than the nonlinear one. This result is used to prove the optimality of some important linear clusterings used in parallel numerical computing     

Making clustering in delay-vector space meaningful

Sequential time series clustering is a technique used to extract important features from time series data. The method can be shown to be the process of clustering in the delay-vector space formalism used in the Dynamical Systems literature. Recently, the startling claim was made that sequential time series clustering is meaningless. This has important consequences for a significant amount of work in the literature, since such a claim invalidates these work’s contribution. In this paper, we show that sequential time series clustering is not meaningless, and that the problem highlighted in these works stem from their use of the Euclidean distance metric as the distance measure in the delay-vector space. As a solution, we consider quite a general class of time series, and propose a regime based on two types of similarity that can exist between delay vectors, giving rise naturally to an alternative distance measure to Euclidean distance in the delay-vector space. We show that, using this alternative distance measure, sequential time series clustering can indeed be meaningful. We repeat a key experiment in the work on which the “meaningless” claim was based, and show that our method leads to a successful clustering outcome. Jason R. Chen received the B.E. degree from Sydney University, Australia, in 1991 and then worked mainly in the banking and finance industry until 1997. From 1997 to 2001, he completed the Ph.D. at Australian National University, Canberra, Australia, in robotics. From 2001 to the present, he has been a Research Engineer in the Research School of Information Science and Engineering, at Australian National University. His research interests broadly include robotics, data mining, and AI.     

基于动态时间弯曲的时序数据聚类算法的研究

时间序列是一类重要的复杂类型数据，时间序列知识发现正成为知识发现的研究热点之一。欧几里的距离及其扩展作为相似测度被广泛应用于时间序列的比较中，但是这种距离测度对数据没有好的鲁棒性。动态时间弯曲技术是基于非线性动态编程的一种模式匹配算法。该文提出了基于动态时间弯曲技术的相似搜索算法，通过计算时序数据之间的最短弯曲路径来获得序列的匹配。对综合控制时序数据进行基于不同距离测度的聚类分析对比结果表明该文提出的算法有很高的精度和对振幅差异、噪声和线性漂移有强的鲁棒性，具有良好的应用价值。     

标签传播时间序列聚类的股指期货套期保值策略研究

利用时间序列聚类方法进行股指期货的套期保值,关键要选择合适的聚类方法。本文从新的视角来研究并提高时间序列聚类方法在金融数据分析领域的应用性能,提出一种基于标签传播时间序列聚类的股指期货套期保值模型。该模型以动态时间弯曲为相似性度量方法来构建现货股票网络空间结构,将每只股票看作一个节点,利用标签传播方法将节点划分到不同的簇中,最终实现股票数据聚类。另外,构建最小追踪误差优化模型来确定每支股票在现货组合中的最优权重,从而得到最优组合。实验分别比较新方法和传统聚类方法确定现货组合的追踪误差,结果表明新方法能够提高现货组合的追踪精度,为丰富金融市场投资和管理方式提供新的研究思路。