Luận văn thạc sĩ tìm hiểu một số thuật toán khai phá tập mục lợi ích cao và ứng dụng

Luận văn thạc sĩ đi sâu vào các thuật toán khai phá tập mục lợi ích cao, từ Apriori đến HUI-Miner, ứng dụng phát hiện lợi nhuận cao trong bán hàng.

2016

84
0
0

Phí lưu trữ

30 Point

Tóm tắt

I. Khai phá Tập mục Lợi ích cao Tổng quan và Tầm quan trọng

Khai phá dữ liệu là một lĩnh vực quan trọng, giúp trích xuất tri thức ẩn và có giá trị từ các tập dữ liệu lớn. Một trong những nhiệm vụ cốt lõi là khai phá luật kết hợp, khởi nguồn từ bài toán tìm kiếm các tập mục phổ biến. Tuy nhiên, mô hình truyền thống chỉ tập trung vào tần suất xuất hiện của các mục, bỏ qua một yếu tố kinh doanh quan trọng: lợi nhuận. Bài toán khai phá tập mục lợi ích cao (High-Utility Itemset Mining - HUIM) ra đời để giải quyết hạn chế này. Thay vì chỉ đếm số lần xuất hiện, HUIM xem xét cả số lượng bán ra và lợi nhuận đơn vị của từng sản phẩm. Mục tiêu là phát hiện những nhóm mặt hàng mang lại lợi nhuận cao nhất, ngay cả khi chúng không được bán thường xuyên. Phương pháp này mang lại giá trị thực tiễn to lớn, đặc biệt trong phân tích giỏ hàng, quản lý chuỗi cung ứng và hoạch định chiến lược kinh doanh. Nó cho phép doanh nghiệp tập trung vào các sản phẩm và nhóm sản phẩm có lợi nhuận cao, từ đó tối ưu hóa doanh thu và hiệu quả hoạt động. Việc chuyển đổi từ phân tích tần suất sang phân tích lợi ích đánh dấu một bước tiến quan trọng, giúp các quyết định kinh doanh trở nên sắc bén và dựa trên dữ liệu hiệu quả hơn.

1.1. Từ tập mục phổ biến đến bài toán phân tích lợi ích

Bài toán khai phá tập mục phổ biến do Agrawal đề xuất năm 1993 tập trung vào việc tìm các tập hợp mục xuất hiện cùng nhau vượt một ngưỡng hỗ trợ tối thiểu (minsup). Mô hình này rất hữu ích nhưng có hạn chế lớn: nó coi tất cả các mục là như nhau và chỉ quan tâm đến tần suất. Trong thực tế, một mặt hàng xa xỉ bán ít lần có thể mang lại lợi nhuận cao hơn nhiều so với một mặt hàng tiêu dùng nhanh bán thường xuyên. Nhận thấy điều này, các nhà nghiên cứu đã mở rộng bài toán. Nghiên cứu của H. Yao và cộng sự vào năm 2004 đã chính thức đề xuất mô hình khai phá tập mục lợi ích cao. Mô hình này đưa vào hai yếu tố mới: giá trị khách quan (số lượng bán) và giá trị chủ quan (lợi nhuận trên mỗi đơn vị). Sự thay đổi này không chỉ là một cải tiến về mặt kỹ thuật mà còn thay đổi hoàn toàn mục tiêu khai phá: từ việc tìm kiếm 'sự phổ biến' sang tìm kiếm 'giá trị'. Điều này giúp các phân tích gần gũi hơn với mục tiêu kinh doanh, chẳng hạn như xác định các combo sản phẩm sinh lời cao nhất để xây dựng chương trình khuyến mãi hiệu quả.

1.2. Các khái niệm cốt lõi lợi ích khách quan và chủ quan

