Xem mẫu
- một ngữ cảnh hình thức cho trước. B
Lương Văn Nghĩa, Lê Văn Sơn, Huỳnh Triệu Vỹ
Trong các thuật toán giới thiệu, trước phạm
MỘT CÁCH TIẾP CẬN TÌM TẬP PHỔ BIẾN
tiên chúng tôi DỰA
tính cơTRÊN
sở của GIÀN
ngữ cảnh, sau đó khái
tính tất KẾT
TRONG KHAI PHÁ LUẬT cả các HỢP
khái niệm từ cơ sở. Ưu điểm của niệm
định lý 4 trong bài báo này là có thể dễ dàng xác
THE APPROACH FOR BUILDING THE FREQUENCY
định quan hệSET BASED
bao hàm ONkhái
của các LATTICE
niệm. nghĩ
IN MINING ASSOCIATION RULES
2. Một số khái niệm cơ sở như
Lương Văn Nghĩa , Lê Văn Sơn2 , Huỳnh
1
Triệu
Sau đây Vỹ1 tôi trình bày một số khái
chúng
1 ,Y)
niệm cơ sở về giànhtrvy@yahoo.com
Trường Đại học Phạm Văn Đồng; Email: nghia.itq@gmail.com, có liên quan. Để có thông tin
2
Trường Đại học Sư phạm, Đại học Đà Nẵng; Email: levansupham2004@yahoo.com nghĩ
chi tiết hơn về giàn, chúng ta có thể xem thêm
trong [2]. tiếp
Tóm tắt – Khai phá luật kết hợp trong các cơ sở dữ liệu giao dịch Abstract – In recently years, the Discovery of Association Rule on
lớn là bài toán đã được nhiều người quan tâm nghiên cứu. Bài toán
Định nghĩa 1. Một ngữ cảnh hình thức
the transaction of large databases has been the most interesting giữa
khai phá luật kết hợp thường được thực hiện qua hai bước. Trong problem in research. The problem of mining association rule is
đó, bước đầu tiên là tìm tập phổ biến và bước thứ hai tìm các luật (formal
usually context)
performed K:=
through steps. The trong
two(G,M,I), đóset
frequency G,isM là in
found X
kết hợp dựa trên tập phổ biến tìm được. Hiện đã có rất nhiều thuật first step, and building the association rule based on the previous
hai tập và I là quan hệ giữa G và M. Các phần tử nối
toán tìm tập phổ biến và thuật toán đề xuất sinh giàn từ quan hệ nhị result of frequency set is second step. In fact, we had many
phân, tuy nhiên các thuật toán này có độ phức tạp rất lớn. Trong bài của G được
algorithms to find gọi là các đối
the frequency settượng, các phần
and to propose tử của
for generating được
báo này chúng tôi giới thiệu một kỹ thuật tìm tập phổ biến dựa trên lattices from binary relationships. However, those algorithms still
giàn có độ phức tạp đa thức. Ưu điểm của cách tiếp cận này là bỏ
M được gọi là các thuộc tính của ngữ cảnh. Để
have been a big complexity. In this paper, we introduce a technique
bộ p
qua giai đọan tìm tập ứng viên như trong thuật toán Apriori mà tìm biểu
to find diễn quan
frequency hệongiữa
set based đối intượng
the lattice g hasGbeen
which there vớithe cho
trực tiếp tập phổ biến. complexity of polynomial. The advantage of this technique not only
thuộc
ignores thetính
stagemoffinding
M tacandidate
viết (g Isetm)ashoặc (g, m)
the Apriori I
algorithm,
H1 v
butvà đọc là “đối tượng g có thuộc tính m”.
also builds the frequency set immediately. khái
Từ khóa – luật kết hợp; tập phổ biến; giàn; lược đồ Hasse; thuật Key words – association rule; frequency set; lattice; Hasse dagram; niệm
toán Apriori. Ví dụ 1. Một ngữ cảnh được trình bày bởi
Apriori algorithm.
hiệu
một bảng tham chiếu chéo như trong Hình 1. Để
1. Giới thiệu là “đối
trìnhtượng g có thuộc
bày một tính m”.
ngữ cảnh hình thức K=(G, M, I),
Xây dựng giàn (lattice) từ tập các quan hệ nhị phân đã có Vívới
dụ 1. Một ngữ cảnh và
G={1,2,3,4,5} được
Mtrình bày bởi ta
={a,b,c,d} mộtlập bảng
bảng tham niệm
nhiều ứng dụng quan trọng. Wille (1982) đã xem mỗi phần chiếu chéo như trong Hình 1. Để trình bày một ngữ cảnh
gồm có 5 dòng (ứng với 5 đối tượng trong G) và ngữ
tử trong giàn như một khái niệm và tạo thành đồ thị tương hình thức K = (G, M, I), với G = {1, 2, 3, 4, 5} và M =
ứng (lược đồ Hasse). Đồ thị như là quan hệ khái quát hóa {a,4b,cột (ứng
c, d} với
ta lập 4 thuộc
bảng gồm cótính trong
5 dòng (ứngM).
với Tại
5 đốimỗi
tượng
giữa các khái niệm. Từ ý tưởng này, giàn biểu diễn một phân trong G) và 4 cột (ứng với 4 thuộc tính trong M).dấu
điểm giao nhau giữa dòng và cột ta đánh Tại X
mỗi
cấp khái niệm. Phân cấp khái niệm đã cho thấy có nhiều ưu nếugiao
điểm đối nhau
tượnggiữa
gG có thuộc
dòng và cột tính m dấu
ta đánh M. × nếu đối
điểm trong các lĩnh vực về khai phá tri thức từ các cơ sở dữ tượng g ∈ G có thuộc tính m ∈ M.
liệu lớn [6]. Đã có nhiều thuật toán được đề xuất sinh giàn
từ quan hệ nhị phân [1][2][4]. Nhưng các thuật toán này ít a b c d
đề cập đến độ phức tạp. Lhouari Nourine và các cộng sự 1 × ×
đã đề xuất một thuật toán nhanh (fast) cho phép xây dựng 2 × ×
giàn [5]. 3 × ×
Trong bài báo này, chúng tôi giới thiệu một phương pháp 4 × × ×
cải tiến xây dựng giàn của các tác giả trong [5]. Các thuật 5 ×
toán cho phép tạo ra tập khái niệm và lược đồ Hasse tương Mộtngữ
ngữ cảnh
HìnhHình
1. 1:
Một hình
cảnh hình thức
thức K. K.
ứng từ một ngữ cảnh hình thức cho trước.
Định nghĩa 2. Cho tập A G gồm các đối
Trong các thuật toán giới thiệu, trước tiên chúng tôi tính Định nghĩa 2. 0Cho tập A ⊆ G gồm các đối tượng. Chúng
cơ sở của ngữ cảnh, sau đó tính tất cả các khái niệm từ cơ ta định nghĩa
tượng. Chúng A :=ta{m ∈ M|g
định nghĩa ∀g:=∈ {m
I m,A’ Mcác| gthuộc
A} (tập I
tính chung của các đối tượng trong A). Tương tự, cho tập
sở. Ưu điểm của định lý 4 trong bài báo này là có thể dễ
B m,
⊆M gta A}(tập
định nghĩa B các
0
:=thuộc
{g ∈ tính
G|g Ichung
m, ∀mcủa
∈ B} các
(tập
dàng xác định quan hệ bao hàm của các khái niệm. 3. T
cácđối
đốitượng trong
tượng có cùngA).tậpTương tự, trong
thuộc tính cho tậpB).B M ta
2. Một số khái niệm cơ sở địnhnghĩa
Định nghĩa3.B’Một kháiniệm
:= {g G | ghình
I mthứcm của
B}ngữ(tập
cảnh
các đối tượng có cùng tập thuộc tính trong B). B trình
0
Sau đây chúng tôi trình bày một số khái niệm cơ sở về (G, M, I) là cặp (A, B), với A ⊆ G, B ⊆ M, A =
giàn có liên quan. Để có thông tin chi tiết hơn về giàn, chúng và B0 = A. Chúng ta gọi A là một phạm vi (extent) và B
ta có thể xem thêm trong [2]. một mục Định nghĩacủa
đích (intent) Mộtniệm
3. khái khái(A,
niệm hình M,
B). B(G, thức
I) là
tậpcủa ngữ
tất cả cáccảnh
khái(G,
niệm M,của
I) ngữ
là cặp (A,
cảnh B),
(G, I). A G,
M,với thức
Định nghĩa 1. Một ngữ cảnh hình thức (formal context)
K := (G, M, I), trong đó G, M là hai tập và I là quan 2 hệ thứ tự bộ phận được định nghĩa trên tập
Một quan
hệ giữa G và M. Các phần tử của G được gọi là các đối B(G, M, I) của ngữ cảnh (G, M, I) như sau:
tượng, các phần tử của M được gọi là các thuộc tính của Cho H1 = (X0 , X) ∈ B(G, M, I) và H2 = (Y0 , Y) ∈
ngữ cảnh. Để biểu diễn quan hệ giữa đối tượng g ∈ G với B(G, M, I), định nghĩa H1 < H2 ⇔ X ⊆ Y, nghĩa là H1 là
thuộc tính m ∈ M ta viết (g I m)4 hoặc (g, m) ∈ I và đọc cha của H2 hay khái quát hóa trực tiếp trong giàn. Thật ra
47
- TẠP CHÍ KHOA HỌC VÀ CÔNG NGHỆ, ĐẠI HỌC ĐÀ NẴNG - SỐ 1(74).2014.QUYỂN II
có một quan hệ đối ngẫu giữa X0 và X trong giàn, nghĩa là, Định lý 1. Cho K = (G, M, I) là một ngữ cảnh hình thức.
X ⊆ Y ⇔ Y0 ⊆ X0 . Vậy, về bản chất giàn là hai giàn được Khi đó, với ∀F ∈ FB , ta có (F, γ(F)) là một khái niệm của
kết nối với nhau. Lược đồ Hasse của giàn có thể được sinh K, và B ≡ {(F, γ(F))|F ∈ FB } = B(G, M, I).
ra bằng cách sử dụng quan hệ thứ tự bộ phận. Nếu H1 < H2
Bây giờ bài toán của chúng ta là đi xây dựng giàn từ ngữ
và không tồn tại H3 sao cho H1 < H3 < H2 thì sẽ tồn tại
cảnh đã cho K = (G, M, I) thông qua thuật toán được thực
một cạnh nối giữa H1 và H2 . Lược đồ/đồ thị này biểu diễn
hiện qua 3 bước sau:
quan hệ khái quát hóa/chuyên biệt hóa giữa các khái niệm
và có thể được sử dụng như một công cụ hiệu quả trong việc (1) Tính cơ sở B của ngữ cảnh K;
khai phá dữ liệu và tri thức. (2) Sinh họ B = {(F, γ(F))|F ∈ FB };
(3) Xây dựng giàn từ B.
Ví dụ 2. Ngữ cảnh của Ví dụ 1 có 9 khái niệm. Đồ thị trong
Hình 2 biểu diễn giàn của ngữ cảnh: 3.1. Tính cơ sở B của ngữ cảnh K
Từ định nghĩa của cơ sở, chúng ta có thể xác định
lực lượng của B là bằng với lực lượng của M, nghĩa là
|B| = |M|.
Thuật toán 1. Cơ sở B.
Input: Ngữ cảnh K = (G, M, I)
Output: Cơ sở B của ngữ cảnh.
Begin
|B| = |M|
for each m0 ∈ B do
m0 = Φ
for each m0 ∈ B do
for each g ∈ G do
if g I m then m0 = m0 ∪ {g}
End
Định lý 2. Thuật toán 1 tính cơ sở B của ngữ cảnh K có độ
Hình 2: Giàn cho ngữ cảnh của hình 1. phức tạp là O(|G| ∗ |M|).
3. Thuật toán nhanh xây dựng giàn Bây giờ chúng ta sử dụng cơ sở B để tạo họ khái niệm
B = {(F, γ(F))|F ∈ FB }.
Trước khi trình bày thuật toán, chúng tôi trình bày định
nghĩa cơ bản sau: 3.2. Tạo họ khái niệm B = {(F, γ(F))|F ∈ FB }
Cho K = (G, M, I) là một ngữ cảnh hình thức. Cho Thuật toán trình bày sau đây tạo ra tất cả các khái
g ∈ G, ta viết g0 thay vì {g}0 cho đối tượng mục đích niệm (F, γ(F)) từ cơ sở B của ngữ cảnh đã cho K, nghĩa
g0 := {m ∈ M|g I m} của đối tượng g. Tương tự, là, tính FB và với mỗi F ∈ FB , ta tìm γ(F) tương ứng.
m0 := g ∈ G|g I m là thuộc tính phạm vi của thuộc tính Dễ dàng ta suy ra được độ phức tạp của thuật toán là
m. Một cơ sở B là tập tất cả các thuộc tính phạm vị của K, O((|G| + |M|) ∗ |M| ∗ |FB|).
nghĩa là,
B = {m0 |m ∈ M} Thuật toán 2. Sinh B(G, M, I) = {(F, γ(F))|F ∈ FB }.
Ta ký hiệu FB là họ được sinh ra bởi các phép giao trong Input: Cơ sở B
B, nghĩa là, Output: B(G, M, I)
\ Begin
FB = { m0 |I ∈ 2B }
FB = {G, γ(G)} = Φ
m0 ∈I
for each m0 ∈ B do
Cho mỗi F ∈ FB , ký hiệu γ(F) ⊆ M, sao cho ∀m ⊆ if m0 = G then γ(G) = γ(G) ∪ m
γ(F), F ⊆ m0 , nghĩa là, for each m0 ∈ B do
γ(F) = {m ∈ M|F ⊆ m0 } for each F ∈ FB do
begin
Ví dụ 3. Trong ngữ cảnh của Hình 1, F0 = F ∩ m0
B = {a0 = {134}, b0 = {1, 4}, if F0 ∈
/ FB then
begin
c0 = {234}, d0 = {25}};
FB = FB ∪ F0
FB = {{12345}, {134}, {14}, {234}, {34}, end
{25}, {2}, {4}, Φ}; và γ(F0 ) = γ(F0 ) ∪ {M}
{γ(F)|F ∈ FB } = {Φ, {a}, {ab}, {c}, {d}, end
{ac}, {cd}, {abc}, {abcd}}. End
Định lý sau đây được suy ra trực tiếp từ định nghĩa trên. Định lý 3. Thuật toán 2 tính họ B = {(F, γ(F))|F ∈ FB }
48
- Lương Văn Nghĩa, Lê Văn Sơn, Huỳnh Triệu Vỹ
từ cơ sở B có độ phức tạp là O((|G| + |M|) ∗ |M| ∗ |FB |). Output: Lược đồ Hasse của B(G,M,I)
Begin
3.3. Xây dựng giàn từ B
for each F ∈ FB do
Giả sử (FB , ⊂) là thứ tự bộ phận của quan hệ bao COUNT(F) = 0
hàm giữa các tập. Cho F0 , F ∈ FB với F0 ⊂ F, ký hiệu for each F ∈ FB do
D(F0 F) = γ(F0 )\γ(F) và định nghĩa chính xác quan hệ for each m’ ∈ B\γ(F) do
bao hàm ≺ của FB như sau: begin
∀F1 , F2 ∈ (FB , ⊂), Nếu F1 ⊂ F2 , không tồn tại F’ = F ∩ m’;
F 6= F1 , F2 , sao cho F1 ⊂ F ⊂ F2 ,thì chúng ta gọi F2 COUNT(F’)++;
bao hàm chính xác F1 và viết F1 ≺ F2 . if |γ(F’)| = COUNT(F’) + |γ(F)| then
Nối (F, γ(F)) với (F’,γ(F’)).
Ví dụ 4. Từ ví dụ 2, cho F0 = Φ, F = {2}, γ(F0 ) =
end
{abcd}, γ(F) = {cd}, khi đó D(F0 , F) = {ab}. Rõ ràng
Reset COUNT;
F0 ≺ F, và chúng ta thấy rằng F\a0 = F\b0 = {2}, tổng
End
quát chúng ta có định lý sau:
Định lý 6. Thuật toán 3 có độ phức tạp là O((|G| + |M|) ∗
Định lý 4. Cho F0 , F ∈ FB với F0 ⊂ F, thì F0 ≺ F ⇔
0 0 0 0 0 |M| ∗ |FB |).
F\m1 = F\m2 với ∀m1 , m2 ∈ D(F , F).
Rõ ràng thuật toán có tổng độ phức tạp là O((|G| +
Chứng minh. Ta thấy F0 có thể được viết F0 = F ∩
|M|) ∗ |M| ∗ |FB |). Thuật toán thật sự đơn giản và hiệu quả
{m0 |m0 ∈ D(F0 , F)} khi đó,
cho việc xây dựng giàn từ cơ sở B của ngữ cảnh K.
⇒ ∀m01 , m02 ∈ D(F0 , F), giả sử F\m01 6⊂ F\m02 , suy ra
ta có F0 = F ∩ {m0 |m0 ∈ D(F0 , F)} ⊂ F00 ≡ F ∩ B1 ∈ F, 4. Kết luận
điều này mâu thuẩn với F0 ≺ F, vậy F\m01 ⊆ F\m02 . Tương Ưu điểm của các thuật toán nhanh xây dựng giàn đã đề
tự chúng ta có F\m01 ⊇ F\m02 . xuất trong bài báo này có độ phức tạp đa thức. Theo hướng
⇐ Giả sử ∃F00 , sao cho F0 ⊂ F00 ⊂ F khi đó ta có tiếp cận này, chúng ta đã rút ngắn được thời gian sinh luật
γ(F) ⊂ γ(F00 ) ⊂ γ(F0 ). Vì γ(F00 )\(F) ∈ γ(F0 )\γ(F) = kết hợp. Thay vì áp dụng thuật toán Apriori ta phải mất
D(F0 , .F), suy ra F00 = F ∩ {m0 |m0 ∈ D(F00 , F)} = F0 . nhiều thời gian cho việc tìm tập ứng viên trước khi sinh tập
0 0
Hệ quả 1. Cho F , F ∈ FB và F ⊂ F, khi đó: phổ biến và thuật toán Apriori có độ phức tạp là hàm mũ.
Trong bài báo này, chúng tôi cũng đã đưa ra một các tiếp
F0 ≺ F ⇔ F0 = F ⇔ m0 với ∀m0 ∈ D(F0 , F).
cận mới là tạo ra tập khái niệm và lược đồ Hasse tương ứng
Bây giờ chúng ta giới thiệu cách xây dựng giàn từ tập từ một ngữ cảnh hình thức cho trước trong thuật toán nhanh
khái niệm B của ngữ cảnh K. Ứng với mỗi F ∈ FB chúng ta xây dựng giàn.
tìm trong FB tất cả các bao hàm chính xác của F, nghĩa là,
∀F ∈ FB tìm {F0 ∈ FB |F0 ≺ F}. Rõ ràng F0 ∈ FB là một Tài liệu tham khảo
ứng viên nếu F0 ⊂ FvF0 được tính từ F ∩ m0 , với ∀m0 ∈
[1] Godin, R, Missaoui, R, alaui, H, Incremental Concept Formation
B\γ(F). Giả sử chúng ta đặt S = {F ∩ m0 |m0 ∈ B\γ(F)}. Algorithm Based on Galois (Concept) Lattice, Computational
Khi đó, ta có định lý sau: Itelligence, 1995, 11(2):246-267.
[2] Bernhard Ganter, Rudolf wille, Formal Concept Analysis, 1999,
Định lý 5. F0 ∈ S, F0 ≺ F nếu và chỉ nếu F0 được tìm thấy Springer-Verlag Berlin Heidelberg.
chính xác |D(F0 , F)| lần trong S. [3] Xie Zhipeng Liu Zong-Tian, A Fast Incremental Algorithm for
Building Concept Lattice, Chinese J.Computer, 2002,25(5).
Chứng minh. Từ định nghĩa của S, định lý được chứng [4] Keyun Hu, Yuchang Lu and Chunyi shi, Incremental Discovering
minh trực tiếp từ Hệ quả 1. Association Rules: A Concept Lattice Approach, PAKDD 1999:
109-113.
Thuật toán sau tính tập S và tần suất xuất hiện của các [5] Lhouari Nourine, Olivier Raynaud, A fast algorithm for building
phần tử F0 trong S (thể hiện trong COUNT(F’)). Sau đó, ứng lattice Information Processing, letters 71 (1999) 199-204.
với mỗi F0 ∈ S, kiểm tra nếu |D(F0 , F)| = COUNT(F0 ) [6] Lương Văn Nghĩa (2012), Khai phá dữ liệu theo tiếp cận tập thô nhằm
thì ta có F0 ≺ F và vẽ một cạnh nối giữa (F, γ(F)) và tìm thuộc tính hạt nhân và chọn đặc trưng trên tập cơ sở dữ liệu lớn,
Tạp chí KH&CN, ISSN 0866-7659, Đại học Phạm Văn Đồng, số (01),
(F0 , γ(F0 )). 12/2012, pp 46-54.
Thuật toán 3. Xây dựng giàn từ B. [7] Kumar A., New Techniques for Data Reduction in Database Systems
for Knowledge Discovery Applications, Journal of Intelligent
Input: B Information Systems, 10(1), 31-48, 2005.
(BBT nhận bài: 22/12/2013, phản biện xong: 07/01/2014)
49
nguon tai.lieu . vn
