Luận Văn: Tìm Kiếm Luật Kết Hợp Trong Cơ Sở Dữ Liệu - ĐH Bách Khoa Hà Nội

Luận văn về các vấn đề tìm kiếm luật kết hợp trong cơ sở dữ liệu. Nghiên cứu chuyên sâu về khai phá luật kết hợp, ứng dụng và thuật toán liên quan.

• Tác giả: Nguyễn Vũ Cương
• Người hướng dẫn: Ts. Trần Đình Khang
• Trường học: Trường Đại Học Bách Khoa Hà Nội
• Chuyên ngành: Công Nghệ Thông Tin
• Đề tài: Một Số Vấn Đề Về Tìm Kiếm Luật Liên Kết Trong Cơ Sở Dữ Liệu
• Loại tài liệu: Luận Văn Thạc Sỹ Khoa Học
• Năm xuất bản: 2005
• Địa điểm: Hà Nội

Tóm tắt

I. Tổng Quan Về Tìm Kiếm Luật Kết Hợp Trong Cơ Sở Dữ Liệu

Thế kỷ XXI đánh dấu bước tiến vượt bậc trong lĩnh vực khoa học và công nghệ. Cuộc cách mạng khoa học kỹ thuật diễn ra mạnh mẽ, tác động đến mọi mặt của đời sống. Việt Nam cũng hòa nhập vào xu thế này, thu thập và lưu trữ một lượng dữ liệu khổng lồ. Trong các cơ sở dữ liệu này ẩn chứa nhiều trí thức có giá trị cần được khám phá. Số lượng dữ liệu lớn vượt quá khả năng phân tích thủ công, đòi hỏi các kỹ thuật phân tích tự động. Nhu cầu tìm kiếm tri thức từ dữ liệu này ngày càng cấp thiết, dẫn đến sự hình thành lĩnh vực khai phá trí thức trong cơ sở dữ liệu (KDD). Đây là một hướng nghiên cứu mới mẻ, ứng dụng cao, và còn nhiều tiềm năng. Khai phá dữ liệu (data mining) giúp chúng ta tìm ra các mối quan hệ, xu hướng và quy luật ẩn sâu trong big data, từ đó đưa ra những quyết định sáng suốt hơn. Theo [7], các phương pháp khai phá dữ liệu được phân chia thành nhiều dạng, tùy thuộc vào mục tiêu và ứng dụng cụ thể. Luận văn này tập trung vào việc tìm hiểu các luật kết hợp trong cơ sở dữ liệu lớn. Mục tiêu là khám phá các mẫu dữ liệu, các mô hình hóa dữ liệu giúp ích cho việc đưa ra quyết định.

1.1. Định Nghĩa và Ý Nghĩa của Luật Kết Hợp

KDD được định nghĩa là quá trình tìm kiếm thông tin hữu ích từ dữ liệu trong cơ sở dữ liệu. Fayyad đề xuất rằng quá trình KDD có thể chia thành các bước: lựa chọn, xử lý, chuyển đổi, tìm kiếm thông tin và diễn giải. Các nhà nghiên cứu tập trung vào tiền trình tìm kiếm thông tin, vì nó chính là sự áp dụng các thuật toán để tìm ra các mô hình từ dữ liệu. Luật kết hợp là một trong những mô hình quan trọng, thể hiện mối quan hệ giữa các tập hợp mục trong cơ sở dữ liệu. Luật kết hợp cho phép chúng ta khám phá các mẫu phổ biến, ví dụ như "nếu khách hàng mua A và B, họ cũng có xu hướng mua C". Những thông tin này có giá trị lớn trong nhiều lĩnh vực, từ business intelligence đến marketing.

1.2. Các Độ Đo Quan Trọng Trong Tìm Kiếm Luật Kết Hợp

