基于序列模式挖掘的隐私保护

研究针对序列模式有关隐私保护议题,提出有效的SDRF序列模式隐藏算法,让分享序列模式时也能保护自己的核心信息。     

Anonymity preserving pattern discovery

It is generally believed that data mining results do not violate the anonymity of the individuals recorded in the source database. In fact, data mining models and patterns, in order to ensure a required statistical significance, represent a large number of individuals and thus conceal individual identities: this is the case of the minimum support threshold in frequent pattern mining. In this paper we show that this belief is ill-founded. By shifting the concept of k -anonymity from the source data to the extracted patterns, we formally characterize the notion of a threat to anonymity in the context of pattern discovery, and provide a methodology to efficiently and effectively identify all such possible threats that arise from the disclosure of the set of extracted patterns. On this basis, we obtain a formal notion of privacy protection that allows the disclosure of the extracted knowledge while protecting the anonymity of the individuals in the source database. Moreover, in order to handle the cases where the threats to anonymity cannot be avoided, we study how to eliminate such threats by means of pattern (not data!) distortion performed in a controlled way.     

序列模式挖掘中的隐私保护方法研究*

目前,已提出了一些关联规则挖掘中的隐私保护方法,而对序列模式挖掘中隐私保护的研究却很少。为此,提出了一种有效的敏感序列隐藏算法CLSDA(current least sequences delete algorithm),该算法对候选序列加权,在删除序列的过程中随时更新权值,使用贪心算法获得局部最优解,尽可能减少对原始数据库的改动。实验结果表明,与现有序列模式隐藏方法相比,算法CLSDA将具有更好的隐藏效果。     

基于频繁项集发现的匿名隐私保护算法*

通过定义考虑权重的匿名表效用度量函数,用于在泛化步骤决定下一个泛化路径以取得较好的泛化效果,在此基础上提出利用频繁项集发现思想的微观数据表匿名隐私保护算法ABFI(algorithm based on frequent set mining),匿名过程仅仅对不满足隐私保护要求等价组中准码属性取值进行泛化。实验结果表明,该方法可以减少信息损失,求解得到更加符合数据分析任务需求的局部最优匿名表。     

闭合序列模式挖掘算法

提出了一种新的挖掘闭合序列模式的PosD算法,该算法利用位置数据保存数据项的顺序信息,并基于位置数据列表保存数据项的顺序关系提出了两种修剪方法：逆向超模式和相同位置数据。为了确保栅格存储的正确性和简洁性,另外还针对一些特殊情况做处理。试验结果表明,在中大型数据库和小支持度的情况下谊算法比CloSpan算法更有效。     

Self-adaptive nonoverlapping sequential pattern mining

Applied Intelligence - Repetitive sequential pattern mining (SPM) with gap constraints is a data analysis task that consists of identifying patterns (subsequences) appearing many times in a...     

Weighted frequent sequential pattern mining

Trillions of bytes of data are generated every day in different forms, and extracting useful information from that massive amount of data is the study of data mining. Sequential pattern mining is a major branch of data mining that deals with mining frequent sequential patterns from sequence databases. Due to items having different importance in real-life scenarios, they cannot be treated uniformly. With today’s datasets, the use of weights in sequential pattern mining is much more feasible. In most cases, as in real-life datasets, pushing weights will give a better understanding of the dataset, as it will also measure the importance of an item inside a pattern rather than treating all the items equally. Many techniques have been introduced to mine weighted sequential patterns, but typically these algorithms generate a massive number of candidate patterns and take a long time to execute. This work aims to introduce a new pruning technique and a complete framework that takes much less time and generates a small number of candidate sequences without compromising with completeness. Performance evaluation on real-life datasets shows that our proposed approach can mine weighted patterns substantially faster than other existing approaches.

     

序列模式挖掘综述

综述了序列模式挖掘的研究状况。首先介绍了序列模式挖掘背景与相关概念;其次总结了序列模式挖掘的一般方法,介绍并分析了最具代表性的序列模式挖掘算法;最后展望序列模式挖掘的研究方向。便于研究者对已有算法进行改进,提出具有更好性能的新的序列模式挖掘算法。     

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

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

基于位置信息的序列模式挖掘算法*

PrefixSpan算法在产生频繁序列模式时会产生大量的投影数据库,其中很多投影数据库是相同的。提出了基于位置信息的序列模式挖掘算法——PVS,该方法通过记录每个已产生投影数据库的位置信息,避免了重复产生相同的投影数据库,从而提高了算法的运行效率。通过实验证明,该算法在处理相似度很高的序列数据时比PrefixSpan算法有效。     

From sequential pattern mining to structured pattern mining: A pattern-growth approach

Sequential pattern mining is an important data mining problem with broad applications. However,it is also a challenging problem since the mining may have to generate or examine a combinatorially explosivenumber of intermediate subsequences. Recent studies have developed two major classes of sequential patternmining methods: (1) a candidate generation-and-test approach, represented by (i) GSP, a horizontal format-basedsequential pattern mining method, and (ii) SPADE, a vertical format-based method; and (2) a pattern-growthmethod, represented by PrefixSpan and its further extensions, such as gSpan for mining structured patterns. In this study, we perform a systematic introduction and presentation of the pattern-growth methodologyand study its principles and extensions. We first introduce two interesting pattern-growth algorithms, FreeSpanand PrefixSpan, for efficient sequential pattern mining. Then we introduce gSpan for mining structured patternsusing the same methodology. Their relative performance in l     

