Luận Văn Thạc Sĩ: Nghiên Cứu Khai Phá Đồ Thị Con Thường Xuyên Sử Dụng Mô Hình MapReduce

Luận văn thạc sĩ khai phá đồ thị con thường xuyên trên mô hình MapReduce, tập trung vào phương pháp hiệu quả để xử lý dữ liệu lớn, ứng dụng trong phân tích đồ thị.

• Tác giả: Nguyễn Kim Ngọc
• Người hướng dẫn: TS. Trần Thiên Thành
• Trường học: Đại học Quy Nhơn
• Chuyên ngành: Khoa học máy tính
• Đề tài: Khai phá đồ thị con thường xuyên trên mô hình MapReduce
• Loại tài liệu: luận văn thạc sĩ
• Địa điểm: Quy Nhơn

Mục lục chi tiết

• LỜI CAM ĐOAN
• LỜI CẢM ƠN
• MỞ ĐẦU
• 0.1. Lý do chọn đề tài
• 0.2. Tổng quan tình hình nghiên cứu đề tài
• 0.3. Mục tiêu và nhiệm vụ nghiên cứu
• 0.4. Nhiệm vụ nghiên cứu
• 0.5. Đối tượng và phạm vi nghiên cứu
• 1. CHƯƠNG 1: KIẾN THỨC TỔNG QUAN
• 1.1. Đồ thị con thường xuyên
• 1.2. Nền tảng Hadoop
• 1.2.1. Tổng quát về Apache Hadoop
• 1.2.2. Kiến trúc Hadoop
• 1.2.3. Nguyên tắc hoạt động của Hadoop MapReduce
• 1.3. Mô hình lập trình MapReduce
• 1.3.1. Tổng quan về mô hình MapReduce
• 1.3.2. Nguyên tắc hoạt động của mô hình MapReduce
• 1.3.3. Một số bài toán ứng dụng mô hình MapReduce
• 1.3.4. Hadoop – Nền tảng lập trình mô hình MapReduce
• 1.4. Lập trình với mô hình ứng dụng MapReduce
• 1.4.1. Phương pháp viết một MapReduce job
• 1.4.2. Các kiểu dữ liệu Hadoop hỗ trợ
• 1.5. Chương trình Mapreduce bằng Java
• 1.6. Kết luận chương 1
• 2. CHƯƠNG 2: CÁC THUẬT TOÁN PHÁT HIỆN ĐỒ THỊ CON THƯỜNG XUYÊN
• 2.1. Chiến lược tìm kiếm theo chiều rộng
• 2.1.1. Thuật toán Subdue
• 2.1.2. Thuật toán FSG
• 2.2. Chiến lược tìm kiếm theo chiều sâu
• 2.2.1. Thuật toán gSpan
• 2.2.2. Thuật toán FFSM
• 2.3. So sánh và đánh giá một số thuật toán
• 2.4. Thuật toán khai phá đồ thị con thường xuyên theo mô hình lập trình MapReduce
• 2.5. Kết luận chương 2
• 3. CHƯƠNG 3: THỰC NGHIỆM
• 3.1. Cấu trúc dữ liệu thử nghiệm
• 3.2. Triển khai thử nghiệm
• 3.3. Đánh giá thuật toán
• 3.4. Kết quả đạt được của luận văn
• 3.5. Kiến nghị và hướng nghiên cứu tiếp theo
• DANH MỤC TÀI LIỆU THAM KHẢO
• DANH MỤC CÁC KÝ HIỆU, CÁC CHỮ VIẾT TẮT
• DANH MỤC CÁC BẢNG
• DANH MỤC CÁC BIỂU ĐỒ
• DANH MỤC CÁC HÌNH VẼ

Tóm tắt

I. Khai phá đồ thị con thường xuyên

Khai phá đồ thị con thường xuyên là một nhiệm vụ quan trọng trong lĩnh vực khai thác dữ liệu có cấu trúc. Đồ thị con thường xuyên được định nghĩa là các đồ thị con xuất hiện thường xuyên trong một tập dữ liệu đồ thị lớn. Việc phát hiện các đồ thị con thường xuyên giúp phân loại, phân nhóm và xây dựng các chỉ số đồ thị, đặc biệt hữu ích trong các lĩnh vực như hóa học, sinh học và mạng xã hội. Các thuật toán như gSpan, FFSM, và FSG đã được phát triển để giải quyết vấn đề này, nhưng chúng thường gặp hạn chế về hiệu suất khi xử lý dữ liệu lớn.

1.1. Đồ thị con đẳng cấu

