Loading...

2.1. The Downward Closure Property of Frequent Patterns

Course video 5 of 38

Module 1 consists of two lessons. Lesson 1 covers the general concepts of pattern discovery. This includes the basic concepts of frequent patterns, closed patterns, max-patterns, and association rules. Lesson 2 covers three major approaches for mining frequent patterns. We will learn the downward closure (or Apriori) property of frequent patterns and three major categories of methods for mining frequent patterns: the Apriori algorithm, the method that explores vertical data format, and the pattern-growth approach. We will also discuss how to directly mine the set of closed patterns.

数据挖掘中的模式发现

伊利诺伊大学香槟分校

课程 4（共 6 门，数据挖掘专项课程）

Learn the general concepts of data mining along with basic methodologies and applications. Then dive into one subfield in data mining: pattern discovery. Learn in-depth concepts, methods, and applications of pattern discovery in data mining. We will also introduce methods for data-driven phrase mining and some interesting applications of pattern discovery. This course provides you the opportunity to learn skills and content to practice and engage in scalable pattern discovery methods on massive transactional data, discuss pattern evaluation measures, and study methods for mining diverse kinds of patterns, sequential patterns, and sub-graph patterns.

查看授课大纲

您将学习的技能

Streams, Sequential Pattern Mining, Data Mining Algorithms, Data Mining

教学方

Jiawei Han
Abel Bliss Professor

脚本

[SOUND]

We are going to introduce a very important

property of frequent patterns,

which is called the Downward Closure Property of Frequent Patterns.

Let's look at this simple transaction database TDB 1,

it contains only two transactions, T sub 1 and T sub 2.

Suppose we get frequent itemsets a1 to a50,

then we actually can clearly see all its subsets like a1, a2,

or a1, a2 as a item set, they're all frequent.

Then you may wonder, there must be some interesting hidden

relationships among different frequent itemsets.

Actually there is a one called downward closure property

of frequent patterns which is also called the Apriori property.

Okay, now let's look at this.

Suppose we know {beer, diaper, nuts}, this itemset is frequent.

Obviously, beer and diapers should be frequent as well,

because any transaction which contains beer, diaper, and

nuts must also contain beer and diaper as a itemset.

That's why the beer, diaper as an itemset should be at least as

frequent as beer, diaper, and nuts.

So we can easily derive this property so

that any subset of a frequent itemset must be frequent,

if we keep the minimum support ratio as the same.

So in that context, we can derive a efficient mining methodology.

The general philosophy is, if you find an itemset S,

any of its subset is infrequent.

Then, there's no chance for S to become frequent because based on this Apriori

property, then we do not even have to consider to mine S.

This actually turns out to be a sharp knife for pruning.

So, this Apriori Pruning, based on this,

it generates quite a lot of Scalable Pattern Mining Methods.

So the first Apriori Pruning principle was discovered

by Rakesh Agrawal and Srikant in VLDB 1994.

[INAUDIBLE] Mannila in KDD'94 workshop also generates a similar methodology.

The methodology generally says if there's any subset,

any itemset which is infrequent,

then its superset should not even being considered and not even being generated.

Based on this, there are three major approaches develop in subsequent studies.

One essentially is Apriori, the first representative work was

published in VLDB 1994 called level-wise join-based approach.

Another method was developed by Zaki and [INAUDIBLE] and

what they got called Eclat is based on vertical data format.

Then the cert approach is essentially pattern based.

It's frequent pattern projection growth is pattern growth approach.

Called api growth, developed by us in year 2000.

[MUSIC]

关于 Coursera

课程、专项课程和在线学位均由全世界一流大学和教育机构的顶尖授课教师教授。

Join a community of 40 million learners from around the world

Earn a skill-based course certificate to apply your knowledge

Gain confidence in your skills and further your career

Coursera 致力于普及全世界最好的教育，它与全球一流大学和机构合作提供在线课程。

© 2019 Coursera Inc. 保留所有权利。

通过 App Store 下载

通过 Google Play 获取