Luận văn Thạc sĩ: Khai phá tri thức trong cơ sở dữ liệu phân tán - Vũ Thị Quyên

Tài liệu toàn văn luận văn Thạc sĩ về khai phá tri thức trong cơ sở dữ liệu phân tán, tập trung vào các thuật toán khai phá luật kết hợp.

• Tác giả: Vũ Thị Quyên
• Người hướng dẫn: PGS. Nguyễn Bá Tường
• Trường học: Học viện Kỹ thuật Quân sự
• Chuyên ngành: Hệ thống thông tin
• Đề tài: Khai phá tri thức trong cơ sở dữ liệu phân tán
• Loại tài liệu: Luận văn Thạc sĩ Kỹ thuật
• Năm xuất bản: 2013
• Địa điểm: Hà Nội

Tóm tắt

I. Khái niệm và Tầm quan trọng của Khai phá Tri thức trong CSDL Phân tán

Khai phá tri thức trong cơ sở dữ liệu phân tán là một lĩnh vực nghiên cứu quan trọng trong khoa học máy tính hiện đại. Khai phá dữ liệu phân tán cho phép các tổ chức khai thác giá trị ẩn từ dữ liệu được lưu trữ trên nhiều hệ thống khác nhau. Với sự phát triển của công nghệ thông tin, các doanh nghiệp ngày càng tích lũy lượng dữ liệu khổng lồ ở các địa điểm địa lý khác nhau. Tri thức từ CSDL phân tán giúp các tổ chức đưa ra quyết định chiến lược tốt hơn, cải thiện hiệu suất kinh doanh và tăng cường khả năng cạnh tranh. Luận văn này tập trung vào các phương pháp tiên tiến để khai phá luật kết hợp một cách hiệu quả trong môi trường phân tán, từ đó mở ra những ứng dụng thực tiễn quan trọng cho các hệ thống thông tin hiện đại.

1.1. Định nghĩa Khai phá Dữ liệu và CSDL Phân tán

Khai phá dữ liệu (Data Mining) là quá trình tìm kiếm các mẫu, quy tắc và tri thức hữu ích từ tập dữ liệu lớn. CSDL phân tán là hệ thống cơ sở dữ liệu được phân bổ trên nhiều site, nút mạng khác nhau. Sự kết hợp giữa hai khái niệm này tạo ra một nhu cầu mới: xử lý dữ liệu không tập trung để phát hiện các quy luật toàn cục một cách hiệu quả.

1.2. Ứng dụng Thực tiễn của Khai phá Tri thức Phân tán

Khai phá tri thức phân tán được ứng dụng rộng rãi trong các lĩnh vực như thương mại điện tử, phân tích hành vi khách hàng, phát hiện gian lận tài chính, và quản lý chuỗi cung ứng. Các hệ thống ngân hàng, viễn thông, và bán lẻ lớn sử dụng thuật toán khai phá CSDL phân tán để phát hiện các mẫu bán hàng, tối ưu hóa chiến lược marketing và cải thiện dịch vụ khách hàng.

II. Các Thuật toán Khai phá Luật Kết hợp Chính

Trong lĩnh vực khai phá dữ liệu, có nhiều thuật toán được phát triển để tìm kiếm luật kết hợp từ cơ sở dữ liệu. Thuật toán Apriori là một trong những phương pháp kinh điển nhất, sử dụng nguyên lý rằng tập con của một tập phổ biến cũng phải là phổ biến. Thuật toán FP-Growth là sự cải tiến đáng kể, sử dụng cây FP-tree để tránh việc quét lại cơ sở dữ liệu nhiều lần. Các thuật toán song song như Count Distribution (CD) và Data Distribution (DD) được thiết kế để xử lý dữ liệu lớn trên hệ thống máy tính nhiều bộ xử lý. Mỗi thuật toán có những ưu nhược điểm riêng, phù hợp với các tình huống cụ thể.

2.1. Thuật toán Apriori và Các Biến thể

Thuật toán Apriori hoạt động bằng cách tìm tập phổ biến một phần tử, sau đó mở rộng thành các tập lớn hơn. Apriori-TID cải tiến bằng cách sử dụng định danh giao tác thay vì dữ liệu gốc. Apriori-Hybrid kết hợp ưu điểm của cả hai phiên bản để đạt hiệu suất tốt hơn trong các giai đoạn khác nhau của quá trình khai phá luật kết hợp.

