一种基于重要点的时间序列分割方法

分段线性表示是时间序列降维的有效方法,其关键在于分割点的确定。在时间序列分段线性表示的基础上,提出一种新的基于重要点的时间序列分割方法。与一般方法比较相邻三点关系不同的是,将时间窗扩展为前一重要点、待考察点和一个指定时间窗组成的区间,再通过比较数据点前后模式变化来确定重要点。通过与其他7种分割方法进行实验比较,证明该方法适应能力强,不但分割结果总体质量高,在压缩率相同时具有更小的拟合误差,而且能够有效滤除噪声,发现时间序列的模式特征。     

An iterative end point fitting based trend segmentation representation of time series and its distance measure

Symbolic approximation representation is a key problem in time series which can significantly affect the accuracy and efficiency of data mining. However, since currently used methods divide the original sequence into segments with equal size, they ignore one of the most important features of time series: the trend. To overcome the defect of equal-sized segmenting, we present a trend segmentation representation based on Iterative End Point Fitting algorithm (IEPF-TSR). Particularly, we use iterative end point fitting (IEPF) algorithm to search the break point of each segment and get the trend segmentation. Then a triplet based symbolic representation is proposed for each segment which includes the start point, mean and trend. Moreover, we define a new distance measure method based on trend segmentation representation (TSR-DIST) which can suit for two representations with different lengths, and prove it to be the lower bound of Euclidean distance. The experimental results on UCR datasets show that the proposed representation and distance measure achieve better performance than the state-of-the-art methods in the classification accuracy and the dimensionality reduction ratio.

     

RPAA：一种基于时间特性的时间序列建模表示

滑动聚集平均近似PAA（Piecewise Aggregate Approximation）是一种表示时间序列的方法，它通过时间序列上滑动一个等宽的滑动窗口将时间序列分成小的区段。考虑到时间序列的时间特性q-不同区段的影响，本文提出了一种改进表示RPAA（Reversed Piecewise Aggregate Approximation）。RPAA表示对处于不同时间段的序列赋以不同的影响因子，具有线性时间复杂度，并且证明了RPAA满足下界定理，因而能够进行实际的查询。最后的实验表明该表示是有效的。     

一种时间序列快速分段及符号化方法

作为一类重要的复杂类型数据,时间序列已成为数据挖掘领域的热点研究对象之一.针对时间序列的挖掘通常首先需要将时间序列分段并转变为种类有限的符号序列,以利于进一步进行时间序列模式挖掘.针对当前的时间序列分段方法复杂度较大,效率不高等问题,本文提出了一种简单高效的基于拐点检测的时间序列分段方法,并且采用动态时间弯曲度量计算不等长子序列的相异度,最后运用层次化聚类算法实现子序列的分类及符号化.实验表明,本文所提出的方法切实可行,实验结果具有较为明显的物理意义.     

基于S分量指数加权H分量的圆形直方图阈值法

HSI颜色空间可以用三维空间下的圆锥模型进行解释,基于HSI颜色空间的H分量圆形直方图实现彩色图像分割具有可行性。针对HSI颜色空间的H分量圆形直方图毛刺较多以及相关阈值选取准则分割精度较低的问题,给出S分量指数加权H分量的直方图公式,利用S分量信息对H分量直方图的毛刺进行平滑处理,并通过分析给出指数加权因子的最优取值。在此基础上,提出一种圆形直方图阈值分割法,通过对整个圆形直方图进行整体角均值计算而得出新的阈值选取准则。实验结果表明,该圆形直方图阈值分割法具有有效性,在测试数据集上,与3个圆形最大熵阈值分割法以及2个阈值分割准则相比,所提方法的像素精度值平均提高3.2%,结构相似度值平均提高2.5%。     

ESPSA: A prediction-based algorithm for streaming time series segmentation

Streaming time series segmentation is one of the major problems in streaming time series mining, which can create the high-level representation of streaming time series, and thus can provide important supports for many time series mining tasks, such as indexing, clustering, classification, and discord discovery. However, the data elements in streaming time series, which usually arrive online, are fast-changing and unbounded in size, consequently, leading to a higher requirement for the computing efficiency of time series segmentation. Thus, it is a challenging task how to segment streaming time series accurately under the constraint of computing efficiency. In this paper, we propose exponential smoothing prediction-based segmentation algorithm (ESPSA). The proposed algorithm is developed based on a sliding window model, and uses the typical exponential smoothing method to calculate the smoothing value of arrived data element of streaming time series as the prediction value of the future data. Besides, to determine whether a data element is a segmenting key point, we study the statistical characteristics of the prediction error and then deduce the relationship between the prediction error and the compression rate. The extensive experiments on both synthetic and real datasets demonstrate that the proposed algorithm can segment streaming time series effectively and efficiently. More importantly, compared with candidate algorithms, the proposed algorithm can reduce the computing time by orders of magnitude.     

基于多元时间序列的自适应贪婪高斯分段算法