Để đánh giá chất lượng của luật kết hợp, người ta sử dụng các độ đo như độ hỗ trợ (support), độ tin cậy (confidence), và độ nâng (lift). Độ hỗ trợ thể hiện tần suất xuất hiện của một tập mục trong cơ sở dữ liệu. Độ tin cậy đo lường khả năng tập mục B xuất hiện khi tập mục A đã xuất hiện. Độ nâng so sánh độ tin cậy của luật kết hợp với tần suất xuất hiện của tập mục B một cách độc lập. Các độ đo này giúp chúng ta chọn ra những luật kết hợp mạnh và có ý nghĩa thực tiễn. Ngưỡng độ hỗ trợ và độ tin cậy tối thiểu thường được sử dụng để lọc ra các luật kết hợp không quan trọng. Việc lựa chọn ngưỡng phù hợp là rất quan trọng, ảnh hưởng đến số lượng và chất lượng của các luật kết hợp được tìm thấy.

1.3. Tiến Trình Khai Phá Luật Kết Hợp Từ Cơ Sở Dữ Liệu

Quá trình khai phá luật kết hợp thường bao gồm hai bước chính: tìm kiếm các tập mục phổ biến (frequent itemsets) và sinh các luật từ các tập mục này. Bước tìm kiếm tập mục phổ biến là bước tốn kém nhất về mặt tính toán. Các giải thuật như Apriori và FP-Growth được sử dụng để giải quyết vấn đề này. Sau khi tìm được các tập mục phổ biến, các luật kết hợp được sinh ra bằng cách chia tập mục thành hai phần: phần tiền đề (antecedent) và phần hệ quả (consequent). Độ tin cậy của mỗi luật kết hợp được tính toán, và chỉ những luật có độ tin cậy vượt quá ngưỡng cho phép mới được giữ lại. Quá trình này đòi hỏi sự kết hợp giữa kiến thức về lĩnh vực ứng dụng và các kỹ thuật khai phá dữ liệu để đảm bảo tìm ra những luật kết hợp có giá trị.

II. Các Thuật Toán Tìm Kiếm Luật Kết Hợp Hiệu Quả Nhất

Nhiều thuật toán đã được phát triển để tìm kiếm luật kết hợp trong cơ sở dữ liệu. Hai trong số các giải thuật phổ biến nhất là Apriori và FP-Growth. Apriori là một giải thuật cổ điển, sử dụng phương pháp sinh và kiểm tra để tìm các tập mục phổ biến. FP-Growth là một giải thuật hiệu quả hơn, sử dụng cấu trúc cây FP-tree để nén cơ sở dữ liệu và khai phá luật kết hợp mà không cần sinh các ứng viên. Ngoài ra, còn có các giải thuật khác như Eclat và Partition, mỗi giải thuật có ưu và nhược điểm riêng, phù hợp với các loại cơ sở dữ liệu và yêu cầu khác nhau. Việc lựa chọn thuật toán phù hợp là rất quan trọng để đảm bảo hiệu suất và độ chính xác của quá trình khai phá luật kết hợp.

2.1. Phân Tích Chi Tiết Thuật Toán Apriori và Ứng Dụng

Giải thuật Apriori là một giải thuật quan trọng trong khai phá luật kết hợp. Nó dựa trên nguyên tắc: nếu một tập mục không phổ biến, thì mọi tập cha của nó cũng không phổ biến. Apriori sử dụng nguyên tắc này để giảm số lượng các tập mục ứng viên cần kiểm tra. Giải thuật hoạt động theo từng vòng lặp. Ở mỗi vòng, nó sinh ra các tập mục ứng viên có kích thước lớn hơn 1 so với vòng trước, sau đó quét cơ sở dữ liệu để tính độ hỗ trợ của các ứng viên. Chỉ những ứng viên có độ hỗ trợ vượt quá ngưỡng tối thiểu mới được giữ lại. Ưu điểm của Apriori là đơn giản và dễ hiểu. Tuy nhiên, nó có thể tốn kém về mặt tính toán khi cơ sở dữ liệu lớn và ngưỡng độ hỗ trợ thấp.

2.2. Ưu Nhược Điểm của Thuật Toán FP Growth So Với Apriori