2.2. Thuật toán FP Growth và Ứng dụng trong CSDL Phân tán

Thuật toán FP-Growth sử dụng cấu trúc dữ liệu cây FP-tree để mã hóa cơ sở dữ liệu một cách nén gọn. Phương pháp này loại bỏ nhu cầu quét cơ sở dữ liệu nhiều lần, giảm đáng kể chi phí tính toán. Khai phá phân tán FP-Growth được áp dụng hiệu quả trong các hệ thống CSDL phân tán để tìm kiếm các mẫu toàn cục một cách nhanh chóng.

III. Khai phá Luật Kết hợp trong Môi trường Phân tán

Khai phá dữ liệu trong CSDL phân tán đặt ra những thách thức độc đáo so với khai phá dữ liệu tập trung. Dữ liệu không được lưu trữ tại một nơi duy nhất mà được phân tán trên nhiều site khác nhau, điều này yêu cầu các thuật toán phải giảm thiểu giao tiếp mạng và xử lý dữ liệu cục bộ trước. Thuật toán FDM (Fast Distributed Mining) và DMAR (Distributed Mining Association Rule) là hai phương pháp tiên tiến được đề xuất để khai phá luật kết hợp phân tán hiệu quả. Các thuật toán này sử dụng chiến lược chia sẻ dữ liệu thông minh, giảm lượng dữ liệu truyền tải trên mạng và tăng tốc độ xử lý tổng thể.

3.1. Thuật toán FDM và Tối ưu hóa Phân tán

Thuật toán FDM (Fast Distributed Mining) được thiết kế để khai phá luật kết hợp phân tán nhanh chóng. Thuật toán sử dụng chiến lược tối ưu hóa tập phổ biến cục bộ (LFI) trước khi tính toán tập phổ biến toàn cục (GFI). Điều này giúp giảm số lượng ứng cử phải truyền giữa các site, từ đó cải thiện hiệu suất tổng thể của hệ thống.

3.2. Thuật toán DMAR và Cơ chế Tương tác Site

Thuật toán DMAR sử dụng một phương pháp tiếp cận khác với khai phá luật kết hợp phân tán. Nó cho phép các site trao đổi thông tin về độ hỗ trợ (support) các tập ứng cử để xác định tập phổ biến toàn cục. DMAR tối ưu hóa giao tiếp mạng bằng cách giảm số lần trao đổi dữ liệu giữa các site, đạt được khai phá dữ liệu nhanh hơn mà vẫn đảm bảo độ chính xác.

IV. Cài đặt Hệ thống và Kết quả Thực nghiệm

Luận văn này đề xuất và cài đặt một hệ thống khai phá luật kết hợp trong CSDL phân tán với hiệu năng cao. Cấu trúc lưu trữ cây FP-tree được xây dựng để mã hóa hiệu quả cơ sở dữ liệu giao tác. Giao diện chương trình cung cấp các chức năng chính như mở file CSDL phân tán, thực hiện khai phá tuần tự và khai phá song song. Hệ thống được thiết kế với khả năng xử lý dữ liệu lớn từ cơ sở dữ liệu phân tán, cho phép so sánh hiệu suất giữa các phương pháp khác nhau. Các kết quả thực nghiệm chứng minh rằng thuật toán đề xuất đạt hiệu suất vượt trội so với các phương pháp truyền thống.

4.1. Thiết kế và Cài đặt Cấu trúc FP tree

Cây FP-tree được cài đặt để lưu trữ thông tin về CSDL giao tác một cách tối ưu. Mỗi nút trong cây lưu trữ một mục hàng và số lần xuất hiện của nó trong các giao tác. Bảng tiền tố (header table) được sử dụng để tra cứu nhanh các nút liên quan. Cầu nối (links) giữa các nút có cùng mục hàng tạo điều kiện cho việc khai phá luật kết hợp mà không cần quét lại cơ sở dữ liệu nhiều lần.

4.2. Giao diện Chương trình và Các Chức năng Chính

