2.6. Mining Closed Patterns

Loading...

Del curso dictado por University of Illinois at Urbana-Champaign

Pattern Discovery in Data Mining

141 calificación

University of Illinois at Urbana-Champaign

Pattern Discovery in Data Mining

141 calificación

Curso 4 de 6 en SpecializationData Mining

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.

De la lección

Module 1

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.

2.1. The Downward Closure Property of Frequent Patterns3:59

2.2. The Apriori Algorithm6:11

2.3. Extensions or Improvements of Apriori7:32

2.4. Mining Frequent Patterns by Exploring Vertical Data Format3:43

2.5. FPGrowth: A Pattern Growth Approach8:04

2.6. Mining Closed Patterns3:49

Conoce a los instructores

Jiawei Han
Abel Bliss Professor
Department of Computer Science

Hi! In this final session of this lecture we're going to discuss mining closed pattern.

As we already know before,

closed pattern is a compact form but it's a last less compression of frequent patterns.

So mining this closed itemsets,

it's very interesting and useful.

And with pattern-growth approach there's

one interesting method developed called 'Closet+'.

Let's look at this 'Closet+'.

How to develop efficient directly mining of closed itemsets.

So let's look at this transaction database,

it contains only four transactions and these are the items in these transactions.

Suppose the minimum support is two,

we'll be able to get these as frequent itemsets.

And based on this we can work out the F-list like the following.

Now, we look at an interesting method developed called 'itemset merging'.

The philosophy can be represented using this example.

Let's look at these projective database.

For these projective database,

we will have ACF,

EF, and ACF based on this.

As you can see this project database will get ACEF and ACF.

But the interesting thing is ACF happens in every transaction project in this database.

ACF have the same support as D. In that case,

we can grab ACF out form

ACFD project database which contains only one item E, it is not frequent.

Therefore, we will be able to get a ACFD support is two, it's the final result.

This method called 'itemset merging' simply says if Y appears in every occurrence of X,

then items of Y is merged with X.

Now, the X is D and a Y is ACF.

ECF occurs in every occurrence of X which is D,

then we will merge ACFD together to form a more compressed form.

That means, you can mine all these immediately.

So this is more efficient.

Actually, there are many tricks developed in Closet+.

For example, hybrid tree projection,

we use bottom-up physical tree projection,

top-down pseudo tree projection.

There's one technical sub-itemset pruning,

itemset skipping, efficient subset testing.

But I'm not going to get into the details.

For details, you can read this paper.

So finally I'll summarize the recommended readings.

These are all classical papers.

Apriori mining and the further improvement of Apriori mining.

Then we have vertical methods,

FP-growth methods, and we have Closet+ methods.

So finally, there is

an interesting survey article called 'Frequent Pattern Mining Algorithms',

which contain many more algorithms covered in this lecture.

If you're interested in,

go ahead and read this chapter.

Explora nuestro catálogo

Inscríbete de manera gratuita y obtén recomendaciones personalizadas, actualizaciones y ofertas.

Coursera brinda acceso universal a la mejor educación del mundo, al asociarse con las mejores universidades y organizaciones, para ofrecer cursos en línea.

© 2018 Coursera Inc. Todos los derechos reservados.

Descargar en la App Store

Consíguelo en Google Play