Để hiểu rõ về khai phá tập mục lợi ích cao, cần nắm vững các khái niệm cơ bản. Giá trị khách quan (objective value) là số lượng của một mục trong một giao dịch cụ thể, ví dụ, số lượng sản phẩm A được bán trong hóa đơn T1. Đây là dữ liệu có sẵn trong cơ sở dữ liệu giao dịch. Giá trị chủ quan (subjective value) là lợi nhuận hoặc giá trị được gán cho mỗi đơn vị của một mục. Giá trị này thường được các chuyên gia kinh doanh xác định và lưu trữ trong một bảng riêng gọi là bảng lợi ích. Lợi ích của một mục trong một giao dịch được tính bằng tích của giá trị khách quan và giá trị chủ quan. Tài liệu nghiên cứu định nghĩa: “Lợi ích của tập mục X tại giao tác Tq, ký hiệu u(X, Tq) là tổng lợi ích của tất cả các mục ip thuộc X tại giao tác Tq”. Tổng lợi ích của một tập mục trên toàn bộ cơ sở dữ liệu là tổng lợi ích của nó trong tất cả các giao dịch chứa nó. Một tập mục được gọi là 'lợi ích cao' nếu tổng lợi ích của nó vượt qua một ngưỡng lợi ích tối thiểu (minutil) do người dùng xác định.

II. Thách thức cốt lõi khi Khai phá Tập mục Lợi ích cao là gì

Việc chuyển đổi từ mô hình tần suất sang mô hình lợi ích mang lại nhiều giá trị nhưng cũng đi kèm với những thách thức tính toán đáng kể. Vấn đề lớn nhất trong khai phá tập mục lợi ích cao là sự thiếu vắng của tính chất phản đơn điệu (anti-monotone property), vốn là nền tảng của các thuật toán hiệu quả như Apriori trong khai phá tập mục phổ biến. Tính chất này phát biểu rằng nếu một tập mục là phổ biến, thì mọi tập con của nó cũng phải phổ biến. Điều này cho phép các thuật toán cắt tỉa không gian tìm kiếm một cách hiệu quả. Tuy nhiên, trong HUIM, một tập mục có lợi ích thấp có thể chứa một tập con có lợi ích cao, và một tập cha của một tập mục lợi ích thấp vẫn có thể trở thành một tập mục lợi ích cao. Ví dụ, tập {kim cương} có thể có lợi ích thấp, nhưng tập {nhẫn, kim cương} lại có thể có lợi ích rất cao. Sự thiếu vắng tính chất này khiến việc áp dụng trực tiếp các phương pháp cắt tỉa truyền thống trở nên bất khả thi, dẫn đến nguy cơ bùng nổ tổ hợp và chi phí tính toán khổng lồ khi phải duyệt qua một không gian tìm kiếm cực lớn.

2.1. Vấn đề thiếu vắng tính chất Apriori trong bài toán lợi ích

Trong khai phá tập mục phổ biến, tính chất Apriori là một nguyên lý vàng. Nó đảm bảo rằng nếu một tập mục không phổ biến, mọi tập cha chứa nó cũng sẽ không phổ biến. Điều này cho phép loại bỏ một lượng lớn các ứng viên không cần thiết ngay từ đầu. Tuy nhiên, ràng buộc lợi ích không tuân theo quy tắc này. Luận văn gốc chỉ rõ: “Đáng tiếc là các tập mục lợi ích cao không thỏa mãn tính chất Apriori”. Lý do là lợi ích của một tập mục không chỉ phụ thuộc vào sự hiện diện của các mục mà còn vào số lượng và lợi nhuận đơn vị của chúng. Một mục có lợi nhuận rất cao có thể biến một tập mục từ lợi ích thấp thành lợi ích cao khi được thêm vào. Ví dụ, tập {bánh mì, sữa} có thể có lợi ích thấp, nhưng khi thêm mục {rượu vang cao cấp}, tập {bánh mì, sữa, rượu vang cao cấp} có thể vượt qua ngưỡng lợi ích tối thiểu. Do đó, không thể loại bỏ một ứng viên chỉ vì một tập con của nó có lợi ích thấp. Đây là rào cản chính khiến các thuật toán khai phá tập mục lợi ích cao phải được thiết kế theo cách tiếp cận hoàn toàn khác.

2.2. Nguy cơ bùng nổ không gian tìm kiếm các tập mục ứng viên