Giao diện chương trình được thiết kế thân thiện, cho phép người dùng dễ dàng mở file CSDL phân tán và thiết lập các tham số như độ hỗ trợ tối thiểu (minsup) và độ tin cậy tối thiểu (minconf). Chức năng khai phá tuần tự sử dụng thuật toán FP-Growth trên một máy tính, trong khi khai phá song song phân chia dữ liệu và xử lý trên nhiều bộ xử lý. Kết quả cuối cùng hiển thị tất cả luật kết hợp được phát hiện cùng với độ hỗ trợ và độ tin cậy của chúng.

Trích đoạn nội dung tài liệu

Chương 1 TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU 1. Các khái niệm cơ bản Dữ liệu (Data): có thể xem là chuỗi các bit, là số, ký tự…mà chúng ta tập hợp hàng ngày trong công việc. Thông tin (Information): là tập hợp của những mảnh dữ liệu đã được chắt lọc dùng mô tả, giải thích đặc tính của một đối tượng nào đó. Tri thức (Knowledge): là tập hợp những thông tin có liên hệ với nhau, có thể xem tri thức là sự kết tinh từ dữ liệu.

Tri thức thể hiện tư duy của con người về một vấn đề. Khám phá tri thức từ cơ sở dữ liệu (KDD): là quy trình bao gồm nhiều công đoạn như: xác định vấn đề, tập hợp và chọn lọc dữ liệu, khai thác dữ liệu, đánh giá kết quả, giải thích dữ liệu, áp dụng tri thức vào thực tế. Tại sao phải khai phá dữ liệu? Nhà bác học nổi tiếng Karan Sing đã từng nói rằng “Chúng ta đang ngập chìm trong biển thông tin nhưng lại đang khát tri thức”. Dữ liệu được thu thập hàng ngày là rất lớn: Từ các cơ sở dữ liệu khổng lồ, từ Internet.

Theo các báo cáo của IBM, chỉ có 80% dữ liệu được khai thác, 20% còn lại ẩn trong các cơ sở dữ liệu là những tri thức quý giá. Khai phá dữ liệu (Data mining): Là một bước trong quy trình khám phá tri thức, nhằm: ➢ Rút trích thông tin hữu ích, chưa biết, tiềm ẩn trong khối dữ liệu lớn 5 ➢ Phân tích dữ liệu bán tự động ➢ Giải thích dữ liệu trên các tập dữ liệu lớn 1. Quá trình khai phá dữ liệu Một quá trình KPDL bao gồm năm giai đoạn chính sau [6]: (1) Tìm hiểu nghiệp vụ và dữ liệu (2) Chuẩn bị dữ liệu (3) Mô hình hóa dữ liệu (4) Hậu xử lý và đánh giá mô hình (5) Triển khai tri thức Quá trình này có thể được lặp lại nhiều lần một hay nhiều giai đoạn dựa trên phản hồi từ kết quả của các giai đoạn sau. Tham gia chính trong quá trình KPDL là các nhà tư vấn và phát triển chuyên nghiệp trong lĩnh vực KPDL.

Tìm hiểu nghiệp vụ và dữ liệu: Nhà tư vấn nghiên cứu kiến thức về lĩnh vực sẽ áp dụng, bao gồm các tri thức cấu trúc về hệ thống và tri thức, các nguồn dữ liệu hiện hữu, ý nghĩa, vai trò và tầm quan trọng của các thực thể dữ liệu. Việc nghiên cứu này được thực hiện qua việc tiếp xúc giữa nhà tư vấn và người dùng. Khác với phương pháp giải quyết vấn đề truyền thống khi bài toán được xác định chính xác ở bước đầu tiên, nhà tư vấn tìm hiểu các yêu cầu sơ khởi của người dùng và đề nghị các bài toán tiềm năng có thể giải quyết với nguồn dữ liệu hiện hữu. Tập các bài toán tiềm năng được tinh chỉnh và làm hẹp lại trong các giai đoạn sau.

