Departamento de Informática, Universidade do Minho
Braga, 27 de Março de 2005
GRIDSD
Extracção de padrões em bases de
dados de grandes dimensões
Ronnie Alves ([email protected])
http://alfa.di.uminho.pt/~ronnie
Centro de Ciências e Tecnologia da Computação
Departamento de Informática
Escola de Engenharia
Universidade do Minho
PORTUGAL
Departamento de Informática, Universidade do Minho
GRID - Grupo de Investigação e Desenvolvimento em Sistemas de Dados
• DBMS, os maiores e mais pesados
• Exploração dos DBMS
• Mineração de bases de dados
– Large Transactional Tables
– Fracamente acoplado
– Fortemente acoplado
• Extracção de conhecimento via Procedural Schema
– Itemset Mining
• Trabalhos Relacionados
Roteiro
1
Departamento de Informática, Universidade do Minho
GRID - Grupo de Investigação e Desenvolvimento em Sistemas de Dados
• Database Size, Decision Support Systems
– All Environments & UNIX Only: Top honors went to France
Telecom for the largest database in the All Environments and
UNIX Only categories. At 29.2TB, the database was three
times as big as that of the 2001 winner. France Telecom runs
the Oracle Database on HP Superdome servers and HP
RAID storage systems.
• Rows/Records, Decision Support Systems
– All Environments & UNIX Only: AT&T received two
additional Grand Prizes for most rows, All Environments and
UNIX Only categories. The 496 billion-row system
represents a doubling of the highest figure for this category
in 2001.
» March 2004 Issue DM Review Magazine
» http://www.dmreview.com/article_sub.cfm?articleId=8182
DBMS, os maiores e mais pesados
1
Departamento de Informática, Universidade do Minho
GRID - Grupo de Investigação e Desenvolvimento em Sistemas de Dados
• Buscar e Resumir dados
– SQL
• SQL + funções de agregação (count, min, sum,…)
» SELECT Empresa, Produto, SUM(Total)
» FROM Vendas
» GROUP BY Empresa, Produto
» HAVING SUM(Total)>10000
• Extrair Padrões dos dados
– Para além das funcionalidades do SQL ANSI.
» Para tal entra em acção os algoritmos e
ferramentas de mineração
Exploração dos DBMS
1
Departamento de Informática, Universidade do Minho
GRID - Grupo de Investigação e Desenvolvimento em Sistemas de Dados
• Actividade básica,
– encontrar padrões frequentes (itemset mining)
Mineração de bases de dados
1
Departamento de Informática, Universidade do Minho
GRID - Grupo de Investigação e Desenvolvimento em Sistemas de Dados
• Fracamente acoplado
– O processo de mineração é feito fora do DBMS
– Usa o DBMS apenas para buscar os dados
• Fortemente acoplado
– Usa todos os recursos do DBMS para efeitos do processo
de mineração
Mineração de bases de dados
1
Departamento de Informática, Universidade do Minho
GRID - Grupo de Investigação e Desenvolvimento em Sistemas de Dados
•
•
•
Tarefa principal e de maior custo para a geração de Regras de
Associação
Regras da Forma: “A  [support s, confidence c]”.
Examples:
– buys(x, “diapers”)  buys(x, “beers”) [0.5%, 60%]
– age(x, “30-34”) ^ income(x ,“42K-48K”) buys(x, “high
resolution TV”) [2%,60%]
– major(x, “CS”) ^ takes(x, “DB”) grade(x, “A”) [1%, 75%]
Itemset Mining
1
Departamento de Informática, Universidade do Minho
GRID - Grupo de Investigação e Desenvolvimento em Sistemas de Dados
• Apriori
• FP-Growth
Itemset Mining Algoritmos
1
Departamento de Informática, Universidade do Minho
GRID - Grupo de Investigação e Desenvolvimento em Sistemas de Dados
Ck: Candidate itemset of size k
Lk : frequent itemset of size k
L1 = {frequent items};
for (k = 1; Lk !=; k++) do begin
Ck+1 = candidates generated from Lk;
for each transaction t in database do
increment the count of all candidates in Ck+1
that are contained in t
Lk+1 = candidates in Ck+1 with min_support
end
return k Lk;
PROBLEMA: As implementações SQL-based do Apriori geram
vários joins de grande custo na medida em que K aumenta!
Apriori—Pseudocode
1
Departamento de Informática, Universidade do Minho
GRID - Grupo de Investigação e Desenvolvimento em Sistemas de Dados
Database D
TID
100
200
300
400
itemset sup.
C1
{1}
2
{2}
3
Scan D
{3}
3
{4}
1
{5}
3
Items
134
235
1235
25
C2 itemset sup
L2 itemset sup
2
2
3
2
{1
{1
{1
{2
{2
{3
C3 itemset
{2 3 5}
Scan D
{1 3}
{2 3}
{2 5}
{3 5}
Apriori Exemplo
2}
3}
5}
3}
5}
5}
1
2
1
2
3
2
L1 itemset sup.
{1}
{2}
{3}
{5}
2
3
3
3
C2 itemset
{1 2}
Scan D
{1
{1
{2
{2
{3
3}
5}
3}
5}
5}
L3 itemset sup
{2 3 5} 2
1
Departamento de Informática, Universidade do Minho
GRID - Grupo de Investigação e Desenvolvimento em Sistemas de Dados
TID
100
200
300
400
500
Items bought
(ordered) frequent items
{f, a, c, d, g, i, m, p}
{f, c, a, m, p}
{a, b, c, f, l, m, o}
{f, c, a, b, m}
{b, f, h, j, o}
{f, b}
{b, c, k, s, p}
{c, b, p}
{a, f, c, e, l, p, m, n}
{f, c, a, m, p}
Etapas:
Header Table
1. Items frequentes de
tamanho 1
Item frequency head
f
4
c
4
a
3
b
3
m
3
p
3
2. Ordenar os items de forma
descendente
3. Construir a FP-tree
correspondente
FP-Growth
min_support = 0.5
{}
f:4
c:3
c:1
b:1
a:3
b:1
p:1
m:2
b:1
p:2
m:1
1
Departamento de Informática, Universidade do Minho
GRID - Grupo de Investigação e Desenvolvimento em Sistemas de Dados
{}
Header Table
Item frequency head
f
4
c
4
a
3
b
3
m
3
p
3
Conditional pattern bases
f:4
c:3
c:1
b:1
a:3
b:1
p:1
m:2
b:1
p:2
m:1
item
cond. pattern base
c
f:3
a
fc:3
b
fca:1, f:1, c:1
m
fca:2, fcab:1
p
fcam:2, cb:1
FP-Growth Conditional Pattern Base
1
Departamento de Informática, Universidade do Minho
GRID - Grupo de Investigação e Desenvolvimento em Sistemas de Dados
Header Table
Item frequency head
f
4
c
4
a
3
b
3
m
3
p
3
{}
f:4
c:3
c:1
b:1
a:3
b:1
p:1
m:2
b:1
p:2
m:1
m-conditional pattern
base:
fca:2, fcab:1


