ݺߣ

ݺߣShare a Scribd company logo

Tai liệu thuyết trình môn khai phá dữ liệu

•Download as DOCX, PDF•
•
freeloadtailieu
freeloadtailieu

data mining

1 of 2
Downloaded 10 times
http://doc.edu.vn/tai-lieu/luan-van-phuong-phap-phan-cum-va-ung-dung-42382/ Clique Cho một đồ thị G(V,E)G(V,E), một tập đỉnh X⊆VX⊆V được gọi là một tập phủ đỉnh (vertex cover) nếu như với mọi cạnh ee của đồ thị, ít nhất một trong hai đầu mút của nó thuộc XX. Tập XX được gọi là một Clique nếu như giữa mọi cặp đỉnh của XXđều tồn tại một cạnh của đồ thị nối hai đỉnh đó. Xem ví dụ trong hình minh họa trong Figure 4. Figure 4: (a) Các đỉnh được tô đậm màu đỏ thuộc Clique có kích thước 4 trong đồ thị và (b) các đỉnh được tô đậm màu xanh là một tập phủ đỉnh của đồ thị. Bài toán VERTEXCOVER được định nghĩa như sau: VERT EXCOVER. Cho một đồ thị vô hướng G(V,E)G(V,E) và một số nguyên KK. Có tồn tại hay không một tập phủ đỉnh có kích thước không quá KK trong đồ thị? Ta có: Lemma 2: VERT EXCOVER ∈∈ Np-complete Chứng minh: Ta sẽ quy dẫn từ bài toán INDEPENDENTSET. Ở đây mình chỉ lượt qua ý tưởng. Chi tiết chứng minh theo từng bước coi như bài tập của bạn đọc. Chứng minh dựa trên nhận xét: nếu XX là một tập phủ đỉnh của đồ thị thì V∖XV∖Xlà một tập độc lập của đồ thị. Nhận xét này có thể chứng minh bằng phản chứng như sau. Kí hiệu X¯=V∖XX¯=V∖X. Nếu X¯X¯ không phải là tập độc lập thì sẽ tồn tại một cạnh nối hai đỉnh của u,vu,v của X¯X¯. Theo định nghĩa của phủ đỉnh, ít nhất một trong hai đầu mút của cạnh này phải thuộc tập phủ đỉnh, ta thu được phản chứng. Bài toán CLIQUE được định nghĩa như sau: CLIQUE. Cho một đồ thị vô hướng G(V,E)G(V,E) và một số nguyên KK. Có tồn tại hay không một Clique có kích thước không quá KK trong đồ thị? Ta có: Lemma 3: CLIQUE ∈∈ Np-complete Chứng minh: Ta sẽ quy dẫn từ bài toán INDEPENDENTSET. Cũng như Lemma 2, mình chỉ nêu ý tưởng chính. Chi tiết chứng minh theo từng bước coi như bài tập của bạn đọc. Ta định nghĩa đồ thị bù, kí hiệu G¯(V¯,E¯)G¯(V¯,E¯), của đồ thị G(V,E)G(V,E) như sau. Tập đỉnh của đồ thị bù cũng là tập đỉnh của đồ thị gốc, i.e, V¯=VV¯=V. Tập cạnh của đồ thị bù là phần bù của tập cạnh của đồ thị gốc. Nói cách khác, nếu giữa hai đỉnh u,vu,v của đồ thị gốc không có cạnh nào nối chúng thì ta sẽ thêm cạnh uvuv vào đồ thị bù và ngược lại.
Quy dẫn từ INDEPENDENTSET dựa trên nhận xét: XX là một Clique của đồ thị G(V,E)G(V,E) khi và chỉ khi nó là một tập độc lập của đồ thị bù G¯(V¯,E¯)G¯(V¯,E¯). - Giải thuật tìm kiếm đồ thị Clique (Clique PercolationMethod - CPM): phƣơng pháp này đƣợc đƣa ra bởi Palla et al. vào năm 2005. Nhóm tác giả đã mở rộng các vấn đề của Girvan Newman là tìm các cộng đồng chồng chéo, trong đó một đỉnh có thể thuộc một hoặc nhiều cộng đồng. Ý tƣởng của giải thuật là mỗi cộng đồng đƣợc hình thành từ các đồ thị Clique và đồ thị ban đầu chứa một số lƣợng lớn đồ thị Clique. Khái niệm đồ thị k-clique đƣợc sử dụng để chỉ ra một đồ thị đầy đủ với k đỉnh. Hai đồ thị k- clique kề nhau có chung (k-1) đỉnh. Palla và các cộng sự đã thiết kế gói phần mềm Cfinder thực thi giải thuật này. Năm 2007, Palla et al. đã đƣa ra định nghĩa đồ thị k- clique có hƣớng và đề xuất giải pháp giải quyết những giới hạn của giải thuật CPM, gọi là CPMd (Clique Percolation Method with directed cliques). Cùng năm đó, Farkas et al. đã mở rộng giải thuật CPM đối với đồ thị có trọng số, giải thuật CPMw. Năm 2008, Kumpula et al. đã đƣa ra giải thuật phát hiện cộng đồng nhanh đƣợc gọi là SCP (Sequential Clique PercolationMethod) đối với các đồ thị có trọng số và không trọng số, trong đó kích thƣớc đồ thị clique đƣợc cho trƣớc. Thời gian chạy của giải thuật SCP nhanh hơn CPM. Giải thuật CPM: 29 Đầu vào: Đồ thị G gồm N đỉnh, đồ thị Clique có k đỉnh. Đầu ra: Cấu trúc cộng đồng. Bƣớc 1: Tìm tất cả các đồ thị k-clique trong đồ thị G. Bƣớc 2: Xây dựng đồ thị Gc là đồ thị mà mỗi đỉnh đại diện cho một kclique trong đồ thị ban đầu. Hai k-clique có cạnh kết nối với nhau nếu chúng có chung (k-1) đỉnh. Bƣớc 3: Mỗi đồ thị Clique đƣợc coi là một cộng đồng trong mạng.

