Customer Activity Sequence Classification for Debt Prevention in Social Security

From a data mining perspective, sequence classification is to build a classifier using frequent sequential patterns. However, mining for a complete set of sequential patterns on a large dataset can be extremely time-consuming and the large number of patterns discovered also makes the pattern selection and classifier building very time-consuming. The fact is that, in sequence classification, it is much more important to discover discriminative patterns than a complete pattern set. In this paper, we propose a novel hierarchical algorithm to build sequential classifiers using discriminative sequential patterns. Firstly, we mine for the sequential patterns which are the most strongly correlated to each target class. In this step, an aggressive strategy is employed to select a small set of sequential patterns. Secondly, pattern pruning and serial coverage test are done on the mined patterns. The patterns that pass the serial test are used to build the sub-classifier at the first level of the final classifier. And thirdly, the training samples that cannot be covered are fed back to the sequential pattern mining stage with updated parameters. This process continues until predefined interestingness measure thresholds are reached, or all samples are covered. The patterns generated in each loop form the sub-classifier at each level of the final classifier. Within this framework, the searching space can be reduced dramatically while a good classification performance is achieved. The proposed algorithm is tested in a real-world business application for debt prevention in social security area. The novel sequence classification algorithm shows the effectiveness and efficiency for predicting debt occurrences based on customer activity sequence data.     

A time-interval sequence classification method

Classification is one of the most popular behavior prediction tools in behavior informatics (behavior computing) to predict group membership for data instances. It has been greatly used to support customer relationship management (CRM) such as customer identification, one-to-one marketing, fraud detection, and lifetime value analysis. Although previous studies showed themselves efficient and accurate in certain CRM classification applications, most of them took demographic, RFM-type, or activity attributes as classification criteria and seldom took temporal relationship among these attributes into account. To bridge this gap, this study takes customer temporal behavior data, called time-interval sequences, as classification criteria and develops a two-stage classification framework. In the first stage, time-interval sequential patterns are discovered from customer temporal databases. Then, a time-interval sequence classifier optimized by the particle swam optimization (PSO) algorithm is developed to achieve high classification accuracy in the second stage. The experiment results indicate the proposed time-interval sequence classification framework is efficient and accurate to predict the class label of new customer temporal data.     

一种基于MDL的日志序列模式挖掘算法

日志数据是互联网系统产生的过程性事件记录数据,从日志数据中挖掘出高质量序列模式可帮助工程师高效开展系统运维工作。针对传统模式挖掘算法结果冗余的问题,提出一种从时序日志序列中挖掘序列模式（DTS）的算法。DTS采用启发式思路挖掘能充分代表原序列中事件关系和时序规律的模式集合,并将最小描述长度准则应用于模式挖掘,设计一种考虑事件关系和时序关系的编码方案,以解决模式规模爆炸问题。在真实日志数据集上的实验结果表明,与SQS、CSC与ISM等序列模式挖掘算法相比,该算法能高效挖掘出含义丰富且冗余度低的序列模式。     

An optimized sequential pattern matching methodology for sequence classification

In this paper we present a novel methodology for sequence classification, based on sequential pattern mining and optimization algorithms. The proposed methodology automatically generates a sequence classification model, based on a two stage process. In the first stage, a sequential pattern mining algorithm is applied to a set of sequences and the sequential patterns are extracted. Then, the score of every pattern with respect to each sequence is calculated using a scoring function and the score of each class under consideration is estimated by summing the specific pattern scores. Each score is updated, multiplied by a weight and the output of the first stage is the classification confusion matrix of the sequences. In the second stage an optimization technique, aims to finding a set of weights which minimize an objective function, defined using the classification confusion matrix. The set of the extracted sequential patterns and the optimal weights of the classes comprise the sequence classification model. Extensive evaluation of the methodology was carried out in the protein classification domain, by varying the number of training and test sequences, the number of patterns and the number of classes. The methodology is compared with other similar sequence classification approaches. The proposed methodology exhibits several advantages, such as automated weight assignment to classes using optimization techniques and knowledge discovery in the domain of application.

Sequential Pattern Mining in Multi-Databases via Multiple Alignment