FP-Growth là một giải thuật hiệu quả hơn Apriori, đặc biệt là đối với các cơ sở dữ liệu lớn. Thay vì sinh và kiểm tra các tập mục ứng viên, FP-Growth sử dụng cấu trúc cây FP-tree để nén cơ sở dữ liệu. Cây FP-tree lưu trữ thông tin về tần suất xuất hiện của các mục, cho phép khai phá luật kết hợp mà không cần quét cơ sở dữ liệu nhiều lần. FP-Growth thường nhanh hơn Apriori vì nó tránh được việc sinh quá nhiều ứng viên. Tuy nhiên, việc xây dựng cây FP-tree có thể tốn bộ nhớ, đặc biệt là đối với các cơ sở dữ liệu có nhiều mục khác nhau.

2.3. So Sánh Các Giải Thuật Khai Phá Luật Kết Hợp Khác

Ngoài Apriori và FP-Growth, còn có các giải thuật khác như Eclat và Partition. Eclat sử dụng biểu diễn dọc của cơ sở dữ liệu, trong đó mỗi mục được liên kết với danh sách các giao dịch chứa mục đó. Eclat có thể hiệu quả hơn Apriori trong một số trường hợp, đặc biệt là khi cơ sở dữ liệu có mật độ cao. Partition chia cơ sở dữ liệu thành các phân vùng nhỏ hơn, khai phá luật kết hợp trong mỗi phân vùng, sau đó kết hợp các kết quả lại. Partition có thể song song hóa dễ dàng, giúp tăng tốc quá trình khai phá luật kết hợp trên các cơ sở dữ liệu rất lớn. Việc lựa chọn giải thuật phù hợp phụ thuộc vào đặc điểm của cơ sở dữ liệu và yêu cầu về hiệu suất.

III. Giải Pháp Nâng Cao Hiệu Quả Tìm Kiếm Luật Kết Hợp

Để tối ưu hóa thuật toán tìm kiếm luật kết hợp, cần xem xét nhiều yếu tố. Giảm số lượng ứng viên là một phương pháp quan trọng. Sử dụng cấu trúc dữ liệu hiệu quả như FP-tree giúp giảm thời gian quét cơ sở dữ liệu. Song song hóa giải thuật là một cách khác để tăng tốc quá trình. Bên cạnh đó, việc lựa chọn ngưỡng độ hỗ trợ và độ tin cậy phù hợp cũng ảnh hưởng lớn đến hiệu quả. Các kỹ thuật mô hình hóa dữ liệu và tiền xử lý có thể giúp giảm kích thước cơ sở dữ liệu và loại bỏ nhiễu, từ đó cải thiện hiệu suất của các giải thuật khai phá luật kết hợp.

3.1. Kỹ Thuật Giảm Số Lượng Tập Ứng Viên Trong Apriori

Trong giải thuật Apriori, việc giảm số lượng tập ứng viên là rất quan trọng để cải thiện hiệu suất. Các kỹ thuật như AprioriTID và AprioriHybrid được phát triển để giải quyết vấn đề này. AprioriTID lưu trữ thông tin về các giao dịch chứa các tập mục phổ biến, giúp giảm thời gian quét cơ sở dữ liệu. AprioriHybrid kết hợp Apriori và AprioriTID để tận dụng ưu điểm của cả hai giải thuật. Ngoài ra, các kỹ thuật như sử dụng hàm băm và cấu trúc cây cũng có thể được sử dụng để giảm số lượng tập ứng viên.

3.2. Phương Pháp Tối Ưu Hóa Cấu Trúc FP Tree trong FP Growth

Cấu trúc cây FP-tree đóng vai trò quan trọng trong hiệu suất của giải thuật FP-Growth. Việc tối ưu hóa cấu trúc cây này có thể giúp giảm thời gian xây dựng và duyệt cây. Các phương pháp như sử dụng danh sách liên kết và cấu trúc cây con được sử dụng để giảm kích thước cây FP-tree. Ngoài ra, việc sắp xếp các mục theo thứ tự tần suất giảm dần cũng giúp giảm thời gian xây dựng cây.

3.3. Áp Dụng Tính Toán Song Song Để Tăng Tốc Độ Khai Phá

