MỞ ĐẦU Trong những năm gần đây, việc nắm bắt được thông tin được coi là cơ sở của mọi hoạt động sản xuất, kinh doanh. Cá nhân hoặc tổ chức nào thu thập và hiểu được thông tin, và hành động dựa trên các thông tin được kết xuất từ các thông tin đã có sẽ đạt được thành công trong mọi hoạt động. Chính vì lý do đó, việc tạo ra thông tin, tổ chức lưu trữ và khai thác ngày càng trở nên quan trọng và gia tăng không ngừng. Sự tăng trưởng vượt bậc của các cơ sở dữ liệu (CSDL) trong cuộc sống như: thương mại, quản lý và khoa học đã làm nảy sinh và thúc đẩy sự phát triển của kỹ thuật thu thập, lưu trữ, phân tích và khai phá dữ liệu… không chỉ bằng các phép toán đơn giản thông thường như: phép đếm, thống kê… mà đòi hỏi cách xử lý thông minh hơn, hiệu quả hơn.
Từ đó các nhà quản lý có được thông tin có ích để tác động lại quá trình sản xuất, kinh doanh của mình… đó là tri thức. Các kỹ thuật cho phép ta khai thác được tri thức hữu dụng từ CSDL (lớn) được gọi là các kỹ thuật khai phá dữ liệu (DM – Data Mining). Khai phá luật kết hợp là một nội dung quan trọng trong khai phá dữ liệu. Luận văn tìm hiểu về luật kết hợp và ứng dụng một số thuật toán khai phá luật kết hợp trong CSDL lớn từ đó áp dụng kỹ thuật khai phá dữ liệu vào hệ thống cơ sở dữ liệu hàng hóa vận chuyển tại công ty STC Việt Nam nhằm phát hiện ra xu hướng về các điều khoản trong giao nhận vận tải(Incoterm) được lựa chọn theo từng khu vực, quốc gia.
8 z CHƢƠNG 1: NGHIÊN CỨU MỘT SỐ VẤN ĐỀ VỀ LUẬT KẾT HỢP Việc dự đoán các thông tin có giá trị cao dựa trên số lượng dữ liệu lớn về nghiệp vụ càng ngày càng trở lên quan trọng đối với nhiều tổ chức, doanh nghiệp. Chẳng hạn, những vấn đề các nhà quản lí và kinh doanh cần biết là các kiểu mẫu hành vi mua hàng của các khách hàng, xu hướng kinh doanh, vv…. Những thông tin này có thể học được từ những dữ liệu có sẵn. Một trong những vấn đề khó khăn nhất trong việc khai phá dữ liệu trong CSDL là có một số vô cùng lớn dữ liệu cần được xử lý.
Các tổ chức doanh nghiệp quy mô vừa có thể có từ hàng trăm Megabyte đến vài Gigabyte dữ liệu thu thập được. Các ứng dụng khai phá dữ liệu thường thực hiện phân tích dữ liệu khá phức tạp, mất nhiều thời gian trong toàn bộ CSDL. Vì vậy, tìm một thuật toán nhanh và hiệu quả để xử lý khối lượng dữ liệu lớn là một thách thức lớn. Chương này trình bày cơ sở lý thuyết của luật và luật kết hợp, khai phá dữ liệu dựa vào luật kết hợp, đồng thời trình bày một số thuật toán liên quan đến luật kết hợp.
Lý thuyết về luật kết hợp Từ khi nó được giới thiệu từ năm 1993, bài toán khai thác luật kết hợp nhận được rất nhiều sự quan tâm của nhiều nhà khoa học. Ngày nay việc khai thác các luật như thế vẫn là một trong những phương pháp khai thác mẫu phổ biến nhất trong việc khám phá tri thức và khai thác dữ liệu (KDD: Knowledge Discovery and Data Mining). Một cách ngắn gọn, một luật kết hợp là một biểu thức có dạng: X Y , trong đó X và Y là tập các trường gọi là item. Ý nghĩa của các luật kết hợp khá dễ nhận thấy: Cho trước một cơ sở dữ liệu có D là tập các giao tác - trong đó mỗi giao tác T D là tập các item - khi đó X Y diễn đạt ý nghĩa rằng bất cứ khi nào giao tác T có chứa X thì chắc chắn T có chứa Y.
Độ tin cậy của luật (rule confidence) có thể được hiểu như xác suất điều khoản p(Y T | X T). Ý tưởng của việc khai thác các luật kết hợp có nguồn gốc từ việc phân tích dữ liệu mua hàng của khách và nhận ra rằng “Một khách hàng mua mặt hàng x1 và x2 thì sẽ mua mặt hàng y với xác suất là c%”. Ứng dụng trực tiếp của các luật này trong các bài toán kinh doanh cùng với tính dễ hiểu vốn có của chúng – ngay cả đối với những người không phải là chuyên gia khai thác dữ liệu – làm cho luật kết hợp trở thành một một phương pháp khai thác phổ biến. Hơn nữa, luật kết hợp không chỉ bị giới hạn trong phân tích sự phụ thuộc lẫn nhau trong phạm vi các ứng dụng bán lẻ mà chúng còn được áp dụng thành công trong rất nhiều bài toán kinh doanh.
9 z Việc phát hiện luật kết hợp giữa các mục (item) trên dữ liệu “giỏ” là bài toán rất đặc trưng của khai phá dữ liệu. Dữ liệu giỏ là dữ liệu bao gồm các mục được mua bởi khách hàng với các thông tin như ngày mua hàng, số lượng, giá cả, … Luật kết hợp chỉ ra tập các mục mà thường được mua nhất với cùng các tập mục khác. Hiện nay, có nhiều thuật toán dùng cho việc phát hiện luật kết hợp. Tuy nhiên, vấn đề nảy sinh là số lần quét (duyệt) CSDL quá nhiều sẽ ảnh hưởng rất lớn đến hiệu quả và tính khả thi của thuật toán trên các CSDL lớn.
Đối với các CSDL được lưu trên đĩa, phép duyệt CSDL sẽ gây ra số lần đọc đĩa rất lớn. Chẳng hạn một CSDL kích thước 1GB sẽ đòi hỏi khoảng 125000 lần đọc khối cho mỗi lần duyệt (với kích thước khối là 8KB). Nếu thuật toán có 10 lần duyệt thì sẽ gây ra 1250000 lần đọc khối. Giả thiết thời gian đọc trung bình là 12ms một trang, thời gian cần thiết để thực hiện một thao tác I/O này là1250000*12ms hay sấp sỉ 4 tiếng đồng hồ !!! Trong phần này, chúng ta xem xét một số định nghĩa, tính chất có liên quan đến luật và luật kết hợp.
Đồng thời chúng ta tìm hiểu ý nghĩa của luật kết hợp. Luật kết hợp a) Ý nghĩa luật kết hợp: Luật kết hợp là một lĩnh vực quan trọng trong khai thác dữ liệu. Luật kết hợp giúp chúng ta tìm được các mối liên hệ giữa các mục dữ liệu (items) của cơ sở dữ liệu. Trong ngành giao nhận vận tải ngày càng xuất hiện nhiều các Công ty tham gia mua bán, giao nhận vận tải cũng như các điểm cung cấp hàng hóa khác nhau với các chủng loại hàng ưu thích khác nhau, áp dụng các điều khoản giao nhận hàng hóa khác nhau theo từng khu vực vùng miền áp dụng sao cho có lợi cho người tham gia vận chuyển hàng hóa để tránh độ rủi ro nhất định, đem lại lợi nhuận kinh tế tối đa cùng với các hình thức vận tải áp dụng theo từng đặc trưng địa lý vùng miền khi nền kinh tế thị trường mở cửa.
Do đó, chúng ta có thể tìm ra mối liên hệ giữa việc tìm ra khách hàng tham gia quá trình giao nhận phù hợp với từng loại mặt hàng và đặc thù mặt hàng theo các đơn hàng. Hay như trong ngành viễn thông, các loại dịch vụ cung cấp cho khách hàng ngày càng nhiều, do đó chúng ta có thể tìm mối liên kết giữa việc sử dụng các loại dịch vụ để phục vụ cho việc quảng cáo, tiếp thị. Ví dụ như để tìm hiểu thói quen sử dụng các dịch vụ viễn thông của khách hàng, người ta thường đặt câu hỏi “Những dịch vụ nào khách hàng thường hay sử dụng cùng lúc với nhau khi đăng ký sử dụng tại trung tâm chăm sóc khách hàng ?”. Các kết quả nhận được có thể dùng cho việc tiếp thị dịch vụ như liệt kê các dịch vụ khách hàng hay sử dụng cùng lúc nằm gần nhau, hoặc khuyến mãi dịch vụ kèm theo….
10 z b) Định nghĩa luật kết hợp: Cho một tập I = {I1, I2, .,Im} là tập gồm m khoản mục (item), còn được gọi là các thuộc tính (attribute). Các phần tử trong I là phân biệt nhau. X I được gọi là tập mục (itemset). Nếu lực lượng của X bằng k (tức là |X| = k) thì X được gọi là k-itemset.
Một giao dịch (transaction) T được định nghĩa như một tập con (subset) của các khoản mục trong I (T I). Tương tự như khái niệm tập hợp, các giao dịch không được trùng lặp, nhưng có thể nới rộng tính chất này của tập hợp và trong các thuật toán sau này, người ta đều giả thiết rằng các khoản mục trong một giao dịch và trong tất cả các tập mục (item set) khác, có thể coi chúng đã được sắp xếp theo thứ tự từ điển của các item. Gọi D là CSDL của n giao dịch và mỗi giao dịch được đánh nhãn với một định danh duy nhất (Unique Transasction IDentifier-TID). Nói rằng, một giao dịch T D hỗ trợ (support) cho một tập X I nếu nó chứa tất cả các item của X, nghĩa là X T, trong một số trường hợp người ta dùng ký hiệu T(X) để chỉ tập các giao dịch hỗ trợ cho X.
Thông tin về các giao dịch cho ở bảng sau : Định danh giao dịch (TID) Tập mục (itemset) 1 ABDE 2 BCE 3 ABDE 4 ABCE 5 ABCDE 6 BCD Bảng 1: Ví dụ về một cơ sở dữ liệu dạng giao dịch - D Ta có: supp( {A }) = 4/6 (%)= 66. 11 z Tập phổ biến (frequent itemset): Support tối thiểu minsup ( 0, 1] (Minimum Support) là một giá trị cho trước bởi người sử dụng. Nếu tập mục X I có supp(X) minsup thì ta nói X là một tập phổ biến-frequent itemset (hoặc large itemset). Một frequent itemset được sử dụng như một tập đáng quan tâm trong các thuật toán, ngược lại, những tập không phải frequent itemset là những tập không đáng quan tâm.
Trong các trình bày sau này, ta sẽ sử dụng những cụm từ khác như “X có support tối thiểu”, hay “X không có support tối thiểu” cũng để nói lên rằng X thỏa mãn hay không thỏa mãn support(X) minsupp. Ví dụ: Với cơ sở dữ liệu D cho ở bảng 1, và giá trị ngưỡng minsupp = 50% sẽ liệt kê tất cả các tập phổ biến (frequent-itemset) như sau : Các tập mục phổ biến Độ hỗ trợ (supp) tƣơng ứng B 100% (6/6) E, BE 83% (5/6) A, C, D, AB, AE, BC, BD, ABE 67% (4/6) AD, CE, DE, ABD, ADE, BCE, BDE 50% (3/6) Bảng 2: Các tập phổ biến trong cơ sở dữ liệu ở bảng 1 với độ hỗ trợ tối thiểu 50% Một số tính chất (TC) liên quan đến các frequent itemset: TC 1.