To efficiently find global patterns from a multi-database, information in each local database must first be mined and summarized at the local level. Then only the summarized information is forwarded to the global mining process. However, conventional sequential pattern mining methods based on support cannot summarize the local information and is ineffective for global pattern mining from multiple data sources. In this paper, we present an alternative local mining approach for finding sequential patterns in the local databases of a multi-database. We propose the theme of approximate sequential pattern mining roughly defined as identifying patterns approximately shared by many sequences. Approximate sequential patterns can effectively summerize and represent the local databases by identifying the underlying trends in the data. We present a novel algorithm, ApproxMAP, to mine approximate sequential patterns, called consensus patterns, from large sequence databases in two steps. First, sequences are clustered by similarity. Then, consensus patterns are mined directly from each cluster through multiple alignment. We conduct an extensive and systematic performance study over synthetic and real data. The results demonstrate that ApproxMAP is effective and scalable in mining large sequences databases with long patterns. Hence, ApproxMAP can efficiently summarize a local database and reduce the cost for global mining. Furthremore, we present an elegant and uniform model to identify both high vote sequential patterns and exceptional sequential patterns from the collection of these consensus patterns from each local databases.     

Mining sequential patterns by pattern-growth: the PrefixSpan approach

Sequential pattern mining is an important data mining problem with broad applications. However, it is also a difficult problem since the mining may have to generate or examine a combinatorially explosive number of intermediate subsequences. Most of the previously developed sequential pattern mining methods, such as GSP, explore a candidate generation-and-test approach [R. Agrawal et al. (1994)] to reduce the number of candidates to be examined. However, this approach may not be efficient in mining large sequence databases having numerous patterns and/or long patterns. In this paper, we propose a projection-based, sequential pattern-growth approach for efficient mining of sequential patterns. In this approach, a sequence database is recursively projected into a set of smaller projected databases, and sequential patterns are grown in each projected database by exploring only locally frequent fragments. Based on an initial study of the pattern growth-based sequential pattern mining, FreeSpan [J. Han et al. (2000)], we propose a more efficient method, called PSP, which offers ordered growth and reduced projected databases. To further improve the performance, a pseudoprojection technique is developed in PrefixSpan. A comprehensive performance study shows that PrefixSpan, in most cases, outperforms the a priori-based algorithm GSP, FreeSpan, and SPADE [M. Zaki, (2001)] (a sequential pattern mining algorithm that adopts vertical data format), and PrefixSpan integrated with pseudoprojection is the fastest among all the tested algorithms. Furthermore, this mining methodology can be extended to mining sequential patterns with user-specified constraints. The high promise of the pattern-growth approach may lead to its further extension toward efficient mining of other kinds of frequent patterns, such as frequent substructures.     

基于位置信息的显露序列模式挖掘研究

显露序列因为具有强区分能力,常被用来构建有效的分类器。当前算法大多关注序列模式的支持度或出现次数,而忽略序列模式在序列中的出现位置,这将导致一些重要的信息丢失。为此,提出一种带有局部位置信息的显露序列模式,并给出位置显露序列模式挖掘算法。该算法基于出现次数框架,结合后缀树,省略了候选模式的生成与选择步骤,能够快速有效地挖掘出位置显露序列模式。实验结果表明,采用位置显露序列模式构建的分类器在平均分类准确度上高于传统的显露序列模式挖掘算法。     

Genetic algorithm in designing fuzzy information retrieval-based classifier by principal component analysis

The aim of this paper is to develop a fuzzy classifier form the point of view of a fuzzy information retrieval system. The genetic algorithm is employed to find useful fuzzy concepts with high classification performance for classification problems; then, each of classes and patterns can be represented by a fuzzy set of useful fuzzy concepts. Each of fuzzy concepts is linguistically interpreted and the corresponding membership functions remain fixed during the evolution. A pattern can be categorized into one class if there exists a maximum degree of similarity between them. For not distorting the usefulness of the proposed classifier for high-dimensional problems, the principal component analysis is incorporated into the proposed classifier to reduce dimensions. The generalization ability of the proposed classifier is examined by performing computer simulations on some well-known data sets, such as the breast cancer data and the wine classification data. The results demonstrate that the proposed classifier works well in comparison with other classification methods.     

Mining weighted sequential patterns in a sequence database with a time-interval weight

Sequential pattern mining, including weighted sequential pattern mining, has been attracting much attention since it is one of the essential data mining tasks with broad applications. The weighted sequential pattern mining aims to find more interesting sequential patterns, considering the different significance of each data element in a sequence database. In the conventional weighted sequential pattern mining, usually pre-assigned weights of data elements are used to get the importance, which are derived from their quantitative information and their importance in real world application domains. In general sequential pattern mining, the generation order of data elements is considered to find sequential patterns. However, their generation times and time-intervals are also important in real world application domains. Therefore, time-interval information of data elements can be helpful in finding more interesting sequential patterns. This paper presents a new framework for finding time-interval weighted sequential (TiWS) patterns in a sequence database and time-interval weighted support (TiW-support) to find the TiWS patterns. In addition, a new method of mining TiWS patterns in a sequence database is also presented. In the proposed framework of TiWS pattern mining, the weight of each sequence in a sequence database is first obtained from the time-intervals of elements in the sequence, and subsequently TiWS patterns are found considering the weight. A series of evaluation results shows that TIWS pattern mining is efficient and helpful in finding more interesting sequential patterns.     