Closed sequential pattern mining for sitemap generation

World Wide Web - A sitemap represents an explicit specification of the design concept and knowledge organization of a website and is therefore considered as the website’s basic ontology. It...     

NetNMSP: Nonoverlapping maximal sequential pattern mining

Applied Intelligence - Nonoverlapping sequential pattern mining, as a kind of repetitive sequential pattern mining with gap constraints, can find more valuable patterns. Traditional algorithms...     

Privacy preserving data mining of sequential patterns for network traffic data

As the total amount of traffic data in networks has been growing at an alarming rate, there is currently a substantial body of research that attempts to mine traffic data with the purpose of obtaining useful information. For instance, there are some investigations into the detection of Internet worms and intrusions by discovering abnormal traffic patterns. However, since network traffic data contain information about the Internet usage patterns of users, network users’ privacy may be compromised during the mining process. In this paper, we propose an efficient and practical method that preserves privacy during sequential pattern mining on network traffic data. In order to discover frequent sequential patterns without violating privacy, our method uses the N-repository server model, which operates as a single mining server and the retention replacement technique, which changes the answer to a query probabilistically. In addition, our method accelerates the overall mining process by maintaining the meta tables in each site so as to determine quickly whether candidate patterns have ever occurred in the site or not. Extensive experiments with real-world network traffic data revealed the correctness and the efficiency of the proposed method.     

Constraint-based sequential pattern mining: the pattern-growth methods

Constraints are essential for many sequential pattern mining applications. However, there is no systematic study on constraint-based sequential pattern mining. In this paper, we investigate this issue and point out that the framework developed for constrained frequent-pattern mining does not fit our mission well. An extended framework is developed based on a sequential pattern growth methodology. Our study shows that constraints can be effectively and efficiently pushed deep into the sequential pattern mining under this new framework. Moreover, this framework can be extended to constraint-based structured pattern mining as well. This research is supported in part by NSERC Grant 312194-05, NSF Grants IIS-0308001, IIS-0513678, BDI-0515813 and National Science Foundation of China (NSFC) grants No. 60303008 and 69933010. All opinions, findings, conclusions and recommendations in this paper are those of the authors and do not necessarily reflect the views of the funding agencies.     

基于深度优先序列模式挖掘的预取模型

序列模式挖掘能够发现隐含在Web日志中的用户的访问规律,可以被用来在Web预取模型中预测即将访问的Web对象。目前大多数序列模式挖掘是基于Apriori的宽度优先算法。提出了基于位图深度优先挖掘算法,采用基于字典树数据结构的深度优先策略,同时采用位图保存和计算各序列的支持度,能够较迅速地挖掘出频繁序列。将该序列模式挖掘算法应用于Web预取模型中,在预取缓存一体化的条件下实验表明具有较好的性能。     

Malicious sequential pattern mining for automatic malware detection

Due to its damage to Internet security, malware (e.g., virus, worm, trojan) and its detection has caught the attention of both anti-malware industry and researchers for decades. To protect legitimate users from the attacks, the most significant line of defense against malware is anti-malware software products, which mainly use signature-based method for detection. However, this method fails to recognize new, unseen malicious executables. To solve this problem, in this paper, based on the instruction sequences extracted from the file sample set, we propose an effective sequence mining algorithm to discover malicious sequential patterns, and then All-Nearest-Neighbor (ANN) classifier is constructed for malware detection based on the discovered patterns. The developed data mining framework composed of the proposed sequential pattern mining method and ANN classifier can well characterize the malicious patterns from the collected file sample set to effectively detect newly unseen malware samples. A comprehensive experimental study on a real data collection is performed to evaluate our detection framework. Promising experimental results show that our framework outperforms other alternate data mining based detection methods in identifying new malicious executables.     

Scalable and parallel sequential pattern mining using spark

World Wide Web - The performance of the existing parallel sequential pattern mining algorithms is often unsatisfactory due to high IO overhead and imbalanced load among the computing nodes. To...     

并发序列模式挖掘方法研究

提出并发关系的概念,在此基础上给出并发度的概念,进而提出并发序列模式的概念。给出了用于挖掘并发序列模式的方法——基于支持向量的并发序列模式挖掘方法。该方法通过产生序列模式的支持向量求得2-分支并发序列模式及其支持向量;然后通过（k-1）-分支并发序列模式的支持向量和序列模式的支持向量产生k-分支并发序列模式及其支持向量,进而求得所有k分支并发序列模式。实验中采用IBM数据生成器产生的合成数据源对算法进行了验证实现,实验表明算法是有效和可行的,在不同的支持度和最小并发度下,挖掘得到并发序列模式总数随最小并发度的增大呈指数递减。     

挖掘闭合多维序列模式的可行方法

为了对闭合多维序列模式进行挖掘,研究了多维序列模式的基本性质,进而提出了挖掘闭合多雏序列模式的新方法.该方法集成了闭合序列模式挖掘方法和闭合项目集模式挖掘方法,通过证明该方法的正确性,指出闭合多维序列模式集合不大于多维序列模式集合,并且能够覆盖所有多维序列模式的结果集.最后分析了该方法所具备的两个明显优点,表明了在闭合多维序列模式挖掘中的可行性.