Vì không thể áp dụng cơ chế cắt tỉa của Apriori, các thuật toán khai phá tập mục lợi ích cao đời đầu phải đối mặt với một không gian tìm kiếm khổng lồ. Với n mục dữ liệu, có tổng cộng 2^n tập mục con cần được xem xét. Nếu không có một chiến lược thông minh để giảm số lượng ứng viên, việc tính toán sẽ trở nên không khả thi, đặc biệt với các cơ sở dữ liệu lớn hàng triệu giao dịch và hàng nghìn mục sản phẩm. Các phương pháp ban đầu thường phải tạo ra một số lượng lớn các tập mục ứng viên và sau đó duyệt toàn bộ cơ sở dữ liệu để tính toán lợi ích chính xác của từng ứng viên. Quá trình này cực kỳ tốn kém về cả thời gian và bộ nhớ. Thách thức đặt ra là phải tìm ra một ràng buộc mới, một tính chất thay thế có thể giúp giới hạn không gian tìm kiếm mà không làm mất đi các tập mục lợi ích cao thực sự. Đây chính là tiền đề cho sự ra đời của các khái niệm như lợi ích TWU và các cấu trúc dữ liệu tiên tiến như utility-list.

III. Hướng dẫn Thuật toán Hai pha để khai phá tập mục lợi ích cao

Để giải quyết thách thức về tính chất phản đơn điệu, thuật toán Hai pha (Two-Phase) được đề xuất như một giải pháp đột phá. Thuật toán này giới thiệu một khái niệm quan trọng là Lợi ích Giao tác Có trọng số (Transaction-Weighted Utility - TWU). TWU của một tập mục được định nghĩa là tổng lợi ích của tất cả các giao dịch chứa nó. Điểm mấu chốt là TWU luôn lớn hơn hoặc bằng lợi ích thực tế của tập mục đó (u(X) ≤ twu(X)), do đó nó đóng vai trò như một cận trên. Quan trọng hơn, TWU lại tuân thủ tính chất phản đơn điệu. Dựa trên nguyên lý này, thuật toán hoạt động theo hai pha rõ rệt. Pha 1 sử dụng một thuật toán tương tự Apriori để tìm tất cả các tập mục có TWU cao (vượt qua ngưỡng lợi ích tối thiểu). Vì TWU có tính chất phản đơn điệu, không gian tìm kiếm có thể được cắt tỉa hiệu quả. Pha 2 chỉ cần duyệt lại cơ sở dữ liệu một lần nữa để tính toán lợi ích thực tế của các tập mục ứng viên tiềm năng đã được tìm thấy ở Pha 1, sau đó loại bỏ những tập mục không đạt ngưỡng. Cách tiếp cận này giúp giảm đáng kể số lượng ứng viên cần xem xét.

3.1. Cơ sở lý thuyết của lợi ích TWU Transaction Weighted Utility

Khái niệm lợi ích TWU là nền tảng của thuật toán Hai pha. Y.Liu đã định nghĩa: “Lợi ích TWU của tập mục X, ký hiệu twu(X), là tổng lợi ích của tất cả các giao tác chứa X trong CSDL”. Vì lợi ích của tập mục X trong một giao tác T luôn nhỏ hơn hoặc bằng tổng lợi ích của toàn bộ giao tác T, nên tổng lợi ích của X trên toàn bộ CSDL luôn nhỏ hơn hoặc bằng twu(X). Đặc tính này biến TWU thành một cận trên hoàn hảo. Nếu twu(X) nhỏ hơn ngưỡng lợi ích tối thiểu minutil, thì chắc chắn u(X) cũng nhỏ hơn minutil. Quan trọng nhất, TWU có tính chất phản đơn điệu: nếu một tập mục có TWU thấp, mọi tập cha của nó cũng sẽ có TWU thấp. Điều này cho phép tái sử dụng logic của thuật toán Apriori. Bằng cách tìm các tập mục có TWU cao trước, thuật toán đã lọc ra một tập hợp ứng viên nhỏ hơn rất nhiều so với không gian tìm kiếm ban đầu, giúp quá trình tính toán ở pha sau trở nên hiệu quả hơn.

3.2. Quy trình thực hiện tìm ứng viên Pha 1 và sàng lọc Pha 2

