Link tải luận văn miễn phí cho ae Kết nối
MỞ ĐẦU
Hiện nay, các phƣơng pháp khai phá dữ liệu đang phải đối diện với vấn
đề số lƣợng ngày càng gia tăng của các đối tƣợng dữ liệu phức tạp. Bên cạnh
đó đồ thị là một cấu trúc dữ liệu tổng quát, có thể sử dụng để mô hình hóa các
đối dữ liệu tƣợng phức tạp đó và vấn đề khai phá đồ thị con thƣờng xuyên là
một trong những vấn đề quan trọng trong khai phá đồ thị. Việc khai phá đồ thị
để tìm đồ thị con thƣờng xuyên nhằm xác định tất cả các đồ thị con trong một
tập dữ liệu đồ thị với giá trị ngƣỡng cho trƣớc [1],[3].
Những khó khăn của vấn đề khai phá đồ thị con thƣờng xuyên nảy sinh
hai vấn đề, đó là: liệt kê tất cả các đồ thị con trong CSDL đồ thị và tính toán
hàm hỗ trợ của các đồ thị con này trong CSDL. Do các đỉnh của đồ thị có thể
đƣợc sắp xếp theo nhiều cách, một đồ thị có thể có số lƣợng lớn các bản sao
hình học tƣơng đƣơng, đƣợc gọi là đồ thị đẳng cấu. Để liệt kê tất cả các đồ thị
con, ta phải tính toán phù hợp với quy tắc biểu diễn đồ thị để giải quyết vấn
đề đồ thị đẳng cấu. Hơn nữa, việc kiểm tra nếu một đồ thị có chứa trong một
CSDL đồ thị hay không đƣợc xem nhƣ bài toán NP-khó và đƣợc gọi là bài
toán đồ thị con đẳng cấu. Trong tất cả các trƣờng hợp, việc tính toán hàm hỗ
trợ chiếm chi phí nhiều nhất trong việc tìm các đồ thị con thƣờng xuyên của
CSDL. Tuy nhiên, sự phức tạp của những vấn đề này sẽ giảm khi CSDL đồ
thị có thêm thông tin về các đỉnh và các cạnh đã đƣợc gán nhãn. Có thể sử
dụng các nhãn để hạn chế các đỉnh có thể tạo thành các cặp trong quá trình
kiểm tra sự đẳng cấu của đồ thị con. Tuy nhiên, nếu CSDL đồ thị chƣa đƣợc
gán nhãn hay chỉ có một số ít các nhãn thì độ phức tạp của bài toán sẽ làm
giảm đáng kể kích thƣớc của tập dữ liệu.
Nhƣ vậy, vấn đề khai phá đồ thị nói chung và khai phá đồ thị con thƣờng
xuyên nói riêng cũng gặp nhiều khó khăn, vì vậy ta cần lựa chọn phƣơng pháp
và thuật toán phù hợp để giải quyết cho từng bài toán cụ thể, đem lại hiệu quả
cao đó chính là ý nghĩa thực tiễn của đề tài.
Nội dung của luận văn và các vấn đề cần giải quyết:
1. Tìm hiểu về các phƣơng pháp khai phá dữ liệu đồ thị.
2. Tìm hiểu các thuật toán phát hiện đồ thị con thƣờng xuyên trong CSDL đồ
thị.
3. Cài đặt thử nghiệm thuật toán phát hiện các đồ thị con thƣờng xuyên
trong CSDL đồ thị
Phƣơng pháp nghiên cứu
+ Nghiên cứu về khai phá dữ liệu đồ thị với trọng tâm là phát hiện các đồ
thị con thƣờng xuyên trong CSDL đồ thị.
+ Tìm hiểu các nguồn thông tin từ các sách,bài báo,tạp chí, Internet..,liên
quan đến khai phá dữ liệu đồ thị.
Cấu trúc luận văn chia làm 4 chƣơng:
Chƣơng 1: “ Tổng quan về khai phá dữ liệu đồ thị ” trình bày tổng quan
các hƣớng nghiên cứu hiện nay về khai phá dữ liệu đồ thị.
Chƣơng 2: “ Phát hiện các cấu trúc con thƣờng xuyên ” trình bày cơ sở lý
thuyết đồ thị, cách tiếp cận dựa trên Apriori, cách tiếp cận dựa trên sự phát
triển mẫu.
Chƣơng 3: “ Các thuật toán phát hiện đồ thị con thƣờng xuyên ” trình
bày một số thuật toán phát hiện đồ thị con thƣờng xuyên theo chiến lƣợc tìm
kiếm theo chiều rộng và chiều sâu.
Chƣơng 4: “ Thiết kế hệ thống thử nghiệm ” trình bày kết quả cài đặt của
thuật toán trong chƣơng 3.
CHƢƠNG 1: TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU ĐỒ THỊ
1.1.TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU ĐỒ THỊ:
Khai phá dữ liệu đồ thị là một trong số các lĩnh vực quan trọng trong
khai phá dữ liệu. Hầu hết nguồn dữ liệu hiện nay có thể biểu diễn đƣợc dƣới
dạng cấu trúc dữ liệu đồ thị, chẳng hạn nhƣ: dữ liệu từ mạng Internet, mạng
xã hội, cấu trúc protein, hợp chất hóa học,... Do đó, khai phá dữ liệu đồ thị
nhằm tìm kiếm các thông tin hữu ích trong một lƣợng lớn dữ liệu là vấn đề
đang đƣợc các nhà nghiên cứu và các tổ chức CNTT quan tâm.
1.1.1. Định nghĩa dữ liệu lớn:
Hiện nay, thuật ngữ “Dữ liệu lớn” (Big data) đang thu hút sự quan tâm
cũng nhƣ đặt ra những thách thức mới với các nhà nghiên cứu, các nhà cung
cấp dịch vụ công nghệ thông tin và các tổ chức, doanh nghiệp. Dữ liệu lớn
đƣợc xem nhƣ sự ra đời tất yếu của quá trình bùng nổ thông tin.
Trong nhiều năm qua, các doanh nghiệp thƣờng đƣa ra các quyết định kinh
doanh dựa trên dữ liệu giao dịch đƣợc lƣu trữ trong cơ sở dữ liệu quan hệ.
Ngoài ra những dữ liệu quan trọng lại thƣờng ở dạng tiềm năng, phi truyền
thống, phi cấu trúc lại có thể đƣợc khai thác một cách hữu ích, giảm chi phí cả
về lƣu trữ và tính toán. Khi dữ liệu lớn đƣợc đƣợc khai thác và phân tích, kết
hợp với dữ liệu doanh nghiệp truyền thống thì các doanh nghiệp sẽ có cái
nhìn toàn diện và sâu sắc hơn về tình hình kinh doanh của họ, dẫn tới nâng
cao năng suất và vị thế cạnh tranh. Do đó, ngày càng có nhiều công ty tìm
kiếm để có đƣợc các dữ liệu phi truyền thống nhƣng rất có giá trị trong công
việc kinh doanh này.
Có thể định nghĩa một cách chung nhất thì “Dữ liệu lớn” là một tập hợp
của các tập dữ liệu lớn và/hay phức tạp mà những phƣơng pháp hiện tại của
CNTT chƣa thể phân tích và xử lý tốt đƣợc chúng.
Do Drive thay đổi chính sách, nên một số link cũ yêu cầu duyệt download. các bạn chỉ cần làm theo hướng dẫn.
Password giải nén nếu cần: ket-noi.com | Bấm trực tiếp vào Link để tải:
MỞ ĐẦU
Hiện nay, các phƣơng pháp khai phá dữ liệu đang phải đối diện với vấn
đề số lƣợng ngày càng gia tăng của các đối tƣợng dữ liệu phức tạp. Bên cạnh
đó đồ thị là một cấu trúc dữ liệu tổng quát, có thể sử dụng để mô hình hóa các
đối dữ liệu tƣợng phức tạp đó và vấn đề khai phá đồ thị con thƣờng xuyên là
một trong những vấn đề quan trọng trong khai phá đồ thị. Việc khai phá đồ thị
để tìm đồ thị con thƣờng xuyên nhằm xác định tất cả các đồ thị con trong một
tập dữ liệu đồ thị với giá trị ngƣỡng cho trƣớc [1],[3].
Những khó khăn của vấn đề khai phá đồ thị con thƣờng xuyên nảy sinh
hai vấn đề, đó là: liệt kê tất cả các đồ thị con trong CSDL đồ thị và tính toán
hàm hỗ trợ của các đồ thị con này trong CSDL. Do các đỉnh của đồ thị có thể
đƣợc sắp xếp theo nhiều cách, một đồ thị có thể có số lƣợng lớn các bản sao
hình học tƣơng đƣơng, đƣợc gọi là đồ thị đẳng cấu. Để liệt kê tất cả các đồ thị
con, ta phải tính toán phù hợp với quy tắc biểu diễn đồ thị để giải quyết vấn
đề đồ thị đẳng cấu. Hơn nữa, việc kiểm tra nếu một đồ thị có chứa trong một
CSDL đồ thị hay không đƣợc xem nhƣ bài toán NP-khó và đƣợc gọi là bài
toán đồ thị con đẳng cấu. Trong tất cả các trƣờng hợp, việc tính toán hàm hỗ
trợ chiếm chi phí nhiều nhất trong việc tìm các đồ thị con thƣờng xuyên của
CSDL. Tuy nhiên, sự phức tạp của những vấn đề này sẽ giảm khi CSDL đồ
thị có thêm thông tin về các đỉnh và các cạnh đã đƣợc gán nhãn. Có thể sử
dụng các nhãn để hạn chế các đỉnh có thể tạo thành các cặp trong quá trình
kiểm tra sự đẳng cấu của đồ thị con. Tuy nhiên, nếu CSDL đồ thị chƣa đƣợc
gán nhãn hay chỉ có một số ít các nhãn thì độ phức tạp của bài toán sẽ làm
giảm đáng kể kích thƣớc của tập dữ liệu.
Nhƣ vậy, vấn đề khai phá đồ thị nói chung và khai phá đồ thị con thƣờng
xuyên nói riêng cũng gặp nhiều khó khăn, vì vậy ta cần lựa chọn phƣơng pháp
và thuật toán phù hợp để giải quyết cho từng bài toán cụ thể, đem lại hiệu quả
cao đó chính là ý nghĩa thực tiễn của đề tài.
Nội dung của luận văn và các vấn đề cần giải quyết:
1. Tìm hiểu về các phƣơng pháp khai phá dữ liệu đồ thị.
2. Tìm hiểu các thuật toán phát hiện đồ thị con thƣờng xuyên trong CSDL đồ
thị.
3. Cài đặt thử nghiệm thuật toán phát hiện các đồ thị con thƣờng xuyên
trong CSDL đồ thị
Phƣơng pháp nghiên cứu
+ Nghiên cứu về khai phá dữ liệu đồ thị với trọng tâm là phát hiện các đồ
thị con thƣờng xuyên trong CSDL đồ thị.
+ Tìm hiểu các nguồn thông tin từ các sách,bài báo,tạp chí, Internet..,liên
quan đến khai phá dữ liệu đồ thị.
Cấu trúc luận văn chia làm 4 chƣơng:
Chƣơng 1: “ Tổng quan về khai phá dữ liệu đồ thị ” trình bày tổng quan
các hƣớng nghiên cứu hiện nay về khai phá dữ liệu đồ thị.
Chƣơng 2: “ Phát hiện các cấu trúc con thƣờng xuyên ” trình bày cơ sở lý
thuyết đồ thị, cách tiếp cận dựa trên Apriori, cách tiếp cận dựa trên sự phát
triển mẫu.
Chƣơng 3: “ Các thuật toán phát hiện đồ thị con thƣờng xuyên ” trình
bày một số thuật toán phát hiện đồ thị con thƣờng xuyên theo chiến lƣợc tìm
kiếm theo chiều rộng và chiều sâu.
Chƣơng 4: “ Thiết kế hệ thống thử nghiệm ” trình bày kết quả cài đặt của
thuật toán trong chƣơng 3.
CHƢƠNG 1: TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU ĐỒ THỊ
1.1.TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU ĐỒ THỊ:
Khai phá dữ liệu đồ thị là một trong số các lĩnh vực quan trọng trong
khai phá dữ liệu. Hầu hết nguồn dữ liệu hiện nay có thể biểu diễn đƣợc dƣới
dạng cấu trúc dữ liệu đồ thị, chẳng hạn nhƣ: dữ liệu từ mạng Internet, mạng
xã hội, cấu trúc protein, hợp chất hóa học,... Do đó, khai phá dữ liệu đồ thị
nhằm tìm kiếm các thông tin hữu ích trong một lƣợng lớn dữ liệu là vấn đề
đang đƣợc các nhà nghiên cứu và các tổ chức CNTT quan tâm.
1.1.1. Định nghĩa dữ liệu lớn:
Hiện nay, thuật ngữ “Dữ liệu lớn” (Big data) đang thu hút sự quan tâm
cũng nhƣ đặt ra những thách thức mới với các nhà nghiên cứu, các nhà cung
cấp dịch vụ công nghệ thông tin và các tổ chức, doanh nghiệp. Dữ liệu lớn
đƣợc xem nhƣ sự ra đời tất yếu của quá trình bùng nổ thông tin.
Trong nhiều năm qua, các doanh nghiệp thƣờng đƣa ra các quyết định kinh
doanh dựa trên dữ liệu giao dịch đƣợc lƣu trữ trong cơ sở dữ liệu quan hệ.
Ngoài ra những dữ liệu quan trọng lại thƣờng ở dạng tiềm năng, phi truyền
thống, phi cấu trúc lại có thể đƣợc khai thác một cách hữu ích, giảm chi phí cả
về lƣu trữ và tính toán. Khi dữ liệu lớn đƣợc đƣợc khai thác và phân tích, kết
hợp với dữ liệu doanh nghiệp truyền thống thì các doanh nghiệp sẽ có cái
nhìn toàn diện và sâu sắc hơn về tình hình kinh doanh của họ, dẫn tới nâng
cao năng suất và vị thế cạnh tranh. Do đó, ngày càng có nhiều công ty tìm
kiếm để có đƣợc các dữ liệu phi truyền thống nhƣng rất có giá trị trong công
việc kinh doanh này.
Có thể định nghĩa một cách chung nhất thì “Dữ liệu lớn” là một tập hợp
của các tập dữ liệu lớn và/hay phức tạp mà những phƣơng pháp hiện tại của
CNTT chƣa thể phân tích và xử lý tốt đƣợc chúng.
Do Drive thay đổi chính sách, nên một số link cũ yêu cầu duyệt download. các bạn chỉ cần làm theo hướng dẫn.
Password giải nén nếu cần: ket-noi.com | Bấm trực tiếp vào Link để tải:
You must be registered for see links