Với cơ sở dữ liệu rất lớn, tính toán song song là một phương pháp hiệu quả để tăng tốc độ khai phá luật kết hợp. Các giải thuật như Partition và PWC được thiết kế để chạy trên nhiều bộ xử lý hoặc máy tính. Partition chia cơ sở dữ liệu thành các phân vùng nhỏ hơn và khai phá luật kết hợp trong mỗi phân vùng song song. PWC sử dụng cấu trúc cây song song để khai phá luật kết hợp. Việc sử dụng các công nghệ như MapReduce và Spark cũng giúp triển khai các giải thuật khai phá luật kết hợp song song trên các cụm máy tính.

IV. Ứng Dụng Luật Kết Hợp Vào Bài Toán Thực Tế và Ví Dụ Cụ Thể

Ứng dụng luật kết hợp rất đa dạng trong nhiều lĩnh vực. Trong bán lẻ, nó giúp phân tích hành vi mua hàng của khách hàng, từ đó đưa ra các chiến lược marketing và khuyến mãi hiệu quả. Trong y tế, nó giúp tìm ra các mối liên hệ giữa các triệu chứng và bệnh tật, hỗ trợ chẩn đoán và điều trị. Trong tài chính, nó giúp phát hiện các giao dịch gian lận và rủi ro tín dụng. Trong viễn thông, nó giúp phân tích hành vi sử dụng dịch vụ của khách hàng, từ đó cải thiện chất lượng dịch vụ và tăng doanh thu. Các ứng dụng luật kết hợp ngày càng trở nên quan trọng trong thời đại big data.

4.1. Phân Tích Giỏ Hàng Market Basket Analysis Trong Bán Lẻ

Phân tích giỏ hàng là một ứng dụng điển hình của luật kết hợp trong bán lẻ. Mục tiêu là tìm ra các sản phẩm thường được mua cùng nhau. Ví dụ, nếu luật kết hợp "khách hàng mua tã giấy cũng có xu hướng mua sữa bột" được tìm thấy, các nhà bán lẻ có thể đặt hai sản phẩm này gần nhau hoặc đưa ra các chương trình khuyến mãi kết hợp để tăng doanh thu. Phân tích giỏ hàng giúp hiểu rõ hơn về hành vi mua hàng của khách hàng, từ đó tối ưu hóa bố trí cửa hàng và chiến lược marketing.

4.2. Ứng Dụng Luật Kết Hợp Trong Lĩnh Vực Y Tế và Chăm Sóc Sức Khỏe

Luật kết hợp có thể được sử dụng trong y tế để tìm ra các mối liên hệ giữa các triệu chứng, bệnh tật, và phương pháp điều trị. Ví dụ, nếu luật kết hợp "bệnh nhân bị sốt và ho thường bị viêm phổi" được tìm thấy, các bác sĩ có thể chú ý hơn đến các bệnh nhân có các triệu chứng này. Luật kết hợp cũng có thể được sử dụng để tìm ra các tác dụng phụ của thuốc và các tương tác thuốc-thuốc. Các ứng dụng này giúp cải thiện chẩn đoán và điều trị, từ đó nâng cao chất lượng chăm sóc sức khỏe.

4.3. Sử Dụng Luật Kết Hợp Để Phát Hiện Gian Lận Trong Tài Chính

Trong lĩnh vực tài chính, luật kết hợp có thể được sử dụng để phát hiện các giao dịch gian lận. Ví dụ, nếu luật kết hợp "các giao dịch lớn được thực hiện vào ban đêm và từ các địa điểm không quen thuộc thường là gian lận" được tìm thấy, các ngân hàng có thể sử dụng nó để phát hiện và ngăn chặn các giao dịch đáng ngờ. Luật kết hợp cũng có thể được sử dụng để đánh giá rủi ro tín dụng và dự đoán khả năng vỡ nợ của khách hàng. Các ứng dụng này giúp bảo vệ hệ thống tài chính và giảm thiểu thiệt hại cho các tổ chức tài chính.

V. Đánh Giá Hiệu Quả Và Hướng Phát Triển Nghiên Cứu Tiếp Theo