Các nguồn và đặc tả dữ liệu có liên quan đến tập các bài toán tiềm năng cũng được xác định. 6 Chuẩn bị dữ liệu: Sử dụng các kỹ thuật tiền xử lý để biến đổi và cải thiện chất lượng dữ liệu để thích hợp với những yêu cầu của các giải thuật học. Phần lớn các giải thuật KPDL hiện nay chỉ làm việc trên một tập dữ liệu đơn và phẳng, do đó dữ liệu phải được trích xuất và biến đối từ các dạng cơ sơ dữ liệu phân bố, quan hệ hay hướng đối tượng sang dạng cơ sở dữ liệu quan hệ đơn giản với một bảng dữ liệu. Các giải thuật tiền xử lý tiêu biểu bao gồm: (a) Xử lý dữ liệu bị thiếu/mất: các dữ liệu bị thiếu sẽ được thay thế bởi các giá trị thích hợp.

(b) Khử sự trùng lặp: các đối tượng dữ liệu trùng lặp sẽ bị loại bỏ đi. Kỹ thuật này không được sử dụng cho các tác vụ có quan tâm đến phân bố dữ liệu. (c) Giảm nhiễu: nhiễu và các đối tượng tách rời (outlier) khỏi phân bố chung sẽ bị loại đi khỏi dữ liệu. (d) Chuẩn hóa: miền giá trị của dữ liệu sẽ được chuẩn hóa.

(e) Rời rạc hóa: các dữ liệu số sẽ được biến đổi ra các giá trị rời rạc. (f) Rút trích và xây dựng đặc trưng mới từ các thuộc tính đã có. (g) Giảm chiều: các thuộc tính chứa ít thông tin sẽ được loại bỏ bớt. Mô hình hóa dữ liệu: Các giải thuật sử dụng các dữ liệu đã được tiền xử lý trong giai đoạn hai để tìm kiếm các qui tắc ẩn và chưa biết.

Công việc quan trọng nhất trong giai đoạn này là lựa chọn kỹ thuật phù hợp để giải quyết các vấn đề đặt ra. Các bài toán được phân loại vào một trong những nhóm bài toán chính trong KPDL dựa trên đặc tả của chúng. Hậu xử lý và đánh giá mô hình: Các mô hình kết quả của giai đoạn ba sẽ được hậu xử lý và đánh giá trong giai đoạn 4. Dựa trên các đánh giá của người dùng sau khi kiểm tra trên các tập thử, các mô hình sẽ được tinh chỉnh và kết hợp lại nếu cần.

Chỉ các mô hình đạt được mức yêu cầu cơ bản của người dùng mới 7 đưa ra triển khai trong thực tế. Trong giai đoạn này, các kết quả được biến đổi từ dạng học thuật sang dạng phù hợp với nghiệp vụ và dễ hiểu hơn cho người dùng. Triển khai tri thức: các mô hình được đưa vào những hệ thống thông tin thực tế dưới dạng các môđun hỗ trợ việc đưa ra quyết định. Mối quan hệ chặt chẽ giữa các giai đoạn trong quá trình KPDL là rất quan trọng cho việc nghiên cứu trong KPDL.

Một giải thuật trong KPDL không thể được phát triển độc lập, không quan tâm đến bối cảnh áp dụng mà thường được xây dựng để giải quyết một mục tiêu cụ thể. Do đó, sự hiểu biết bối cảnh vận dụng là rất cần thiết. Thêm vào đó, các kỹ thuật được sử dụng trong các giai đoạn trước có thể ảnh hưởng đến hiệu quả của các giải thuật sử dụng trong các giai đoạn tiếp theo. Các kỹ thuật khai phá dữ liệu Phân lớp dữ liệu [3] Khái niệm phân lớp dữ liệu được Han và Kamber đưa ra năm 2000.

Phân lớp dữ liệu là xây dựng một mô hình mà có thể phân các đối tượng thành những lớp để dự đoán giá trị bị mất tại một số thuộc tính của dữ liệu hay tiên đoán giá trị của dữ liệu sẽ xuất hiện trong tương lai. Quá trình phân lớp dữ liệu được thực hiện qua hai bước. Bước thứ nhất: Dựa vào tập hợp dữ liệu huấn luyện, xây dựng một mô hình mô tả những đặc trưng của những lớp dữ liệu hoặc những khái niệm, đây là quá trình học có giám sát, học theo mẫu được cung cấp trước. Bước thứ hai: Từ những lớp dữ liệu hoặc những khái niệm đã được xác định trước, dự đoán giá trị của những đối tượng quan tâm.

