zunia.vn

Tuyển sinh 2024 dành cho Gen-Z

zunia.vn

» Công Nghệ Thông Tin

» Kỹ thuật lập trình

Một phương pháp khai phá luật kết hợp hiệu quả trong môi trường phân tán

Chia sẻ: Minh Minh | Ngày: | Loại File: PDF | Số trang:11

Báo xấu

44
lượt xem 2
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài báo này đề xuất một thuật toán mới được gọi là EDMAR (an Efficient Distributed algorithm for Mining Association Rules) . Thuật toán này sử dụng thuật toán FP-Growth và cấu trúc FP-Tree để khai phá tập phổ biến cục bộ tại các điểm đã làm giảm số lần quét cơ sở dữ liệu, từ đó tăng hiệu quả khai phá tại các điểm cục bộ.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Một phương pháp khai phá luật kết hợp hiệu quả trong môi trường phân tán

JOURNAL OF SCIENCE OF HNUE FIT., 2011, Vol. 56, pp. 29-39 MỘT PHƯƠNG PHÁP KHAI PHÁ LUẬT KẾT HỢP HIỆU QUẢ TRONG MÔI TRƯỜNG PHÂN TÁN Nguyễn Thế Bình(∗) , Lương Thế Dũng Trung Tâm CNTT - Ban Cơ yếu Chính phủ Nguyễn Mạnh Hùng Học viện Kỹ thuật quân sự Email: (∗) nguyenthebinh81@yahoo.com Tóm tắt. Khai phá luật kết hợp trong môi trường phân tán là một hướng nghiên cứu quan trọng trong lĩnh vực khai phá dữ liệu, một số thuật toán khai phá luật kết hợp phân tán đã được đề xuất. Tuy nhiên việc phát triển các thuật toán mới hiệu quả hơn vẫn đang là vấn đề dành được nhiều sự quan tâm. Bài báo này đề xuất một thuật toán mới được gọi là EDMAR (an Efficient Distributed algorithm for Mining Association Rules) . Thuật toán này sử dụng thuật toán FP-Growth và cấu trúc FP-Tree để khai phá tập phổ biến cục bộ tại các điểm đã làm giảm số lần quét cơ sở dữ liệu, từ đó tăng hiệu quả khai phá tại các điểm cục bộ. Hơn nữa, EDMAR đã giảm thiểu được số lượng các tập ứng cử toàn cục, sử dụng ít hơn các bước đồng bộ, do đó làm tăng hiệu quả trong quá trình khai phá. 1. Mở đầu Khai phá luật kết hợp là một nội dung quan trọng trong khai phá dữ liệu (KPDL), được khởi xướng từ năm 1993 [1] và cho đến thời điểm này đã có rất nhiều thuật toán khai phá luật kết hợp đã được các tác giả đưa ra. Quá trình khai phá luật kết hợp được chia thành hai bài toán: Tìm tất cả các tập mục phổ biến có trong cơ sở dữ liệu (CSDL) dựa vào ngưỡng độ hỗ trợ tối thiểu và tạo ra các luật mong muốn từ các tập mục phổ biến với điều kiện chúng thỏa mãn ngưỡng độ tin cậy tối thiểu. Trong hai bài toán này thì bài toán thứ hai là đơn giản hơn, vì vậy hầu hết các nghiên cứu về luật kết hợp đều tập trung ở bài toán thứ nhất. Một trong những thuật toán khá nổi tiếng là Apriori [1], sau đó có một vài thuật toán phát triển dựa trên Apriori [2, 3]. Thuật toán thực hiện các bước lặp, trong mỗi bước lặp sẽ dùng tập phổ biến (k-1 ) phần tử để tạo ra các tập ứng cử k phần tử, sau đó duyệt CSDL để đối sánh mẫu và đếm số lần xuất hiện của của các 29
Nguyễn Thế Bình, Lương Thế Dũng, Nguyễn Mạnh Hùng ứng cử viên. Từ đó tìm ra tập phổ biến k phần tử. Quá trình lặp kết thúc khi không có tập phổ biến nào được tạo ra. Hạn chế của thuật toán Apriori và các thuật toán dựa vào Apriori là việc phải tạo ra một lượng rất lớn các tập ứng cử viên và phải duyệt CSDL nhiều lần, nếu số phần tử của tập phổ biến có độ dài dài nhất là n thì thuật toán phải quét CSDL (n+1 ) lần. Điều này dẫn đến thuật toán hoạt động kém hiệu quả. Các thuật toán phát triển dựa trên Apriori mặc dù đã có rất nhiều cải tiến nhưng vẫn chưa giải quyết được tốt các vấn đề trên. Gần đây, thuật toán khai phá tập phổ biến FP-Growth [4] sử dụng cấu trúc FP-Tree được phát triển bởi JIA WEI HAN có hiệu quả khá tốt nếu so sánh với thuật toán Apriori. Ý tưởng của thuật toán là dùng đệ quy để gia tăng độ dài của mẫu phổ biến dựa trên cây FP-Tree và các mẫu được phân hoạch. Ưu điểm của thuật toán này là không tạo ra các tập ứng cử và chỉ phải quét CSDL hai lần, lần quét thứ nhất là để tìm tập phổ biến một phần tử và lần quét thứ hai là để xây dựng cây FP-Tree. Nói chung đến thời điểm hiện tại thì thuật toán FP-Growth vẫn được đánh giá là một thuật toán hoạt động hiệu quả. Ngày nay với sự phát triển mạnh mẽ của công nghệ tính toán và công nghệ mạng đã dẫn đến việc phân tán nguồn dữ liệu. Khi dữ liệu được lưu trữ trên một CSDL phân tán, thì một thuật toán khai phá dữ liệu phân tán lại là cần thiết để khai phá các luật kết hợp. Khai phá các luật kết hợp trong môi trường phân tán là một vấn đề phải được giải quyết bằng việc sử dụng một thuật toán phân tán mà không cần phải trao đổi dữ liệu thô giữa các bên tham gia. Đến nay cũng đã có nhiều thuật toán khai phá luật kết hợp trong môi trường phân tán được đề xuất, ví dụ các thuật toán phổ biến như CD [9], FDM [7], PMFI [6] và DMAR [8]. Nhìn chung trong các thuật toán trên thường sử dụng một thủ tục (Ví dụ: Apriori_gen) để sinh tập ứng cử phổ biến toàn cục từ các dữ liệu cục bộ. Sau đó, sử dụng các kỹ thuật như: Cắt tỉa cục bộ tập ứng cử, cắt tỉa toàn cục tập ứng cử nên số lượng tập ứng cử đã giảm từ đó số lượng truyền thông cần trao đổi giữa các điểm cũng giảm. Mặc dù một số thuật toán được đánh giá là hiệu quả, nhưng số lượng truyền thông vẫn lớn do số lần đồng bộ nhiều. Do đó, vấn đề triển khai các thuật toán này cho các ứng dụng thực tế đặc biệt là các ứng dụng mà có các tập dữ liệu rất lớn còn gặp nhiều hạn chế, việc phát triển các phương pháp hiệu quả hơn vẫn đang là vấn đề được rất nhiều người quan tâm. Vấn đề được đặt ra khi xây dựng một thuật toán khai phá phân tán là làm thế nào để giảm thiểu được xử lý ở các điểm, giảm số lần quét CSDL, giảm thiểu khối lượng truyền thông giữa các điểm hoặc giữa các điểm với điểm chính và giảm thiểu số lần đồng bộ. Bài báo này chúng tôi đề xuất một thuật toán hiệu quả cho việc khai phá luật kết hợp trong môi trường phân tán EDMAR. Ý tưởng chính của EDMAR là sử dụng thuật toán FP-Growth để khai phá tập phổ biến tại các điểm, do đó tại mỗi 30
Một phương pháp khai phá luật kết hợp hiệu quả trong môi trường phân tán điểm chỉ cần hai lần quét CSDL. Trong quá trình xây dựng cây FP-treei tại mỗi điểm Si , thuật toán sẽ sử dụng danh sách tập phổ biến toàn cục 1-phần tử F’, điều này làm giảm đáng kể thời gian xử lý tại mỗi điểm. Thuật toán này sử dụng số lần đồng bộ tương đối ít (năm lần) và giảm thiểu chi phí truyền thông bằng cách sử dụng các kỹ thuật ở điểm chính để tạo ra các tập phổ biến toàn cục từ đó giảm bớt đi số lượng các tập mục ứng cử toàn cục phải gửi trả lại các điểm để tính toán lại. EDMAR được cài đặt để thử nghiệm, đánh giá và so sánh trên ngôn ngữ OpenMP thông qua các luồng, mỗi luồng sẽ khai phá một CSDL riêng biệt. 2. Nội dung nghiên cứu 2.1. Một số vấn đề kỹ thuật 2.1.1. Vấn đề khai phá luật kết hợp trong môi trường phân tán Cho một tập các mục I = {i1 , i2 , . . . , im } và một CSDL giao dịch DB, ở đó mỗi giao dịch T là một tập các mục và T ⊆ I. Mỗi một giao dịch T có một trường khóa duy nhất gọi là TID. Trong T chứa một tập mục P , P ⊆ I nếu như P ⊆ T . Độ hỗ trợ của tập mục P là số lượng các giao dịch có chứa P trong DB. Chúng ta nói rằng P là một tập mục phổ biến nếu như độ hỗ trợ của P là lớn hơn hoặc bằng một ngưỡng hỗ trợ tối thiểu minsup. Chúng ta khảo sát quá trình khai phá luật kết hợp trong một môi trường phân tán. Cho CSDL DB với D giao dịch, giả sử rằng có n điểm S1 , S2 , . . . , Sn trong một hệ thống phân tán và cơ sở dữ liệu DB được phân mảnh ngang vào n S n điểm (DB1 , DB2 , . . . , DBn ), trong đó DB = DBi , kích cỡ của DBi là Di với i i=1 = 1, 2,.., n. X.sup là độ hỗ trợ toàn cục của tập X trong DB và X.supi là độ hỗ trợ cục bộ của tập X trong DBi tại điểm Si . Với một ngưỡng độ hỗ trợ tối thiểu cho trước minsup, X là một tập phổ biến toàn cục (trên DB) nếu X.sup ≥ minsup×D và X là một tập phổ biến cục bộ (trên DBi ) nếu X.supi ≥ minsup × Di . Chúng ta ký hiệu GFI (global frequent itemsets) là những tập phổ biến toàn cục trong DB và LF I i (local frequent itemsets) là những tập phổ biến cục bộ trong DBi . Nhiệm vụ chính của thuật toán là tìm ra các tập mục phổ biến toàn cục GFI, từ đó sinh ra tập các luật kết hợp mong muốn, ký hiệu là AR (association rules). 2.1.2. Một số khái niệm cơ bản Bài báo này sử dụng một số bổ đề và khái niệm sau [6]: Bổ đề 2.1. Nếu một tập mục X là phổ biến toàn cục thì tồn tại ở một Si (i = 31
Nguyễn Thế Bình, Lương Thế Dũng, Nguyễn Mạnh Hùng 1, 2, . . . , n) với X và mọi tập con của nó là phổ biến cục bộ tại Si . Hệ quả: - Một tập X là phổ biến toàn cục thì X sẽ là phổ biến cục bộ tại ít nhất một Si . - Nếu X không là phổ biến cục bộ tại mọi Si thì chắc chắn X không là phổ biến toàn cục. T n Bổ đề 2.2. Nếu tập mục X ∈ LF I i thì X và mọi tập con của nó là phổ biến i=1 toàn cục. Hệ quả: Nếu X là phổ biến cục bộ tại mọi Si thì X và mọi tập con của nó là phổ biến toàn cục. S n T n Định nghĩa 2.1. Với bất kỳ X ∈ LFIi − LFIi thì X là tập ứng cử viên i=1 i=1 (candidate) phổ biến toàn cục. Kí hiệu CGFI (candidate global frequent itemsets). Hệ quả: X là ứng cử viên phổ biến toàn cục khi X là phổ biến cục bộ tại ít nhất một Si (Nhưng không phải phổ biến cục bộ tại mọi Si , vì khi đó X là phổ biến toàn cục rồi). P n Bổ đề 2.3. Với bất kỳ X ∈ CGFI, nếu X.supi ≥ minsup × D thì X là phổ i=1 biến toàn cục. Từ bổ đề 2.2, nếu các tập mục X là phổ biến cục bộ tại mọi điểm thì X phải là phổ biến toàn cục. Từ bổ đề 2.1 và định nghĩa 2.1, ta xây dựng được tập ứng cử phổ biến toàn cục. Tập ứng cử phổ biến toàn cục sẽ là các tập mà phổ biến cục bộ tại ít nhất một điểm, đồng thời loại bỏ đi các tập mà chúng là phổ biến cục bộ tại mọi điểm. Từ bổ đề 2.3, nếu điều kiện của bổ đề 2.2 không được thỏa mãn, nhưng độ hỗ trợ của X lớn hơn hoặc bằng độ hỗ trợ toàn cục thì X vẫn là phổ biến toàn cục. Nếu độ hỗ trợ của X nhỏ hơn độ hỗ trợ toàn cục, chúng ta phải tính lại độ hỗ trợ của X tại các điểm mà nó không là phổ biến cục bộ để quyết định tính chất của nó. Việc áp dụng các bổ đề vào thuật toán sẽ làm giảm số lượng các tập ứng cử toàn cục, giảm số lượng thông điệp phải truyền thông giữa các điểm. Điều này góp phần làm tăng hiệu quả của thuật toán. 32
Một phương pháp khai phá luật kết hợp hiệu quả trong môi trường phân tán 2.1.3. Các thuật toán nền tảng Bài báo này cũng sử dụng một số giải thuật cơ bản sau đây: Giải thuật xây dựng cây FP-treei [4]: Giải thuật này xây dựng cây FP-tree từ CSDL phục vụ cho việc tìm ra các tập mục phổ biến. Giải thuật FP-Growth [4]: Giải thuật này sử dụng cây FP-treei làm đầu vào và kết quả là tìm ra các tập mục phổ biến. Giải thuật tạo luật kết hợp GenRules [2]: Giải thuật này sinh ra các luật kết hợp thỏa mãn điều kiện minconf từ đầu vào là các tập mục phổ biến. Chi tiết các giải thuật: Giải thuật xây dựng cây FP-treei . Input: DBi (i = 1, 2, .., n), minsup, F ’. //F ’: Danh sách tập phổ biến toàn cục 1-phần tử. Output: FP-treei . 1. Sắp xếp F ’ theo thứ tự giảm dần của độ hỗ trợ, ta thu được danh sách L. 2. - Tạo nút gốc R của FP-treei với nhãn là “null”. - Tạo bảng Header có |F ’| dòng, đặt mọi node-link trỏ đến null. 3. For each giao tác T ∈ DBi { - Chọn các phần tử của T có xuất hiện trong F ’ đưa vào P ; - Sắp các phần tử trong P theo trật tự L; - Call Insert_Tree (P , R); } Procedure Insert_Tree(P , R) 1. Đặt P =[p|P - p], với p là phần tử đầu tiên và P − p là phần còn lại của danh sách. 2. if (R có một con N sao cho N.item-name = p) N.count++; else { Tạo nút mới N; N.count = 1; N.item-name = p; N.parent = R; // Tạo node-link chỉ đến item, H là bảng Header. N.node-link = H[p].head; H[p].head = N; } 3. //Tăng biến count của p trong bảng Header thêm 1. H [p].count ++; 33
Nguyễn Thế Bình, Lương Thế Dũng, Nguyễn Mạnh Hùng If ((P − p) != null) Call Insert_Tree(P − p, N) ; Giải thuật FP-Growth Input: FP-treei , minsup Output: LFI i Procedure FP_Growth(FP-treei , α) 1. LFI I = φ; 2. If (FP-treei chỉ chứa một đường dẫn đơn P ) for each tổ hợp β của các nút trong P do { phát sinh mẫu p = β ∪ α; support_count(p) = minsup các nút trong β; LFI i = LFI i ∪ p;} else for each ai trong Header của FP-treei do { Phát sinh mẫu β = ai ∪ α; support_count (β) = ai .support_count; LFI i = LFI i ∪β; Xây dựng cơ sở có điều kiện của β; Xây dựng FP-Tree có điều kiện FP-treei β của β; If (FP-treei β φ) Call FP_Growth(FP-treei , β);} Giải thuật tạo luật kết hợp GenRules Input: GFI, minconf. Output: AR. Procedure GenRules(GFI, minconf) forall tập mục phổ biến lk ∈ GFI, k ≥ 2 do Call Gen(lk , lk ); Procedure Gen(lk : k-itemset phổ biến; am : m-itemset phổ biến) A = {(m − 1) − itemsetam−1 |am−1 ⊂ am ; forall am−1 ∈ A do { conf = sup(lk )sup(am−1 ); if (conf ≥ minconf) { Xuất ra luật am−1 ⇒ (lk − am−1 ); if ((m − 1) > 1) Call Gen(lk , am−1 ); }} 2.2. Đề xuất thuật toán hiệu quả trong khai phá luật kết hợp phân tán EDMAR được đề xuất trong bài báo này được thực hiện thông qua bảy bước: 34
Một phương pháp khai phá luật kết hợp hiệu quả trong môi trường phân tán Bước 1: Được thực hiện tại mọi điểm. Tại mỗi điểm, thuật toán sẽ quét CSDL một lần để đếm độ hỗ trợ của các tập 1-phần tử. Sau đó các điểm này sẽ gửi độ hỗ trợ của các tập 1-phần tử vừa tìm được lên điểm chính. Bước 2: Được thực hiện tại điểm chính. Tại bước này, thuật toán sẽ tổng hợp độ hỗ trợ của các tập 1-phần tử mà các điểm gửi lên, từ đó tìm ra tập phổ biến toàn cục 1-phần tử F ’. Sau đó điểm chính gửi F ’ tới mọi điểm. Bước 3: Được thực hiện tại mọi điểm. Tại mỗi điểm, thuật toán sẽ xây dựng cây FP-treei từ danh sách F ’ và CSDL DB i , sau đó sử dụng giải thuật FP-Growth để tìm ra tập phổ biến cục bộ LF I i . Kết thúc bước này, các điểm sẽ gửi lên điểm chính danh sách LF I i . Bước 4: Được thực hiện tại điểm chính. Thuật toán sử dụng bổ đề 2 để tìm ra các tập phổ biến toàn cục GF I mà là phổ biến cục bộ tại mọi điểm. Tiếp theo thuật toán sử dụng định nghĩa 1 để xây dựng tập ứng cử phổ biến toàn cục CGF I. Áp dụng bổ đề 3 để tìm các tập GF I từ các tập CGF I. Với các tập X ∈ CGF I mà không thỏa mãn bổ đề 3 sẽ được gửi về các điểm mà ở đó nó không là phổ biến cục bổ để tính lại độ hỗ trợ, từ đó sẽ quyết định tính chất của nó. Bước 5: Được thực hiện tại các điểm. Với mỗi tập X ∈ CGF I vừa nhận từ điểm chính, nếu X ∈/ LF I i thì thuật toán sẽ tính lại độ hỗ trợ của X và gửi độ hỗ trợ của X lên điểm chính. Bước 6: Được thực hiện tại điểm chính. Với mỗi tập X ∈ CGF I, thuật toán sẽ tính lại độ hỗ trợ để quyết định tính chất của nó. Nếu tổng độ hỗ trợ của X lớn hơn hoặc bằng ngưỡng độ hỗ trợ toàn cục thì X sẽ là tập phổ biến toàn cục. Kết thúc bước này, ta thu được tập phổ biến toàn cục GF I. Bước 7: Được thực hiện tại điểm chính. Thuật toán sinh luật kết hợp AR từ tập phổ biến toàn cục GF I thỏa mãn ngưỡng tin cậy tối thiểu minconf. Điểm mới của thuật toán nằm ở các bước 1, 2 và 3. Theo như thuật toán được trình bày tại [6], khi khai phá LF I i tại Si , tại mỗi điểm sẽ quét CSDL DBi một lần để tìm ra danh sách tập phổ biến cục bộ 1-phần tử Fi , sau đó thuật toán sẽ sử dụng danh sách Fi này để xây dựng cây FP-treei . Vấn đề sẽ nảy sinh ở bước 5 khi ta cần tính lại độ hỗ trợ của X ∈ CGF I tại các điểm mà nó không là phổ biến cục bộ. Vậy làm thế nào để tại điểm Si có thể tìm được độ hỗ trợ của một phần tử X có độ hỗ trợ nhỏ hơn ngưỡng cho phép. Để giải quyết điều này chúng ta có hai cách sau: Hoặc là chúng phải hạ thấp ngưỡng hỗ trợ tối thiểu để xây dựng lại cây, sau đó thì tìm độ hỗ trợ của phần tử X cần tìm. Như thế, chúng ta phải mất chi phí xây dựng lại cây. Hoặc là ngay từ đầu, mỗi điểm Si xây dựng cây với độ hỗ trợ tối thiểu là 0, sau đó khai phá trên cây với giá trị minsup là ngưỡng yêu cầu để tìm LFI i . Như 35
Nguyễn Thế Bình, Lương Thế Dũng, Nguyễn Mạnh Hùng thế thì lại mất phí lớn xây dựng cây ngay từ đầu vì với ngưỡng hỗ trợ tối thiểu là 0 cây sẽ tăng trưởng rất nhanh. Để giải quyết vấn đề này, thuật toán trong bài báo đã thêm hai bước 1 và 2. Nhiệm vụ của hai bước này là tìm ra một danh sách tập phổ biến toàn cục 1-phần tử F ’, tại bước 3 các điểm Si sẽ sử dụng danh sách F ’ để xây dựng cây FP-treei . Điều này đảm bảo rằng thuật toán sẽ không bỏ xót bất kỳ một tập phổ biến toàn cục nào và tại Si cũng không phải hạ thấp ngưỡng hỗ trợ để xây dựng lại cây hoặc xây cây ngay từ đầu với ngưỡng là 0. Với cải tiến này, thuật toán chỉ phải thêm hai bước đồng bộ, còn số lần quét CSDL vẫn giữ nguyên là hai lần. Đây chính là điểm mấu chốt để làm nên tính hiệu quả của thuật toán. Giải thuật chính: Input: DBi (i = 1, 2, .., n), minsup, minconf. Output: AR (Tập các luật kết hợp). Bước 1: //Thực hiện tại từng Si . For i = 1 to n do{ Đếm độ hỗ trợ của các phần tử 1-phần tử; Gửi tới điểm chính; } Bước 2: //Thực hiện tại điểm chính Tổng hợp độ hỗ trợ của các phần tử 1-phần tử để tìm ra tập phổ biến 1-phần tử toàn cục F ’; Gửi F’ về mọi Si ; Bước 3: //Khai phá LF I i tại từng Si . For i = 1 to n do{ Xây dựng FP-treei dựa trên tập phổ biến 1-phần tử toàn cục F ’; Khai phá LFI i dựa trên FP-treei (FP-Growth); Gửi LFI i tới điểm chính;} Bước 4: //Khai phá GFI và CGFI, thực hiện tại điểm chính. T n S n Tn Tính GF I = LF I i , CGF I = LF I i − LF I i ; i=1 i=1 i=1 P n For all X ∈ CGF I: If ( X. supi ≥ min sup × D ){ i=1 GF I = GF I ∪ {X}; CGF I = CGF I˘{X}; } Gửi CGF I tới mọi Si ; Bước 5: //Tính lại độ hỗ trợ cục bộ X.supi của mọi X CGFI 36
Một phương pháp khai phá luật kết hợp hiệu quả trong môi trường phân tán //Thực hiện tại Si For i = 1 to n do { For all X ∈ CGF I { if (X ∈ / LF I i ) { - Tính lại giá trị X.supi ; - Gửi X.supi tới điểm chính; } } } Bước 6: //Tính độ hỗ trợ toàn cục X.sup của mọi X ∈ CGF I, thực hiện tại điểm chính. For all X ∈ CGF I: Pn If ( X.sup = X. supi ≥ min sup × D ){ GF I = GF I ∪ {X}; } i=1 Bước 7: // Tạo tập luật kết hợp AR từ tập các tập mục phổ biến GFI, thực hiện tại điểm chính. Tạo tập luật AR bằng cách gọi thủ tục GenRules(GF I, minconf); 2.3. Kết quả thử nghiệm Môi trường và công cụ phát triển: Sử dụng ngôn ngữ C++ trong môi trường OpenMP để thực hiện cài đặt thuật toán. Lý do sử dụng OpenMP: OpenMP là giao diện lập trình ứng dụng, nó chứa tập các hàm, lệnh cho phép dễ dàng cài đặt các thuật toán song song cho cả hai trường hợp sử dụng chung một CSDL và sử dụng các CSDL riêng biệt (phân tán). Dữ liệu kiểm thử: Thuật toán được chạy thử nghiệm trên các bộ CSDL được sinh ngẫu nhiên có kích thước khác nhau nhưng cùng một độ hỗ trợ, độ tin cậy. CSDL được tổ chức thành bốn CSDL riêng biệt, mỗi CSDL là một file txt. Loại phần tử từ I1 ⇒ I100. Mỗi hàng (giao dịch) trong file txt có 50 phần tử. Kích thước CSDL (Bao gồm cả bốn CSDL riêng biệt) lần lượt là: D = 4000 (giao dịch); D = 24000; D = 40000 và D = 80000. Thuật toán được chạy thử nghiệm trên máy PC IntelR CoreT M 2 Duo CPU T6600 @ 2.2 GHz, 2 GB RAM, máy được cài đặt hệ điều hành Microsoft Windows XP Professional. Theo hiểu biết của chúng tôi thì PMFI là một trong những thuật toán hiệu quả nhất trong việc khai phá luật kết hợp phân tán. Vì vậy, trong bài báo này, chúng tôi tiến hành so sánh trực tiếp hiệu quả của EDMAR với thuật toán PMFI. Để so 37
Nguyễn Thế Bình, Lương Thế Dũng, Nguyễn Mạnh Hùng sánh, chúng ta tiến hành chạy thử nghiệm trên hai thuật toán với Minsup = 0,4; Minconf = 0,8. Thuật toán thứ nhất PMFI, trong thuật toán này không sử dụng hai bước 1 và 2, thuật toán xây dựng cây FP-treei dựa vào danh sách tập phổ biến cục bộ 1-phần tử Fi với ngưỡng độ hỗ trợ là 0 ngay từ ban đầu. Thuật toán thứ hai là EDMAR được trình bày trong bài báo. Kết quả chạy thử nghiệm hai thuật toán được thể hiện trong đồ thị hình 1. Theo quan sát đồ thị chúng ta thấy rằng, thuật toán EDMAR nhanh hơn đáng kể so với thuật toán PMFI, đặc biệt khi kích thước CSDL lớn. Điều đó cho thấy rằng, việc xây dựng cây F P − treei tại các điểm Si bằng danh sách tập phổ biến toàn cục 1-phần tử F ’ đã tiết kiệm được khá nhiều thời gian, mặc dù thuật toán EDMAR phải thêm hai bước đồng bộ. Chính vì điều này mà thuật toán EDMAR đã cải thiện được hiệu quả khai phá luật kết hợp. Hình 1 : Biến thiên thời gian theo kích thước CSDL 3. Kết luận Trong bài báo này, một thuật toán khai phá luật kết hợp phân tán EDMAR đã được đề xuất. EDMAR đã sử dụng các kỹ thuật tại điểm chính để có thể tìm các tập phổ biến toàn cục từ đó làm giảm bớt được số lượng các tập ứng cử toàn cục. Chính vì vậy mà thuật toán sử dụng ít hơn số lượng truyền thông so với các thuật toán trước. Đồng thời, với việc xây dựng cây FP-treei tại các điểm cục bộ sử dụng danh sách tập phổ biến toàn cục 1-phần tử cũng góp phần làm tăng thêm tính hiệu quả của thuật toán. REFERENCES 38
Một phương pháp khai phá luật kết hợp hiệu quả trong môi trường phân tán [1] R. Agrawal, T. Imielinski and A. Swami, (1993). Minning association rules be- tween sets of items i large databases. In ACM SIGMOD Intil. C@ Managenment of Data, May. [2] R. Agrawal and R. Srikant, (1994). Fast algorithms for minning association rule. In 20th VL.DBConf, Sept. [3] R Agrawal, H.Manila, R. Srikant, H. Toivonen and A. 1. Verkamo, (1996). Fast discovery of association rules. In U.Fayyad and et al, editors, Advances in Knowl- edge Discovery and Data Minning. MIT Press. [4] J. Han, J. Pei, Y. Yin and R. Mao. (2003). Mining frequent patterns without can- didate generation: A frequent-pattern tree approach. Data Mining and Knowledge Discovery. [5] Ji-Fu Zhang, Hong Shi, Lian Zheng, (2002). A method and algorithm of dis- tributed mining associationrules in synchronisms. Proceedings of the First Inter- national Conference on Machine Learning and Cybernetics, Beijing. [6] You-Lin Ruan, Gan Liu, Qing-Hua Li, (2005). Parallel Algorithm For Mining Frequent Itemsets. Proceedings of the Fourth International Conference on Machine Learning and Cybernetics, Guangzhou. [7] David W. Cheung, Jiawei Han, Vincent T. Ng, Ada W. Fu, Yongjian Fu, (1996). A Fast Distributed Algorithm for Mining Association Rules. IEEE. [8] Ji-Fu Zhang, Hong Shi, Lian Zheng, (2002). A method and algorithm of dis- tributed mining associationrules in synchronisms. Proceedings of the First Inter- national Conference on Machine Learning and Cybernetics, Beijing. [9] Agrawal and J.Shafer, (1996). Parallel mining of association rules. In IEEE Trans, on Knowledge and Data Engg, pp. 8(6): 962 - 969. ABSTRACT An effective association mining rules method in the distributed environment Association mining rules in the distributed environment is an important prob- lem in data mining, serveral algorithms of distributed association mining rules have been proposed. However, developing a more efficient algorithms is still an active problem. This paper proposes a new algorithm called EDMAR (an Efficient Dis- tributed algorithm for Mining Association Rules). This algorithm uses FP-Growth algorithm and FP-Tree structure to mine the local frequent item sets. Thus, it de- creases the number of the database scanning and increases the efficiency of mining in the local sites. In addition, EDMAR decreases the number of candidates of global frequent itemsets and uses fewer synchronization steps, thus the efficiency is im- proved. 39

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN

TRỢ GIÚP

HỖ TRỢ KHÁCH HÀNG

Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.