Việc đánh giá hiệu quả của các giải thuật tìm kiếm luật kết hợp là rất quan trọng. Các độ đo như thời gian chạy, bộ nhớ sử dụng, và độ chính xác của các luật kết hợp được sử dụng để so sánh các giải thuật. Các hướng phát triển nghiên cứu tiếp theo bao gồm việc phát triển các giải thuật khai phá luật kết hợp hiệu quả hơn cho các cơ sở dữ liệu rất lớn và phức tạp, nghiên cứu các phương pháp kết hợp luật kết hợp với các kỹ thuật khai phá dữ liệu khác, và ứng dụng luật kết hợp vào các lĩnh vực mới.

5.1. Các Tiêu Chí Đánh Giá Hiệu Quả Thuật Toán Tìm Kiếm Luật

Các tiêu chí đánh giá hiệu quả thuật toán tìm kiếm luật kết hợp bao gồm: thời gian chạy (thời gian cần thiết để tìm ra các luật kết hợp), bộ nhớ sử dụng (lượng bộ nhớ cần thiết để chạy giải thuật), độ chính xác (khả năng tìm ra các luật kết hợp có ý nghĩa và loại bỏ các luật không liên quan), và khả năng mở rộng (khả năng xử lý các cơ sở dữ liệu lớn). Các độ đo như độ hỗ trợ, độ tin cậy, và độ nâng được sử dụng để đánh giá độ chính xác của các luật kết hợp. Việc lựa chọn các tiêu chí đánh giá phù hợp phụ thuộc vào mục tiêu và yêu cầu của từng ứng dụng.

5.2. Thách Thức Và Hướng Nghiên Cứu Tìm Kiếm Luật Kết Hợp

Các thách thức trong tìm kiếm luật kết hợp bao gồm: xử lý các cơ sở dữ liệu rất lớn và phức tạp, tìm ra các luật kết hợp có ý nghĩa trong số lượng lớn các luật được sinh ra, và kết hợp luật kết hợp với các kỹ thuật khai phá dữ liệu khác. Các hướng nghiên cứu tiếp theo bao gồm: phát triển các giải thuật khai phá luật kết hợp hiệu quả hơn cho big data, nghiên cứu các phương pháp lọc và lựa chọn luật kết hợp quan trọng, và phát triển các framework tích hợp luật kết hợp với các mô hình dự đoán và phân loại.

VI. Kết Luận và Triển Vọng Phát Triển Của Luật Kết Hợp Hiện Nay

Luận văn đã trình bày một số vấn đề về tìm kiếm luật kết hợp trong cơ sở dữ liệu. Các giải thuật Apriori và FP-Growth là hai phương pháp phổ biến để giải quyết vấn đề này. Các kỹ thuật tối ưu hóa và tính toán song song giúp tăng tốc quá trình khai phá luật kết hợp. Ứng dụng luật kết hợp rất đa dạng trong nhiều lĩnh vực. Tuy nhiên, vẫn còn nhiều thách thức và cơ hội để nghiên cứu và phát triển luật kết hợp hơn nữa. Trong tương lai, luật kết hợp sẽ tiếp tục đóng vai trò quan trọng trong việc khai phá trí thức từ big data.

6.1. Tổng Kết Các Kết Quả Nghiên Cứu Về Tìm Kiếm Luật Kết Hợp

Nghiên cứu về tìm kiếm luật kết hợp đã đạt được nhiều tiến bộ trong những năm gần đây. Các giải thuật mới và hiệu quả hơn đã được phát triển, giúp xử lý các cơ sở dữ liệu lớn hơn và phức tạp hơn. Các kỹ thuật tối ưu hóa và tính toán song song giúp tăng tốc quá trình khai phá luật kết hợp. Các ứng dụng mới của luật kết hợp tiếp tục được khám phá trong nhiều lĩnh vực.

6.2. Hướng Nghiên Cứu Mở Rộng Liên Quan Đến Luật Kết Hợp