Mining manufacturing databases to discover the effect of operation sequence on the product quality

Data mining techniques can be used for discovering interesting patterns in complicated manufacturing processes. These patterns are used to improve manufacturing quality. Classical representations of quality data mining problems usually refer to the operations settings and not to their sequence. This paper examines the effect of the operation sequence on the quality of the product using data mining techniques. For this purpose a novel decision tree framework for extracting sequence patterns is developed. The proposed method is capable to mine sequence patterns of any length with operations that are not necessarily immediate precedents. The core induction algorithmic framework consists of four main steps. In the first step, all manufacturing sequences are represented as string of tokens. In the second step a large set of regular expression-based patterns are induced by employing a sequence patterns. In the third step we use feature selection methods to filter out the initial set, and leave only the most useful patterns. In the last stage, we transform the quality problem into a classification problem and employ a decision tree induction algorithm. A comparative study performed on benchmark databases illustrates the capabilities of the proposed framework.     

DNA序列数据挖掘技术

DNA序列数据是一类重要的生物数据.研究DNA序列数据解读其含义是后基因组时代的主要研究任务.数据挖掘是目前最有效的数据分析手段之一,用于发现大量数据所隐含的各种规律,也是生物信息学采用的主要数据分析技术.将数据挖掘技术用于DNA序列数据分析,已得到了广泛关注和快速发展,并取得了许多研究成果.综述了DNA序列数据挖掘领域的研究状况和进展,提出了3个研究阶段:基于统计的挖掘方法应用阶段、一般化挖掘方法应用阶段和专门的DNA序列数据挖掘方法设计阶段.阐述了DNA序列数据挖掘的基础是序列相似性,评述了DNA序列数据挖掘领域所采用的关键技术,包括DNA序列模式、关联、聚类、分类和异常挖掘等,分析讨论了其相应的生物应用背景和意义.最后给出DNA序列数据挖掘进一步研究的热点问题,包括DNA序列数据新的存储和索引机制的设计、根据生物领域知识的数据挖掘新模型和算法的设计等.     

多维序列模式挖掘算法

提出一种基于最大频繁模式、模式相似与属性描述相结合的多维序列模式挖掘算法MSP,该算法包括3个步骤:挖掘数据集中的最大频繁模式,每个频繁模式成为一个模式类;比较数据中各序列项序列与各模式类的包含与相似关系;按照一定的规则抽取与各模式类相关的属性,给出以属性为前件、模式类为后件的多维序列规则为形式的多维序列模式挖掘结果....     

序列模式挖掘算法研究

数据挖掘领域一个活跃的研究分支就是序列模式的发现,即在序列数据库中找出所有的频繁子序列。目前的序列模式挖掘方法主要分为两类,一类是候选集生成-测试方法;另一类是模式扩展方法。先介绍序列模式挖掘中的基本概念,然后描述几个重要算法,最后给出性能分析。     

网络入侵检测中序列模式挖掘技术研究

面向入侵检测的数据挖掘是目前国际上网络安全和数据库、信息决策领域的最前沿的研究方向之一。入侵检测中进行序列模式挖掘时，由于频繁网络模式和频繁系统活动模式只能在网络或操作系统的单个审计数据流中获得，因而传统从事件流数据中获取单序列模式的算法，以及从不同多数据序列中获取多个序列模式的算法都不再适用。本文研究了入侵数据的特性，提出了网络入侵检测中序列模式挖掘框架和实时序列模式挖掘模型，并设计了一种新的面向入侵检测．基于轴属性、参考属性、相关支持度的序列模式挖掘算法SPM—ID(Sequential Patterns Mining for Intrusion Detection)。最后在KDD Cup99数据集的基础上实现算法及分析算法的性能。     

基于相邻频繁模式段的闭合序列模式挖掘算法

直接对生物序列进行频繁模式挖掘会产生很多冗余模式,闭合模式更能表达出序列的功能和结构。根据生物序列的特点,提出了基于相邻闭合频繁模式段的模式挖掘算法－JCPS。首先产生闭合相邻频繁模式段,然后对这些闭合频繁模式段进行组合,同时进行闭合检测,产生新的闭合频繁模式。通过对真实的蛋白质序列家族库的处理,证明该算法能有效处理生物序列数据。     