Đồ thị con đẳng cấu là một khái niệm cơ bản trong phân tích đồ thị. Một đồ thị được coi là đồ thị con đẳng cấu của một đồ thị khác nếu tồn tại một ánh xạ song ánh giữa các đỉnh và cạnh của chúng. Việc xác định đồ thị con đẳng cấu có độ phức tạp tính toán cao, thuộc lớp NP-complete, đòi hỏi các thuật toán tối ưu hóa để xử lý hiệu quả.

1.2. Đồ thị con thường xuyên

Đồ thị con thường xuyên được xác định dựa trên ngưỡng hỗ trợ tối thiểu (minsup). Một đồ thị con được coi là thường xuyên nếu nó xuất hiện trong một tỷ lệ nhất định của các đồ thị trong tập dữ liệu. Việc phát hiện các đồ thị con thường xuyên đóng vai trò quan trọng trong việc khám phá các mẫu dữ liệu hữu ích, đặc biệt trong các bộ dữ liệu có cấu trúc phức tạp.

II. Mô hình MapReduce và xử lý dữ liệu lớn

Mô hình MapReduce là một giải pháp mạnh mẽ để xử lý dữ liệu lớn, đặc biệt trong các hệ thống phân tán. Mô hình này chia nhỏ dữ liệu và công việc thành các phần nhỏ hơn, thực hiện song song trên nhiều máy tính. Hadoop, một nền tảng mã nguồn mở, là một trong những công cụ phổ biến nhất để triển khai mô hình MapReduce. Nó cho phép xử lý hiệu quả các tập dữ liệu khổng lồ, đặc biệt trong các ứng dụng như tìm kiếm web và phân tích dữ liệu.

2.1. Kiến trúc Hadoop

Hadoop bao gồm hai thành phần chính: HDFS (Hadoop Distributed File System) và MapReduce. HDFS là hệ thống lưu trữ phân tán, cho phép lưu trữ và truy cập dữ liệu trên nhiều máy tính. MapReduce là mô hình lập trình giúp xử lý dữ liệu song song. Kiến trúc này cho phép Hadoop xử lý hiệu quả các bài toán lớn, đặc biệt trong các hệ thống phân tán.

2.2. Ứng dụng MapReduce trong khai phá đồ thị

MapReduce đã được áp dụng để cải tiến các thuật toán khai phá đồ thị con thường xuyên. Bằng cách chia nhỏ dữ liệu và thực hiện song song, MapReduce giúp tăng tốc độ xử lý và giảm thời gian tính toán. Các thuật toán như FSM-H đã được phát triển để khai thác đồ thị con thường xuyên trên nền tảng Hadoop, mang lại hiệu quả cao trong việc xử lý dữ liệu lớn.

III. Thuật toán và thực nghiệm

Các thuật toán khai phá đồ thị con thường xuyên như gSpan, FFSM, và FSG đã được nghiên cứu và cải tiến để phù hợp với mô hình MapReduce. Việc thực nghiệm trên nền tảng Hadoop cho thấy sự cải thiện đáng kể về tốc độ xử lý, đặc biệt với các tập dữ liệu lớn. Các kết quả thực nghiệm cũng chỉ ra rằng việc áp dụng MapReduce giúp giảm thời gian tính toán và tăng hiệu suất của các thuật toán.

3.1. So sánh các thuật toán

Các thuật toán gSpan, FFSM, và FSG được so sánh về hiệu suất và độ phức tạp. gSpan và FFSM sử dụng chiến lược tìm kiếm theo chiều sâu, trong khi FSG sử dụng chiến lược tìm kiếm theo chiều rộng. Kết quả cho thấy các thuật toán tìm kiếm theo chiều sâu thường hiệu quả hơn trong việc giảm số lượng đồ thị ứng viên và tiết kiệm bộ nhớ.

3.2. Kết quả thực nghiệm

Thực nghiệm trên các bộ dữ liệu lớn cho thấy FSM-H, một thuật toán khai phá đồ thị con thường xuyên trên Hadoop, đạt hiệu suất cao hơn so với các thuật toán truyền thống. Kết quả cũng chỉ ra rằng việc sử dụng MapReduce giúp tăng tốc độ xử lý và giảm thời gian tính toán, đặc biệt với các tập dữ liệu có kích thước lớn.

Nội dung chính

Tổng quan nghiên cứu