现有多元时间序列分段算法中分段点的选择以及分段个数的确定往往需要分别独立完成,大大增加了算法的计算复杂度.为解决上述问题,提出一种基于多元时间序列的自适应贪婪高斯分段算法.该算法将多元时间序列各个分段所对应的数据解释为来自不同多元高斯分布的独立样本,进而将分段问题转化为协方差正则化的最大似然估计问题进行求解.为提高学习效率,采用贪婪搜寻方法使每个段的似然值最大化进而近似地找到最优分段点,并且在搜寻的过程中利用信息增益方法自适应地获取最优的分段个数,避免分段个数确定和分段点选择分别独立进行,从而减少计算的复杂度.基于多种领域的真实数据集实验结果表明,所提出方法的分段精度以及运行效率均优于传统方法,并且能够有效完成多元时间序列的异常检测任务.     

基于分割模式的时间序列矢量符号化算法

针对符号化聚合近似算法(SAX)中时间序列必须等长分割的缺陷,提出一种基于分割模式的时间序列符号化算法(SMSAX)。利用三角阈值法对随机抽样的时间序列进行特征提取,计算时间序列最大压缩比,将其作为时间窗宽提取分割点,进而求出时间序列的分割模式。利用得到的分割模式对时间序列进行分割降维,通过均值和波动率对分割后的子序列进行向量符号化。根据时间序列特征对其进行不等长分割,并加入波动率消除奇异点的影响。实验结果表明,SMSAX能获得比SAX更精确的结果。     

Online Segmentation and Clustering From Continuous Observation of Whole Body Motions

This paper describes a novel approach for incremental learning of human motion pattern primitives through online observation of human motion. The observed time series data stream is first stochastically segmented into potential motion primitive segments, based on the assumption that data belonging to the same motion primitive will have the same underlying distribution. The motion segments are then abstracted into a stochastic model representation and automatically clustered and organized. As new motion patterns are observed, they are incrementally grouped together into a tree structure, based on their relative distance in the model space. The tree leaves, which represent the most specialized learned motion primitives, are then passed back to the segmentation algorithm so that as the number of known motion primitives increases, the accuracy of the segmentation can also be improved. The combined algorithm is tested on a sequence of continuous human motion data that are obtained through motion capture, and demonstrates the performance of the proposed approach.     

Anomaly detection using piecewise aggregate approximation in the amplitude domain

Anomaly detection has received much attention due to its various applications. Generally, the first step to discover anomalies is a data representation method which reduces dimensionality as well as preserves key information. Anomaly detection based on real-value representation methods is meaningful for its convenience in numeric operation. A typical real-value representation method is the Piecewise Aggregate Approximation (PAA) that is simple and intuitive by capturing mean values of segments in a sequence. However, if segments are same or similar in their average values but different in their oscillation amplitudes, the PAA method is ineffective to describe a sequence composed of such segments. To address this issue, we propose a representation method called the Piecewise Aggregate Approximation in the Amplitude Domain (AD-PAA). For discovering anomalies, a sequence is partitioned into subsequences by a sliding window firstly. Then in the AD-PAA method, a subsequence is divided into equal size subsections according to the amplitude domain. With mean values of subsections computed, the amplitude oscillation of a subsequence is embodied effectively. When the AD-PAA method is applied to approximate subsequences, the AD-PAA representation of a sequence is constructed. Anomalies are determined by anomaly scores that are based on similarities among representation results. Experimental results on various data confirm that the proposed method is more accurate than the PAA based method and other comparison methods. The ability to differentiate anomalies of the proposed algorithm is also superior.     

Online segmentation of time series based on polynomial least-squares approximations

The paper presents SwiftSeg, a novel technique for online time series segmentation and piecewise polynomial representation. The segmentation approach is based on a least-squares approximation of time series in sliding and/or growing time windows utilizing a basis of orthogonal polynomials. This allows the definition of fast update steps for the approximating polynomial, where the computational effort depends only on the degree of the approximating polynomial and not on the length of the time window. The coefficients of the orthogonal expansion of the approximating polynomial-obtained by means of the update steps-can be interpreted as optimal (in the least-squares sense) estimators for average, slope, curvature, change of curvature, etc., of the signal in the time window considered. These coefficients, as well as the approximation error, may be used in a very intuitive way to define segmentation criteria. The properties of SwiftSeg are evaluated by means of some artificial and real benchmark time series. It is compared to three different offline and online techniques to assess its accuracy and runtime. It is shown that SwiftSeg-which is suitable for many data streaming applications-offers high accuracy at very low computational costs.     

BIC-Based Speaker Segmentation Using Divide-and-Conquer Strategies With Application to Speaker Diarization

In this paper, we propose three divide-and-conquer approaches for Bayesian information criterion (BIC)-based speaker segmentation. The approaches detect speaker changes by recursively partitioning a large analysis window into two sub-windows and recursively verifying the merging of two adjacent audio segments using $Delta BIC$ , a widely-adopted distance measure of two audio segments. We compare our approaches to three popular distance-based approaches, namely, Chen and Gopalakrishnan's window-growing-based approach, Siegler 's fixed-size sliding window approach, and Delacourt and Wellekens's DISTBIC approach, by performing computational cost analysis and conducting speaker change detection experiments on two broadcast news data sets. The results show that the proposed approaches are more efficient and achieve higher segmentation accuracy than the compared distance-based approaches. In addition, we apply the segmentation approaches discussed in this paper to the speaker diarization task. The experiment results show that a more effective segmentation approach leads to better diarization accuracy.      

