Efficient mining of constrained patterns

随着技术的进步，在许多应用中，如无线传感器网络，可以产生大量的数据。因此，我们淹没在数据中，却渴望知识。为了能够“从消防水管中喝水”（即，为了理解大量数据），需要用于从大量数据中提取有用信息的方法。这就需要数据挖掘，它是指搜索可能嵌入在数据中的隐含的、以前未知的和潜在有用的知识（如频繁模式和异常模式）。在过去的几年里，我开发了交互式算法来寻找满足某类约束的频繁模式。这些算法通过一些优化得到了增强，例如轻量级结构，可以为频繁模式的频率提供更清晰的界限。此外，我还开发了一种新颖的树结构，用于在增量环境中有效地捕获和更新数据库的内容。沿着这个方向，我建议建立一个更有效的，用户友好的，和强大的挖掘系统，使它（i）纳入用户的偏好，（ii）允许用户可视化的数据，（iii）允许用户在挖掘过程中改变挖掘参数和/或约束，（iv）为用户提供可理解的反馈，在"实时"的方式，（v）发现和利用约束的任何未知性质以避免不必要的计算并进一步加速性能，以及（vi）通过探索现实生活中的应用（例如，从购物篮数据、Web点击流、农业/气象数据和医学/生物医学数据中挖掘）。发现的频繁模式揭示了共同的趋势;发现的异常模式为预防疾病爆发或灾难敲响了警钟。从长远来看，这一建议还可以扩展到处理各种类型的数据，从传统的字母数字数据到非传统的多媒体数据，从结构化数据到半结构化XML数据，从传统的“静态”事务数据到“动态”连续数据流。

With the advance in technology, a flood of data can be produced in many applications such as wireless sensor networks. Consequently, we are drowning in data but starving for knowledge. To be able to ''drink from a fire hose'' (i.e., to make sense of the flood of data), methods for extracting useful information from the flood of data are in demand. This calls for data mining, which refers to the search for implicit, previously unknown, and potentially useful knowledge (such as frequent patterns and exceptional patterns) that might be embedded in the data. Over the past few years, I have developed interactive algorithms for finding frequent patterns satisfying a certain class of constraints. The algorithms are enhanced with some optimizations such as a light-weight structure that provides sharper bounds on the frequency of frequent patterns. Furthermore, I have also developed a novel tree structure for effectively capturing and updating the contents of the database in an incremental environment. Along this direction, I propose to build a more efficient, user-friendly, and powerful mining system such that it (i) incorporates users' preferences, (ii) allows users to visualize the data, (iii) permits users to change the mining parameter and/or constraints during the mining process, (iv) provides users with comprehensible feedback in a ''real-time'' fashion, (v) discovers and exploits any unknown properties of constraints to avoid unnecessary computation and to further speed up performance, and (vi) keeps a good fusion of theory and practice via the exploration of real-life applications (e.g., mining from market basket data, Web click stream, agricultural/meteorological data, and medical/biomedical data). The discovered frequent patterns reveal the common trends; the discovered exceptional patterns trigger alarm bells for prevention of outbreaks or disasters. In the long term, this proposal can also be extended to handle various types of data, ranging from traditional alphanumeric data to non-traditional multimedia data, from structured data to semi-structured XML data, and from traditional ''static'' transactional data to ''dynamic'' streams of continuous data.