Quy trình của thuật toán Hai pha được chia thành hai bước chính. Pha 1: Mục tiêu là tìm tất cả các tập mục có TWU cao. Thuật toán bắt đầu bằng cách duyệt CSDL một lần để tính tổng lợi ích của mỗi giao tác và TWU của từng mục đơn lẻ. Sau đó, nó sử dụng một quy trình lặp tương tự Apriori: từ các (k-1)-tập mục có TWU cao, nó tạo ra các k-tập mục ứng viên, rồi duyệt CSDL để tính TWU của chúng và loại bỏ những ứng viên không đạt ngưỡng. Quá trình này tiếp tục cho đến khi không thể tạo thêm ứng viên mới. Kết quả của Pha 1 là một tập hợp các ứng viên tiềm năng. Pha 2: Thuật toán duyệt lại CSDL một lần cuối cùng. Với mỗi giao dịch, nó xác định các ứng viên từ Pha 1 có trong giao dịch đó và cộng dồn lợi ích thực tế của chúng. Cuối cùng, nó lọc ra những ứng viên có tổng lợi ích thực tế lớn hơn hoặc bằng ngưỡng lợi ích tối thiểu để cho ra kết quả cuối cùng là các tập mục lợi ích cao. Mặc dù vẫn phải duyệt CSDL nhiều lần ở Pha 1, thuật toán này hiệu quả hơn nhiều so với việc kiểm tra toàn bộ không gian tìm kiếm.

IV. Thuật toán HUI Miner Bí quyết tối ưu hiệu suất khai phá

Mặc dù thuật toán Hai pha đã cải thiện đáng kể hiệu suất, nó vẫn còn nhược điểm là sinh ra quá nhiều ứng viên và phải duyệt cơ sở dữ liệu nhiều lần. Để khắc phục điều này, thuật toán HUI-Miner được đề xuất bởi Liu và Qu vào năm 2012, mang đến một cách tiếp cận hoàn toàn mới. Thay vì tạo ứng viên, HUI-Miner sử dụng một cấu trúc dữ liệu thông minh gọi là utility-list. Cấu trúc này được xây dựng chỉ sau hai lần duyệt cơ sở dữ liệu ban đầu. Một utility-list của một tập mục X lưu trữ thông tin chi tiết về các giao dịch chứa X, bao gồm: mã giao dịch (tid), lợi ích của chính X trong giao dịch đó (iutil), và tổng lợi ích của các mục xuất hiện sau X trong cùng giao dịch (rutil - lợi ích còn lại). Điểm đột phá của HUI-Miner là khả năng xây dựng utility-list của một tập mục lớn (ví dụ, XY) bằng cách kết hợp (join) hai utility-list của các tập mục con (X và Y). Toàn bộ quá trình khai phá sau đó được thực hiện trực tiếp trên các cấu trúc utility-list này mà không cần truy cập lại cơ sở dữ liệu, giúp tăng tốc độ và giảm yêu cầu bộ nhớ một cách ngoạn mục.

4.1. Cấu trúc utility list Lưu trữ thông tin lợi ích hiệu quả

Cấu trúc utility-list là trái tim của thuật toán HUI-Miner. Mỗi tập mục sẽ được liên kết với một utility-list. Mỗi phần tử trong danh sách này là một bộ ba (tid, iutil, rutil). tid là định danh của giao dịch chứa tập mục. iutil (itemset utility) là lợi ích của chính tập mục đó trong giao dịch này. rutil (remaining utility) là tổng lợi ích của tất cả các mục xuất hiện sau mục cuối cùng của tập mục trong giao dịch đã được sắp xếp. Việc sắp xếp các mục trong mỗi giao dịch theo thứ tự TWU tăng dần là một bước chuẩn bị quan trọng. Ví dụ, với giao dịch {e, c, b, a, d} và tập mục {c}, iutil là lợi ích của 'c', còn rutil là tổng lợi ích của {b, a, d}. Thông tin rutil này cực kỳ hữu ích, vì tổng của iutil và rutil của một phần tử trong utility-list tạo thành một cận trên chặt chẽ hơn cho lợi ích của bất kỳ tập cha nào có thể được tạo ra từ tập mục hiện tại, giúp cắt tỉa không gian tìm kiếm hiệu quả hơn nữa.

4.2. Cách thức xây dựng và khai phá trực tiếp từ utility list

Quá trình hoạt động của thuật toán HUI-Miner bắt đầu bằng hai lần duyệt CSDL. Lần đầu để tính TWU của tất cả các mục và xác định thứ tự các mục. Lần thứ hai để xây dựng các utility-list ban đầu cho các 1-tập mục. Sau bước khởi tạo này, thuật toán không cần đụng đến CSDL nữa. Quá trình khai phá diễn ra theo phương pháp đệ quy theo chiều sâu. Để tìm các 2-tập mục lợi ích cao, thuật toán kết hợp utility-list của các 1-tập mục. Ví dụ, utility-list của {XY} được tạo bằng cách tìm các tid chung trong utility-list của {X} và {Y}. Với mỗi tid chung, một phần tử mới được tạo ra cho danh sách của {XY} với iutil được cập nhật và rutil được lấy từ danh sách của mục đứng sau. Bằng cách tính tổng các iutil, thuật toán có thể xác định ngay lập tức một tập mục có phải là lợi ích cao hay không. Phương pháp này tránh hoàn toàn việc sinh và kiểm tra ứng viên theo từng cấp như Apriori, giúp nó trở thành một trong những thuật toán khai phá hiệu quả nhất cho bài toán khai phá tập mục lợi ích cao.