Trong bối cảnh phát triển mạnh mẽ của công nghệ thông tin, lượng dữ liệu khổng lồ và đa dạng được tạo ra hàng ngày, việc khai thác tri thức từ dữ liệu trở thành một nhu cầu cấp thiết. Đặc biệt, dữ liệu có cấu trúc đồ thị ngày càng phổ biến trong các lĩnh vực như mạng xã hội, cấu trúc hóa học, gen tế bào, và các hệ thống phức tạp khác. Khai phá đồ thị con thường xuyên là một nhiệm vụ quan trọng nhằm phát hiện các mẫu cấu trúc lặp lại trong tập dữ liệu đồ thị lớn, giúp hỗ trợ phân loại, phân nhóm và tìm kiếm tương tự hiệu quả.

Tuy nhiên, việc khai phá đồ thị con thường xuyên gặp nhiều thách thức do tính phức tạp cao của bài toán, đặc biệt là vấn đề xác định đồ thị con đẳng cấu có độ phức tạp tính toán thuộc lớp NP-complete. Các thuật toán truyền thống như gSpan, FFSM, FSG mặc dù đã được phát triển nhưng vẫn chưa đáp ứng tốt với tập dữ liệu lớn do thời gian xử lý không đa thức và yêu cầu bộ nhớ cao.

Mục tiêu của luận văn là nghiên cứu và triển khai thuật toán khai phá đồ thị con thường xuyên trên mô hình lập trình phân tán MapReduce, sử dụng nền tảng Hadoop nhằm tăng hiệu năng xử lý trên tập dữ liệu lớn. Phạm vi nghiên cứu tập trung vào việc áp dụng mô hình MapReduce để cải tiến các thuật toán khai phá đồ thị con thường xuyên, thực nghiệm trên các bộ dữ liệu đồ thị có kích thước khác nhau và so sánh hiệu quả với các thuật toán truyền thống.

Việc nghiên cứu này có ý nghĩa quan trọng trong việc nâng cao khả năng xử lý dữ liệu lớn có cấu trúc phức tạp, góp phần phát triển các ứng dụng trong lĩnh vực khoa học máy tính, công nghệ thông tin và các ngành liên quan. Theo ước tính, việc áp dụng mô hình MapReduce có thể giảm thời gian xử lý xuống còn khoảng 30-50% so với các thuật toán đơn máy truyền thống trên cùng bộ dữ liệu.

Cơ sở lý thuyết và phương pháp nghiên cứu

Khung lý thuyết áp dụng

Luận văn dựa trên các khái niệm và mô hình lý thuyết sau:

• Đồ thị gán nhãn và đồ thị con thường xuyên: Đồ thị được định nghĩa gồm tập đỉnh, tập cạnh và các hàm gán nhãn cho đỉnh và cạnh. Đồ thị con thường xuyên là đồ thị con đẳng cấu xuất hiện với tần suất vượt ngưỡng minsup trong tập dữ liệu đồ thị.

• Đồ thị đẳng cấu và đồ thị con đẳng cấu: Hai đồ thị được gọi là đẳng cấu nếu tồn tại hàm song ánh giữa các đỉnh sao cho nhãn đỉnh và cạnh tương ứng được bảo toàn. Đồ thị con đẳng cấu là đồ thị con của một đồ thị lớn hơn mà có tính đẳng cấu.

• Mô hình lập trình MapReduce: Mô hình lập trình phân tán được phát triển bởi Google, chia công việc lớn thành các tác vụ nhỏ thực hiện song song qua hai hàm chính là map và reduce. Mô hình này giúp xử lý hiệu quả các tập dữ liệu lớn trên hệ thống phân tán.

• Nền tảng Hadoop: Hệ thống mã nguồn mở hỗ trợ thực thi mô hình MapReduce với hệ thống tập tin phân tán HDFS, cung cấp khả năng lưu trữ và xử lý dữ liệu lớn trên cụm máy tính.

• Các thuật toán khai phá đồ thị con thường xuyên: Bao gồm các thuật toán tìm kiếm theo chiều rộng như FSG, Subdue và theo chiều sâu như gSpan, FFSM. Các thuật toán này dựa trên nguyên tắc Apriori hoặc tìm kiếm sâu để phát hiện các đồ thị con thường xuyên.

Phương pháp nghiên cứu

Luận văn sử dụng phương pháp nghiên cứu kết hợp lý thuyết và thực nghiệm:

• Nguồn dữ liệu: Sử dụng các bộ dữ liệu đồ thị có cấu trúc hóa học và mạng xã hội với kích thước từ 500 đến 1000 đồ thị, có nhãn đỉnh và cạnh đa dạng.

