Chương 1: TỔNG QUAN 1. Khai thác dữ liệu Khối lượng dữ liệu khổng lồ được thu thập trên toàn thế giới, tăng lên hàng terabyte (hoặc petabyte) dữ liệu mỗi ngày từ nhiều nguồn dữ liệu: dữ liệu về kinh tế, khoa học kỹ thuật, y tế, mạng internet, mạng xã hội, các hệ thống truyền dữ liệu tự động và từ các khía cạnh khác trong cuộc sống hàng ngày của con người. Từ những năm đầu thập kỷ 60 đến cuối những năm 1980, công nghệ sưu tập, lưu trữ và xử lý, phân tích dữ liệu đã tiến bộ vượt bậc trước sự phát triển mạnh mẽ của xu hướng tin học hóa trên toàn thế giới. Ban đầu sự thu thập và phát sinh cơ sở dữ liệu, chỉ là truy xuất file thô sơ (đầu những năm 1960).
Sau những năm 1970 đến đầu 1980s, phát triển sang hệ thống quản lý CSDL, trong đó đã có công cụ phân tích dữ liệu giao dịch trực tuyến - OLTP. Từ giữa đến cuối những năm 1980, phát triển hệ thống cơ sở dữ liệu nâng cao và hệ thống phân tích CSDL nâng cao, triển khai kèm theo đó là các công cụ nổi bật dành cho phân tích dữ liệu nâng cao. Trong đó có sự ra đời của kiến trúc kho dữ liệu mới đi kèm kỹ thuật OLAP, có khả năng khai thác dữ liệu đa chiều, phân tích dữ liệu sâu, xem thông tin với nhiều góc độ khác nhau. Tuy nhiên khối dữ liệu khổng lồ được thu thập và lưu trữ trong nhiều kho chứa dữ liệu lớn không ngừng tăng nhanh.
Việc hiểu hết các thông tin, cũng như rút trích ra các kiến thức ẩn đã nhúng trong khối dữ liệu khổng lồ cực lớn này mà không có công cụ mạnh mẽ hỗ trợ là vượt xa khả năng của con người. Điều này đòi hỏi cần có một công cụ mạnh mẽ, linh hoạt hơn để đáp ứng nhu cầu khám phá các mẫu dữ liệu đặc biệt, quan trọng, nhằm rút trích ra các thông tin, kiến thức có giá trị từ khối dữ liệu khổng lồ. Cuối những năm 1980, khai thác dữ liệu ra đời, đánh dấu sự tiến triển mới của công nghệ thông tin. Các chức năng của khai thác dữ liệu bao gồm: mô tả đặc tính và phân biệt dữ liệu, khai thác các mẫu (chuỗi) phổ biến, sự kết hợp và tương quan, phân lớp và hồi quy, phân tích gom cụm, và nhận dạng ngoại lệ.
4 Trong tương lai, nếu phát sinh thêm nhiều kiểu dữ liệu mới, ứng dụng mới và nhu cầu phân tích dữ liệu mới thì việc xuất hiện thêm các thao tác khai thác dữ liệu mới là điều có thể dự đoán được. Ứng dụng của khai thác dữ liệu Khai phá dữ liệu đã và đang được ứng dụng rộng rãi trong rất nhiều lĩnh vực và hiện nay đã có rất nhiều công cụ thương mại và phi thương mại triển khai các nhiệm vụ của khai phá dữ liệu. Sau đây là một số lĩnh vực mà khai phá dữ liệu đang được ứng dụng rộng rãi: • Phân tích dữ liệu tài chính. • Công nghiệp bán lẻ.
• Công nghiệp viễn thông. • Phân tích dữ liệu sinh học. • Phát hiện xâm nhập. • Một số ứng dụng trong khoa học.
Phân tích dữ liệu tài chính Dữ liệu tài chính trong ngân hàng và trong ngành tài chính thường đáng tin cậy và có chất lượng cao, tạo điều kiện cho khai phá dữ liệu. Dưới đây là một số ứng dụng điển hình trong khai phá dữ liệu tài chính: • Dự đoán khả năng vay và thanh toán của khách hàng, phân tích chính sách tín dụng đối với khách hàng. • Phân tích hành vi khách hàng (vay, gửi tiền). • Phân loại và phân nhóm khách hàng mục tiêu cho tiếp thị tài chính.
• Phát hiện các hoạt động rửa tiền và tội phạm tài chính khác. Công nghiệp bán lẻ Khai phá dữ liệu có vai trò rất quan trọng trong ngành công nghiệp bán lẻ, do dữ liệu thu thập từ lĩnh vực này rất lớn từ doanh số bán hàng, lịch sử mua hàng của khách hàng, vận chuyển hàng hóa, tiêu thụ và dịch vụ. Điều tự nhiên là khối lượng dữ 5 liệu từ ngành công nghiệp này sẽ tiếp tục tăng lên nhanh chóng và dễ dàng thu thập bởi tính sẵn có trên môi trường Web. Ứng dụng khai phá dữ liệu trong ngành công nghiệp bán lẻ nhằm xây dựng mô hình giúp xác định xu hướng mua hàng của khách hàng, giúp doanh nghiệp cải thiện chất lượng sản phẩm dịch vụ nhằm nâng cao sự hài lòng của khách hàng và giữ chân khách hàng tốt.
Dưới đây là một số ứng dụng của khai phá dữ liệu trong ngành công nghiệp bán lẻ: • Khai phá dữ liệu trên kho dữ liệu khách hàng. • Phân tích đa chiều trên kho dữ liệu khách hàng về doanh số bán hàng, khách hàng, sản phẩm, thời gian và khu vực. • Phân tích hiệu quả của các chiến dịch bán hàng, Marketing. • Quản trị mối quan hệ khách hàng.
• Giới thiệu và tư vấn sản phẩm phù hợp cho khách hàng. Công nghiệp viễn thông Công nghiệp viễn thông là một trong những ngành công nghiệp mới nổi, cung cấp nhiều dịch vụ như trên điện thoại di động, internet, truyền hình ảnh. Do sự phát triển mạnh của công nghệ máy tính và mạng máy tính, viễn thông đang phát triển với tốc độ rất nhanh. Đây là lý do tại sao khai phá dữ liệu trở nên rất quan trọng trong lĩnh vực này.
Khai phá dữ liệu trong ngành công nghiệp viễn thông giúp xác định các mô hình viễn thông, phát hiện các hoạt động gian lận trong viễn thông, sử dụng tốt hơn nguồn tài nguyên và cải thiện chất lượng dịch vụ viễn thông. Dưới đây là một số ứng dụng của khai phá dữ liệu trong ngành công nghiệp này: • Phân tích dữ liệu đa chiều viễn thông. • Xây dựng các mô hình phát hiện gian lận. • Phát hiện bất thường trong giao dịch viễn thông.
• Phân tích hành vi sử dụng dịch vụ viễn thông của khách hàng. • Sử dụng các công cụ trực quan trong phân tích dữ liệu viễn thông. 6 Phân tích dữ liệu sinh học Khai phá dữ liệu sinh học là một phần rất quan trọng của lĩnh vực Tin - Sinh Học. Sau đây là một số ứng dụng của khai phá dữ liệu ứng dụng trong sinh học: • Lập chỉ mục, tìm kiếm tương tự, bất thường trong cơ sở dữ liệu Gen.
• Xây dựng mô hình khai phá các mạng di truyền và cấu trúc của Gen, protein. • Xây dựng các công cụ trực quan trong phân tích dữ liệu di truyền. Phát hiện xâm nhập bất hợp pháp Xâm nhập bất hợp pháp là những hành động đe dọa tính toàn vẹn, bảo mật và tính sẵn sàng của tài nguyên mạng. Trong thế giới của kết nối, bảo mật đã trở thành vấn đề lớn đối với tồn tại của hệ thống.
Với sự phát triển của internet và sự sẵn có của các công cụ, thủ thuật trợ giúp cho xâm nhập và tấn công mạng, yêu cầu kiểm soát truy cập bất hợp pháp là yếu tố rất quan trọng đảm bảo cho sự ổn định của hệ thống. Dưới đây là một số ứng dụng của khai phá dữ liệu có thể được áp dụng để phát hiện xâm nhập: - Phát triển các thuật toán khai phá dữ liệu để phát hiện xâm nhập. - Phân tích kết hợp, tương quan và khác biệt để phát hiện xâm nhập. - Phân tích dòng dữ liệu để phát hiện bất thường.
Khai thác dàn các tập phổ biến đóng Tìm luật kết hợp từ hàng triệu giao dịch trong nhiều CSDL lớn, hiện tại trở nên khó khăn trong lĩnh vực khai thác dữ liệu. Tập phổ biến và tập phổ biến đóng là chìa khóa quan trọng của việc khai thác các luật kết hợp. Các luật kết hợp có thể được khai thác hiệu quả từ Dàn các tập phổ biến đóng. Không thừa, chính xác, thời gian và chiếm dụng bộ nhớ là các nhân tố cần được xem xét trong khi phát triển thuật toán để tìm các luật kết hợp hữu ích.
Xây dựng dàn tập phổ biến đóng là xây dựng quan hệ cha con (trực tiếp) giữa các tập phổ biến đóng với nhau. Do vậy sẽ tiết kiệm được thời gian khi duyệt dàn để sinh luật. Ý nghĩa khoa học và thực tiễn của đề tài - Thuật toán BVCL đổi mới hơn so với thuật toán CHARML cũng như các thuật toán duyệt tuần tự tập hạng mục ở những điểm chính sau: o Cấu trúc DSBV lưu thông tin tập cha ở dạng bit nên việc truyền thông tin cho các tập trong dàn khi gọi đệ qui là nhanh chóng. o Cách tổ chức 2 danh sách subsume list và non - subsume list làm cho thuật toán bỏ qua khá nhiều bước khi đệ qui với các tập trong subsume list.
- Thuận toán mới cải thiện hiệu suất khai thác dàn các tập phổ biến đóng này góp phần giải quyết vấn đề trong việc khai thác luật kết hợp với nhiều ứng dụng rộng, bao gồm những phân tích về hành vi mua sắm của khách hàng, chuỗi truy xuất web, những thực nghiệm có tính khoa học, điều trị bệnh, ngăn chặn tai họa thiên nhiên và sự hình thành protein… 5. Phương pháp nghiên cứu và đối tượng nghiên cứu • Phương pháp nghiên cứu: - Phương pháp nghiên cứu tài liệu: dựa vào các tài liệu đã công bố của các nhà nghiên cứu về các thuật toán khai thác tập phổ biến, tập phổ biến đóng, và khai thác Dàn: Apriori-Gen, FP-tree, Charm, CharmL, MG-Charm, DCI- Closed, LCM, DBV-Miner, GENCLOSE, NAFCP. Phân tích cách sử dụng cấu trúc dữ liệu DBV, DSBV cách tổ chức CSDL (ngang hay dọc), cách phát sinh mẫu ứng viên mới, các kỹ thuật khai thác Dàn… và xu hướng phát triển của các thuật toán. - Phương pháp thực nghiệm: Tiến hành hiện thực và thực nghiệm các phương pháp được đề xuất trong luận văn để xác định tính đúng đắn, khả thi và phát triển so với các phương pháp đã công bố của các tác giả trong và ngoài nước có liên quan đến luận văn.
- Phương pháp thống kê, phân tích dữ liệu: Thống kê, tổng hợp các số liệu trong quá trình thực nghiệm để phân tích, đánh giá từ đó nhận thức, phát hiện, và chọn lọc những ưu điểm để phát huy, tìm cách khắc phục những hạn chế, đồng thời kết hợp những thông tin liên quan đã thu thập được lại thành 8 một nội dung logic đầy đủ để đề xuất thuật toán mới có thời gian khai thác đồng thời Dàn các tập phổ biến đóng và tập sinh của chúng nhanh hơn và tiết kiệm bộ nhớ hơn (có so sánh kết quả thực nghiệm).