V. Ứng dụng thực tiễn của Khai phá Tập mục Lợi ích cao

Lý thuyết về khai phá tập mục lợi ích cao mang lại giá trị ứng dụng to lớn trong nhiều ngành công nghiệp. Ứng dụng phổ biến và trực quan nhất là trong lĩnh vực bán lẻ và thương mại điện tử. Các doanh nghiệp có thể sử dụng các thuật toán như HUI-Miner để phân tích dữ liệu giao dịch và xác định các nhóm sản phẩm không chỉ được mua cùng nhau thường xuyên mà còn tạo ra lợi nhuận cao nhất. Kết quả này là cơ sở để thiết kế các chiến lược marketing hiệu quả như chương trình khuyến mãi chéo (cross-selling), tạo các gói sản phẩm (product bundling), và sắp xếp layout cửa hàng một cách thông minh. Thay vì chỉ đẩy mạnh các sản phẩm bán chạy, doanh nghiệp có thể tập trung vào các combo 'vàng' giúp tối đa hóa lợi nhuận. Ngoài bán lẻ, kỹ thuật này còn được áp dụng trong nhiều lĩnh vực khác. Ví dụ, trong phân tích web, nó giúp xác định các chuỗi hành động của người dùng mang lại giá trị chuyển đổi cao nhất. Trong y sinh, nó có thể được dùng để tìm các tổ hợp gen hoặc triệu chứng liên quan đến các bệnh lý có chi phí điều trị cao, hỗ trợ việc chẩn đoán và phân bổ nguồn lực.

5.1. Phân tích giỏ hàng Tìm nhóm sản phẩm mang lại lợi nhuận cao

Trong bán lẻ, việc phân tích giỏ hàng (market basket analysis) là một nhiệm vụ kinh điển. Mô hình tập mục phổ biến truyền thống giúp tìm ra các quy tắc như "khách hàng mua tã cũng thường mua bia". Tuy nhiên, khai phá tập mục lợi ích cao đưa phân tích này lên một tầm cao mới. Luận văn gốc đã trình bày một ví dụ thực nghiệm về “phát hiện nhóm mặt hàng mang lại lợi nhuận cao trên tập dữ liệu bán hàng của siêu thị”. Thay vì chỉ biết {Bánh mì, Sữa} là một cặp phổ biến, doanh nghiệp có thể phát hiện ra rằng tập mục {Rượu vang, Phô mai nhập khẩu} tuy có tần suất mua thấp hơn nhưng lại mang về lợi nhuận gấp nhiều lần. Thông tin này vô cùng quý giá. Nó giúp các nhà quản lý đưa ra quyết định chính xác hơn: nên đặt sản phẩm nào cạnh nhau, nên tạo combo khuyến mãi cho nhóm sản phẩm nào, và nên tập trung nguồn lực marketing vào đâu để tối ưu hóa biên lợi nhuận trên mỗi giỏ hàng. Đây là một công cụ mạnh mẽ để chuyển từ tư duy bán hàng theo số lượng sang bán hàng theo giá trị.

5.2. Mở rộng ứng dụng sang tài chính y sinh và khai phá web