More Related Content

Tai liệu thuyết trình môn khai phá dữ liệu

  • 1. http://doc.edu.vn/tai-lieu/luan-van-phuong-phap-phan-cum-va-ung-dung-42382/ Clique Cho một đồ thị G(V,E)G(V,E), một tập đỉnh X⊆VX⊆V được gọi là một tập phủ đỉnh (vertex cover) nếu như với mọi cạnh ee của đồ thị, ít nhất một trong hai đầu mút của nó thuộc XX. Tập XX được gọi là một Clique nếu như giữa mọi cặp đỉnh của XXđều tồn tại một cạnh của đồ thị nối hai đỉnh đó. Xem ví dụ trong hình minh họa trong Figure 4. Figure 4: (a) Các đỉnh được tô đậm màu đỏ thuộc Clique có kích thước 4 trong đồ thị và (b) các đỉnh được tô đậm màu xanh là một tập phủ đỉnh của đồ thị. Bài toán VERTEXCOVER được định nghĩa như sau: VERT EXCOVER. Cho một đồ thị vô hướng G(V,E)G(V,E) và một số nguyên KK. Có tồn tại hay không một tập phủ đỉnh có kích thước không quá KK trong đồ thị? Ta có: Lemma 2: VERT EXCOVER ∈∈ Np-complete Chứng minh: Ta sẽ quy dẫn từ bài toán INDEPENDENTSET. Ở đây mình chỉ lượt qua ý tưởng. Chi tiết chứng minh theo từng bước coi như bài tập của bạn đọc. Chứng minh dựa trên nhận xét: nếu XX là một tập phủ đỉnh của đồ thị thì V∖XV∖Xlà một tập độc lập của đồ thị. Nhận xét này có thể chứng minh bằng phản chứng như sau. Kí hiệu X¯=V∖XX¯=V∖X. Nếu X¯X¯ không phải là tập độc lập thì sẽ tồn tại một cạnh nối hai đỉnh của u,vu,v của X¯X¯. Theo định nghĩa của phủ đỉnh, ít nhất một trong hai đầu mút của cạnh này phải thuộc tập phủ đỉnh, ta thu được phản chứng. Bài toán CLIQUE được định nghĩa như sau: CLIQUE. Cho một đồ thị vô hướng G(V,E)G(V,E) và một số nguyên KK. Có tồn tại hay không một Clique có kích thước không quá KK trong đồ thị? Ta có: Lemma 3: CLIQUE ∈∈ Np-complete Chứng minh: Ta sẽ quy dẫn từ bài toán INDEPENDENTSET. Cũng như Lemma 2, mình chỉ nêu ý tưởng chính. Chi tiết chứng minh theo từng bước coi như bài tập của bạn đọc. Ta định nghĩa đồ thị bù, kí hiệu G¯(V¯,E¯)G¯(V¯,E¯), của đồ thị G(V,E)G(V,E) như sau. Tập đỉnh của đồ thị bù cũng là tập đỉnh của đồ thị gốc, i.e, V¯=VV¯=V. Tập cạnh của đồ thị bù là phần bù của tập cạnh của đồ thị gốc. Nói cách khác, nếu giữa hai đỉnh u,vu,v của đồ thị gốc không có cạnh nào nối chúng thì ta sẽ thêm cạnh uvuv vào đồ thị bù và ngược lại.
  • 2. Quy dẫn từ INDEPENDENTSET dựa trên nhận xét: XX là một Clique của đồ thị G(V,E)G(V,E) khi và chỉ khi nó là một tập độc lập của đồ thị bù G¯(V¯,E¯)G¯(V¯,E¯). - Giải thuật tìm kiếm đồ thị Clique (Clique PercolationMethod - CPM): phƣơng pháp này đƣợc đƣa ra bởi Palla et al. vào năm 2005. Nhóm tác giả đã mở rộng các vấn đề của Girvan Newman là tìm các cộng đồng chồng chéo, trong đó một đỉnh có thể thuộc một hoặc nhiều cộng đồng. Ý tƣởng của giải thuật là mỗi cộng đồng đƣợc hình thành từ các đồ thị Clique và đồ thị ban đầu chứa một số lƣợng lớn đồ thị Clique. Khái niệm đồ thị k-clique đƣợc sử dụng để chỉ ra một đồ thị đầy đủ với k đỉnh. Hai đồ thị k- clique kề nhau có chung (k-1) đỉnh. Palla và các cộng sự đã thiết kế gói phần mềm Cfinder thực thi giải thuật này. Năm 2007, Palla et al. đã đƣa ra định nghĩa đồ thị k- clique có hƣớng và đề xuất giải pháp giải quyết những giới hạn của giải thuật CPM, gọi là CPMd (Clique Percolation Method with directed cliques). Cùng năm đó, Farkas et al. đã mở rộng giải thuật CPM đối với đồ thị có trọng số, giải thuật CPMw. Năm 2008, Kumpula et al. đã đƣa ra giải thuật phát hiện cộng đồng nhanh đƣợc gọi là SCP (Sequential Clique PercolationMethod) đối với các đồ thị có trọng số và không trọng số, trong đó kích thƣớc đồ thị clique đƣợc cho trƣớc. Thời gian chạy của giải thuật SCP nhanh hơn CPM. Giải thuật CPM: 29 Đầu vào: Đồ thị G gồm N đỉnh, đồ thị Clique có k đỉnh. Đầu ra: Cấu trúc cộng đồng. Bƣớc 1: Tìm tất cả các đồ thị k-clique trong đồ thị G. Bƣớc 2: Xây dựng đồ thị Gc là đồ thị mà mỗi đỉnh đại diện cho một kclique trong đồ thị ban đầu. Hai k-clique có cạnh kết nối với nhau nếu chúng có chung (k-1) đỉnh. Bƣớc 3: Mỗi đồ thị Clique đƣợc coi là một cộng đồng trong mạng.