• Phương pháp phân tích: Thuật toán khai phá đồ thị con thường xuyên được cài đặt trên nền tảng Hadoop sử dụng mô hình MapReduce. Các bước thực hiện bao gồm:

  1. Phân tích và chuẩn bị dữ liệu đầu vào dưới dạng cặp key/value phù hợp với mô hình MapReduce.

  2. Cài đặt hàm map để sinh ra các đồ thị con ứng viên và kiểm tra đẳng cấu.

  3. Cài đặt hàm reduce để tính toán độ hỗ trợ và lọc các đồ thị con thường xuyên.

  4. Thực hiện các vòng lặp để mở rộng kích thước đồ thị con theo thuật toán Apriori.

• Timeline nghiên cứu: Quá trình nghiên cứu kéo dài khoảng 12 tháng, trong đó 4 tháng đầu tập trung vào nghiên cứu lý thuyết và chuẩn bị dữ liệu, 5 tháng tiếp theo cài đặt và tối ưu thuật toán trên Hadoop, 3 tháng cuối thực nghiệm, đánh giá và hoàn thiện luận văn.

• Cỡ mẫu và chọn mẫu: Bộ dữ liệu thử nghiệm gồm khoảng 3 bộ dữ liệu với kích thước lần lượt là 500, 700 và 1000 đồ thị, được lựa chọn đại diện cho các trường hợp kích thước nhỏ đến vừa và lớn để đánh giá hiệu năng thuật toán.

• Phương pháp đánh giá: So sánh thời gian chạy, độ chính xác và khả năng mở rộng của thuật toán MapReduce với các thuật toán truyền thống như gSpan và FSM-H.

Kết quả nghiên cứu và thảo luận

Những phát hiện chính

1. Hiệu năng xử lý được cải thiện rõ rệt: Thuật toán khai phá đồ thị con thường xuyên trên mô hình MapReduce (FSM-H) cho thấy thời gian xử lý giảm trung bình 40% so với thuật toán gSpan trên cùng bộ dữ liệu 1000 đồ thị với ngưỡng minsup 0.3. Cụ thể, thời gian chạy của FSM-H là khoảng 120 phút, trong khi gSpan mất khoảng 200 phút.

2. Khả năng mở rộng tốt trên tập dữ liệu lớn: Khi kích thước bộ dữ liệu tăng từ 500 lên 1000 đồ thị, thời gian xử lý của FSM-H tăng không quá 1.8 lần, trong khi gSpan tăng gần gấp đôi. Điều này chứng tỏ mô hình MapReduce giúp phân tán tải tính toán hiệu quả.

3. Độ chính xác và tính đầy đủ của kết quả: FSM-H đảm bảo phát hiện đầy đủ các đồ thị con thường xuyên với độ hỗ trợ tối thiểu, tương đương với các thuật toán truyền thống, không có sai lệch về kết quả.

4. Giảm thiểu bộ nhớ lưu trữ: Nhờ việc phân tán dữ liệu và xử lý song song, FSM-H giảm được khoảng 30% bộ nhớ cần thiết so với các thuật toán chạy trên máy đơn, nhờ đó có thể xử lý các tập dữ liệu lớn hơn.

Thảo luận kết quả

Nguyên nhân chính của sự cải thiện hiệu năng là do mô hình MapReduce tận dụng được khả năng xử lý song song và phân tán trên nhiều nút trong cụm Hadoop, giảm tải cho từng máy tính đơn lẻ. Việc chia nhỏ dữ liệu đầu vào thành các split và thực thi đồng thời các hàm map giúp tăng tốc độ sinh ứng viên và kiểm tra đẳng cấu.

So với các nghiên cứu trước đây, kết quả thực nghiệm của luận văn phù hợp với báo cáo của ngành về hiệu quả của mô hình MapReduce trong xử lý dữ liệu lớn. Biểu đồ so sánh thời gian chạy giữa FSM-H và gSpan trên các bộ dữ liệu khác nhau minh họa rõ ràng sự vượt trội của FSM-H.

Ý nghĩa của kết quả này là mở ra hướng phát triển các thuật toán khai phá dữ liệu đồ thị trên nền tảng phân tán, giúp giải quyết các bài toán phức tạp với dữ liệu lớn trong thực tế như phân tích mạng xã hội, phát hiện cấu trúc hóa học, và các ứng dụng sinh học phân tử.

Đề xuất và khuyến nghị

1. Tối ưu hóa thuật toán MapReduce cho khai phá đồ thị: Cần tiếp tục cải tiến các bước sinh ứng viên và kiểm tra đẳng cấu để giảm thiểu số lượng đồ thị con không cần thiết, từ đó giảm thời gian xử lý và tài nguyên sử dụng. Thời gian thực hiện dự kiến 6 tháng, do nhóm nghiên cứu CNTT đảm nhiệm.

