Giới thiệu khai phá mẫu phổ biến, luật kết hợp
Khái niệm về khai phá mẫu phổ biến
A frequent pattern refers to itemsets, itemlists, subsequences, or substructures that appear commonly within a dataset.
Agrawal, Imielinski, Swami – 1993 – trong ngữ cảnh bài toán tập phổ biến và luật kết hợp
Sữa và bánh mì là hai mặt hàng thường xuyên xuất hiện cùng nhau trong các tập dữ liệu giao dịch, cho thấy chúng là những sản phẩm phổ biến mà người tiêu dùng thường mua kết hợp.
Khách hàng thường bắt đầu bằng việc mua một máy tính PC, tiếp theo là một máy quay kỹ thuật số, và sau đó là một thẻ nhớ Khi những giao dịch này xuất hiện thường xuyên trong cơ sở dữ liệu lịch sử bán hàng, chúng được gọi là mẫu dãy phổ biến (frequent sequential pattern).
Các cấu trúc như đồ thị con, cây con và mắt xích con có thể kết hợp với các tập mục hoặc dãy con Khi một cấu trúc con xuất hiện thường xuyên, nó được gọi là mẫu cấu trúc phổ biến.
2.1.2 Ý nghĩa của khai phá mẫu phổ biến
Tìm kiếm mẫu phổ biến là một yếu tố quan trọng trong khai phá luật kết hợp, giúp phát hiện mối tương quan và các mối quan hệ trong cơ sở dữ liệu Nó không chỉ hỗ trợ phân lớp và phân cụm dữ liệu mà còn nâng cao hiệu quả của các nhiệm vụ khai phá dữ liệu Vì vậy, khai phá mẫu phổ biến đã trở thành một nhiệm vụ thiết yếu trong lĩnh vực này.
Chủ đề về khai phá mẫu phổ biến rất phong phú và rộng lớn Các lĩnh vực nghiên cứu chú trọng đến mốt số vấn đề như sau:
Để tìm thấy các tập mục phổ biến trong một cơ sở dữ liệu lớn, bạn cần áp dụng các phương pháp phân tích dữ liệu hiệu quả Đầu tiên, hãy xác định loại dữ liệu mà bạn đang làm việc, có thể là dữ liệu giao dịch hoặc dữ liệu quan hệ Sau đó, sử dụng các thuật toán khai thác dữ liệu như Apriori hoặc FP-Growth để phát hiện các mẫu thường xuyên Cuối cùng, việc tối ưu hóa truy vấn và sử dụng các công cụ phân tích dữ liệu mạnh mẽ sẽ giúp bạn nhanh chóng nhận diện các tập mục phổ biến trong cơ sở dữ liệu của mình.
Làm thế nào để có thể khai phá được các luật kết hợp trong không gian đa mức và đa chiều?
Những luật kết hợp nào là phù hợp nhất?
Để chỉ ra các thuật toán và phương pháp KPDL hiệu quả trong việc phát hiện các luật kết hợp và mối tương quan giữa các mục dữ liệu, cần xác định các tiêu chí phù hợp Điều này sẽ tạo nền tảng vững chắc cho việc mở rộng các hình thức khai thác mẫu phổ biến trong tương lai.
Phân tích giỏ hàng thương mại trong cơ sở dữ liệu giao dịch lịch sử bán hàng tại siêu thị là một ví dụ điển hình về khai phá mẫu Việc phát hiện mối tương quan trong các bản ghi giao dịch hàng ngày hỗ trợ doanh nghiệp trong quá trình ra quyết định, từ thiết kế mẫu hàng hóa đến tiếp thị chéo và phân tích thói quen mua sắm của khách hàng Khám phá các mối quan hệ này giúp các nhà bán lẻ phát triển chiến lược tiếp thị hiệu quả bằng cách hiểu rõ hơn về các danh mục mặt hàng mà khách hàng thường xuyên mua.
Để xác định khả năng khách hàng mua bánh mì khi họ đã chọn mua sữa tại siêu thị, các nhà bán lẻ có thể sử dụng thông tin này để tối ưu hóa doanh thu Việc tiếp thị các sản phẩm một cách chọn lọc và sắp xếp chúng ở vị trí hợp lý sẽ giúp tăng cường trải nghiệm mua sắm và khuyến khích khách hàng mua thêm.
Là giám đốc siêu thị, việc hiểu thói quen mua sắm của khách hàng là rất quan trọng Bạn cần phân tích giỏ hàng từ dữ liệu bán lẻ để xác định những mặt hàng thường được mua cùng nhau Kết quả phân tích này có thể giúp bạn xây dựng kế hoạch marketing, quảng cáo hoặc thiết kế catalog mới Ngoài ra, việc bố trí hàng hóa hợp lý tại quầy hàng cũng rất cần thiết; các mặt hàng thường mua chung nên được đặt gần nhau để khuyến khích khách hàng mua sắm nhiều hơn Ví dụ, nếu khách hàng mua máy giặt, họ cũng có thể quan tâm đến bột giặt, vì vậy việc đặt bột giặt gần máy giặt sẽ tăng doanh số cho cả hai sản phẩm.
Khai phá mẫu phổ biến là quá trình khám phá các mối quan hệ tuần hoàn và lặp lại trong cơ sở dữ liệu.
Khách hàng mua máy giặt thường có xu hướng mua xà phòng giặt máy cùng lúc, điều này được thể hiện qua luật kết hợp trong hành vi tiêu dùng.
Độ hỗ trợ và độ tin cậy là hai chỉ số quan trọng trong việc phân tích luật khai phá dữ liệu Độ hỗ trợ 2% cho thấy 2% trong tổng số giao dịch có sự kết hợp giữa máy giặt và xà phòng giặt Trong khi đó, độ tin cậy 60% cho thấy rằng khi khách hàng mua máy giặt, có 60% khả năng họ cũng sẽ mua xà phòng giặt Các luật kết hợp thường được xem xét khi đáp ứng cả ngưỡng hỗ trợ tối thiểu và ngưỡng tin cậy tối thiểu.
Tổng quan về luật kết hợp
2.2.1 Khái niệm luật kết hợp Để đơn giản hóa, chúng ta có thể hiểu luật kết hợp như sau: luật kết hợp là luật chỉ ra mối quan hệ của hai hay nhiều đối tượng (đối tượng chúng ta đang xét ở đây là các mặt hàng)
Cấu trúc của luật như sau: X=>Y (sup, conf) Có nghĩa là luật có X thì kéo theo Y với độ hỗ trợ sup và độ tin cậy conf
- sup= support (độ hỗ trợ): là tỉ lệ giao dịch chứa cả hai mặt hàng X và Y trên tổng số giao dịch
- conf= confidence (độ tin cậy): là tỉ lệ giao dịch chứa mặt hàng Y trong các giao dịch chứa mặt hàng X
Nếu nhìn nhận luật kết hợp theo lý thuyết tập hợp thì chúng ta có thể định nghĩa như sau:
Tập hợp I = {i1, i2, …, ik} đại diện cho "tất cả các mặt hàng", trong khi D là cơ sở dữ liệu giao dịch chứa danh sách các mặt hàng trong phiếu mua hàng của khách hàng Mỗi giao dịch T được định nghĩa là một tập con của I, thể hiện các mặt hàng mà khách hàng đã mua.
I Mỗi giao dịch T có một định danh là TID X là một tập mục X I và T là một giao dịch: Gọi T chứa X nếu X T Gọi XY là một “luật kết hợp” nếu X I, Y
Kí hiệu support(X) (hoặc sup(X), s(X)) là tỷ lệ phần trăm của các giao dịch hỗ trợ X trên tổng các giao dịch trong D, nghĩa là:
Tập mục X có P(X) s>0 (với s cho trước) được gọi là tập phổ biến (frequent set)
Luật kết hợp XY có độ hỗ trợ (support) s trong CSDL giao dịch D nếu trong
D có s% các giao dịch T chứa XY: chính là xác suất P(XY)
Luật kết hợp XY có độ tin cậy (confidence) c trong CSDL D nếu như trong
D có c% các giao dịch T chứa X thì cũng chứa Y: chính là xác suất P(X|Y) Confidence (XY) = P(X|Y) : 1 c (XY) 0 (3)
Luật XY được coi là đảm bảo độ hỗ trợ s trong tập dữ liệu D nếu s(XY) đạt ít nhất giá trị s Tương tự, luật này được xem là đảm bảo độ tin cậy c trong D nếu c(XY) đạt tối thiểu giá trị c Những luật thỏa mãn cả hai ngưỡng hỗ trợ tối thiểu (min_sup) và ngưỡng tin cậy tối thiểu (min_conf) được gọi là luật mạnh Độ hỗ trợ và độ tin cậy có giá trị từ 0% đến 100% hoặc từ 0.0 đến 1.0, với các giá trị min_sup và min_conf được xác định bởi người dùng hoặc chuyên gia.
Công thức (3) có thể được viết lại như sau:
Độ tin cậy của luật XY có thể được xác định dễ dàng từ độ hỗ trợ của X và X∪Y Do đó, quá trình khai phá luật kết hợp cần được thực hiện qua hai bước.
Bước đầu tiên là xác định tất cả các tập mục có độ hỗ trợ lớn hơn mức hỗ trợ tối thiểu mà người dùng đã chỉ định Những tập mục đạt yêu cầu về độ hỗ trợ tối thiểu này được gọi là các tập mục phổ biến.
Bước 2: Tạo ra các luật liên kết mạnh từ các tập mục phổ biến để sinh ra các luật mong muốn Cụ thể, nếu xem XYZW và XY là các tập mục phổ biến, chúng ta có thể xác định luật liên kết XY => ZW với tỷ lệ độ tin cậy cao.
Sup XYZW conf Sup XY (5)
Nếu conf ≥ min_conf thì luật được giữ lại (luật này sẽ thoả mãn độ hỗ trợ tối thiểu vì XYZW là phổ biến)
Ví dụ, minh họa bài toán khai phá mẫu phổ biến tìm luật kết hợp
Cho tập mục I= {A,B,C,D,E,F} gồm 6 mục Xét cơ sở giao dịch D với các giao dịch có định danh TID ở bảng dưới đây (Giả sử min_sup = 50%, min_conf = 50%)
TID Các mục hàng trong giỏ
Hình 2.1: Cơ sở dữ liệu giao dịch D
Duyệt cơ sở dữ liệu, dựa vào tần suất xuất hiện của các tập mục trong các giao dịch từ
Từ ngày 01 đến 04, chúng tôi đã xác định được các tập mục phổ biến có độ hỗ trợ đạt yêu cầu min_sup, trong khi các tập mục có độ hỗ trợ thấp hơn min_sup sẽ bị loại bỏ.
Tập các mục Tần suất xuất hiện Độ hỗ trợ (Support)
Hình 2.2: Tần xuất xuất hiện và độ hỗ trợ của các tập mục phổ biến
Luật A C, ta có độ tin cậy và độ hỗ trợ lần lượt thỏa mãn min_sup và min_conf nên luật này là luật mạnh:
Luật CA, ta có độ tin cậy và độ hỗ trợ lần lượt thỏa mãn min_sup và min_conf nên luật này là luật mạnh:
2.2.2 Giải thuật Apriori để sinh các luật kết hợp
Phương pháp Apriori áp dụng kỹ thuật đệ quy để phát hiện luật kết hợp, trong đó k-itemset được sử dụng để tìm kiếm (k+1)-itemsets Đầu tiên, tập 1-itemsets được xác định bằng cách duyệt qua cơ sở dữ liệu để đếm số lần xuất hiện của các mục, từ đó chọn ra những mục đáp ứng tiêu chí độ hỗ trợ tối thiểu (min-sup) Kết quả này được biểu diễn qua tập F1.
F 1 được dùng để tìm F 2 (có hai tập mục phổ biến), rồi sử dụng F 2 để tìm F 3 (3- itemset) và tiếp tục cho đến khi không có k-itemset được tìm thấy
Tính chất Apriori cho rằng mọi tập con không rỗng của một tập mục phổ biến cũng phải được coi là phổ biến Chẳng hạn, nếu tập mục {bia, bỉm, hạnh nhân} được xác định là phổ biến, thì tập con {bia, bỉm} cũng sẽ là phổ biến Điều này có nghĩa là mọi giao dịch chứa {bia, bỉm, hạnh nhân} cũng sẽ tự động chứa tập con {bia, bỉm}.
Thuật toán được thực hiện qua hai bước cơ bản, bao gồm bước kết nối (join) và bước cắt tỉa (prune)
- Bước kết nối (join): Tìm tập mục phổ biến L k từ tập ứng viên C k
Tập ứng viên C k được tạo ra bằng cách kết nối L k-1 với chính nó, trong đó l 1 và l 2 là các tập mục thuộc L k-1 Ký hiệu li[j] thể hiện tập mục thứ j trong tập mục li Theo quy ước của Apriori, các mục trong một giao dịch được sắp xếp theo thứ tự từ điển, với (k-1)-tập mục l i có thứ tự li[1] < l i [2] < < l i [k-1] Việc kết nối L k-1 với L k-1 được thực hiện bằng cách kết hợp các thành phần của L k-1 nếu (k-2) mục đầu tiên giống nhau Cụ thể, l 1 và l 2 của L k-1 sẽ được kết hợp nếu l 1 [1] < l 2 [1] và l 1 [k-1] < l 2 [k-1], nhằm đảm bảo không có trùng lặp Tập mục kết hợp được hình thành từ l 1 và l 2 theo thứ tự l 1 [1], l 1 [2],
Bước tỉa (prune) là quá trình giảm kích thước tập ứng viên C k, trong đó C k là tập cha L k với các thành viên có thể chứa k mục Việc duyệt cơ sở dữ liệu để xác định số lượng ứng viên trong C k có thể gây khó khăn do số lượng lớn ứng viên Để tối ưu hóa, tính chất Apriori được áp dụng: nếu bất kỳ tập con nào có kích thước (k-1) không phổ biến, thì nó không thể là tập con của tập k mục phổ biến, do đó có thể loại bỏ khỏi C k Việc kiểm tra tính phổ biến của tập con này có thể thực hiện nhanh chóng bằng cách duy trì một cây băm của tất cả các mục phổ biến.
2.2.3 Mô tả thuật toán Apriori dưới dạng giả mã Đầu vào:
- Cơ sở dữ liệu giao dịch D = {t|t : giao dịch}
- Độ hỗ trợ tối thiểu min_sup > 0 Đầu ra: Tập hợp tất cả các tập phổ biến
(1) F 1 = {tất cả các tập mục phổ biến có độ dài bằng 1};
(3) C k = Apriori-gen (F k-1 ); //Sinh mọi ứng viên có độ dài k
(4) For ( mỗi giao dịch t D) { // quét CSDL D để đếm
(5) C t = ( c C k | c t); //tất cả các ứng viên c thuộc C k với c là tập con của giao dịch t
(8) } // kết thúc lặp các giao dịch t D
Thuật toán Apriori là một phương pháp quan trọng trong khai thác dữ liệu, bắt đầu bằng việc xác định các tập mục phổ biến F1 có độ dài 1 Từ bước 2 đến bước 10, thuật toán sử dụng Fk-1 để tạo ra các ứng viên Ck nhằm tìm kiếm các tập mục phổ biến Lk với k ≥ 2 Thủ tục Apriori_gen giúp sinh các ứng viên và loại trừ các tập con không phổ biến theo tính chất Apriori Sau khi sinh ra tất cả các ứng viên, cơ sở dữ liệu sẽ được quét để kiểm tra từng giao dịch, sử dụng hàm con để tìm tất cả các tập con ứng cử Số lượng ứng viên cho mỗi giao dịch được tính toán, và những ứng viên đạt độ hỗ trợ tối thiểu sẽ được xác định để tạo thành tập mục phổ biến Cuối cùng, thủ tục được gọi để sinh ra các luật kết hợp từ tập mục phổ biến này.
Thủ tục Apriori_gen thực hiện hai bước chính: kết nối và cắt tỉa Trong bước kết nối, F k-1 được kết nối với F k-1 để tạo ra các ứng viên tiềm năng (từ bước 1 đến bước 4) Tiếp theo, trong bước cắt tỉa (từ bước 5 đến bước 7), tính chất Apriori được áp dụng để loại bỏ các ứng viên có tập con không phổ biến Để kiểm tra các tập con không phổ biến, thủ tục has_infrequent_subset được sử dụng.
Procedure Apriori_gen (F k-1 : tập mục phổ biến có độ dài k-1)
(4) c = l 1 ⋈ l 2 ; // bước kết nối: sinh ứng viên
(5) If has_infrequent_subset (c, F k-1 ) then
(6) delete c; //bước tỉa: loại bỏ các ứng viên không có lợi
Procedure has_infrequent_subset (c: ứng viên, F k-1 : t ập các tập phổ biến có độ dài (k-1));
(1) For (mỗi (k-1) – tập con s của c)
2.2.4 Ví dụ minh họa thuật toán Apriori
Xét CSDL giao dịch D được cho trong bảng sau:
Bao gồm 9 giao dịch với độ hỗ trợ tối thiểu là 2, nghĩa là min_sup = 2/9 = 22 %, độ tin cậy tối thiểu là 70%
TID Danh sách các mục
Hình 2.3: CSDL sử dụng minh hoạ thuật toán Apriori
Trong lần lặp đầu tiên của thuật toán, mỗi mục được xem là một ứng viên thuộc tập ứng viên C1 (gồm 1 mục) Thuật toán sẽ quét toàn bộ các giao dịch trong tập D để đếm số lần xuất hiện của từng mục.
Giả sử độ hỗ trợ cực tiểu được xác định là Minsup = 22% Tập mục phổ biến 1-Itemset (F1) bao gồm tất cả các ứng viên thuộc C1 thỏa mãn điều kiện độ hỗ trợ tối thiểu Trong trường hợp này, tất cả các ứng viên trong C1 đều vượt qua ngưỡng hỗ trợ tối thiểu, với giá trị lớn hơn 2.
Hình 2.4: Duyệt CSDL tìm các tập mục phổ biến 1-Itemset (F 1 )
Tìm ra các tập mục phổ biến 2-Itemset (F 2 ), thuật toán sử dụng kết nối F 1 với
Lưu trữ dữ liệu lớn dựa trên Oracle DBMS
Giới thiệu hệ quản trị CSDL Oracle
Các công ty viễn thông xử lý khối lượng lớn dữ liệu khách hàng và chi tiết cuộc gọi, do đó, việc sử dụng CSDL Oracle là giải pháp tối ưu để lưu trữ và quản lý hiệu quả lượng dữ liệu khổng lồ này.
Oracle cung cấp một bộ sản phẩm toàn diện cho việc xây dựng ứng dụng, cùng với các giải pháp công nghệ thông tin tối ưu cho người dùng cuối Các ứng dụng của Oracle tương thích với nhiều hệ điều hành, từ máy tính cá nhân đến các hệ thống xử lý song song quy mô lớn.
Oracle cung cấp hệ quản trị cơ sở dữ liệu linh hoạt, Oracle Server, để lưu trữ và quản lý thông tin cho các ứng dụng Hệ quản trị này bao gồm nhiều sản phẩm và công cụ tích hợp, giúp tối ưu hóa quy trình quản lý dữ liệu.
1 SQL: Là ngôn ngữ dùng để truy xuất cơ sở dữ liệu quan hệ, kể cả Oracle Có thể được dùng với mỗi công cụ Oracle khi có yêu cầu truy xuất dữ liệu
2 PL/SQL: Là ngôn ngữ thủ tục Oracle để viết các ứng dụng xử lý và thao tác dữ liệu bên ngoài CSDL Có thể bao gồm một tập con các lệnh SQL khi có yêu cầu truy xuất dữ liệu Sẵn có trong Oracle Server
3 Thủ tục lưu trữ (Stored procedures): Là các hàm hay các thủ tục, đây là một tập hợp các câu lệnh SQL và PL/SQL Sau khi Stored procedures được biên dịch, nó sẽ được gán tên và có thể thực hiện trực tiếp mà không cần phải biên dịch lại thêm bất cứ một lần nào nữa Các functions và procedures cho phép sử dụng tham số dưới dạng tham số vào (IN) và tham số ra (OUT) hoặc cũng có thể sử dụng tham số vừa vào vừa ra (IN OUT) Theo mặc định, các tham số được xác định ở chế độ vào IN Một số ưu điểm của hệ quản trị CSDL quan hệ là: a Các Stored procedures được nạp sẵn vào bộ nhớ, do đó có thể giảm bớt việc truy xuất đĩa khi thực hiện thủ tục b Đảm bảo an toàn cho dữ liệu, ngăn không cho các users truy cập trực tiếp vào dữ liệu mà phải thông qua các thủ tục và hàm giao tiếp đã được cung cấp c Cho phép nhiều users có thể cùng sử dụng các bản sao của Stored
4 Packages chuẩn: Một packages thông thường gồm hai phần: specification (phần đặc tả hay còn gọi là phần khai báo) và body (phần thân) Chúng được lưu riêng biệt trong cùng một database a Phần specification là phần giao tiếp với các ứng dụng Phần này chứa các lời khai báo, các kiểu, biến, hằng, exceptions, cursors, và các khai báo hàm để sử dụng b Phần body là phần cài đặt cụ thể (implementation) của các khai báo trong phần specification
Chức năng của packages tương tự như Stored procedures, cho phép nhiều ứng dụng khác nhau sử dụng chúng sau khi đã được biên dịch Một lợi ích lớn nhất của việc sử dụng packages là khi được gọi lần đầu tiên, toàn bộ package sẽ được nạp vào bộ nhớ, giúp cải thiện hiệu suất và tiết kiệm thời gian xử lý.
5 Index (chỉ mục): Index của Bảng được tạo ra nhằm tăng tốc độ truy xuất, tăng hiệu quả của tính duy nhất trên một hoặc một tập của cột
6 Table partitioning (Phân khu trong bảng dữ liệu): Kỹ thuật phân chia bảng thành từng khu (Table partitioning) nhằm quản lý hiệu quả cơ sở dữ liệu với dung lượng lớn và các bảng trong CSDL có số lượng truy cập lớn và đồng thời với các mục đích: a Khi một câu lệnh chỉ cần lấy dữ liệu ở một khu nào đó thì hệ thống chỉ cần truy nhập vào khu đó và bỏ qua các khu còn lại b Khi các khu dữ liệu được lưu trữ ở các ổ cứng khác nhau sẽ làm giảm tranh chấp vào/ra giữa các câu lệnh Ví dụ hai câu lệnh SELECT và UPDATE hoạt động trên cùng một bảng nhưng ở hai khu khác nhau có thể thực hiện hoàn toàn song song với nhau
7 Câu lệnh SQL tĩnh (Static SQL): Câu lệnh SQL không thay đổi hay nói cách khác là đã được định nghĩa trước khi chạy, toàn bộ câu lệnh SQL tĩnh là được nhận biết khi biên dịch, nó sẽ có nhiều ích lợi như: a Sự biên dịch thành công sẽ xác minh rằng các câu lênh SQL đã tham chiếu đến các đối tượng hợp lệ trong CSDL Ví dụ, câu lệnh SQL truy vấn dữ liệu từ một bảng chắc chắn tồn tại trong cơ sở dữ liệu b Xác minh quyền có thể truy cập vào các đối tượng cơ sở dữ liệu c Hiệu suất thực hiện của các câu lệnh SQL tĩnh nói chung là tốt hơn so với SQL động
8 SQL động (Dynamic SQL): Cho phép viết các chương trình sử dụng các câu lệnh SQL, toàn bộ đoạn lệnh chương trình sẽ không được nhận biết cho đến trước khi chạy Bởi vì những lợi thế này, bạn nên sử dụng SQL động chỉ khi bạn không thể sử dụng SQL tĩnh để hoàn thành mục tiêu của bạn, hoặc nếu sử dụng SQL tĩnh là cồng kềnh so với SQL động
SQL tĩnh có những hạn chế mà SQL động có thể khắc phục Đôi khi, bạn không thể biết toàn bộ câu lệnh SQL cần thực hiện trong một thủ tục PL/SQL Chương trình của bạn có thể nhận đầu vào là các câu lệnh SQL do người dùng định nghĩa, hoặc các câu lệnh này có thể thay đổi tùy thuộc vào kết quả của một tiến trình khác hoặc các tham số đầu vào Trong những tình huống như vậy, việc sử dụng SQL động là lựa chọn hợp lý.
Phương pháp tiếp cận và kiến trúc
Bài viết trình bày một hệ thống KPDL trên cơ sở dữ liệu quan hệ Oracle, sử dụng các truy vấn SQL và hàm do người dùng định nghĩa Luận văn sẽ chứng minh rằng quan điểm "SQL không hiệu quả hoặc không đầy đủ cho khai phá dữ liệu" là sai lầm Mục tiêu chính là khám phá những vấn đề phát sinh khi tích hợp cơ sở dữ liệu vào quá trình khai phá dữ liệu.
Hiện nay, thị trường có nhiều công cụ khai thác dữ liệu thương mại như IBM's Intelligent Miner, DBMiner và Oracle Data Mining, giúp cung cấp kiến thức từ dữ liệu lớn trên cơ sở dữ liệu quan hệ Mặc dù các công cụ này rất hiệu quả, nhưng chúng thường được phát triển cho các hệ quản trị cơ sở dữ liệu cụ thể.
Với sự gia tăng sử dụng hệ quản trị CSDL quan hệ, việc khai thác dữ liệu trực tiếp trên hệ thống này mang lại lợi ích từ nhiều thập kỷ nghiên cứu trong lĩnh vực quản lý dữ liệu Mặc dù bộ nhớ chính có giới hạn về kích thước dữ liệu, nhưng hệ quản trị CSDL quan hệ cho phép sử dụng các hệ thống quản lý bộ đệm, giúp người dùng không phải lo lắng về kích thước dữ liệu Việc xây dựng thuật toán khai thác dữ liệu trên hệ quản trị CSDL quan hệ còn giúp xử lý các tập dữ liệu lớn, vì hệ thống này được thiết kế để quản lý khối lượng dữ liệu khổng lồ.
Các file được sử dụng cho các thuật toán khai phá dữ liệu thường không nằm trong cơ sở dữ liệu và có giới hạn về số lượng giao dịch có thể khai thác Chẳng hạn, DBMiner chỉ có thể xử lý tối đa 64K giao dịch Người dùng có thể lựa chọn hệ quản trị cơ sở dữ liệu (CSDL) quan hệ cho ứng dụng của mình, nhưng các thuật toán khai phá cần phải tuân thủ các tiêu chuẩn đã được công nhận để đảm bảo tính linh hoạt trong việc chuyển đổi giữa các hệ quản trị CSDL khác nhau Vì vậy, luận văn này sẽ tập trung vào việc áp dụng tiêu chuẩn SQL-92 và các hàm định nghĩa người dùng (UDFs) do hệ quản trị CSDL Oracle cung cấp để khai phá luật kết hợp.
Với xu hướng KPDL trên các kho dữ liệu lớn, chúng tôi đề xuất một phương pháp hiệu quả chỉ cần quét cơ sở dữ liệu giao dịch một lần để tạo ra tất cả các luật phù hợp, trái ngược với thuật toán Apriori chuẩn yêu cầu quét lặp lại nhiều lần, dẫn đến tăng cường truy cập vào/ra, đặc biệt khi xử lý các bộ dữ liệu ứng cử viên lớn Ngôn ngữ PL/SQL đã được tích hợp hoàn toàn với cơ sở dữ liệu.
Tính toàn vẹn dữ liệu trong cấu trúc dữ liệu cho phép lưu trữ các tập phổ biến đầy đủ trong bảng quan hệ, giúp tăng tốc độ truy cập đến các phần tử thông qua các truy vấn trong PL/SQL Các thí nghiệm cho thấy, thuật toán được triển khai trong PL/SQL có khả năng giải quyết vấn đề kích thước lớn mà thuật toán Apriori truyền thống gặp phải, đặc biệt khi khối lượng giao dịch và dữ liệu gia tăng.
Sau khi quét toàn bộ cơ sở dữ liệu, các tập phổ biến thích hợp được tổ chức trong một cây tập phổ biến đầy đủ Kết quả thu được được hiển thị ở bên trái hình dưới đây, với cây tập phổ biến đầy đủ bao gồm năm tập mục: „a‟, „b‟, „c‟.
„d‟ và „e‟ trong cơ sở dữ liệu D là một ví dụ điển hình
Tổ chức các bộ đếm trong cây tập phổ biến giúp lưu trữ hiệu quả và tiết kiệm bộ nhớ, đồng thời hỗ trợ việc tạo ra các luật kết hợp Hình ảnh minh họa cho thấy một dãy thuộc tính biểu thị số lượng của các tập phổ biến, được xác định qua việc đếm các tập trong cơ sở dữ liệu Các tập không phổ biến, được khoanh tròn, sẽ bị loại bỏ vì không đạt yêu cầu về độ hỗ trợ tối thiểu.
Hình 3.1: Bảng dữ liệu quan hệ lưu giữ số lượng các tập mục
Chúng ta sẽ tạo ra các bảng với các thuộc tính đa dạng để lưu trữ thông tin và đếm số lượng các mục trong cơ sở dữ liệu (CSDL), thông qua việc thống kê số lượng mục có trong CSDL.
- Dữ liệu gốc và dữ liệu tiền xử lý đều được lưu giữ trong các bảng dữ liệu quan hệ của CSDL ORACLE
Các thủ tục và hàm thực thi thuật toán khai thác dữ liệu được lập trình bằng ngôn ngữ PL/SQL và lưu trữ trong cơ sở dữ liệu Người dùng sẽ sử dụng các thủ tục hoặc hàm này để thực hiện các chương trình khai phá dữ liệu mà không cần truy cập trực tiếp vào dữ liệu, với các tham số được truyền vào.
Giới hạn trong CSDL Oracle
Oracle cung cấp thông tin về giới hạn số cột và số dòng trong bảng, giúp người dùng dễ dàng đánh giá bài toán, lựa chọn thuật toán và thiết kế chương trình Dưới đây là một số giới hạn quan trọng trong cơ sở dữ liệu Oracle.
Số indexs Tối đa trên một bảng Không giới hạn
Số cột Trên một bảng 1000 cột
Số cột Trên một indexs 32 cột
Số cột Trên một phân khu 16 cột
Số dòng Trên một bảng Không giới hạn
Số bảng Trên một CSDL Không giới hạn
Hình 3.3: Giới hạn trong CSDL Oracle
Phân tích Luật kết hợp dựa trên Cơ Sở Dữ Liệu Oracle
Đặc tả bài toán
Dữ liệu đầu vào được cấu trúc dưới dạng một bảng gồm hai cột: cột đầu tiên là định danh giao dịch (tid) và cột thứ hai là danh mục mặt hàng (item) Trong trường hợp một giao dịch chứa nhiều mặt hàng, bảng giao dịch sẽ có nhiều dòng dữ liệu với cùng giá trị trong cột tid nhưng khác nhau trong cột mặt hàng.
Một tùy chọn để chuyển đổi cấu trúc bảng dữ liệu giao dịch là sử dụng định dạng bảng bình thường với nhiều cột, trong đó một cột là tid và các cột còn lại là các mặt hàng (items) Đối với những giao dịch có số lượng lớn mặt hàng, định dạng này sẽ có danh sách hữu hạn các mặt hàng, phản ánh số lượng thực tế của chúng trong giao dịch Lựa chọn cách này được đưa ra vì hai lý do chính.
1 Đầu tiên là chúng ta không biết số lượng của các mục trong mỗi giao dịch
2 Ngoài ra cơ sở dữ liệu hiện tại trên thị trường có thể chỉ hỗ trợ số lượng nhất định các cột cho một bảng Nếu một trường hợp phát sinh trong đó có số lượng mặt hàng trong một giao dịch hơn mức cho phép của các cơ sở dữ liệu cơ bản, không có cách nào chúng ta có thể quản lý chính xác của dữ liệu Cũng sẽ có rất nhiều các giá trị null trong các hàng, các item không được sử dụng trong tất cả các giao dịch
Dữ liệu ra được trình bày dưới dạng bảng có tên là RULES, chứa các bộ quy tắc kết hợp Để xác định số lượng cột trong bảng, chúng ta sử dụng độ dài tối đa của các luật kết hợp, với điều kiện mỗi luật phải có ít mặt hàng hơn số lượng cột Các cột bổ sung cho luật kết hợp sẽ được gán giá trị 0 Cấu trúc của bảng RULES bao gồm các cột item 1, item 2, …, itemk, nullm, rulem, confidence và support, trong đó k là độ dài của tập phổ biến lớn nhất Cột nullm chứa giá trị 0 đầu tiên, rulem xác định vị trí của dấu "=>", trong khi confidence và support lần lượt biểu thị độ tin cậy và độ hỗ trợ của luật kết hợp.
Sinh tập các ứng viên
4.2.1 Thực hiện phép nối giữa tập mục phổ biển F k
Thuật toán Apriori, được trình bày trong chương 2, cho phép sinh tập ứng viên có độ dài k (C k ) từ tất cả các tập mục phổ biến có độ dài k-1 (F k-1 ) Tập F k-1 bao gồm k-1 cột: Item 1, Item 2, …, Item k-1, với các giá trị của tập mục phổ biến được sắp xếp theo thứ tự tăng dần.
Hình 4.2: Thực hiện phép nối giữa tập mục phổ biến Fk
Ví dụ, Tập mục phổ biến có độ dài k=3,
F3: {{1, 2, 3}, {1, 2, 4}, {1, 3, 4}, {1, 3, 5}, {2, 3, 4}}, ta sẽ có được tập các ứng viên có độ dài k = 4 như sau: C4: {1, 2, 3, 4}, and {1, 3, 4, 5}
4.2.2 Thực hiện bước tỉa loại bỏ ứng viên không có lợi
Bước tiếp theo trong quá trình lọc ứng viên là tỉa để loại bỏ những ứng viên không có lợi Các tập con có độ dài (k-1) từ tập ứng viên C k sẽ bị xóa nếu chúng không tồn tại trong các tập mục phổ biến có độ dài k-1 (F k-1) Chúng ta áp dụng phương pháp K-way join để thực hiện quy trình này, dựa trên các giá trị của tập mục phổ biến được sắp xếp theo thứ tự tăng dần Tất cả các tập con của tập phổ biến phải đều phổ biến, và các tập con có độ dài k-1 sẽ xác nhận cho các tập phổ biến có độ dài k Quá trình này bao gồm việc thêm phép kết nối với điều kiện để xác nhận cho từng cột (item) một cách lần lượt, bắt đầu từ việc kiểm tra item1.
F k-1 như trong phép kết nối với I3 được thể hiện ở hình bên dưới Một phép kết nối với
I r (3