Tiềm năng của khai phá tập mục lợi ích cao không chỉ giới hạn trong ngành bán lẻ. Trong lĩnh vực tài chính, các thuật toán khai phá này có thể được sử dụng để phân tích danh mục đầu tư, xác định các nhóm cổ phiếu hoặc tài sản khi kết hợp với nhau không chỉ giảm thiểu rủi ro mà còn tối đa hóa lợi nhuận. Trong khai phá web (web mining), các nhà phân tích có thể gán 'lợi ích' cho các trang khác nhau dựa trên thời gian người dùng ở lại hoặc khả năng dẫn đến chuyển đổi. Việc khai phá các chuỗi truy cập có lợi ích cao giúp tối ưu hóa luồng người dùng và thiết kế website hiệu quả hơn. Trong lĩnh vực y sinh (bioinformatics), kỹ thuật này có thể giúp các nhà nghiên cứu xác định các tập hợp gen có biểu hiện đồng thời liên quan đến các tình trạng bệnh lý nghiêm trọng, với 'lợi ích' được định nghĩa là mức độ ảnh hưởng hoặc chi phí liên quan đến tình trạng đó. Sự linh hoạt trong định nghĩa 'lợi ích' cho phép áp dụng HUIM vào giải quyết nhiều bài toán phức tạp trong các lĩnh vực khác nhau.

VI. Tương lai của Khai phá Tập mục Lợi ích cao và Xu hướng mới

Lĩnh vực khai phá tập mục lợi ích cao đã có những bước tiến vượt bậc, từ việc giải quyết bài toán thiếu tính chất phản đơn điệu bằng lợi ích TWU trong thuật toán Hai pha đến việc tối ưu hóa hiệu suất với cấu trúc utility-list của thuật toán HUI-Miner. Những thuật toán này đã chứng minh được hiệu quả và tính ứng dụng cao trong thực tế. Tuy nhiên, thế giới dữ liệu không ngừng phát triển, đặt ra những thách thức và cơ hội mới. Hướng nghiên cứu trong tương lai sẽ tập trung vào việc giải quyết các bài toán phức tạp hơn. Một trong những xu hướng quan trọng là khai phá trên các dòng dữ liệu (data streams), nơi dữ liệu đến liên tục và các mẫu lợi ích cao có thể thay đổi theo thời gian. Một hướng khác là phát triển các thuật toán song song và phân tán để xử lý các tập dữ liệu khổng lồ (Big Data) mà một máy tính đơn lẻ không thể đảm đương. Ngoài ra, việc tích hợp các ràng buộc khác vào mô hình, chẳng hạn như trọng số mục, lợi ích âm (chi phí), hoặc các ràng buộc về không gian, sẽ làm cho kết quả khai phá trở nên thực tế và hữu ích hơn nữa.

6.1. Tổng kết giá trị và hiệu quả của các thuật toán đã nghiên cứu

Nhìn lại chặng đường phát triển, có thể thấy rõ sự tiến hóa trong các phương pháp khai phá tập mục lợi ích cao. Các thuật toán ban đầu gặp khó khăn lớn do không gian tìm kiếm bùng nổ. Thuật toán Hai pha là một bước đột phá khi giới thiệu khái niệm lợi ích TWU làm cận trên, cho phép áp dụng lại nguyên lý cắt tỉa và giảm đáng kể số lượng ứng viên. Tiếp nối thành công đó, thuật toán HUI-Miner đã tối ưu hóa hơn nữa bằng cách loại bỏ hoàn toàn bước tạo ứng viên. Với cấu trúc utility-list thông minh, HUI-Miner chỉ cần hai lần duyệt CSDL ban đầu và thực hiện toàn bộ quá trình khai phá trong bộ nhớ, mang lại hiệu suất vượt trội. Các thuật toán này không chỉ giải quyết được các thách thức lý thuyết mà còn cung cấp những công cụ mạnh mẽ, sẵn sàng cho các ứng dụng thực tiễn, giúp doanh nghiệp và các nhà nghiên cứu khai thác sâu hơn giá trị từ dữ liệu.

6.2. Các hướng nghiên cứu và phát triển tiềm năng trong tương lai

Tương lai của khai phá tập mục lợi ích cao hứa hẹn nhiều hướng đi thú vị. Một lĩnh vực đầy tiềm năng là khai phá tập mục lợi ích cao có yếu tố không gian và thời gian (spatio-temporal high-utility itemset mining), ví dụ như tìm các combo sản phẩm lợi nhuận cao tại các địa điểm và thời điểm cụ thể. Khai phá trên dữ liệu không chắc chắn (uncertain data) cũng là một thách thức, nơi lợi ích của các mục có thể là một khoảng giá trị thay vì một con số cố định. Hơn nữa, sự phát triển của học sâu (deep learning) có thể mở ra những phương pháp mới để học các biểu diễn (representation) của các tập mục và lợi ích của chúng, có khả năng phát hiện các mẫu phức tạp hơn. Cuối cùng, việc tăng cường tính diễn giải (interpretability) của kết quả, giúp người dùng cuối hiểu rõ 'tại sao' một tập mục lại có lợi ích cao, cũng là một hướng đi quan trọng để cầu nối giữa nghiên cứu học thuật và ứng dụng kinh doanh.