2. Mở rộng ứng dụng trên các nền tảng đám mây: Triển khai thuật toán trên các dịch vụ đám mây như AWS, Azure để tận dụng khả năng mở rộng linh hoạt và giảm chi phí đầu tư hạ tầng. Khuyến nghị thực hiện trong vòng 1 năm, phối hợp với các đơn vị cung cấp dịch vụ đám mây.

3. Phát triển giao diện người dùng trực quan: Xây dựng công cụ hỗ trợ trực quan hóa kết quả khai phá đồ thị con thường xuyên, giúp người dùng dễ dàng phân tích và ứng dụng kết quả. Thời gian phát triển khoảng 4 tháng, do nhóm phát triển phần mềm đảm nhận.

4. Nâng cao khả năng xử lý dữ liệu phi cấu trúc và đa dạng: Nghiên cứu tích hợp các kỹ thuật xử lý dữ liệu phi cấu trúc, dữ liệu thời gian thực vào mô hình khai phá đồ thị để mở rộng phạm vi ứng dụng. Thời gian nghiên cứu 8 tháng, do nhóm nghiên cứu khoa học máy tính thực hiện.

Đối tượng nên tham khảo luận văn

1. Nhà nghiên cứu và sinh viên ngành Khoa học máy tính: Luận văn cung cấp kiến thức chuyên sâu về khai phá dữ liệu đồ thị và mô hình lập trình phân tán MapReduce, hỗ trợ nghiên cứu và phát triển các thuật toán xử lý dữ liệu lớn.

2. Chuyên gia phát triển phần mềm và kỹ sư dữ liệu: Tham khảo để áp dụng mô hình MapReduce và nền tảng Hadoop trong các dự án xử lý dữ liệu lớn, đặc biệt trong lĩnh vực khai phá dữ liệu đồ thị phức tạp.

3. Doanh nghiệp công nghệ và các tổ chức nghiên cứu: Sử dụng kết quả nghiên cứu để nâng cao hiệu quả xử lý dữ liệu lớn, phát triển các sản phẩm phân tích mạng xã hội, sinh học phân tử, và các ứng dụng liên quan.

4. Nhà quản lý và hoạch định chính sách trong lĩnh vực CNTT: Hiểu rõ tiềm năng và ứng dụng của công nghệ khai phá dữ liệu đồ thị trên nền tảng phân tán, từ đó định hướng đầu tư và phát triển công nghệ phù hợp.

Câu hỏi thường gặp

1. Khai phá đồ thị con thường xuyên là gì và tại sao quan trọng?
   Khai phá đồ thị con thường xuyên là quá trình tìm kiếm các mẫu đồ thị con xuất hiện với tần suất cao trong tập dữ liệu đồ thị lớn. Nó giúp phát hiện các cấu trúc lặp lại quan trọng, hỗ trợ phân tích, phân loại và dự đoán trong nhiều lĩnh vực như mạng xã hội, hóa học và sinh học.

2. Mô hình MapReduce giúp gì cho khai phá dữ liệu đồ thị?
   MapReduce cho phép phân tán công việc xử lý dữ liệu lớn thành các tác vụ nhỏ thực hiện song song trên nhiều máy tính, giúp tăng tốc độ xử lý và khả năng mở rộng, đặc biệt hữu ích với các bài toán phức tạp như khai phá đồ thị con thường xuyên.

3. Tại sao Hadoop được chọn làm nền tảng thực thi?
   Hadoop là hệ thống mã nguồn mở phổ biến hỗ trợ mô hình MapReduce, có khả năng lưu trữ và xử lý dữ liệu lớn trên cụm máy tính phân tán, đảm bảo độ tin cậy và hiệu suất cao, phù hợp với yêu cầu xử lý dữ liệu đồ thị lớn.

4. Các thuật toán khai phá đồ thị con thường xuyên truyền thống có hạn chế gì?
   Các thuật toán như gSpan, FFSM, FSG có độ phức tạp tính toán cao, thời gian xử lý không đa thức, và yêu cầu bộ nhớ lớn, làm hạn chế khả năng xử lý các tập dữ liệu lớn và phức tạp trong thực tế.

5. Kết quả thực nghiệm cho thấy hiệu quả của mô hình MapReduce như thế nào?
   Thực nghiệm trên các bộ dữ liệu từ 500 đến 1000 đồ thị cho thấy thuật toán khai phá đồ thị con thường xuyên trên mô hình MapReduce giảm thời gian xử lý trung bình 40% so với thuật toán truyền thống, đồng thời cải thiện khả năng mở rộng và giảm bộ nhớ sử dụng.

Kết luận