基于三维限制区域生长的SD-OCT中浆NRD病变区域分割

中浆(CSC)病变区域的大小对于病变的诊断及研究有着关键的作用,而视网膜神经上皮层脱离(NRD)形态在中浆病变中最为普遍且病变程度最为严重,因此快速准确地分割出NRD病变区域十分重要。给出一种全自动的频域光学相干断层(SD-OCT)中浆NRD病变分割方法。首次在三维空间进行NRD病变分割,将二维图像上的病变区域分割问题转化为三维空间的体分割问题,充分利用了数据的三维结构信息,提高了分割精度。18组中浆NRD病变的SD-OCT图像的实验结果表明:该算法能够准确分割出中浆NRD病变,且平均覆盖率高达89.5%。与其他4种分割方法相比,所提方法精度最高且耗时最短,在临床应用与研究中具有极大的优势。     

运动串:一种用于行为分割的运动捕获数据表示方法

运动数据的行为分割是运动捕获过程中非常重要的一环.针对现有分割方法的不足,提出了一种可用于行为分割的运动数据表示方法,并基于该表示实现了数据的行为分割.运动数据经过谱聚类(spectral clustering)、时序恢复和最大值滤波法(max filtering)后生成一个字符串,该字符串称为运动串,然后采用后缀树(suffix tree)分析运动串,提取出所有静态子串和周期子串,对这些子串进行行为标注,从而实现运动数据的行为分割.实验表明,基于运动串的分割具有较好的鲁棒性和分割效果.     

一种基于密度峰值聚类的图像分割算法

聚类作为一种有效的图像分割方法,被广泛地应用于计算机视觉领域。相较于其他聚类方法,密度峰值聚类(DPC)具有参数少且能有效识别非球形聚类的特点。基于此,引入信息论中的不确定性度量熵,提出一种改进的DPC图像分割算法。将图像像素点的颜色空间CIE Lab值作为特征数据,通过计算信息熵求得自适应截断距离以取代经验取值,建立相应的决策图并确定聚类中心总数,归类非聚类中心点,剔除噪声点从而完成图像分割。在Berkeley数据集上的实验结果表明,该算法能较好地实现彩色图像的分割,其平均分割时间和PRI指标分别为14.658 s和0.721。     

A novel image thresholding method based on Parzen window estimate

Image segmentation is one of the most important and fundamental tasks in image processing and techniques based on image thresholding are typically simple and computationally efficient. However, the image segmentation results depend heavily on the chosen image thresholding methods. In this paper, histogram is integrated with the Parzen window technique to estimate the spatial probability distribution of gray-level image values, and a novel criterion function is designed. By optimizing the criterion function, an optimal global threshold is obtained. The experimental results for synthetic real-world and images demonstrate the success of the proposed image thresholding method, as compared with the OTSU method, the MET method and the entropy-based method.     

汉语语音的聚类分段研究

本文提出了一种新的聚类分段算法,这个算法以段内平均离散度最小、段间平均离散度 最大为准则,采用聚类的方法逐次迭代选择最佳分段断点和分段段数,能正确地对汉语语音 进行音素分段,它和以往分段方法相比在性能上有很大提高.文中还给出了应用该算法对汉 语单音所作的部分实验统计结果,可供进一步开展基于音素或音位的汉语语音识别研究参 考.     

基于多尺度的时间序列固定分段数线性表示

针对目前的时间序列线性表示方法多采用启发式方法提取局部特征点作为分段点,容易陷入局部最优化,不能很好地表示时间序列全局特征,而且多采用单一的拟合误差作为阈值,不能准确预计分段数量,不利于后期进行的时间序列分析应用的问题。提出了一种新的固定分段数的表示方法--PLR_BTBU,首先根据二叉树层次遍历的思想,提取时间序列全局特征点将时间序列初始分段,再通过斜率变化特征将整个时间序列符号化,以各初始分段内的符号特征来确定各初始分段中的分段点分布,最后采用一种改进的固定分段数的自底向上融合算法,将各个子序列逐步融合到要求的分段数。实验结果表明,与已有的方法相比,该方法不仅较好地保留时间序列的全局特征,而且拟合后的时间序列和原时间序列之间的拟合误差更小。     

分段式音频检索算法

本文提出了一种基于分段的快速音频检索算法。该算法将检索目标划分成多个较小的片段,每个片段可以独立进行检索;检索过程中使用检索窗控制参与检索的片段及数量。该算法的速度不随检索目标的长度变化,检索速度可调,且能获得良好的查全率和查准率,适用于从未知音频数据源中检索任意长度的特定音频数据及实时应用场合。     

时间序列数据的分段线性表示

在时间序列分段线性表示(PLR)基础上,提出一种新的基于特征点的分段方法,克服采用单一误差算法的模型失配问题,更加准确地反映过程状态的变化.