Todos os padrões
frequentes a m
m,
fm, cm, am,
fcm, fam, cam,
fcam
•PROBLEMA: Tamanho da FP-tree e a memória disponível.
A recursão para geração das Conditional FP-trees implica
em várias reconstruções de tabelas (CONFP)!
FP-Growth Construct Conditional FP-tree
1
Departamento de Informática, Universidade do Minho
GRID - Grupo de Investigação e Desenvolvimento em Sistemas de Dados
• Premissas:
– Não gerar joins
– Não permitir reconstrução de tabelas CONFP
• Programação do DBMS para itemset mining
– Store procedures
– Funções UDF
– Cursores(salvo cuidado!)
Pattern Growth Mining on DBMS
1
Departamento de Informática, Universidade do Minho
GRID - Grupo de Investigação e Desenvolvimento em Sistemas de Dados
• Disponibilzar uma pattern tree
• Extrair padrões via pattern growth
PGS etapas
1
Departamento de Informática, Universidade do Minho
GRID - Grupo de Investigação e Desenvolvimento em Sistemas de Dados
1. Dado um suporte mínimo gerar os itemsets frequentes de
tamanho_1
2. Gerar nova tabela de transações a partir de 1
3. Criar pattern tree
CREATE TABLE #save_time ( start_time datetime not null)
INSERT #save_time VALUES ( GETDATE())
exec genfitems '3' -->removes infrequent 1-L items
exec gentransfi -->generates only transactions with frequent 1-L items
exec genefp -->generates pattern-tree (fp)
exec genpb '3' -->generates the (pb) and (confp)
exec up_confp -->maintain the position control of items
GO
SELECT 'Structure, msec' = DATEDIFF(millisecond, start_time,
getdate())
FROM #save_time
DROP TABLE #save_time
GO
PGS pattern tree
1
Departamento de Informática, Universidade do Minho
GRID - Grupo de Investigação e Desenvolvimento em Sistemas de Dados
1. PROCEDURE EFP
2. DO with (EXISTS TRANSFI)
3. CREATE TABLE EFP (item, cnt, path)
4. CREATE TABLE FP (item, cnt, path)
5. DECLARE
6. BEGIN
7.
count = 1
8.
curpath = null
9.
c_transfi CURSOR for TRANSFI
10. FOR each row in c_transfi
11. BEGIN
12.
curpath = curpath + ‘:’ + c_transfi.item
13.
INSERT INTO EFP
14.
values(c_transfi.item, count, curpath)
15. END
16. SELECT item, sum(cnt) as cnt, path
17. INTO FP
18. FROM EFP
19. GROUP BY item, path
20. END
Pattern tree
1
Departamento de Informática, Universidade do Minho
GRID - Grupo de Investigação e Desenvolvimento em Sistemas de Dados
1. Extracção de single Patterns
2. Extracção de not single Patterns
CREATE TABLE #save_time ( start_time datetime not null)
INSERT #save_time VALUES ( GETDATE())
exec genspg '3' -->generates single patterns in table (patterns)
exec genpg '3' -->add not single patterns in table (patterns)
GO
SELECT 'Mining, msec' = DATEDIFF(millisecond, start_time,
getdate())
FROM #save_time
DROP TABLE #save_time
GO
PGS Minerar
1
Departamento de Informática, Universidade do Minho
GRID - Grupo de Investigação e Desenvolvimento em Sistemas de Dados
1. DECLARE pg_subPath CURSOR for
2.
SELECT *
3.
FROM getTable_pb(@v_prefix,@v_item) order by ord
4.
SELECT list_pg_item = pg_subPath.item
5.
FOR each row in pg_subPath
6.
BEGIN
7.
SELECT node_path = pg_subPath.item+’%’+ c_confp.item
8.
SELECT node_supp =
9.
getNodeSupp(pg_subPath.prefix, node_path)
10.
SELECT pat_item = pg_subPath.item
11.
SELECT pat_fp = node_path+'%'+ pg_subPath.prefix
12.
SELECT pat_cnt = node_supp
13.
SELECT exist_pat = (
14.
SELECT count(*) FROM PATTERNS
15.
WHERE item=pat_item and fp=pat_fp)
16. INSERT INTO PATTERNS (item,fp,cnt)
17. VALUES (pat_item, pat_fp, pat_cnt)
18.
SELECT list_pg_item = list_pg_item
19. +’%’+ pg_subPath.item
20.
END
Fragment Growth
1
Departamento de Informática, Universidade do Minho
GRID - Grupo de Investigação e Desenvolvimento em Sistemas de Dados
Gerador de datasets
1
Departamento de Informática, Universidade do Minho
GRID - Grupo de Investigação e Desenvolvimento em Sistemas de Dados
Comparativo
1
Departamento de Informática, Universidade do Minho
GRID - Grupo de Investigação e Desenvolvimento em Sistemas de Dados
• Problema para portabilidade do algoritmo
– Outro DBMS, outro PGS ORACLE PLSQL
• Máximo cuidado com os cursores!
PGS open questions
1
Departamento de Informática, Universidade do Minho
GRID - Grupo de Investigação e Desenvolvimento em Sistemas de Dados
• Jiawei Han
– http://www-faculty.cs.uiuc.edu/~hanj/
• Bart Goethals
– http://www.adrem.ua.ac.be/~goethals/
• Frequent Itemset Mining Implementations Repository
– http://fimi.cs.helsinki.fi
• Weka 3: Data Mining Software in Java
– http://www.cs.waikato.ac.nz/ml/weka/
Sites
1
Departamento de Informática, Universidade do Minho
GRID - Grupo de Investigação e Desenvolvimento em Sistemas de Dados
• Pattern Growth Tightly Coupled on RDBMS (PKDD’05
submitted)
• Integrating Pattern Growth Mining on SQL Server (technical
report)
• A Hybrid Method to Discover Inter-Transactional Rules
(JISBD’05 accepted)
Trabalhos Relacionados
1
Departamento de Informática, Universidade do Minho
GRID - Grupo de Investigação e Desenvolvimento em Sistemas de Dados
• Ponto de partida para Mineração sobre cubos (ROLAP)
– Itemset mining integrado em RDBMS
– Mineração de cubos pre-computados
– Mineração integrada com os cubos on-the-fly
– Aplicação sobre webhouses
• Primeiras interações
– When the Hunter becomes the prey... (DataGadgets’04)
– Clickstreams, The basis to Establish User Navigation
Patterns (DataMining’04)
– Mining Clickstream based Data Cubes (ICEIS’04)
Trabalhos Relacionados
1
Departamento de Informática, Universidade do Minho
GRID - Grupo de Investigação e Desenvolvimento em Sistemas de Dados
1. Agarwal, R., Shim., R.: Developing tightly-coupled data mining application on a relational
database system. In Proc.of the 2nd Int. Conf. on Knowledge Discovery in Database and
Data Mining, Portland, Oregon (1996)
2. Agrawal, R., Imielinski, T., Swami, A..: Mining association rules between sets of items in large
databases. In Proc. of the ACM SIGMOD Intl. Conference on Management of Data (1993)
207–216
3. Agrawal, R., Srikant., R.: Fast algorithms for mining association rules. In Proc. of the 20th Very
Large Data Base Conference (1994) 487–499
4. Alves, R., Belo, O.: Integrating Pattern Growth Mining on SQL-Server RDBMS. Technical
Report-003, University of Minho, Department of Informatics, May (2005)
http://alfa.di.uminho.pt/~ronnie/files_files/rt/2005-RT3-Ronnie.pdf
5. Alves, R., Gabriel, P., Azevedo, P., Belo, O.: A Hybrid Method to Discover Inter-Transactional
Rules. In Proceedings of the JISBD’2005, Granada (2005) to appear
6. Cheung, W., Zaïane, O. R.: Incremental Mining of Frequent Patterns Without Candidate
Generation or Support Constraint, Seventh International Database Engineering and
Applications Symposium (IDEAS 2003), Hong Kong, China, July 16-18 (2003) 111-116
7. El-Hajj, M., Zaïane, O.R.: Inverted Matrix: Efficient Discovery of Frequent Items in Large
Datasets in the Context of Interactive Mining, in Proc. 2003 Int'l Conf. on Knowledge
Discovery and Data Mining (ACM SIGKDD), Washington, DC, USA, August 24-27 (2003)
109-118
8. Han, J., Pei, J., Yin., Y.: Mining frequent patterns without candidate generation. In Proc. of
ACM SIGMOD Intl. Conference on Management of Data, (2000) 1–12
References(1)
1
Departamento de Informática, Universidade do Minho
GRID - Grupo de Investigação e Desenvolvimento em Sistemas de Dados
9. Hidber, C.: Online association rule mining. In A. Delis, C. Faloutsos, and S. Ghandeharizadeh,
editors, Proceedings of the 1999 ACM SIGMOD International Conference on Management
of Data, volume 28(2) of SIGMOD Record. ACM Press (1999) 145–156
10. Orlando, S., Palmerini, P., Perego, R.: Enhancing the apriori algorithm for frequent set
counting. In Y. Kambayashi, W. Winiwarter, and M. Arikawa, editors, Proceedings of the
Third International Conference on Data Warehousing and Knowledge Discovery, volume
2114 of Lecture Notes in Computer Science (2001) 71–82
11. Orlando, S., Palmerini, P., Perego, R., Silvestri, F.: Adaptive and resource-aware mining of
frequent sets. In V. Kumar, S. Tsumoto, P.S. Yu, and N.Zhong, editors, Proceedings of the
2002 IEEE International Conference on Data Mining. IEEE Computer Society (2002) To
appear
12. Rantzau, R.: Processing frequent itemset discovery queries by division and set containment
join operators. In DMKD03: 8th ACM SIGMOD Workshop on Research Issues in Data
Mining and Knowledge Discovery (2003)
13. Sarawagi, S., Thomas, S., Agrawal, R.: Integrating mining with relational database systems:
alternatives and implications. In Proc. of the ACM SIGMOD Conference on Management of
data, Seattle, Washington, USA (1998)
14. Shang, X., Sattler, K., Geist, I.: Sql based frequent pattern mining without candidate
generation. In SAC’04 Data Mining, Nicosia, Cyprus (2004)
15. Wang, H., Zaniolo, C.: Using SQL to build new aggregates and extenders for ObjectRelational systems. In Proc. Of the 26th Int. Conf. on Very Large Databases, Cairo, Egypt
(2000)
16. Yoshizawa, T., Pramudiono, I., Kitsuregawa, M.: Sql based association rule mining using
commercial rdbms (ibm db2 udb eee). In In Proc. DaWaK, London, UK (2000)
References(2)
1
Departamento de Informática, Universidade do Minho
Belém, 10 de Janeiro de 2005
GRIDSD
Extracção de padrões em bases de
dados de grandes dimensões
Ronnie Alves ([email protected])
http://alfa.di.uminho.pt/~ronnie
Centro de Ciências e Tecnologia da Computação
Departamento de Informática
Escola de Engenharia
Universidade do Minho
PORTUGAL