Các hướng nghiên cứu mở rộng liên quan đến luật kết hợp bao gồm: khai phá luật kết hợp từ dữ liệu luồng (data stream), khai phá luật kết hợp từ dữ liệu không chắc chắn (uncertain data), khai phá luật kết hợp từ dữ liệu không đồng nhất (heterogeneous data), và khai phá luật kết hợp từ dữ liệu không cân bằng (imbalanced data). Ngoài ra, việc nghiên cứu các phương pháp kết hợp luật kết hợp với các kỹ thuật học máy khác (ví dụ như học sâu) cũng là một hướng nghiên cứu đầy tiềm năng.

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

Chương IL Tin kiểm luật liên kết với các tập mục có lrọng số Chương II. Một số vận dé nang cao Chương IV. Vị dụ minh họa. Trong quá trình thực hiện để án nảy, tặc dù đã rất có gắng, song không thể tránh khỏi những sai sót, em rất mong nhận dược sự chí bảo và giúp đỡ từ phía thấy cỗ và cáo bạn.

description cho các ứng dụng tìm kiếm dữ liệu cụ thể khác nhau thi sẽ khác nhau rất nhiều. Theo [7], các phương pháp khai phá đữ liệu được phân chia thành các dạng như sau: Phan lop — Classification: Phân lớp là việc xem xét một hảm số ảnh xạ các đơn vị dữ liệu(đata item) với một trong số các lớp đã được định nghĩa trước. Ví dụ của các phương pháp phân lớp được sử dụng như một phản của các ứng dụng khai phá trì thức bao gồm việc phân loại các xu hướng trong thị trường tài chính vả việc xác Debt Income Hinh 1.4: Mét vi du về biên giới phân lớp thông qua các bộ lọc phân lớp không tuyến tính(ví dụ như mạng nơ-ron) đỉnh tự động các đối tượng theo dõi trong các hệ cơ sở đữ liệu ảnh lớn.4 chỉ ra việc phân lớp dữ liệu tài khoản nợ thành 2 lớp khác nhau. Chúý rằng, không cân thiết phải phân chia các lớp một cách hoàn hảo bằng việc sử dụng, các ranh giới tuyến tính.

Ngân hảng có thê sử dụng các vùng phân lớp đề quyết định 9 1.3 KDD và các lĩnh vực có liên quan KDD là một lĩnh vực liên quan tới nhiều ngành khác nhau, cụ thể là thống kê, học máy, cơ sở đữ liệu, giải thuật, tính toán hiện năng cao và tính toán song song, thu thập trí thức cho hệ chuyên gia, hiện thực hóa đữ liệu v. Hệ thống KDD thường được xây dựng dựa trên các phương pháp, giải thuật, và kỹ thuật từ những lĩnh vực. khác nhan nay. Muc đích đuy nhất là kết xuất được trị thức từ đứ liệu trong các cơ sở dữ liệu lớn.

Lĩnh vực học máy và nhận dạng ruẫu chồng lấp với KDD tương việc nghiên cửu lý thuyết và các giải thuật để lẫy ra được các mẫu và các mô hình tử dữ liệu(các phương pháp tim kiểm dữ liện) KDD tập trưng vào việc mở rộng nhùng lý thuyết và giải thuật nảy cho các bải toản tim kiếm những mẫu đặc biệt(có thể hiểu là những trị thức hữu ich va dang quan tam) trong các tập đũ liệu thực lớn. KDD cũng có nhiều điểm chúng với khoa học thông kẻ, đặc biệt là việc phân tích đữ liệu. Hệ thống KDD thường được nhúng các thủ tục thống kẻ để maô hình hóa đủ liệu và xứ lý nhiễu ong toàn bộ các ứng dụng nền trị thức Kham phá Một lĩnh vực khác có liên quan là kho dữ liệu - data warehousing. Kho dit ligu gan đây cỏ xu hưởng là một hệ thông théng tin quan ly Management information System phd bién cho việc thu thập và xử lý dữ liệu giao địch và có thể thu thập, xử lý online.

