Download miễn phí Đồ án Tìm hiểu phương pháp phân cụm



MỤC LỤC
LỜI NÓI ĐẦU 4
CHƯƠNG 1 : TỔNG QUAN VỀ DATA MINING 6
 1.1. Data Mining là gì ? 6
1.2. Quá trình khám phá tri thức trong CSDL 7
1.3. Các kỹ thuật tiếp cận trong Data Mining 9
1.4. Các dạng dữ liệu có thể khai phá trong Data mining 11
1.4.1. Cơ sở dữ liệu quan hệ 11
1.4.2. Kho dữ liệu tích hợp 11
1.4.3. Cơ sở dữ liệu giao tác 12
1.4.4. Các hệ CSDL cao cấp 12
1.5. Các nhiệm vụ của khai phá dữ liệu. 13
1.5.1. Phát hiện các luật tối ưu truy vấn ngữ nghĩa . 13
1.5.2. Phát hiện sự phụ thuộc CSDL. 14
1.5.3. Phát hiện sự sai lệch. 14
1.5.4. Phát hiện luật kết hợp. 14
1.5.5. Mô hình hóa sự phụ thuộc. 15
1.5.7. Phân cụm. 16
1.5.8. Phân lớp. 16
1.5.9. Hồi quy. 16
1.5.10. Tổng hợp. 17
1.5.11. So sánh các nhiệm vụ phát hiện tri thức. 17
CHƯƠNG 2: PHƯƠNG PHÁP PHÂN CỤM VÀ CÁCH TIẾP CẬN 18
2.1. Vấn đề về phân cụm dữ liệu. 18
2.2. Các kiểu dữ liệu và độ đo tương tự 19
2.2.1. Phân loại các kiểu dữ liệu dựa trên kích thước miền. 20
2.2.2 Phân loại các kiểu dữ liệu dựa trên hệ đo 20
2.3. Khái niệm về tương tự và phi tương tự. 21
2.4. Các phương pháp tiếp cận trong phân cụm dữ liệu. 26
2.4.1. Phương pháp phân hoạch 26
2.4.2. Phương pháp phân cấp 27
2.4.3 Phương pháp phân cụm dữ liệu dựa trên mật độ 27
2.4.4. Phương pháp phân cụm dựa trên lưới. 28
2.4.5. Phương pháp phân cụm dựa trên mô hình 29
2.4.6. Phân cụm dữ liệu có ràng buộc 29
CHƯƠNG 3: TÌM HIỂU MỘT SỐ THUẬT TOÁN PHÂN CỤM 31
3.1. Thuật toán phân hoạch K-means. 31
3.2. Thuật toán DBSCAN 33
3.3. Thuật toán OPTICS 40
CHƯƠNG 4: KẾT QUẢ VÀ ĐÁNH GIÁ THỰC NGHIỆM. 45
4.1.Chương trình cài đặt thử nghiệm với thuật toán K-means. 45
4.2.Chương trình cài đặt thử nghiệm với thuật toán DBSCAN. 45
KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN
TÀI LIỆU THAM KHẢO 52
 
 


http://s1.liketly.com/flash/edoc/web-viewer.html?file=jh2i1fkjb33wa7b577g9lou48iyvfkz6-demo-2016-01-14-do_an_tim_hieu_phuong_phap_phan_cum_Nts11ezs50.png /tai-lieu/do-an-tim-hieu-phuong-phap-phan-cum-87385/


Để tải tài liệu này, vui lòng Trả lời bài viết, Mods sẽ gửi Link download cho bạn ngay qua hòm tin nhắn.

Ket-noi - Kho tài liệu miễn phí lớn nhất của bạn


Ai cần tài liệu gì mà không tìm thấy ở Ket-noi, đăng yêu cầu down tại đây nhé:
Nhận download tài liệu miễn phí

Tóm tắt nội dung tài liệu:

kiện của tiền đề, thì bộ dữ liệu đó có lớp chỉ ra trong kết luận”.
1.5.9. Hồi quy.
Về mặt khái niệm, nhiệm vụ hồi quy tương tự như phân lớp. Điểm khác nhau là ở chỗ thuộc tính dự báo là liên tục thay vì rời rạc.
Việc dự báo các giá trị số thường được thực hiện bởi công cụ thống kê cổ điển, chẳng hạn như hồi quy tuyến tính. Tuy nhiên, các phương pháp mô hình hóa cũng có thế sử dụng, chẳng hạn như cây quyết định, trong đó các nút lá là một mô hình tuyến tính phát sinh tập các lớp giả (pseudo-class) có giá trị thuộc tính đích tương tự nhau, sau đó sử dụng phương pháp quy nạp bằng tổ hợp các giá trị của thuộc tính lớp cho các bộ dữ liệu theo luật.
1.5.10. Tổng hợp.
Nhiệm vụ của tổng hợp chính là việc sản sinh ra các mô tả đặc trưng cho một lớp. Các mô tả này là một kiểu tổng hợp, tóm tắt mô tả các đặc tính chung của tất cả ( hay hấu hết ) các bộ dữ liệu dạng giỏ mua hàng thuộc một lớp.
Các mô tả đặc trưng thể hiện dưới dạng các luật thường có khuôn dạng :”nếu một bộ dữ liệu thuộc về một lớp đã chỉ ra trong tiền đề, thì bộ dữ liệu đó có tất cả cá thuộc tính đã nêu ra trong kết luận ”. Các luật này có những đặc trưng khác biệt so với các luật phân lớp. Luật phát hiện đặc trưng cho một lớp chỉ được sản sinh khi các bộ dữ liệu đã thuộc về lớp đó.
1.5.11. So sánh các nhiệm vụ phát hiện tri thức.
Phát hiện tri thức hướng CSDL có độ chính xác cao. Đây là điểm khác biệt quan trọng so với các đòi hỏi của các nhiệm vụ phát hiện tri thức khác. Nhiệm vụ phát hiện sự sai lệch liên quan đến phát hiện tri thức ở mức ý nghĩa do người dùng quy định. Nhiệm vụ xác định liên kết cũng tương tự với ngưỡng tin cậy và ngưỡng hỗ trợ (tần suất tương đối ). Nhiệm vụ tổng hợp liên quan đến phát hiện tri thức có tính phổ biến cao tức là luật được phát hiện phải bao hàm một số dữ liệu. Các nhiệm vụ như phát hiện sự phụ thuộc, nhân quả, phân lớp và hồi quy chủ yếu liên quan đến phát hiện tri thức có độ chính xác cao.
CHƯƠNG 2
PHƯƠNG PHÁP PHÂN CỤM VÀ CÁC CÁCH TIẾP CẬN
Trong chương này sẽ trình bày về một số phương pháp phân cụm và hướng tiếp cận.
Vấn đề về phân cụm dữ liệu
Các kiểu dữ liệu và độ đo tương tự
Khái niệm về tương tự và phi tương tự
Các phương pháp tiếp cận trong phân cụm dữ liệu.
2.1. Vấn đề về phân cụm dữ liệu.
Phân cụm dữ liệu là một lĩnh vực đang được phát triển mạnh mẽ như thống kê, học máy, nhận dạng, Data mining, Ở một mức cơ bản nhất, người ta đã đưa ra định nghĩa phân cụm dữ liệu như sau [1][7]:
" Phân cụm dữ liệu là một kỹ thuật trong DATA MINING, nhằm tìm kiếm, phát hiện các cụm, các mẫu dữ liệu tự nhiên tiềm ẩn, quan tâm trong tập dữ liệu lớn, từ đó cung cấp thông tin, tri thức hữu ích cho việc ra quyết định"
Như vậy , phân cụm dữ liệu là quá trình phân chia một tập dữ liệu ban đầu thành các cụm dữ liệu sao cho các phần tử trong một cụm "tương tự" (Similar) với nhau và các phần tử trong các cụm khác nhau sẽ "phi tương tự" (Dissimilar) với nhau. Số các cụm dữ liệu được phân ở đây có thể được xác định trước theo kinh nghiệm hay có thể được tự động xác định của phương pháp phân cụm.
Chúng ta có thể minh hoạ vấn đề phân cụm như hình 3 sau đây :
Hình 3 : Mô phỏng vấn đề phân cụm dữ liệu
Ở hình trên, sau khi phân cụm ta thu được bốn cụm trong đó các đối tượng "gần nhau" hay là "tương tự" thì được xếp vào một cụm, trong khi đó các đối tượng "xa nhau" hay là "phi tương tự" thuộc về các cụm khác nhau.
Trong phân cụm dữ liệu khái niệm (Concept Clustering) thì hai hay hay nhiều đối tượng cùng được xếp vào một cụm nếu chúng có chung một định nghĩa về khái niệm hay chúng xấp xỉ với các khái niệm mô tả cho trước. Ở đây phân cụm dữ liệu không sử dụng khái niệm “tương tự” như đã trình bày ở trên.
Vấn đề thường gặp trong phân cụm dữ liệu đó là hầu hết các dữ liệu cần cho phân cụm đều có chứa dữ liệu "nhiễu" (noise) do quá trình thu thập thiếu chính xác hay thiếu đầy đủ, vì vậy cần xây dựng chiến lược cho bước tiền xử lý dữ liệu nhằm khắc phục hay loại bỏ "nhiễu" trước khi bước vào giai đoạn phân tích phân cụm dữ liệu.
2.2. Các kiểu dữ liệu và độ đo tương tự
Trong phân cụm dữ liệu, các đối tượng dữ liệu cần phân tích có thể là con người, các thực thể phần mềm, Các đối tượng này thường được diễn tả dưới dạng các đặc tính hay còn gọi là thuộc tính của nó. Các thuộc tính này là các tham số cho giải quyết vấn đề phân cụm dữ liệu và sự lựa chọn chúng có tác động đáng kể đến các kết quả của phân cụm. Phân loại khái niệm các kiểu thuộc tính khác nhau là một vấn đề cần giải quyết đối với hầu hết các tập dữ liệu nhằm cung cấp các phương tiện thuận lợi để nhận dạng sự khác nhau của các phần tử dữ liệu. Dưới đây là cách phân lớp dựa trên hai đặc trưng là: kích thước miền (Domain Size) và hệ đo (Measurement Scale)
Cho một CSDL D chứa n đối tượng trong không gian k chiều trong đó x,y,z là các đối tượng thuộc D : x=(x1,x2,..,xk);y=(y1,y2,..,yk);z=(z1,z2,..,zk), trong đó xi, yi, zi với là các đặc trưng hay thuộc tính tương ứng của các đối tượng x,y,z. Vì vậy, hai khái niệm “các kiểu dữ liệu” và “các kiểu thuộc tính dữ liệu” được xem là tương đương với nhau, như vậy, chúng ta sẽ có các kiểu dữ liệu sau :
2.2.1. Phân loại các kiểu dữ liệu dựa trên kích thước miền.
Thuộc tính liên tục (Continuous Attribute) : nếu miền giá trị của nó là vô hạn không đếm được, nghĩa là giữa hai giá trị tồn tại vô số giá trị khác.
Thuộc tính rời rạc (DiscretteAttribute) : Nếu miền giá trị của nó là tập hữu hạn, đếm được.
Lớp các thuộc tính nhị phân là trường hợp đặc biệt của thuộc tính rời rạc mà miền giá trị của nó chỉ có 2 phần tử được diễn tả như : Yes / No hay False/true,
2.2.2 Phân loại các kiểu dữ liệu dựa trên hệ đo
Giả sử rằng chúng ta có hai đối tượng x, y và các thuộc tính xi, yi tương ứng với thuộc tính thứ i của chúng. Chúng ta có các lớp kiểu dữ liệu như sau :
Thuộc tính định danh (nominal Scale): đây là dạng thuộc tính khái quát hoá của thuộc tính nhị phân, trong đó miền giá trị là rời rạc không phân biệt thứ tự và có nhiều hơn hai phần tử - nghĩa là nếu x và y là hai đối tượng thuộc tính thì chỉ có thể xác định là x y hay x=y.
Thuộc tính có thứ tự (Ordinal Scale): là thuộc tính định danh có thêm tính thứ tự, nhưng chúng không được định lượng. Nếu x và y là hai thuộc tính thứ tự thì ta có thể xác định là x y hay x=y hay x>y hay x<y.
Thuộc tính khoảng (Interval Scale) : Nhằm để đo các giá trị theo xấp xỉ tuyến tính. Với thuộc tính khoảng, chúng ta có thể xác định một thuộc tính là đứng trước hay đứng sau thuộc tính khác với một khoảng là bao nhiêu. Nếu xi>yi thì ta nói x cách y một khoảng xi – yi tương ứng với thuộc tính thứ i.
Thuộc tính tỉ lệ (Ratio Scale) : là thuộc tính khoảng nhưng được xác định một cách tương đối so với điểm mốc đầy ý nghĩa.
Trong các thuộc tính dữ liệu trình bày ở trên, thuộc tính định danh và thuộc tính có thứ tự gọi chung là thuộc tính hạng mục (Categorical), trong khi đó thì thuộc tính khoảng và thuộc tính tỉ lệ được gọi là thuộc tính số (Numeric).
Người ta còn đặc biệt quan tâm đến dữ liệu không gian (Spatial Data). Đây là loại dữ liệu có các thuộc tính số khái quát trong không gian nhiều chiều, dữ liệu không gian mô tả các thông tin liên quan đến không gian chứa đựng các đối tượng, thí dụ như thông tin về hình học, Dữ liệu không gian có thể là dữ liệu liên tục hay rời rạc :
Dữ liệu không gian rời rạc : có thể là một điểm trong không gian nhiều chiều và cho phép ta xác định được khoảng cách giữa các đối tượng dữ liệu trong không gian.
Dữ liệu không gian liên tục : bao chứa một vùng trong không gian.
2.3. Khái niệm về tương tự và phi tương tự.
Khi các đặc tính của dữ liệu được xác định, người ta đi tìm cách thích hợp để xác định "khoảng cách" giữa các đối tượng, hay là phép đo tương tự dữ liệu. Đây là các hàm để đo sự giống nhau giữa các cặp đối tượng dữ liệu, thông thường các hàm này hay là để tính độ tương tự (Similar) hay là tính độ phi tương tự (Dissimilar) giữa các đối tượng dữ liệu. Giá trị của hàm tính độ đo tương tự càng lớn thì sự giống nhau giữa đối tượng càng lớn và ngược lại, còn hàm tính độ phi tương tự tỉ lệ nghịch với hàm tính độ tương tự. Độ tương tự hay độ phi tương tự có nhiều cách để xác định, chúng thường được đo bằng khoảng cách giữa các đối tượng. Tất cả các cách đo độ tương tự đều phụ thuộc vào kiểu thuộc tính mà chúng ta phân tích. Thí dụ, đối với thuộc tính hạng mục (Categorical) người ta không sử dụng độ đo khoảng cách mà sử dụng một hướng hình học của dữ liệu.
Tất cả các độ đo dưới đây được xác định trong không đo gian metric. Bất kỳ một metric nào cũng là một độ đo, nhưng điều ngược lại không đúng. Để tránh sự nhầm lẫn, thuật ngữ độ đo ở đây đề cập đến hàm tính độ tương tự hay hàm tính độ phi tương tự.
Một không gian metric là một tập trong đó có xác định các "khoảng cách" giữa từng cặp phần tử, với những tính chất thông thường của khoảng cách hình học. Nghĩa là, một tập X (các phần tử của nó có thể là những đối tượng bất kỳ ) các đối tượng dữ liệu trong CSDL D như đã đề cập ở trên được gọi là một không gian metric nếu:
Với mỗi cặp phần...

---