8 Một kỹ thuật phân lớp dữ liệu được Han và Kamber đưa ra là cây quyết định. Mỗi nút của cây đại diện một quyết định dựa vào giá trị thuộc tính tương ứng. Kỹ thuật này đã được nhiều tác giả nghiên cứu và đưa ra nhiều thuật toán. Phân nhóm dữ liệu [3, 4] Phân nhóm là kỹ thuật khai phá dữ liệu tương tự như phân lớp dữ liệu.

Tuy nhiên, sự phân nhóm dữ liệu là quá trình học không được giám sát, là quá trình nhóm những đối tượng vào trong những lớp tương đương, đến những đối tượng trong một nhóm là tương đương nhau, chúng phải khác với những đối tượng trong những nhóm khác. Trong phân lớp dữ liệu, một bản ghi thuộc về lớp nào là phải xác định trước, trong khi phân nhóm không xác định trước. Trong phân nhóm, những đối tượng được nhóm lại cùng nhau dựa vào sự giống nhau của chúng. Sự giống nhau giữa những đối tượng được xác định bởi những chức năng giống nhau.

Thông thường những sự giống nhau về định lượng như khoảng cách hoặc độ đo khác được xác định bởi những chuyên gia trong lĩnh vực của mình. Đa số các ứng dụng phân nhóm được sử dụng trong sự phân chia thị trường. Với sự phân nhóm khách hàng vào trong từng nhóm, những doanh nghiệp có thể cung cấp những dịch vụ khác nhau tới nhóm khách hàng một cách thuận lợi. Ví dụ, dựa vào chi tiêu, số tiền trong tài khoản và việc rút tiền của khách hàng, một ngân hàng có thể xếp những khách hàng vào những nhóm khác nhau.

Với mỗi nhóm, ngân hàng có thể cho vay những khoản tiền tương ứng cho việc mua nhà, mua xe, … Trong trường hợp này ngân hàng có thể cung cấp những dịch vụ tốt hơn, và cũng chắc chắn rằng tất cả các khoản tiền cho vay đều có thể thu hồi được. 9 Hồi quy (Regression): Là việc học một hàm ánh xạ từ một tập dữ liệu thành một biến dự đoán có giá trị thực. Nhiệm vụ hồi qui tương tự như phân lớp, điểm khác nhau chính là ở chỗ thuộc tính để dự báo là liên tục chứ không rời rạc [4, 5]. Việc dự báo các giá trị số thường được làm bởi các phương pháp thống kê cổ điểm chẳng hạn như hồi qui tuyến tính.

Tuy nhiên, phương pháp mô hình hóa cũng được sử dụng [3, 4]. Ứng dụng của hồi quy là rất nhiều, ví dụ: dự đoán số lượng sinh vật phát quang hiện thời trong khi rừng bằng cách dò tìm vi sóng bằng thiết bị cảm biến từ xa; dự đoán khả năng tử vong của bệnh nhân khi biết các kết quả xét nghiệm chuẩn đoán; dự đoán nhu cầu tiêu thụ một sản phẩm mới bằng một hàm chi tiêu quảng cáo… Tổng hợp (summarization): Là công việc liên quan đến các phương pháp tìm kiếm một mô tả cô đọng cho tập con dữ liệu [3, 5]. Các kỹ thuật tổng hợp thường được áp dụng trong việc phân tích dữ liệu có tính thăm dò và báo cáo tự động. Phát hiện sự thay đổi và độ lệch (change and deviation dectection): Nhiệm vụ này tập trung vào khám phá những thay đổi có ý nghĩa trong dữ liệu dựa vào các giá trị chuẩn hay độ đo đã biết trước, phát hiện độ lệch đáng kể giữa nội dung của tập con dữ liệu và nội dung mong đợi.

Hai mô hình độ lệch thường dùng là lệch theo thời gian và lệch theo nhóm. Độ lệch theo thời gian là sự thay đổi có nghĩa của dữ liệu theo thời gian. Độ lệch theo nhóm là sự khác nhau giữa dữ liệu trong hai tập con dữ liệu, tính cả trường hợp tập con của đối tượng này thuộc tập con kia, nghĩa là xác định dữ liệu trong một nhóm con của đối tượng có khác nhau đáng kể so với toàn bộ đối tượng [3, 4].