• Luận văn đã nghiên cứu và triển khai thành công thuật toán khai phá đồ thị con thường xuyên trên mô hình MapReduce, sử dụng nền tảng Hadoop, đáp ứng tốt yêu cầu xử lý dữ liệu lớn có cấu trúc phức tạp.
• Kết quả thực nghiệm chứng minh hiệu năng xử lý được cải thiện rõ rệt, giảm thời gian chạy và tăng khả năng mở rộng so với các thuật toán truyền thống.
• Nghiên cứu góp phần mở rộng ứng dụng của mô hình MapReduce trong lĩnh vực khai phá dữ liệu đồ thị, hỗ trợ các ngành khoa học và công nghệ phát triển.
• Đề xuất các giải pháp tối ưu hóa thuật toán, mở rộng ứng dụng trên nền tảng đám mây và phát triển công cụ trực quan hóa kết quả.
• Các bước tiếp theo bao gồm triển khai thực tế trên các hệ thống lớn hơn, nghiên cứu tích hợp dữ liệu phi cấu trúc và phát triển giao diện người dùng thân thiện.

Để tiếp tục phát triển lĩnh vực này, các nhà nghiên cứu và chuyên gia công nghệ được khuyến khích áp dụng và mở rộng các kết quả nghiên cứu trong luận văn nhằm giải quyết các bài toán thực tiễn ngày càng phức tạp.

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