Closed inter-sequence pattern mining

Inter-sequence pattern mining can find associations across several sequences in a sequence database, which can discover both a sequential pattern within a transaction and sequential patterns across several different transactions. However, inter-sequence pattern mining algorithms usually generate a large number of recurrent frequent patterns. We have observed mining closed inter-sequence patterns instead of frequent ones can lead to a more compact yet complete result set. Therefore, in this paper, we propose a model of closed inter-sequence pattern mining and an efficient algorithm called CISP-Miner for mining such patterns, which enumerates closed inter-sequence patterns recursively along a search tree in a depth-first search manner. In addition, several effective pruning strategies and closure checking schemes are designed to reduce the search space and thus accelerate the algorithm. Our experiment results demonstrate that the proposed CISP-Miner algorithm is very efficient and outperforms a compared EISP-Miner algorithm in most cases.     

基于多源告警的攻击事件分析

为解决多源告警中的复杂攻击难以被发现的问题,提出一种攻击序列模式挖掘算法。利用正则表达式匹配告警,将多源告警规范化为统一格式。对冗余告警信息进行压缩,利用强关联规则训练得到的规则集聚合同一阶段的告警,有效去除冗余告警,精简告警数量。利用滑动窗口对聚合后的告警进行划分得到候选攻击事件数据集,通过改进的PrefixSpan算法挖掘得到多阶段攻击事件的攻击序列模式。实验结果表明,该算法在不依赖专家知识的前提下,能够准确并高效地分析告警相关性,还原攻击事件中的攻击步骤。相比传统PrefixSpan算法,提出的改进算法的攻击模式挖掘效率提升了48.05%。     

Online feature importance ranking based on sensitivity analysis

Online learning is a growing branch of data mining which allows all traditional data mining techniques to be applied on a online stream of data in real time. In this paper, we present a fast and efficient online sensitivity based feature ranking method (SFR) which is updated incrementally. We take advantage of the concept of global sensitivity and rank features based on their impact on the outcome of the classification model. In the feature selection part, we use a two-stage filtering method in order to first eliminate highly correlated and redundant features and then eliminate irrelevant features in the second stage. One important advantage of our algorithm is its generality, which means the method works for correlated feature spaces without preprocessing. It can be implemented along with any single-pass online classification method with separating hyperplane such as SVMs. The proposed method is primarily developed for online tasks, however, we achieve very significant experimental results in comparison with popular batch feature ranking/selection methods. We also perform experiments to compare the method with available online feature ranking methods. Empirical results suggest that our method can be successfully implemented in batch learning or online mode.     

Speech recognition using hybrid hidden markov model and NN classifier

This paper discusses the use of an integrated HMM/NN classifier for speech recognition. The proposed classifier combines the time normalization property of the HMM classifier with the superior discriminative ability of the neural net (NN) classifier. Speech signals display a strong time varying characteristic. Although the neural net has been successful in many classification problems, its success (compared to HMM) is secondary to HMM in the field of speech recognition. The main reason is the lack of time normalization characteristics of most neural net structures (time-delay neural net is one notable exception but its structure is very complex). In the proposed integrated hybrid HMM/NN classifier, a left-to-right HMM module is used first to segment the observation sequence of every exemplar into a fixed number of states. Subsequently, all the frames belonging to the same state are replaced by one average frame. Thus, every exemplar, irrespective of its time scale variation, is transformed into a fixed number of frames, i.e., a static pattern. The multilayer perceptron (MLP) neural net is then used as the classifier for these time normalized exemplars. Some experimental results using telephone speech databases are presented to demonstrate the potential of this hybrid integrated classifier.     

Analyzing Sequential Patterns in Retail Databases

Finding correlated sequential patterns in large sequence databases is one of the essential tasks in data mining since a huge number of sequential patterns are usually mined, but it is hard to find sequential patterns with the correlation. According to the requirement of real applications, the needed data analysis should be different. In previous mining approaches, after mining the sequential patterns, sequential patterns with the weak affinity are found even with a high minimum support. In this paper, a new framework is suggested for mining weighted support affinity patterns in which an objective measure, sequential ws-confidence is developed to detect correlated sequential patterns with weighted support affinity patterns. To efficiently prune the weak affinity patterns, it is proved that ws-confidence measure satisfies the anti-monotone and cross weighted support properties which can be applied to eliminate sequential patterns with dissimilar weighted support levels. Based on the framework, a weighted support affinity pattern mining algorithm （WSMiner） is suggested. The performance study shows that WSMiner is efficient and scalable for mining weighted support affinity patterns.