Tài liệu Khai phá luật kết hợp với dữ liệu phân tán dựa trên mô hình mapreduce

HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG --------------------------------------- TRẦN THỊ LỊCH KHAI PHÁ LUẬT KẾT HỢP VỚI DỮ LIỆU PHÂN TÁN DỰA TRÊN MÔ HÌNH MAPREDUCE LUẬN VĂN THẠC SĨ KỸ THUẬT HÀ NỘI – 2014 HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG --------------------------------------- KHAI PHÁ LUẬT KẾT HỢP VỚI DỮ LIỆU PHÂN TÁN DỰA TRÊN MÔ HÌNH MAPREDUCE Chuyên ngành: Khoa học máy tính Mã số : 60.48.01.01 LUẬN VĂN THẠC SĨ KỸ THUẬT NGƯỜI HƯỚNG DẪN KHOA HỌC: PGS.TS TRẦN ĐÌNH QUẾ HÀ NỘI - 2014 1 MỞ ĐẦU 1. Lý do chọn đề tài Khai phá dữ liệu (Data Mining ) là một lĩnh vực khoa học liên ngành mới xuất hiện gần đây nhằm đáp ứng nhu cầu phát hiê ̣n ra những tri thức có ích , phục vụ cho công viê ̣c của con người. Các kết quả nghiên cứu cùng với những ứng dụng thành công trong khai phá dữ liệu, khám phá tri thức cho thấy khai phá dữ liệu là một lĩnh vực khoa học tiềm năng, mang lại nhiều lợi ích, đồng thời có ưu thế hơn hẳn so với các công cụ phân tích dữ liệu truyền thống. Trong lĩnh vực khai phá dữ liệu , mục đích của luật kết hợp (Association Rule - AR) là tìm ra các mối kết hợp (Association) hay tương quan (Correlation) giữa các đối tượng trong khối lượng lớn dữ liệu. Ứng dụng của luật kết hợp rất phổ biến trong nhiều lĩnh vực, nhất là trong kinh doanh như phân tić h hành vi khách hàng , dự đoán nhu cầ u của khách hàng... Mô hin ̀ h MapReduce là một mô hình lập trình giúp các ứng dụng có thể xử lý nhanh một lượng lớn dữ liê ̣u trên các máy phân tán hoa ̣t đô ̣ng song son g, đô ̣c lâ ̣p với nhau từ đó giúp rút ngắ n thời gian xử lý toàn bô ̣ dữ liê ̣u. MapReduce có thể chạy trên các phần cứng thông thường (commodity hardware), không đòi hỏi các server chạy MapReduce phải là các máy tính có khả năng tính 2 toán, lưu trữ và truy xuất mạnh mẽ. Do vậy, chi phí triển khai MapReduce sẽ rẻ hơn. MapReduce làm đơn giản hoá các giải thuật tính toán phân tán. Với MapReduce, bạn chỉ cần cung cấp hai hàm Map và Reduce cùng với một số thành phần xử lý dữ liệu đầu vào. Do vậy, các nhà phát triển ứng dụng phân tán có thể tập trung nhiều hơn cho phần logic của ứng dụng, bỏ qua các chi tiết phức tạp của việc phân tán xử lý. Sự ra đời của MapReduce đã mở ra cho các doanh nghiệp cơ hội xử lý các nguồn dữ liệu đồ sộ với chi phí thấp và thời gian nhanh hơn. Với việc áp dụng MapReduce, Amazon có thể xử lý được các file log phát sinh trong quá trình bán hàng trên mạng, phục vụ cho việc dự đoán xu hướng mua hàng của khách hàng, các sản phẩm đang được mua nhiều… Facebook có thể xử lý được khối lượng hơn 10 tỷ hình ảnh mà họ đang lưu trữ để rút trích các thông tin về kích thước hình ảnh, phát hiện các hình ảnh xấu. Vì những lý do trên mà tôi chọn đề tài “ Khai phá luật kế t hợp với dữ liê ̣u phân tán dựa trên mô hình MapReduce” làm đề tài luận văn của mình. 2. Mục đích nghiên cứu  Tìm hiểu kỹ thuật , thuâ ̣t toán khai phá luâ ̣t kế t hơ ̣p trong khai phá dữ liê ̣u. 3  Nghiên cứu mô ̣t mô hình lâ ̣p trình MapReduce trong viê ̣c ứng du ̣ng vào các bài toán xử lý mô ̣t lươ ̣ng lớn dữ liê ̣u . Sử du ̣ng H adoop, mô ̣t thể hiê ̣n của MapReduce, cho viê ̣c phân tić h dữ liê ̣u.  Áp du ̣ng cấ u trúc, tham chiế u các đă ̣c trưng của mô hình MapReduce vào bài toán phân tić h xu hướng khách hàng nhằm rút ra những luật kết hợp. 3. Đối tƣợng và phạm vi nghiên cứu  Nghiên cứu khái niệm, vai trò, ứng dụng và các kỹ thuật khai phá dữ liệu.  Tìm hiểu, nghiên cứu khai phá dữ liê ̣u với luâ ̣t kế t hơ ̣p và mô ̣t số thuâ ̣t toán .  Tìm hiểu , nghiên cứu mô hình lâ ̣p trình MapReduce, Hadoop. 4. Phƣơng pháp nghiên cứu  Nghiên cứu, tìm hiểu lý thuyết về các kỹ thuật khai phá dữ liệu.  Tìm hiểu và cài đặt mô hình lập trình MapReduce trên nề n Hadoop . Sử du ̣ng ngôn ngữ lâ ̣p trin ̀ h Java tích hợp Framework Hadoop trên môi trư Eclipse. ờng  Nguồ n dữ liê ̣u sẽ sử du ̣ng để thử nghiê ̣m là dữ liê ̣u mua bán lẻ của khách hàng đã đươ ̣c lưu trữ ta ̣i siêu thị. 4 5. Kết cấu luận văn Chƣơng 1: TỔNG QUAN KHAI PHÁ DƢ̃ LIỆU Giới thiê ̣u tổ ng quan về quá trình khai phá dữ liê ̣u, các phương pháp khai phá dữ liệu , nhiê ̣m vu ̣ chính , quy trình khai phá dữ liệu. Chƣơng 2: KHAI PHÁ LUẬT KẾT HỢP Trình bày tổng quan về khai phá luật kết hợp và giới thiê ̣u mô ̣t số thuâ ̣t toán khai phá luâ ̣t kế t hơ ̣p. Chƣơng 3: TỔNG QUAN MÔ HÌ NH LẬP TRÌ NH MAPREDUCE Trình bày tổng quan mô hình lập trình MapReduce , các thành phần , cấ u trúc của mô hiǹ h này . Làm quen với môi trường phân tán Hadoop trên mô hình đó . Chƣơng 4: ỨNG DỤNG LUẬT KẾT HỢP TRONG MÔ HÌ NH MAPREDUCE Tóm tắt lại kết quả đạt được , ưu điể m , nhươ ̣c điể m của thuâ ̣t toán và phương hướng phát triể n tiế p theo. 5 CHƢƠNG 1 TỔNG QUAN KHAI PHÁ DỮ LIỆU 1.1 Khai phá dƣ̃ liêụ là gi?̀ 1.2 Quy trin ̀ h khai phá dƣ̃ liêụ 1. Làm sạch dữ liệu 2. Tích hợp dữ liệu 3. Trích chọn dữ liệu 4. Chuyển đổi dữ liệu 5. Khai phá dữ liệu 6. Ước lượng mẫu 7. Biểu diễn tri thức 1.3 Các phƣơng pháp khai phá dữ liệu 1.3.1 Phát hiện các luật kết hợp 1.3.2 Phân cụm 1.3.3 Phân lớp 1.3.4 Hồi quy 1.3.5 Mô hình phụ thuộc 1.3.6 Phát hiện sự thay đổi và độ lệch 1.4 Các dạng cơ sở dữ liệu có thể khai phá  CSDL quan hệ (relational databases)  CSDL dạng giao dịch (transactional databases)  CSDL mở rộng 6 1.5 Phân loại các hệ khai phá dữ liệu  Phân loại dựa trên kiểu dữ liệu được khai phá  Phân loại dựa trên dạng tri thức được khám phá  Phân loại dựa trên kỹ thuật được áp dụng  Phân loại dựa trên lĩnh vực được áp dụng 1.6 Nhƣ̃ng thách thƣ́c khai phá dƣ̃ liêụ 1.7 Các ứng dụng trong khai phá dữ liệu 1.8 Kế t luâ ̣n Trong chương một, luận văn đã trình bày một cách tổng quan nhất về KPDL - cụ thể là định nghĩa về KPDL và những mục đích, ứng dụng, động cơ thúc đẩy các nhà tin học chú trọng vào lĩnh vực nghiên cứu này. 7 CHƢƠNG 2: KHAI PHÁ LUẬT KẾT HỢP 2.1 Giới thiêụ 2.1.1 Các khái niệm cơ bản Định nghĩa 2.1: Độ hỗ trợ (support) của luật kết hợp X  Y là : Support = Định nghĩa 2.2: Độ tin cậy (Confidence) của luật kết hợp X  Y là : Đơn vị tính %. Confidence = Các luật thỏa mãn có support và confidence thỏa mãn (lớn hơn hoặc bằng) cả Minimum support và Minimum confidence gọi là các luật mạnh (Strong Rule) Một itemsets mà tần suất xuất hiện của nó >= min_sup goi là frequent itemsets. 2.1.2 Khai phá luật kế t hợp 2.1.2.1 Phát biểu bài toán: - Cho một tập mục I = {I1, I2,..., Im} - Một cơ sở dữ liệu giao dịch D (n giao dịch) - Độ hỗ trợ tối thiểu minsup và độ tin cậy tối thiểu mincof. 8 Tìm tập các luật kết hợp R: X  Y sao cho support(X  Y) >= minsup và confidence(X  Y) >= mincof. 2.1.2.2 Giải quyết bài toán  Tìm tất cả các tập mục thỏa mãn độ hỗ trợ tối thiểu minsup cho trước, hay tập mục phổ biến.  Tìm tất cả những luật kết hợp từ những tập mục phổ biến thỏa độ tin cậy tối thiểu mincof cho trước. 2.1.2.3 Phân loại luật kết hợp  Luật kết hợp nhị phân  Luật kết hợp mờ  Luật kết hợp nhiều mức 2.2 Mô ̣t số thuâ ̣t toán khai phá luâ ̣t kế t hơ ̣p 2.2.1 Thuật toán khai phá luật kế t hợp tuầ n tự 2.2.2 Thuật toán khai phá luật kết hợp song song 2.2.3 Thuật toán khai phá luật kế t hợp phân tán 2.3 Ứng dụng của luật kết hợp 9 2.4 Kế t luâ ̣n Trong chương này chúng ta tìm hiểu được một số vấn đề sau:  Các hiểu biết, khái niệm về luật kết hợp, một số thuật toán dùng trong khai phá luật kết hợp, làm quen thuật toán Apriori.  Phân biệt thế nào là độ hỗ trợ, độ tin cậy, Frequent items, ItemSet và đặc biệt là cách tìm ra một frequent items như thế nào?  Thuật toán Apriori được dùng để phát hiện các luật kết hợp dạng khẳng định nhị phân chứ không thể phát hiện các luật kết hợp ở dạng phủ định. 10 CHƢƠNG 3: TỔNG QUAN MÔ HÌ NH LẬP TRÌ NH MAPREDUCE 3.1 Giới thiêụ mô hin ̀ h tính toán MapReduce 3.1.1 Nguyên nhân và lich ̣ sử ra đời Khi khối lượng dữ liệu của một hệ thống gia tăng tới một mức độ nhất định (khoảng hàng ngàn Terabyte chẳng hạn), thì việc hệ thống sẽ phải đối mặt với thách thức làm sao để lưu trữ và phân tích dữ liệu. Sự bùng nổ về dữ liệu đã đặt ra các cơ hội, cơ hội chiếm lĩnh một nguồn thông tin khổng lồ, làm sao để lưu trữ và phân tích nguồn dữ liệu đó nếu chúng ta có đủ khả năng phân tích và xử lý nguồn dữ liệu đó, biến những dữ liệu thô thành những thông tin hữu ích với một mức chi phí hợp lý. 3.1.2 MapReduce là gì ? “MapReduce là mô hình lập trình và thực thi song song các xử lý và phát sinh các tập dữ liệu lớn”. Hình 3.1 Mô hình MapReduce của Google. 11 12 MapReduce sử dụng hai thao tác chính cho việc thực thi công việc ban đầu từ người dùng là hàm map và hàm reduce Hàm map có input là một cặp (k1, v1) và output là một danh sách các cặp (k2, v2). map(k1, v1) -> list(k2, v2) Sau giai đoạn này thì chúng ta có một tập hợp rất nhiều cặp (key, value) thuộc kiểu (k2, v2) gọi là các cặp (key, value) trung gian. MR cũng sẽ nhóm các cặp này theo từng key, như vậy các cặp (key, value) trung gian có cùng k2 sẽ nằm cùng một nhóm trung gian. Một cách hình thức, hàm này có thể mô tả như sau reduce(k2, list (v2))->list(v3) Trong đó k2 là key chung của nhóm trung gian, list(v2) là tập các values trong nhóm, và list(v3)là một danh sách các giá trị trả về của reduce thuộc kiểu dữ liệu v3. Do reduce được áp dụng vào nhiều nhóm trung gian độc lập nhau, chúng lại một lần nữa có thể được chạy song song với nhau. 3.1.3 Ưu điểm của MapReduce 3.1.4 Nguyên tắ c hoa ̣t động của MapReduce 13  Đọc dữ liệu đầu vào  Thực hiện xử lý các phần dữ liệu vào (xử lý từng phần một ) (Thực hiện hàm Map)  Trộn và sắp xếp các kết quả thu được từ các máy tính làm sao để được kết quả tiện lợi nhất so với mục đích của quá trình.  Tổng hợp các kết quả trung gian thu được từ các máy tính phân tán (Thực hiện hàm reduce) Hình 3.2 Sơ đồ hoạt động của quá trình Mapreduce  Đưa ra kết quả cuối cùng 14 3.2 Giới thiêụ nề n tảng tính toán phân tán Hadoop trên mô hin ̀ h MapReduce 3.2.1 Hadoop là gì? 1) Hadoop là một framework cho phép phát triển các ứng dụng phân tán. 2) Hadoop cung cấp một phương tiện lưu trữ dữ liệu phân tán trên nhiều node. 3.2.2 Lịch sử Hadoop. 3.2.3 Các thành phần của Hadoop. 3.2.4 Ứng dụng của Hadoop 3.3 Hadoop Distributed File System (HDFS) 3.3.1 Giới thiê ̣u 3.4 Kế t luâ ̣n Một số ván đề đã tìm hiểu trong chương này:  MapReduce là mô hình lập trình và thực thi song song các xử lý và phát sinh các tập dữ liệu lớn.  MapReduce là một mô hình được áp dụng trên một hệ thống các máy tính được kết nối với nhau và cài đặt chương trình MapReduce và thường kèm theo nó là một hệ thống chia sẻ file phân tán (HDFS). 15 CHƢƠNG 4: ỨNG DỤNG LUẬT KẾT HỢP TRONG MÔ HÌ NH MAPREDUCE 4.1 Giới thiệu bài toán Maket Basket Analysis (MBA) là một trong những phương pháp khai phá dữ liệu để phân tích dựa trên một tập dữ liệu với nhau. Ý tưởng chính của thuật toán là đi tìm sự kết hợp của các cặp mặt hàng trong cửa hàng… Trong chương này chúng ta sẽ thực nghiệm mô hình lập trình MapReduce với bài toán Maket Basket Analysis . 4.1.1 Thuật toán khai phá luật kết hợp Apriori tuần tự Bài toán khai phá luật kết hợp được chia thành hai bài toán nhỏ: Bài toán 1: Tìm tất cả các tập mục thỏa mãn độ hỗ trợ tối thiểu minsup cho trước hay tập mục phổ biến. Bài toán 2: Tìm tất cả những luật kết hợp từ những tập mục phổ biến thỏa độ tin cậy tối thiểu mincof cho trước. Thuật toán như sau: 16 //(1) Map transaction t in data source to all Map nodes; C1 = {size 1 frequent items}; // (2) min_support = num/total items; L1 = {size 1 frequent items min_support}; for (k = 1; Lk !=∅; k++) do begin // (3) sắp xếp và loại bỏ các items trùng nhau từ Lk Ck+1 = Lk join_sort Lk; for each transaction t in data source with Ck+1 do // Đếm số lần xuất hiện Ck+1 trong t // (5) Tìm Lk+1 với Ck+1 thỏa mãn min_support Lk+1 = {size k+1 frequent items min_support}; end end return ∪k Lk; Hình 4.1 Thuật toán Apriori tuần tự 4.1.2 Thuật toán khai phá luật kết hợp Apriori trên MapReduce Giai đoạn Mapper: 17 Step 1: Đọc mỗi giao dịch của dữ liệu đầu vào và tạo ra một tập các Item (, ,…, ) where < Vn>:(vn1, vn2,.. vnm) Step 2: Sắp xếp tất cả các tập và tạo ra một tập các dữ liệu đã được sắp xếp là : (, , …, ) trong đó < Un>: (un1, un2,.. unm) Step 3: Vòng lặp While < Un> có phần tử tiếp theo; //Chú ý:mỗi danh sách Un được xử lý riêng rẽ. 3.1: Vòng lặp For mỗi Item từ un1 tới unm của < Un> with NUM_OF_PAIRS 3.a: sinh ra một tập dữ liệu : (yn1, yn2,.. ynl); Ynl: (unx uny) là danh sách của các cặp (un1, un2,.. unm) where unx uny 3.b: Làm tăng sự xuất hiện của ynl; //Chú ý: (key, value) = (ynl, số lần xuất hiện) 3.2: Kết thúc vòng lặp For Step 4: Kết thúc vòng lặp While Tập dữ liệu được tạo ra là đầu vào của giai đoạn Reducer: (key, ) = (ynl, ) Hình 4.2 MBA Algorithm for Mapper 18 Giai đoạn Reducer 1 Đọc(ynl,) data từ nhiều node. 2. Add the values for ynl to have (ynl, total number of occurrences) Hình 4.3. MBA Algorithm for Reducer 4.1.3 So sánh thuật toán apriori trên MapReduce và thuật toán Apriori tuần tự. Độ phức tạp của thuật toán Apriori tuần tự là O(k t n)) với k: kích cỡ của frequent items, t: số giao dịch, n: số Items của giao dịch với t>>k, n>>k. Độ phức tạp của thuật toán Apriori-Map/Reduce là O(k t n/p) với k: kích thước của frequent items, t: số transactions, n: số items của transactions, p: số nodes Map và Reduce giả sử rằng kích thước các Node là như nhau. Với điều kiện t >> k, n >> k. Lý thuyết này đã chỉ ra rằng độ phức tạp của thuật toán Apriori sử dụng Map/Reduce ít hơn p lần so với thuật toán Apriori tuần tự.