02/10/2025

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

Chương I: TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU VÀ KHAI PHÁ TẬP MỤC PHỔ BIẾN 1.1 Khái niệm về khai phá tri thức và khai phá dữ liệu KPDL là việc rút trích tri thức một cách tự động và hiệu quả từ một khối dữ liệu lớn. Tri thức đó thường ở dạng các mẫu có tính chất không tầm thường, không tường minh (ẩn), chưa được biết đến và có tiềm năng mang lại lợi ích. Có một số nhà nghiên cứu còn gọi KPDL là phát hiện tri thức trong cơ sở dữ liệu (Knowledge Discovery in Database – KDD). Ở đây chúng ta có thể coi KPDL là cốt lõi của quá trình phát hiện tri thức.

Quá trình phát hiện tri thức gồm các bước [4]: Bước 1: Trích chọn dữ liệu (data selection): Là bước trích chọn những tập dữ liệu cần được khai phá từ các tập dữ liệu lớn (databases, data ware houses). Bước 2: Tiền xử lý dữ liệu (data preprocessing): Là bước làm sạch dữ liệu (xử lý dữ liệu không đầy đủ, dữ liệu nhiễu, dữ liệu không nhất quán,…v.v), rút gọn dữ liệu (sử dụng các phương pháp thu gọn dữ liệu, histograms, lấy mẫu…v.v), rời rạc hóa dữ liệu (dựa vào histograms, entropy, phân khoảng,. Sau bước này, dữ liệu sẽ nhất quán, đầy đủ, được rút gọn và được rời rạc hóa. Bước 3: Biến đổi dữ liệu (data transformation): Là bước chuẩn hóa và làm mịn dữ liệu để đưa dữ liệu về dạng thuận lợi nhất nhằm phục vụ cho các kỹ thuật khai thác ở bước sau.

Bước 4: Khai phá dữ liệu (data mining): Đây là bước quan trọng và tốn nhiều thời gian nhất của quá trình khám phá tri thức, áp dụng các kỹ thuật khai phá (phần lớn là các kỹ thuật của machine learning) để khai phá, trích chọn được các mẫu (pattern) thông tin, các mối liên hệ đặc biệt trong dữ liệu. Bước 5: Đánh giá và biểu diễn tri thức (knowledge representation & evaluation): Dùng các kỹ thuật hiển thị dữ liệu để trình bày các mẫu thông tin download by : skknchat@gmail.com 3 (tri thức) và mối liên hệ đặc biệt trong dữ liệu đã được khai thác ở bước trên biểu diễn theo dạng gần gũi với người sử dụng như đồ thị, cây, bảng biểu, luật,…v. Đồng thời bước này cũng đánh giá những tri thức khám phá được theo những tiêu chí nhất định. Trong giai đoạn khai phá dữ liệu, có thể cần sự tương tác của người dùng để điều chỉnh và rút ra các tri thức cần thiết nhất.

Các tri thức nhận được cũng có thể được lưu và sử dụng lại.1: Quá trình phát hiện tri thức Việc KPDL có thể được tiến hành trên một lượng lớn dữ liệu có trong CSDL, các kho dữ liệu hoặc trong các loại lưu trữ thông tin khác. Các mẫu đáng quan tâm có thể được đưa đến người dùng hoặc được lưu trữ trong một cơ sở tri thức.2 Quá trình khai phá dữ liệu Các giải thuật khai phá dữ liệu thường được miêu tả như những chương trình hoạt động trực tiếp trên tệp dữ liệu. Với các phương pháp học máy và thống kê trước đây, thường thì bước đầu tiên là các giải thuật nạp toàn bộ tệp dữ liệu vào trong bộ nhớ. Khi chuyển sang các ứng dụng công nghiệp liên quan đến việc khai phá các kho dữ liệu lớn, mô hình này không thể đáp ứng được.

Không chỉ bởi vì nó không thể nạp hết dữ liệu vào trong bộ nhớ mà còn vì khó download by : skknchat@gmail.com 4 có thể chiết xuất dữ liệu ra các tệp đơn giản để phân tích được. Quá trình khai phá dữ liệu được thể hiện bởi mô hình sau: Hình 1.2: Quá trình KPDL + Xác định nhiệm vụ: Xác định chính xác vấn đề cần giải quyết. + Xác định các dữ liệu liên quan dùng để xây dựng giải pháp. + Thu thập các dữ liệu có liên quan và xử lý chúng thành dạng sao cho giải thuật khai phá dữ liệu có thể hiểu được.

Ở đây có thể gặp một số vấn đề: dữ liệu phải được sao ra nhiều bản (nếu được chiết suất vào các tệp), quản lý tập các tệp dữ liệu, phải lặp đi lặp lại nhiều lần toàn bộ quá trình (nếu mô hình dữ liệu thay đổi v. + Chọn thuật toán khai phá dữ liệu thích hợp và thực hiện việc khai phá dữ liệu: nhằm tìm được các mẫu (pattern) có ý nghĩa dưới dạng biểu diễn tương ứng với các ý nghĩa đó.3 Một số kỹ thuật khai phá dữ liệu Mục đích của khai phá dữ liệu là chiết xuất ra các tri thức có lợi cho kinh doanh hay cho nghiên cứu khoa học… Do đó, ta có thể xem mục đích của khai phá dữ liệu sẽ là mô tả các sự kiện và dự đoán. Các mẫu khai phá dữ liệu phát hiện được nhằm vào mục đích này. Dự đoán liên quan đến việc sử dụng các biến hoặc các đối tượng (bản ghi) trong CSDL để chiết xuất ra các mẫu, dự đoán được những giá trị chưa biết hoặc những giá trị tương lai của các biến download by : skknchat@gmail.com 5 đáng quan tâm.

Mô tả tập trung vào việc tìm kiếm các mẫu mô tả dữ liệu mà con người có thể hiểu được. Để đạt được những mục đích này, nhiệm vụ chính của khai phá dữ liệu bao gồm như sau: Phân lớp dữ liệu 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. 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.

Một ví dụ tiêu biểu về cây quyết định: Hình 1.3: Cây quyết định download by : skknchat@gmail.com 6 Trong hình 1.3 là một cây quyết định cho lớp mua laptop, chỉ ra một khách hàng sẽ mua hay không mua một laptop. Mỗi nút lá đại diện một lớp mà đánh giá mua laptop là Yes hay No. Sau khi mô hình này được xây dựng, chúng ta có thể dự đoán việc có thể mua một laptop hay không dựa vào những thuộc tính khách hàng mới là tuổi và nghề nghiệp. Cây quyết định có thể ứng dụng rộng rãi trong nhiều hoạt động của đời sống thực.

Phân nhóm dữ liệu 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 lọ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 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.4: Mẫu kết quả của nhiệm vụ phân cụm dữ liệu Đ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 download by : skknchat@gmail.com 7 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. Ta có thể tham khảo một khảo sát toàn diện về kỹ thuật và thuật toán phân nhóm trong. Hồi qui (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.

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ển 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 Hình 1.5: Mẫu kết quả của nhiệm vụ hồi quy Ứ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 khu 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 chẩ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… hình 1.6 chỉ ra mẫu kết quả hồi quy tuyến tính đơn giản, download by : skknchat@gmail.com 8 ở đây tổng số nợ được điều chỉnh cho phù hợp giống như một hàm thu nhập tuyến tính. Việc điều chỉnh này là không đáng kể bởi vì chỉ tồn tại một tương quan yếu giữa hai biến. 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.

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. Mô hình hóa phụ thuộc (dependency modeling): Là việc tìm kiếm mô tả các phụ thuộc quan trọng giữa các biến. Mô hình phụ thuộc tồn tại hai mức: + Mức cấu trúc của mô hình (thường dưới dạng đồ thị) xác định các biến phụ thuộc cục bộ vào các biến khác; + Mức định lượng của mô hình xác định mức độ phụ thuộc của biến. Những phụ thuộc này thường được biểu thị dưới dạng luật.

Quan hệ phụ thuộc cũng có thể biểu diễn dưới dạng mạng tin cậy. Đó là đồ thị có hướng không có dạng chu trình, các nút biểu diễn thuộc tính và trọng số chỉ liên kết phụ thuộc giữa các nút đó.

Nội dung được bảo vệ bản quyền — Tải xuống đầy đủ