序列大数据复杂情景模式发现算法研究

One common problem of traditional frequent episode mining algorithms is the great number of output patterns. This problem will become more intractable in big data circumstance. We emphasize the essential reason is that traditional episodes are usually described by only events which is simple and uninformative. Too many combinations of events can form candidates of episodes. Meanwhile, data type in big data era appears multi-source and heterogeneous characteristics significantly. Complex episodes may be contained in them. In addition, data update swift in big data era. It gives a new requirement for complex episode mining algorithms over dynamic data, and that is the algorithms need be real-time. As a consequent, in this project, we will research the complex episode mining algorithms in big sequence data. We focus on studying (1) the definition of complex episodes and its mining algorithms; (2) complex episode mining algorithms in multi-source and heterogeneous data; (3) real-time algorithms for complex episode mining over dynamic data stream. We will meanwhile discuss their applications on personalized recommendation and financial temporal data analysis and so on. Specifically, we will augment episode representations by appending time information, multi-dimensional attributes and multi-level abstraction, etc. to the definition of traditional episode. Because of the problem of ‘combination explosion’, the algorithms mining episodes in sequence data have a high complexity in both time and space. Therefore, the design of compact storage data structure and efficient enumeration method is one of the key challenges of this project.

传统频繁情景模式发现算法的一个共性问题是输出的模式数量过多。大数据环境下这一问题将更突显。我们认为其本质原因是传统的情景模式仅用事件进行表示，形式简单，能形成候选情景模式的组合过多。同时，大数据环境数据类型的多源异构特征明显，其中可能蕴含非传统的复杂情景模式需要挖掘。此外，大数据更新迅速，给面向动态数据的复杂情景模式发现算法提出实时性要求。因此，本项目针对序列大数据，重点研究（1）复杂表达的情景模式的形式化定义和挖掘算法，（2）面向多源异构数据的复杂情景模式挖掘算法，（3）面向动态数据的复杂情景模式实时算法，并探讨它们在个性化推荐、金融时序数据分析等方面的应用。具体地，本项目通过在情景模式的表达形式上加入时间、多维度属性、多层级抽象概念等信息扩充表达的多样性。由于“组合爆炸”问题，从序列数据中挖掘复杂情景模式具有很高的复杂度，因此高压缩存储结构和快速计算方法的设计是本项目的挑战问题之一。

青年基金项目《序列大数据复杂情景模式发现算法研究》（批准号61602438，以下简称“项目”）针对大数据环境下情景模式发现面临的(1)传统情景模式信息表达能力不足、数量过多，(2)多源异构数据复杂情景模式发现算法复杂度高，(3)动态数据复杂情景模式发现算法复杂度高等关键问题，研究了精确定位的情景规则、趋同情景模式等复杂情景模式产生机理、形式化定义与快速挖掘算法，并在金融、交通领域实际时序数据中开展应用；研究了层次敏感的情景模式分布式挖掘算法，缓解异构数据情景模式发现算法复杂度高的问题；研究了高噪声多序列共演化情景模式挖掘算法，缓解动态数据情景模式发现算法复杂度高的问题；研究了情景模式效用评价、模式有效性验证方法，过滤冗余的复杂情景模式。在项目支持下，共发表论文17篇，其中包括SCI期刊论文5篇、CCF A类会议论文6篇、CCF B类会议论文6篇，1项国内发明专利获得授权。项目负责人敖翔博士担任第一作者的有关精确定位的情景规则挖掘算法的论文发表在CCF A类会议ICDE2017和CCF A类期刊IEEE TKDE、基于二元划分模式有效性检验方法的论文发表在CCF B类会议DASFAA2018、层次结构敏感的情景模式发现分布式算法的论文发表在JCR二区期刊ACM TIST。在项目的支持下，提出的趋同交易情景模式发现分布式挖掘算法用于我国证券监管部门“老鼠仓”证据发现实际应用，效率提升3个数量级，将算法运行时间由“天”级降低至“分钟”级，有效缓解了“老鼠仓”举证难问题，获相关领导好评。在项目执行期间，项目负责人敖翔博士晋升为中科院计算所副研究员、硕士生导师，并入选中国科学院青年创新促进会。