Một hướng tiếp cận phô biển khác trong việc phân tích cắc kho dữ liêu, đ là QUAP - online analptieal processing, Các tools QLAP tập trung vào việc phần tích dữ liệu đa chiều, đây là loại dũ liệu cao cấp hơn so với SỢI. Chúng la gừng công nhận việc tìm kiếm tri thức và OLAP lả các mặt liên quan tới nhau của một thẻ hệ rnởi các tool xứ lý và kết xuất thông tin thông minh, 1I. Các phương pháp khai phá dữ liệu Tai mục tiêu của việc tim kiếm đữ liệu trong thực tế có xu hướng lâ có thê đự đoán duve - prediction và cô thể tuiều tả dược - description. Prediclion sử dụng các biên hoặc các trường dữ liệu trong cơ sở dữ liệu để dự đoán các giả trị chưa biết hoặc các giả trị tương lại của các biến khác m on theo di.

Description lập (rung vào các mẫu có thể diễn giải được dễ miều tả đữ liệu. Tâm quan trọng của prediction và 8 1.3 KDD và các lĩnh vực có liên quan KDD là một lĩnh vực liên quan tới nhiều ngành khác nhau, cụ thể là thống kê, học máy, cơ sở đữ liệu, giải thuật, tính toán hiện năng cao và tính toán song song, thu thập trí thức cho hệ chuyên gia, hiện thực hóa đữ liệu v. Hệ thống KDD thường được xây dựng dựa trên các phương pháp, giải thuật, và kỹ thuật từ những lĩnh vực. khác nhan nay.

Muc đích đuy nhất là kết xuất được trị thức từ đứ liệu trong các cơ sở dữ liệu lớn. Lĩnh vực học máy và nhận dạng ruẫu chồng lấp với KDD tương việc nghiên cửu lý thuyết và các giải thuật để lẫy ra được các mẫu và các mô hình tử dữ liệu(các phương pháp tim kiểm dữ liện) KDD tập trưng vào việc mở rộng nhùng lý thuyết và giải thuật nảy cho các bải toản tim kiếm những mẫu đặc biệt(có thể hiểu là những trị thức hữu ich va dang quan tam) trong các tập đũ liệu thực lớn. KDD cũng có nhiều điểm chúng với khoa học thông kẻ, đặc biệt là việc phân tích đữ liệu. Hệ thống KDD thường được nhúng các thủ tục thống kẻ để maô hình hóa đủ liệu và xứ lý nhiễu ong toàn bộ các ứng dụng nền trị thức Kham phá Một lĩnh vực khác có liên quan là kho dữ liệu - data warehousing.

Kho dit ligu gan đây cỏ xu hưởng là một hệ thông théng tin quan ly Management information System phd bién cho việc thu thập và xử lý dữ liệu giao địch và có thể thu thập, xử lý online. Một hướng tiếp cận phô biển khác trong việc phân tích cắc kho dữ liêu, đ là QUAP - online analptieal processing, Các tools QLAP tập trung vào việc phần tích dữ liệu đa chiều, đây là loại dũ liệu cao cấp hơn so với SỢI. Chúng la gừng công nhận việc tìm kiếm tri thức và OLAP lả các mặt liên quan tới nhau của một thẻ hệ rnởi các tool xứ lý và kết xuất thông tin thông minh, 1I. Các phương pháp khai phá dữ liệu Tai mục tiêu của việc tim kiếm đữ liệu trong thực tế có xu hướng lâ có thê đự đoán duve - prediction và cô thể tuiều tả dược - description.

Prediclion sử dụng các biên hoặc các trường dữ liệu trong cơ sở dữ liệu để dự đoán các giả trị chưa biết hoặc các giả trị tương lại của các biến khác m on theo di. Description lập (rung vào các mẫu có thể diễn giải được dễ miều tả đữ liệu. Tâm quan trọng của prediction và 8 Nội dung Chương I. Khái niệm cơ bản về khai phá dữ liệu và tìm kiếm luật liên kết I.

Tỗng quan về khai phá dữ liệu Ngày nay, máy tính đã được sử dụng rông rãi trong nhiêu lĩnh vực. Khả năng lưu trữ nhanh, đáng tin cậy và không hạn chẻ của máy tính tạo ra cho người sử dụng một môi trường hoàn hảo đề thu thập vả lưu trữ một khói lượng thông tin không lỏ Máy tỉnh cũng được dùng đề tìm kiếm những thông tin hữu ích trong hàng loạt các dữ liêu Đây chính là quá trình khai phả trí thúc trong cơ sở dữ liệu (KDD- Knowledge discovery in database) hay tim kiêm thông tin.1 Định nghĩa KDD KDD được định nghĩa là quả trình tìm kiếm thông tin có thể sử dụng được từ những dữ liệu trong CSDL. Fayyad gợi ý rằng quá trình KDD có thê chia ra làm các bước, như được chỉ ra trong hình 1. Toản bộ quá trình của KDD bao gồm các bước lựa chọn, xử lý, chuyển đổi, tìm kiếm thông tin và diễn giải hay kết luận.

Các nhà nghiên cứu tập trung vào tiền trình tìm kiểm thông tin, vi nó chính là sự ap dụng các thuật toán để tìm ra các mô hình từ các dữ liệu, và đây là không phải là một công việc đơn giản lsieprstiiot‹ Evahation balao|za] Paigras Dabs Minin OD Transformed Data Hình 1. : Tiên trình KDD “ sử dụng đầu cuối có thê quan tâm tới việc hiểu biết mô hinh nhiều hơn là khả năng phản đoán của nó). Data organized by feng cenmten The KDD Process target CN datas Data warehousing ——— Select phing Sample ata Technique’ HNrising) [ nolEttminat data Ne Transfo ‘ed|_, Find importani| VAme [ÔN Tem” [| NướMe | > ates ï Ệ £ Select DM Select DM Extract Test Refine task (8) *)| method (s) *| knowledge (>) knowledge knowledge ‘Transform to represttation Hình 1.2: Các nhiệm vụ chinh trong tién trinh KDD «Tìm kiểm dữ liệu đề lây ra được các mâu hoặc mô hình - Data mining to extract patterns/models: tim kiểm các mẫu được quan tâm trong một mẫu biểu diễn riêng hoặc một tập các biểu diễn khác nhau: luật phản lớp hay cây, hổi quy, hoặc phan lớp. Người dùng có thể tác động hiệu quả tới các phương pháp tìm kiếm dữ liệu bằng việc thực hiện chính xác các bước ở trên.

® Diễn giải và đánh gia cac maw/mé hinh - Interpretation and evaluation of pattern/models e Thống nhất dữ liệu được khai pha - Consolidating discovered knowledge phối hợp những trị thức nảy trong các hệ thống hoặc diễn giải đơn giản trí thức đỏ bằng tài liệu. Điều này bao gồm cả việc kiểm tra và phân tích những xung đột tiểm năng với những trí thức đã có. Mở đầu lệ kỳ XX dã qua di dánh một dấu sơn chói lợi trong lĩnh vực khoa học công nghệ. Cách mạng khoa học kỹ thuật điển ra mọi lúc, mọi nơi, trên nhiễu lĩnh vực cửa dời sống.

Và Việt Nam cũng không nằm ngoài qui luật chưng đó. Trong quả trình phát triển nảy, chủng ta đã thu thập được một khỏi lượng rất lớn đữ liệu. Và trong chính những cơ sở đữ liệu này tiềm ấn rất nhiều trị thức có ích mà can người chưa khám phả. Ngoài ra, số lượng dữ liệu lớn dược thu thập vượt quá khả năng, phân tích của chủng ta mà không sứ dụng những kỹ thuật phân tích tu déng.

Do vay đã có một nhu câu rất thiết thực là tìm kiêm được những trị thức trong những nui dir liệu này. Nhu cầu này ngày cảng cấp thiết và dã dẫn tới sự hình thành của xnột lĩnh vực mới, đó là khai phá trí thức trong cơ sở đữ liệu — Knowledge discovery in database(KDD). Đây là một hướng nghiên cửu còn khá mới mẻ, có tính ứng dụng, thue tiền cao và con nhiều bài Loài mở. Xuất phát từ thực tế nói trên, và với mục dich tim hiểu việc tim ra các luật liên kết trong cơ sở đít liệu cỡ lớn, em đã quyết.

định lựa chơn để tài “Một số vẫn để về tìm kiếm luật liền kết trong cơ sở đữ liệu”.