CHƯƠNG 1: KIẾN THỨC TỔNG QUAN 1.1 Đồ thị con thường xuyên Trong phần này ta ký hiệu tập các đỉnh của đồ thị là V, tập các cạnh là E và tập các nhãn là L. Đồ thị gán nhãn Định nghĩa 1.1 [5] Cho một tập nhãn các đỉnh LV và một tập nhãn cạnh LE. Một đồ thị được gán nhãn g là một bộ gồm 4 thành phần g = (V, E, µ, ν), trong đó:  V là một tập hữu hạn các đỉnh.  E ⊆ V×V là một tập các cạnh.

 µ : V→LV là hàm gán nhãn cho các đỉnh.  ν : E→LE là hàm gán nhãn cho các cạnh. Tập V có thể được coi là một tập các định danh đỉnh và thường được đánh số bằng tập các số tự nhiên V = {1,. Trong khi V xác định các đỉnh, tập các cạnh E thể hiện cấu trúc của đồ thị.

Đó là một đỉnh u ∈ V được kết nối với một đỉnh v ∈ V bằng một cạnh (u, v) nếu (u, v) ∈ E. Hàm ghi nhãn có thể được sử dụng để tích hợp thông tin về các đỉnh và các cạnh vào trong các đồ thị bằng cách gán các thuộc tính từ LV và LE tới các đỉnh và các cạnh tương ứng. Ví dụ: [14] đồ thị biểu diễn các kết nối hóa học của axit sulfuric. V = {1, 2, 3, 4, 5, 6, 7}, LV = {O, S, H}, E = {(1, 3), (2,3), (3, 4), (3, 5), (4, 6), (5, 7)}, LE= {SingleLink, DoubleLink} e 8 V µ E v 1 O (1,3) DoubleLink 2 O (2,3) DoubleLink 3 S (3,4) SingleLink 4 O (3,5) SingleLink 5 O (4,6) SingleLink 6 H (5,7) SingleLink 7 H Hình 1.

Đồ thị các kết nối hóa học của axit Sulfuric [13] 1. Đồ thị con Định nghĩa 1. Đồ thị g1 là đồ thị con của đồ thị g2, ký hiệu g1 ⊆ g2 nếu:  V1 ⊆ V2  E1 = E2 ∩ (V1×V1)  µ1(u) = µ2(u) với mọi u ∈ V1  ν1(u, v) = ν2(u, v) với mọi (u, v) ∈ E1 Ví dụ: đồ thị chứa kết nối O-H là một đồ thị con trong đồ thị biểu diễn kết nối hóa học của axit Sulfuric. Đồ thị đẳng cấu Định nghĩa 1.

Một đồ thị đẳng cấu giữa g1 và g2 là một hàm song ánh f : V1→V2 thỏa mãn:  µ1(u) = µ2(f (u)) với mọi u ∈ V1. e 9  Với mỗi cạnh e1 = (u, v) ∈ E1, tồn tại một cạnh e2 = (f (u), f (v)) ∈ E2 sao cho ν1(e1) = ν2(e2).  Với mỗi cạnh e2 = (u, v) ∈ E2, tồn tại một cạnh e1 = (f-1(u), f-1(v)) ∈ E1 sao cho ν1(e1) = ν2(e2). Hai đồ thị g1 và g2 được gọi là đẳng cấu nếu tồn tại một đồ thị đẳng cấu giữa chúng.

Ví dụ: hai đồ thị hình dưới là đẳng cấu. Đồ thị đẳng cấu 1. Đồ thị con đẳng cấu Định nghĩa 1.4 [5] Cho g là một đồ thị, g1 là một đồ thị con đẳng cấu của đồ thị g nếu tồn tại một đồ thị g2 con của g sao cho g1 đẳng cấu với g2. Ví dụ: trong hình dưới, đồ thị Q là đồ thị con đẳng cấu của đồ thị P.

Đồ thị con đẳng cấu 1.5 Đồ thị con thường xuyên Định nghĩa 1.5 [13] e 10 Cho một tập đồ thị D và một ngưỡng hỗ trợ tối thiểu minsup, độ hỗ trợ của một đồ thị g đối với D, ký hiệu supg là số đồ thị trong D mà g là đồ thị con đẳng cấu của nó. |{𝑔 ′ ∈ 𝐷 |𝑔  𝑔′}| supg= |𝐷| Đồ thị g được gọi là đồ thị con thường xuyên trong D nếu supg  minsup.4 biểu diễn một đồ thị con thường xuyên trong tập dữ liệu đồ thị các kết nối hóa học với minsup =2/4=0. Đồ thị con thường xuyên [14] Phát hiện các đồ thị con thường xuyên là một trong những nhiệm vụ cơ bản trong khai phá dữ liệu có cấu trúc từ việc phát hiện các mẫu có thể được sử dụng cho những đặc trưng của những bộ dữ liệu có cấu trúc, phân loại và phân nhóm các cấu trúc phức tạp, xây dựng các chỉ số đồ thị và thực hiện việc tìm kiếm tương tự trong cơ sở dữ liệu đồ thị lớn. Hiện nay đã có vài thuật toán khai phá đồ thị con thường xuyên như gSpan [15], FFSM [6], FSG [10].

Tuy nhiên các thuật toán này có độ phức tạp thời gian không đa thức nên hạn chế trong việc khai phá các tập dữ liệu e 11 lớn. Để khắc phục điều này một số nghiên cứu đã cải tiến thuật toán trên mô hình lập trình song song MapReduce và thực thiện trên nền tảng Hadoop.2 Nền tảng Hadoop Hiện nay có rất nhiều công cụ dùng để xử lý dữ liệu lớn đã và đang được nghiên cứu và phát triển bởi các viện nghiên cứu lớn trên thế giới. Các công cụ này giúp cho việc xử lý một lượng dữ liệu khổng lồ một cách nhanh chóng, giúp người dùng có thể dễ dàng tìm được thông tin cần thiết trong thời gian thực, nhất là khi kỷ nguyên của exabytes đang đến gần.1 Tổng quát về Apache Hadoop Hadoo là một dự án phần mềm mã nguồn mở được phát triển bởi Apache, nhằm thu các giá trị có ích từ khối lượng, tốc độ và tính đa dạng của dữ liệu (cấu trúc/phi cấu trúc). Apache Hadoop là một khuôn khổ cho phép để xử lý và phân phối các bộ dữ liệu lớn trên các cụm máy tính sử dụng mô hình lập trình đơn giản.

Nó được thiết kế để mở rộng từ một máy chủ duy nhất đến hàng ngàn máy, mỗi máy cung cấp tính toán và lưu trữ địa phương. Không giống như các hệ quản trị cơ sở dữ liệu truyền thống, Hadoop được thiết kế để làm việc với nhiều loại dữ liệu và dữ liệu nguồn. Công nghệ HDFS của Hadoop cho phép khối lượng lớn công việc được chia thành các khối dữ liệu nhỏ hơn được nhân rộng và phân phối trên các phần cứng của một cluster để xử lý nhanh hơn. Công nghệ này đã được sử dụng rộng rãi bởi một số trang web lớn nhất thế giới, chẳng hạn như Facebook, eBay, Amazon, Baidu, và Yahoo.

Các nhà quan sát nhấn mạnh rằng Yahoo là một trong những nhà đóng góp lớn nhất đối với Hadoop.2 Kiến trúc Hadoop Hadoop làm việc trên nguyên tắc xử lí theo lô dựa trên một cụm máy tính gọi là các nút (nodes). Các nút được cung cấp nền tảng phục vụ các hoạt động phân tích dữ liệu lớn theo mô hình ánh xạ rút gọn (Map-reduce) cho dữ e 12 liệu phi cấu trúc trên hệ thống tập tin phân tán. Hadoop là nền tảng chính đóng góp cho thành công của bộ tìm kiếm Yahoo. Hadoop bao gồm nhiều thành phần cung cấp chức năng tính toán song song và phân tán.

Kiến trúc tổng quát của Hadoop được cho trong Hình 1. Kiến trúc Hadoop Lõi (core) Hadoop Là bao gồm một tập hợp của các thành phần và các giao diện cung cấp chức năng truy cập vào các hệ thống tập tin phân tán và vào ra tổng quát. Các thành phần cốt lõi cũng cung cấp sự tối ưu hóa dựa vào phân nhóm địa lý của máy chủ nhằm giảm thiểu lưu lượng mạng giữa các máy chủ trong các cụm tính toán. Hệ thống tập tin phân tán (Hadoop Distributed File System-HDFS) Là hệ thống lưu trữ chính được sử dụng bởi các ứng dụng Hadoop.

HDFS, như tên gọi của nó, một hệ thống tập tin phân tán cung cấp truy cập thông lượng cao vào dữ liệu của ứng dụng, tạo ra nhiều bản sao của khối dữ liệu và phân phối chúng trên các nút tính toán trong một cụm để cho phép tính toán song song, đáng tin cậy và nhanh chóng. Hbase Là một cơ sở dữ liệu phân tán theo cột. HBase sử dụng HDFS cho việc e 13 lưu trữ cơ bản của nó. Nó ánh xạ dữ liệu HDFS vào một cơ sở dữ liệu có cấu trúc giống và cung cấp các giao diện lập trình được cho Java (Java API) truy cập vào CSDL này.

Nó hỗ trợ hàng loạt kiểu tính toán sử dụng các truy vấn MapReduce và đọc ngẫu nhiên. HBase thường được sử dụng trong Hadoop khi có truy cập đọc/ ghi ngẫu nhiên, thời gian thực. Mục tiêu của nó là lưu trữ các bảng rất lớn đang chạy trên cụm thiết bị phần cứng. Pig Là ngôn ngữ xử lí dòng dữ liệu.

Apache Pig là một nền tảng cho việc phân tích dữ liệu lớn bao gồm một ngôn ngữ cấp cao để diễn tả các chương trình phân tích dữ liệu. Đặc điểm chính của chương trình Pig là cấu trúc của chúng có thể được song song hóa cho phép nó xử lý các tập hợp dữ liệu rất lớn, cú pháp đơn giản. Các tính năng xây dựng sẵn (built-in functionality) cung cấp một mức độ trừu trượng để cho phát triển các công việc Hadoop nhanh hơn và dễ dàng hơn để viết hơn so với MapReduce truyền thống. Zookeeper Là một công cụ cấu hình cụm (cluster) và quản lý sự dãy hóa (serialization) rất hữu ích để xây dựng các cụm lớn các nút của Hadoop, dịch vụ hiệu năng cao cho các ứng dụng phân tán.

Nó tập trung vào các dịch vụ như quản lí thông tin cấu hình, đặt tên, đồng bộ hóa phân tán cũng và các dịch vụ nhóm. Hive Là một kho dữ liệu cơ sở hạ tầng được xây dựng trên Hadoop. Hive cung cấp các công cụ để cho phép tóm tắt dữ liệu, truy vấn không chuẩn (ad- hoc) và phân tích các bộ dữ liệu lớn được lưu trữ trong các tập tin Hadoop. Nó cung cấp một cơ chế để định cấu trúc cho loại dữ liệu này và cung cấp e 14 một ngôn ngữ truy vấn đơn giản gọi là Hive QL, dựa trên SQL, cho phép người sử dụng quen thuộc với SQL để truy vấn dữ liệu này.

Chukwa: Công cụ mã nguồn mở, được sử dụng để quản lí các cụm lớn máy chủ phân tán. Nó là một hệ thống thu thập dữ liệu để theo dõi các hệ thống phân tán lớn. Chukwa bao gồm một bộ công cụ linh hoạt và mạnh mẽ cho hiển thị, theo dõi và phân tích kết quả để sử dụng tốt nhất các dữ liệu thu thập được. HCatalog: Là một lớp quản lý lưu trữ cho Hadoop cho phép người dùng sử dụng với các công cụ xử lý dữ liệu khác nhau.

Bảng HCatalog trình bày cho người dùng một khung nhìn kiểu quan hệ cho dữ liệu trong hệ thống tập tin phân tán Hadoop (HDFS) và đảm bảo rằng người dùng không cần phải quan tâm về nơi lưu trữ hoặc định dạng của dữ liệu được lưu trữ.