Đề tài: Phân tích chùm mờ và không mờ các phần tử rời rạc

Chia sẻ: Thai Van Thanh | Ngày: | Loại File: DOCX | Số trang:57

Thêm vào BST

Báo xấu

103
lượt xem 13
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Đề tài "Phân tích chùm mờ và không mờ các phần tử rời rạc" được thực hiện nhằm mục đích tổng hợp các phương pháp xây dựng chùm mờ và không mờ cho các phần tử rời rạc làm cơ sở để nghiên cứu lý thuyết vấn đề này, đặc biệt vấn đề tính toán cho số liệu thực tế lớn để áp dụng cho nhiều lĩnh vực khác nhau. Hy vọng nội dung đề tài phục vụ hữu ích nhu cầu học tập, làm việc hiệu quả.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Đề tài: Phân tích chùm mờ và không mờ các phần tử rời rạc

PHẦN MỞ ĐẦU LÝ DO CHỌN ĐỀ TÀI Phân tích chùm là việc nhóm các phần tử trong tập hợp đã cho thành các chùm sao cho các phần tử trong cùng chùm tương tự nhau theo những dấu hiệu nào đó. Khi chùm được xây dựng, những phần tử trong cùng một chùm sẽ có sự tương tự nhiều hơn so với những phần tử của chùm khác. Có rất nhiều ứng dụng trong y học, kinh tế, kỹ thuật, xã hội,… Trong phân tích chùm truyền thống (không mờ), các nhà khoa học đã nghiên cứu các phương pháp phân tích chùm thứ bậc và không thứ bậc với các tiêu chuẩn đánh giá khác nhau như khoảng cách hay độ rộng chùm. Tuy nhiên các phương pháp phân tích chùm không mờ đòi một phần tử phải thuộc hoặc không thuộc một chùm một cách rõ ràng, điều này không thực sự hợp lý khi trong thực tế có nhiều phần tử nằm ở những vị trí “nhạy cảm” đan xen giữa các chùm. Nghiên cứu chùm có kèm theo xác suất gọi là phân tích chùm mờ. Phương pháp này khắc phục nhược điểm của phương pháp phân tích chùm không mờ khi tập dữ liệu có các phần tử nằm gần biên giới giữa các chùm. Mặc dù đã được quan tâm nhiều, nhưng các tài liệu về phân tích chùm cũng được trình bày khá rời rạc, do đó các ứng dụng thực tế cũng chỉ xét cho từng trường hợp riêng biệt không có sự so sánh đối chiếu. Với mong muốn tổng hợp các phương pháp xây dựng chùm mờ và không mờ cho các phần tử rời rạc làm cơ sở để nghiên cứu lý thuyết vấn đề này, đặc biệt vấn đề tính toán cho số liệu thực tế lớn để áp dụng cho nhiều lĩnh vực khác nhau em chọn đề tài Phân tích chùm mờ và không mờ các phần tử rời rạc. TỔNG QUAN VỀ PHÂN TÍCH CHÙM Khái niệm phân tích chùm. Chùm coi như là một đối tượng (phần tử, điểm). trong đó mỗi đối tượng dần tới đối tượng trung tâm của một chum và những thánh viên của những chùm khác nhau thì không tương tự nhau. Hay nói ngắn ngọn là ta sẽ thực hiện cực đại hóa sự tương tự giữa các đối tượng cùng một chum, nhưng cực tiểu hóa các đối tượng khác chum. Trong ý nghĩa, chum có thể xem như là “mật độ cao khu vực” của một không gian đa chiều. 1
Quá trình nhốm các đối tượng vào cùng một chùm được gọi là việc xếp nhóm (clastering). Clastering đề cập tới vấn đề quang trọng nhất là nghiêm cứu không giám sát ( unsperviced learning) – không có thông tin về nhãn lớp của đối tượng. Hay nói cách khác, đây là công việc “ xử lí để tổ chức các đối tượng vào các nhóm mà trong đó, các phần tử của mỗi nhóm giống nhau theo một nghĩa nào đó”. Phân tích chùm là một lớp các kĩ thuật được sử dụng để phân loại các đối tượng hoặc các trường hợp thành các nhóm đối tượng gọi là chùm. Phân tích chùm còn được gọi là phân tích phân loại hoặc phân loại số. Phân tích chùm dữ liệu là một lĩnh vực nghiên cứu đầy thách thức và công việc này luôn đặc ra những yêu cầu đặc thù sau đây: Tính khả mở: Nhiều thuật toán phân tích chùm hoạt động tốt trên nhựng tập dữ liệu nhỏbao gồm vài tram đối tượng dữ liệu. Tuy nhiên, một cơ sở dữ liệu lớn bao gồm hàng triệu, hàng tỉ đối tượng. xếp nhóm trên tập dữ liệu lớn có thể dẫn tới kết quả kém. Các thuật toán này có tính khả mở cao là rất cần thiết. Khả năng phát hiện được các nhóm có hình dạng bất kì: các thuật toán phải tìm ra được các nhóm có hình dạng bất kì, bao gồm những hình có kẻ hở, lõm hoặc lồng nhau. Thích nghi với các kiểu dữ liệu khác nhau: thuật toán có thể áp dụng hiệu quả cho việc phân chùm với điều kiện dữ liệu khác nhau như: dữ liệu số, nhị phân,…và thích nghi với các kiểu dữ liệu hỗn hợp của các dữ liệu đơn trên. Khả năng làm việc được với các dữ liệu chứa nhiễu: cơ chế phân chum thích ứng được với nhiều điểm nhiễu. Không nhạy cảm với thứ tự dữ liệu đầu vào: tức là kết quả phân chum độc lập với dữ liệu input Giảm thiểu yêu cầu với tham số đầu vào: dữ liệu không cần phải có kiến thức tiên nhiệm nào Xử lí được dữ liệu đa chiều: tức là thuộc tính dữ liệu lớn. Có thể phân chum trên cơ sở ràng buộc: các ứng dụng thực tế có thể cần phân chum dưới điều kiện rang buộc, Chẳng hạn công việc của bạn là chọn một vị trí dể đặt máy ATM trong thành phố,… Đây có thể là cả một thử thách của phân tích chum khi dựa vào bài toán thực tế các lĩnh vực đời sống, tìm ra cách phân tích chum tốt đối với dữ liệu đầu vào mà vẫn tôn trọng các rang buộc ban đầu. 2
Tính có thể hiểu được, tiện lợi và khả dụng: Người dùng luôn mong nhận được một bộ phân chùm có thể hiểu được và tiện lợi. Có một số thuật toán khi thực hiện và so sánh với các kết quả thực tế không khớp, không hợp lí. Vậy kết quả thực tế là vấn đề quan trọng của thuật toán, Điều quang trọng là nghiên cứu thực tế có thể chi phối các đặc trưng và các Phương pháp phân nhóm. Một số ứng dụng của phân tích chùm Phân tích chùm có nhiều tên gọi khac nhau như: phân tích Q, phân tích phân loại, phân tích bằng kĩ thuật định lượng,… Có nhiều tên gọi khác nhau như vậy là vì phương pháp phân tích chùm được ứng dụng trong nhiều lĩnh vực khác nhau. Phân tích chùm đã và đang được sử dụng rộng rãi và có đóng góp quan trọng trong mọi mặt đời song xã hội. Các ứng dụng chính bao gồm: Trong thương mại: Phân tích chùm có thể giúp khám phá ra các khách hang quang trọng có các đặc trưng tương đồng nhau và đặc tả trong cơ sở mua bán từ dữ liệu khách hàng. Từ đó nâng cao lợi nhuận, cải thiện thu nhập. Trong sinh học: phương pháp này hữu dụng để phát hiện các loài sinh vật , phân loại các gen với các chức năng tương đồng và thu thập được các cấu trúc trong các mẫu. Trong phân tích dữ liệu không gian: Do sự đồ sộ của các dữ liệu không gian như các hình ảnh thủ được từ các hình ảnh chụp dduocj từ các vệ tinh, các thiết bị khoa học hay các hệ thống thông tin địa lí(GÍ),… làm cho người dùng rất khó kiểm tra các dữ liệu không gian một cách chi tiết rõ ràng. Phương pháp phân tích chùm có thể trợ giúp nguoief dùng tự động phân tích và xử lí các dự liệu không gian như nhận dạng chiết xuất các đặc tính hoặc các dữ liệu quan tâm có thể tồn tại trông cơ sở dữ liệu không gian. Trong web mining: Phân tích chùm có thể khám phá ra các nhóm tài liệu quan trọng. có ý nghĩa theo tiêu chí đặc ra. Tương lai của web mining sẽ ngày càng phát triển cùng với sụ phát triển của internet. Trong địa lí: Phân lớp động vật và thực vật và đưa ra đặc trung của chúng. Trong qui hoạch đô thị: Nhận dạng các nhóm nhà theo kiểu và vị trí địa lí,… Nhằm cung cấp thông tin cho qui hoạch đô thị. 3
Trong nghiên cứu trái đất: Phân tích chùm để theo dõi các trận động đất nhằm cung cấp thông tin cho nhận dạng các vùng nguy hiểm. Trong nén dữ liệu: Tìm ra các nhóm thể hiện đồng nhất từ đó có thể hổ trợ nén dữ liệu. Chương I: PHÂN TÍCH CHÙM KHÔNG MỜ 1.1 GIỚI THIỆU Theo Jain và Dubes (1988), Kaufman và Rousseeuw (1990), Sharma (1996) và Everitt et al (2001), phân tích chùm là một phương pháp thống kê đa biến nhằm nhóm một tập các đối tượng lại thành các chùm theo những đặc điểm định trước. Chùm được coi như là một nhóm dữ liệu, trong đó những phần tử trong cùng một chùm thì có sự tương tự nhau theo một nghĩa nào đó. Khi có nhiều dữ liệu, người ta muốn chia các dữ liệu này thành nhiều nhóm sao cho những đối tượng trong cùng nhóm thì gần nhau hơn so với những đối tượng của nhóm khác. Từ yêu cầu đó bài toán phân tích chùm ra đời. Chúng ta có thể hiểu phân tích chùm là việc nhóm các phần tử trong dữ liệu ban đầu thành các chùm sao cho các phần tử trong cùng một chùm thì tương tự nhau theo một dấu hiệu nào đó. Khi chùm được xây dựng, những phần tử trong cùng một chùm sẽ có sự tương tự nhiều hơn so với những phần tử của chùm khác. Bài toán phân tích chùm là một hướng phát triển quan trọng của nhận dạng thống kê, thường được gọi là nhận dạng không được giám sát. Phần tử trong phân tích chùm là những phần tử rời rạc hoặc các hàm mật độ xác suất. Đối với phần tử rời rạc, việc xác định sự tương tự của các phần tử chủ yếu dựa vào khoảng cách giữa các phần tử đó, những phần tử có khoảng cách nhỏ nhất so với những phần tử khác thì gần nhau hơn và được xếp cùng một chùm. Hiện tại có hai phương pháp chủ yếu để xây dựng chùm cho các phần tử rời rạc: phương pháp thứ bậc và phương pháp không thứ bậc. Trong đó khoảng cách của hai phần tử được sử dụng chủ yếu là khoảng cách Euclide và khoảng cách . Trong khi khoảng cách giữa hai tập hợp được sử dụng là khoảng cách min, khoảng cách max, khoảng cách trung bình và khoảng cách Ward. Các phần mềm thống kê như Matlab, Maple, … đều có những gói sử dụng cho bài toán phân tích chùm các phần tử rời rạc với các tiêu chuẩn đánh giá là các khoảng cách vừa nêu. Phân tích chùm được sử dụng đầu tiên bởi Tryon (1939) với một số ý tưởng đơn giản ban đầu. Các ý tưởng này được phát triển thành các thuật toán phân tích chùm cụ thể bởi Sibson (1973), Defays (1977) và Rohlf (1982). Các thuật toán này dựa trên tiêu chuẩn khoảng cách giữa các phần tử rời rạc. Nhiều tác giả đã phát triển thuật toán 4
này bằng cách thay đổi những khoảng cách khác nhau. Webb (2002) đã tổng kết khá đầy đủ bài toán phân tích chùm của các dữ liệu rời rạc. Phân tích chùm được ứng dụng khá phổ biến trong nhiều lĩnh vực: sinh học, y học, kinh tế, xã hội…. Hartigan (1975) đã cung cấp một bảng tóm tắt tương đối đa dạng và đầy đủ những nghiên cứu thực tế của bài toán phân tích chùm. Chẳng hạn như, trong y học phân tích chùm giúp phân loại bệnh có những dấu hiệu gần nhau. Trong khoa học khí tượng, phân tích chùm đã phát triển rộng rãi từ năm 1990 cho đến nay. Trong khảo cổ học, phân tích chùm dùng để phân loại công cụ bằng đá. Eshref Shevki và Wendell Bell (1955) sử dụng phân tích chùm trong điều tra dữ liệu dân số. Nhóm tác giả Piotr Kulczycki, Malgorzata Charytanowicz, Piotr A. Kowalski, Szymon Lukasik (2011) dùng phân tích chùm để phân loại hạt giống ngũ cốc phục vụ cho sản xuất và hỗ trợ chiến lược tiếp thị điều hành điện thoại di động cho các nhà cung cấp mạng điện thoại di động. Ở Việt Nam, chúng tôi chưa tìm thấy những đóng góp đáng kể về mặt lý thuyết cho bài toán phân tích chùm, tuy việc áp dụng đã được một số nhà toán học, tin học quan tâm trong lĩnh vực khai phá dữ liệu. 1.2 TIÊU CHUẨN XÂY DỰNG CHÙM CÁC PHẦN TỬ RỜI RẠC 1.2.1 Khoảng cách giữa hai phần tử rời rạc Khoảng cách là đại lượng dùng để đánh giá sự tương tự của các chùm khi dữ liệu phân tích là các phần tử rời rạc. Khoảng cách giữa hai phần tử là một metric, nghĩa là nếu là khoảng cách của hai phần tử x và y thì phải thỏa các điều kiện sau đây: i) d(x,y) 0 . Dấu bằng xảy ra khi , ii) d(x,y) = d(y,x), iii) d(x,y) + d(y,z) d(x,z). Theo 3 điều kiện trên, ta có thể định nghĩa khoảng cách giữa 2 phần tử x và y (x, y) theo nhiều cách khác nhau. Thông thường các loại khoảng cách sau được sử dụng phổ biến: Khoảng cách Euclide: (1.1) Khoảng cách city block: (1.2) Khoảng cách Chebyshev: (1.3) Khoảng cách Minkowski với bậc m: (1.4) Nhận xét: i) Khoảng cách Euclide là khoảng cách thường được sử dụng nhất trong trong toán học, nó mô tả độ dài của đoạn thẳng nối hai điểm x và y. 5
ii) Khoảng cách cityblock mô tả tổng độ dài (tổng các khoảng cách Euclide) của n đoạn gấp khúc nối hai điểm x, y thuộc không gian n chiều. Mỗi đoạn trong n đoạn này sẽ song song với 1 trục tương ứng trong n trục chúng ta chọn làm hệ quy chiếu. iii) Khoảng cách Chebyshev mô tả đoạn thẳng có độ dài lớn nhất trong n đoạn gấp khúc đã được đề cập trong khoảng cách city block. Đây là khoảng cách tổng quát nhất, với những m khác nhau, khoảng cách Minkowski bậc m sẽ tương ứng với một loại khoảng cách khác nhau. Với m =1, , với m = 2, , độ lớn của khoảng cách càng giảm khi m càng tăng, khi m, . Hình vẽ sau minh họa 3 khoảng cách phổ biến của hai điểm x(1;2) và y(2;4). 6 Khoang cach Euclide 5 mo ta do dai doan thang nay y(2;4) 4 Khoang cach Chebyshev mo 3 ta do dai duongt gap khuc lon nha 2 x(1;2) 1 0 -1 Khoang cach city-block mo ta do dai 2 doan gap khuc -2 -2 -1 0 1 2 3 4 5 6 Hình 1.1: Các loại khoảng cách giữa hai phần tử x và y Như đã thấy, khoảng cách Euclide mô tả đoạn thẳng nối 2 điểm x và y trong khi khoảng cách cityblock mô tả 2 đoạn gấp khúc nối x và y, chúng lần lượt song song với trục hoành và trục tung của hệ tọa độ. Tương tự như vậy, nếu x, y thuộc không gian thì khoảng cách cityblock sẽ mô tả 3 đoạn thẳng lần lượt song song với Ox, Oy, Oz. Hình trên cũng chỉ ra khoảng cách Chebyshev mô tả đoạn thẳng dài nhất trong hai đường gấp khúc. 1.2.2 Khoảng cách giữa hai tập các phần tử rời rạc Cho A, B là hai nhóm, mỗi nhóm gồm nhiều phần tử rời rạc khác nhau. Gọi D(A;B) là khoảng cách giữa hai nhóm A và B, d(x,y) là khoảng cách giữa phần tử x và phần tử y (). Thông thường ta sử dụng các định nghĩa sau cho D(A;B): Khoảng cách min: (1.5) Khoảng cách max: (1.6) Khoảng cách trung bình: (1.7) Với lần lượt là số phần tử của nhóm A và nhóm B. 6
Nhận xét: i) Việc tính khoảng cách giữa hai nhóm dữ liệu không chỉ phụ thuộc vào việc chọn loại khoảng cách giũa hai nhóm mà còn phụ thuộc vào loại khoảng cách giữa hai phần tử, do đó sẽ có nhiều kết quả khác nhau tùy vào loại khoảng cách được chọn. Cho đến nay, người ta chưa chứng minh được sử dụng khoảng cách nào là tối ưu. Trong thực tế các loại khoảng cách phổ biến đã được nêu ở trên thường được sử dụng nhiều nhất. ii) Khi hai nhóm A và B được nhập lại thành một nhóm (A+B) thì việc tính khoảng cách từ nhóm (A+B) đến một nhóm C bất kỳ cũng có thể thực hiện theo những công thức trên. Tuy nhiên, ta có thể áp dụng những công thức sau đây để cho việc tính toán được thuận tiện hơn. (1.8) (1.9) (1.10) Ngoài các khoảng cách thông dụng trên, Ward (1963) đã đưa ra công thức tính khoảng cách trường hợp này bằng biểu thức: (1.11) Trong đó,, và lần lượt là số phần tử của nhóm A, B và C. Ví dụ 1.1. Cho Tính: a) giữa A và B. b) giữa A+C và B. Giải Trước tiên ta chọn khoảng cách Euclide làm khoảng cách giữa hai phần tử. Khoảng cách giữa các nhóm được tính như sau: a) = = 2.5 7
Tương tự = b) = = = Ta có thể mô tả hình học ví dụ trên như sau: 5 Y Dmax(A,B) 4 Nhom A Nhom A+C 3 2 Nhom 1 C Dmin(A,B) Dmin(A+C,B) 0 O X -1 Dmax(A+C,B) Nhom B -2 -3 -6 -5 -4 -3 -2 -1 0 1 2 3 5 Y 4 Nhom A 3 2 Nhom C 1 X 0 O -1 -2 Nhom B 8 -3 -6 -5 -4 -3 -2 -1 0 1 2 3
Hình 1.2: Khoảng cách giữa các nhóm bằng trung bình các khoảng cách được thể hiện bởi các đoạn thẳng liền nét. bằng trung bình các khoảng cách được thể hiện bởi các đoạn thẳng liền nét và không liền nét. Chú ý: i) Trước khi tính khoảng cách đối với các biến dữ liệu kiểu số thì cần chú ý về vấn đề chuẩn hóa dữ liệu sao cho chúng cùng một thang đo dữ liệu. Tình huống thực tế nảy sinh là có nhiều dữ liệu nhưng thang đo khác nhau. Ví dụ trong bộ dữ liệu có các thuộc tính như: cân nặng, chiều cao, lương,… đều là dữ liệu kiểu số nhưng rõ ràng thang đo của chúng là khác nhau (cân tính theo kg, chiều cao tính theo cm hay m, lương tính theo đơn vị đồng,....). Nếu sử dụng trực tiếp ngay khoảng cách trên tập dữ liệu số chưa được chuẩn hoá dễ gây sai lệch về độ đo. Ví dụ khoảng cách trọng lượng giữa hai người là 10 kg được coi là lớn (cách xa nhau), nhưng khoảng cách lương 100 000 có thể coi là nhỏ (đối với vật giá hiện tại). Nhưng số 100 000 lại là quá lớn so với 10. Do đó các dữ liệu cần được chuẩn hoá về cùng một “thang bậc” để không ảnh hưởng đến phân tích chùm. ii) Có nhiều loại dữ liệu khác nhau có thể thực hiện bài toán phân tích chùm. Thông thường ta có các loại dữ liệu phổ biến là dữ liệu kiểu số, nhị phân, định giá, thứ tự,… 1.3 XÂY DỰNG CHÙM CÁC PHẦN TỬ RỜI RẠC 1.3.1 Phương pháp thứ bậc Một trong những phương pháp phổ biến trong cả phân tích chùm là phương pháp thứ bậc. Kết quả của phương pháp này là tạo ra một dãy các chùm, trong đó một số chùm có thể chứa các lớp con bên trong nó, và đến lượt các lớp con này lại chứa bên trong nó các lớp con nhỏ hơn. Cấu trúc chùm được minh họa bởi một đồ thị hai chiều được gọi là sơ đồ (sơ đồ nhánh hoặc cây phân tích chùm). Cây phân tích chùm minh họa cho việc hợp nhất hoặc chia nhỏ các chùm đã được thực hiện bằng cách phân nhóm, và có thể hiển thị theo chiều dọc hoặc chiều ngang. 9
Hình 1.3: Cây phân tích chùm 3 phần tử A, B, C Thuật toán phân tích chùm theo phương pháp thứ bậc cụ thể như sau: Bước 1: Bắt đầu với n chùm, mỗi chùm chứa một phần tử. Tính từng đôi khoảng cách của hai phần tử. Thành lập ma trận đối xứng của các khoảng cách với là khoảng cách giữa hai phần tử i và j, . Bước 2: Trong ma trận khoảng cách E, tìm khoảng cách nhỏ nhất của hai chùm khác nhau, tức là hai chùm có sự tương tự nhiều nhất. Bước 3: Gọi là khoảng cách giữa hai chùm U và V có sự tương tự nhau nhất. Hợp nhất hai chùm U và V thành chùm mới. Tính toán lại ma trận khoảng cách giữa các chùm mới. Bước 4: Lặp lại bước 2 và bước 3 cho đến khi các phần tử được nhóm lại thành một chùm duy nhất. Ví dụ 1.2. Gọi là số lần bắn trúng trọng tâm của 4 xạ thủ . Sử dụng khoảng cách giữa các phần tử là khoảng cách Euclide, khoảng cách giữa các tập hợp là khoảng cách trung bình, ta tiến hành phân tích chùm bằng phương pháp thứ bậc như sau: Ban đầu, xem mỗi phần tử là một chùm, ta có ma trận khoảng cách ban đầu của các chùm: Hợp nhất hai chùm A và B lại thành chùm (AB) tính toán lại ma trận khoảng cách: Hợp nhất hai chùm C và D lại thành chùm (CD), tính toán lại ma trận khoảng cách: 10
Cuối cùng, hợp nhất hai chùm (AB) và (CD) lại thành một chùm duy nhất. Ta có cây phân tích chùm như sau: Hình 1.4: Cây phân tích chùm 4 phần tử A, B, C, D Ví dụ 1.3. Cho bảng sau: Bảng 1.1: Số lần bắn trúng mục tiêu của các vận động viên Vận động Số lần bắn trúng Số lần bắn trúng mục tiêu viên mục tiêu cố định di động A 1 0 B 2 0 C 7 4 D 9 10 Sử dụng khoảng cách giữa các phần tử là khoảng cách Euclide, khoảng cách giữa các tập hợp là khoảng cách trung bình, ta tiến hành phân tích chùm bằng phương pháp thứ bậc như sau: Ban đầu, xem mỗi phần tử là một chùm, ta có ma trận khoảng cách ban đầu của các chùm: 11
Hợp nhất hai chùm A và B lại thành chùm (AB) tính toán lại ma trận khoảng cách: Hợp nhất hai chùm C và D lại thành chùm (CD), tính toán lại ma trận khoảng cách: Cuối cùng, hợp nhất hai chùm (AB) và (CD) lại thành một chùm duy nhất. Ta có cây phân tích chùm như sau: Hình 1.5: Cây phân tích chùm của 4 vận động viên 1.3.2 Phương pháp không thứ bậc a) Phương pháp Trong phương pháp thứ bậc, các chùm được thành lập theo cấp độ của sự tương tự từ nhiều đến ít. Tập các phần tử được xem là một chùm lớn, chùm lớn này chứa các chùm nhỏ hơn và cứ vậy cho đến chùm cuối cùng chỉ gồm 1 phần tử. Trong thực tế người ta có nhu cầu phân chia dữ liệu ban đầu thành k chùm một cách riêng biệt, do đó bên cạnh phương pháp thứ bậc, người ta còn phân tích chùm theo phương pháp không thứ bậc. Kết quả của phương pháp không thứ bậc là quá trình phân nhóm một tập dữ liệu thành k chùm riêng biệt và các chùm này không chứa các chùm con khác bên trong nó. Thuật toán phân tích chùm theo phương pháp không thứ bậc được trình bày cụ thể như sau: Bước 1: Chia n phần tử thành k chùm một cách ngẫu nhiên (số lượng phần tử trong mỗi chùm là tùy ý). Tính trọng tâm của mỗi chùm. Bước 2: Tính khoảng cách từ mỗi phần tử đến trọng tâm của các chùm. Nếu khoảng cách từ một phần tử đến trọng tâm của chùm nó đang thuộc là nhỏ nhất thì ta giữ phần tử đó trong chùm ban đầu. Nếu tồn tại một chùm khác mà khoảng cách từ 12
phần tử đang xét đến trọng tâm của chùm là nhỏ nhất thì ta gán phần tử đang xét vào chùm này, bỏ phần tử trong chùm nó đang thuộc. Nếu phần tử được di chuyển đến chùm khác thì cần phải tính lại giá trị trọng tâm của hai chùm mới có sự thay đổi. Bước 3: Quay lại bước 2 và dừng lại khi ta có k chùm, sao cho một phần tử bất kỳ trong chùm có khoảng cách đến chùm nó đang thuộc nhỏ hơn khoảng cách đến các chùm khác Ví dụ 1.4 Với dữ liệu ở ví dụ 1.2 phân tích chùm bằng phương pháp không thứ bậc với k = 2. Sử dụng khoảng cách giữa các phần tử là khoảng cách Euclide, ta tiến hành phân tích chùm bằng phương pháp thứ bậc như sau: Chia các phần tử thành 2 chùm một cách ngẫu nhiên: và . Tính tọa độ trọng tâm của mỗi chùm, ta có kết quả Khoảng cách từ các phần tử đến trọng tâm các chùm lần lượt là , , , , Ta thấy khoảng cách từ B đến trọng tâm chùm thứ nhất nhỏ hơn khoảng cách từ B đến chùm chứa nó nên ta chuyển B từ chùm 2 sang chùm 1. Lặp lại các bước tính trên, ta lần lượt có kết quả sau: Bảng 1.2: Vòng lặp 1 Chùm Chùm Trọng tâm 3.33 9 Khoảng cách từ phần tử đến trọng Chùm Chùm tâm chùm A 2.33 8 B 1.33 7 C 3.67 2 D 5.67 0 Bảng 1.3: Vòng lặp 2 13
Chùm Chùm Trọng tâm 1.5 8 Khoảng cách từ phần tử đến trọng tâm Chùm Chùm chùm A 0.5 7 B 0.5 6 C 5.5 1 D 7.5 1 Sau hai vòng lặp thì điều kiện khoảng cách từ các phần tử đến trọng tâm chùm chứa nó là nhỏ nhất đã thỏa mãn. Do đó thuật toán kết thúc và ta có kết quả hai chùm riêng biệt là chùm và . Kết quả này cũng phù hợp với kết quả của cây phân tích chùm ở phương pháp thứ bậc. b) Vấn đề xác định số chùm ban đầu Trong phân tích chùm theo phương pháp không thứ bậc, chúng ta cần phần tích bộ số liệu thành k chùm riêng biệt. Tuy nhiên, đối với những bộ số liệu lớn, việc xác định chính xác số k và chọn chùm khởi tạo như thế nào là một vấn đề khó khăn. Vì kết quả của thuật toán không thứ bậc đặc biệt đối với những bộ số liệu lớn phụ thuộc nhiều vào việc chọn số chùm k và cách chọn các phần tử vào chùm khởi tạo nên vấn đề này được quan tâm rất nhiều. Có nhiều phương pháp được áp dụng để tìm số chùm được đưa ra như dựa vào kiến thức tiên nghiệm về tập dữ liệu hay so sánh các hệ số tương quan phân vùng, chỉ số phân vùng, chỉ số XieBeni của các trường hợp với các số k khác nhau. Tuy nhiên, việc tính các chỉ số này được thực hiện sau khi đã phân tích bộ số liệu thành các trường hợp k chùm khác nhau, điều này làm cho việc tính toán trở nên cồng kềnh, kém hiệu quả. Mặt khác, việc áp dụng các phương pháp này chỉ có thể xác định gần đúng k mà lại không xác định được nên chọn chùm khởi tạo như thế nào để việc tính toán là tối ưu, không trải qua nhiều vòng lặp. Phần này của luận văn sẽ trình bày một phương pháp mới được Hung và Wen Liang đưa ra gọi là phương pháp “tự động cập nhật” SU (self update). Phần chứng minh tính đúng đắn và hiệu quả của phương pháp đã được trình bày trong [6], trong luận văn chỉ trình bày thuật toán SU và ví dụ minh họa. Gọi là dãy N điểm dữ liệu, là dãy N trọng tâm của chùm mà N điểm dữ liệu đó thuộc. Thuật toán SU được trình bày như sau: Bước 1: Khi , khởi tạo =, rất nhỏ. Bước 2: Cập nhật dãy trọng tâm theo công thức: 14
(1.12) Trong công thức trên, Với là trung bình các khoảng cách của các điểm dữ liệu và . Bước 3: Lặp lại bước 2 cho đến khi . Ví dụ 1.5. Thực hiện lại ví dụ 1.4 với thuật toán SU để tìm chùm khởi tạo Với dữ liệu đã cho, ta tính được và . Áp dụng công thức ở bước 2, ta lần lượt có kết quả được cho trong bảng sau: Bảng 1.4: Kết quả các vòng lặp thuật toán SU Trọng tâm của chùm A B C D chứa phần tử Vòng lặp 0 1.00 2.00 7.00 9.00 Vòng lặp 1 1.11 1.89 7.03 8.97 Vòng lặp 2 1.24 1.76 7.07 8.93 Vòng lặp 3 1.37 1.63 7.10 8.90 Vòng lặp 4 1.47 1.53 7.15 8.85 Vòng lặp 5 1.50 1.50 7.20 8.80 Vòng lặp 6 1.50 1.50 7.25 8.75 Vòng lặp 7 1.50 1.50 7.32 8.68 Vòng lặp 8 1.50 1.50 7.39 8.61 Vòng lặp 9 1.50 1.50 7.48 8.52 Vòng lặp 10 1.50 1.50 7.49 8.51 Vòng lặp 11 1.50 1.50 7.72 8.28 Vòng lặp 12 1.50 1.50 7.85 8.15 Vòng lặp 13 1.50 1.50 7.96 8.04 Vòng lặp 14 1.50 1.50 8.00 8.00 Vòng lặp 15 1.50 1.50 8.00 8.00 Như vậy, sau 15 vòng lặp, ta thấy trọng tâm của phần tử A và B hội tụ về 1.5, còn trọng tâm của C và D hội tụ hội về 8.0 nên ta chọn chùm khởi tạo cho thuật toán không thứ bậc gồm 2 chùm là và . Kết quả này cũng tương ứng với vòng lặp cuối cùng của ví dụ 1.4, nghĩa là ta kết thúc thuật toán không thứ bậc chỉ với việc tính toán khoảng cách giữa các phần tử đến trọng tâm của chùm mà không phải thực hiện vòng lặp nào cả. 1.4 VẤN ĐỀ TÍNH TOÁN Việc thực hiện thủ công các phương pháp phân tích chùm với các công thức phức tạp là một vấn đề khó khăn, đặc biệt đối với các bộ số liệu lớn. Phần này của luận 15
văn sẽ trình bày các chương trình được viết trên phần mềm Matlab nhằm đưa bài toán phân tích chùm trở nên dễ thực hiện và áp dụng trong thực tế nhiều hơn. Chương trình 1.1 Phương pháp thứ bậc với khoảng cách min, max, trung bình, ward % Nhap chuoi so lieu x = [chuoi phan tu]; % Tinh khoang cach va dua ve dang ma tran vuong y=pdist(x,'euclide') squareform(y) % Phan tich chum phuong phap thu bac voi khoang cach trung binh z=linkage(y,'single') % Ve do thi d=dendrogram(z,'colorthreshold','default') set(d,'linewidth',2) Nếu sử dụng khoảng cách max, trung bình, ward thì ta thay thế single lần lượt bằng complete, average, ward. Chương trình 1.2 Phương pháp không thứ bậc % Khai báo chuoi cac phan tu x= [chuoi phan tu] % Nhap vao so k chum k=so chum % Thuc hien phan tich [z c]=kmeans(x,k,'Distance','sqeuclide') BÀI TOÁN ỨNG DỤNG Kết quả thi học kì II các môn Khoa học tự nhiên (gồm toán, lí, hóa) của 13 lớp khối 10 trường THPT Tân Quới. Nhà trường muốn biết mức độ tương đồng của các lớp thông qua điểm thi của các môn này( Toánbiến X, Lí biến Y, Hóa biến Z) để có thể phân bố lại lớp trong năm học sau. Tổng quan việc thực hiện: Số liệu: Số liệu được cung cấp bới phòng đào tạo trường THPT Tân Quới. Của 14 lớp khối 10 và điểm thi của 321 học sinh thuộc các lớp. Các lớp được mã hóa như sau: 1: Lớp 10A1 2: Lớp 10A2 16
3: Lớp 10A3 4: Lớp 10 A4 5 : Lớp 10 A5 6: Lớp 10A6 7: Lớp 10A7 8: Lớp 10A8 9: Lớp 10A9 10: Lớp 10A10 11: Lớp 10A11 12: Lớp 10A12 13: Lớp 10A13 14: Lớp 10A14 Phương pháp thực hiện: Trước tiên ta tính giá tri trung bình của mỗi nhóm rồi lấy giá trị đó làm đại diện sau đó phân chùm các nhóm theo khoảng cach min, khoảng cách max, khoảng cách ward rồi đưa ra kết luận định hướng phân bố cho nhà trường. Phân tích chùm không mờ. Phương pháp phân tích chùm theo thứ bậc i ) Sử dụng khoảng cách Euclide giữa hai phần tử và khoảng cách min giữa hai chùm. Theo thuật toán 1 quá trình tính toán theo các bước sau: Bước 0: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14 Bước 1: (79), 1, 2, 3, 4, 5, 6, 8, 10, 11, 12, 13, 14 Bước 2: (23), (79), 1, 4, 5, 6, 8, 10, 11, 12, 13,14 Bước 3: (112), (23), (79), 4, 5, 6, 8, 10, 11, 13, 14 Bước 4: (11210), (23), (79), 4, 5, 6, 8, 11, 13, 14 Bước 5: (7911), (11210), (23), 4, 5, 6, 8, 13, 14 Bước 6: (79115), (11210), (23), 4, 6, 8, 13, 14 Bước 7: (112108), (79115), (23), 4, 6, 13, 14 Bước 8: (11210814), (79115), (23), 4, 6, 13 Bước 9: (1121081413), (79115), (23), 4, 6 Bước 10: (236), (1121081413), (79115), 4 Bước 11: (2364), (1121081413), (79115) 17
Bước 12: (23641121081413), (79115) Bước 13: (2364112108141379115) Hình 1.6 ii) Sử dụng khoảng cách Euclide giữa hai phần tử và khoảng cách max giữa hai chùm. Theo thuật toán 1 quá trình tính toán theo các bước sau: Bước 0: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14 Bước 1: (79), 1, 2, 3, 4, 5, 6, 8, 10, 11, 12, 13, 14 Bước 2: (23), (79), 1, 4, 5, 6, 8, 10, 11, 12, 13,14 Bước 3: (112), (23), (79), 4, 5, 6, 8, 10, 11, 13, 14 Bước 4: (7911), (23), (112), 4, 5, 6, 8, 10, 13, 14 Bước 5: (11210), (7911), (23), 4, 5, 6, 8, 13, 14 Bước 6: (814), (11210), (7911), (23), 4, 5 , 6, 13 Bước 7: (236), (814), (11210), (7911), 4, 5, 13 Bước 8: (791113), (236), (814), (11210), 4, 5 Bước 9: (11210814), (791113), (236), 4, 5 Bước 10: (7911135), (11210814), (236), 4 Bước 11: (2364), (7911135), (11210814) Bước 12: (791113511210814), (2364) Bước 13: (7911135112108142364) 18
Hình 1.7 iii) Sử dụng khoảng cách Euclide giữa hai phần tử và khoảng cách trung bình giữa hai chùm. Theo thuật toán 1 quá trình tính toán theo các bước sau: Bước 0: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14 Bước 1: (79), 1, 2, 3, 4, 5, 6, 8, 10, 11, 12, 13, 14 Bước 2: (23), (79), 1, 4, 5, 6, 8, 10, 11, 12, 13,14 Bước 3: (112), (23), (79), 4, 5, 6, 8, 10, 11, 13, 14 Bước 4: (7911), (112), (23), 4, 5, 6, 8, 10, 13, 14 Bước 5: (11210), (7911), (23), 4, 5, 6, 8, 13, 14 Bước 6: (236), (11210), (7911), 4, 5, 8, 13, 14 Bước 7: (814), (236), (11210), (7911), 4, 5, 13 Bước 8: (791113), (814), (236), (11210), 4, 5 Bước 9: (11210814), (791113), (236), 4, 5 Bước 10: (7911135), (11210814), (236), 4 Bước 11: (2364), (7911135), (11210814) Bước 12: (791113511210814), (2364) Bước 13: (7911135112108142364) 19
Hình 1.8 iv) Sử dụng khoảng cách Euclide giữa hai phần tử và khoảng cách ward giữa hai chùm. Theo thuật toán 1 quá trình tính toán theo các bước sau: Bước 0: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14 Bước 1: (79), 1, 2, 3, 4, 5, 6, 8, 10, 11, 12, 13, 14 Bước 2: (23), (79), 1, 4, 5, 6, 8, 10, 11, 12, 13,14 Bước 3: (112), (23), (79), 4, 5, 6, 8, 10, 11, 13, 14 Bước 4: (11210), (23), (79), 4, 5, 6, 8, 11, 13, 14 Bước 5: (7911), (11210), (23), 4, 5, 6, 8, 13, 14 Bước 6: (79115), (11210), (23), 4, 6, 8, 13, 14 Bước 7: (112108), (79115), (23), 4, 6, 13, 14 Bước 8: (11210814), (79115), (23), 4, 6, 13 Bước 9: (1121081413), (79115), (23), 4, 6 Bước 10: (236), (1121081413), (79115), 4 Bước 11: (2364), (1121081413), (79115) Bước 12: (23641121081413), (79115) Bước 13: (2364112108141379115) 20