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

Ở Ầ

Ầ

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 cùng chùm t ng t

ữ ẽ ự ề ộ ơ ầ ử ự ầ ử ấ ự ươ trong cùng m t chùm s có s t trong t p h p đã cho thành các chùm sao ệ nhau theo nh ng d u hi u nào đó. Khi chùm ng t nhi u h n so

cho các ph n t ượ đ ớ v i nh ng ph n t

c xây d ng, 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 ươ 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á

ư ả

ộ

ặ ự ế ề

ạ ả ẩ các ph ộ ộ ươ ng pháp phân tích khác nhau nh kho ng cách hay đ r ng chùm. Tuy nhiên các ph ộ ộ ầ ử ả ộ ờ ộ 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 nh ng n m ữ ị 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 ậ ữ ng pháp phân tích chùm không m khi t p d i gi a các chùm. này kh c ph c nh li u có các ph n t c đi m c a ph ầ n m g n biên gi

ặ ượ ư ề ệ ề M c dù đã đ ượ c

ự ế ườ ừ ợ ỉ ờ ạ c quan tâm nhi u, nh ng các tài li u v phân tích chùm cũng đ ng h p cũng ch xét cho t ng tr

ứ ố ụ ế ự ệ trình bày khá r i r c, do đó các ng d ng th c t riêng bi t không có s so sánh đ i chi u.

ươ ờ ờ

ợ ơ ở ể ệ ấ ặ ng pháp xây d ng chùm m và không m cho ứ r i r c làm c s đ nghiên c u lý thuy t v n đ này, đ c bi ề t v n đ

ề ự ụ ể ọ ề l n đ áp d ng cho nhi u lĩnh v c khác nhau em ch n đ

ự ế ớ ờ ờ ố ổ ớ V i mong mu n t ng h p các ph ầ ử ờ ạ các ph n t ố ệ tính toán cho s li u th c t 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 d n

ộ ố ượ ộ ủ ầ ử ng (ph n t ữ ỗ ố ượ ữ

ự ươ ẽ ự ắ

ộ ự ng t ố ượ gi a các đ i t

, đi m). trong đó m 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 t i đ i t ọ ươ ng nhau. Hay nói ng n ng n là ta s th c hi n c c đ i hóa s t thì không t ư ự ể ự ữ t ng khác chum. ng cùng m t chum, nh ng c c ti u hóa các đ i t ậ ộ 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.ề

ượ ọ

ề ộ ọ ố ượ ề ậ ớ ấ

ề ệ ế c g i là vi c x p nhóm ng vào cùng m t chùm đ ấ ứ i v n đ quang tr ng nh t là nghiêm c u không giám ớ ủ ố ượ ng. Hay nói

ể ổ ứ ố ượ ử ệ

ch c các đ i t ộ ầ ử ủ ố ộ

ậ ượ ử ụ ể ạ ợ

ặ ng ho c các tr ượ ọ ạ ọ ng vào các nhóm mà trong đó, 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 ườ ng h p thành c g i là phân tích phân lo i ố ượ c s d ng đ phân lo i các đ i t ng g i là chùm. Phân tích chùm còn đ

ặ ố Quá trình nh m các đ i t (clastering). Clastering đ c p t sát ( unsperviced learning) – không có thông tin v nhãn l p c a đ i t cách khác, đây là công vi c “ x lí đ t ỗ các ph n t ớ l p các kĩ thu t đ ố ượ các nhóm đ i t ạ ố 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 ng d li u. Tuy nhiên, m t c s d li u l n bao ể ẫ ớ ế i k t

ả ở ậ ậ ả ở ố ượ ồ ệ li u nh bao g m vài tram đ i t ồ ỉ ố ượ ệ g m hàng tri u, hàng t đ i t ả qu kém. Các thu t toán này có tính kh m cao là r t c n thi ộ ơ ở ữ ệ ớ ậ ữ ệ ớ ng. x p nhóm trên t p d li u l n có th d n t ế ấ ầ t.

ả ạ ậ ấ c các nhóm có hình d ng b t kì: các thu t toán ph i tìm

ả ặ ồ ẻ ở ữ ấ ượ ệ ượ Kh năng phát hi n đ ồ ạ 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

ra đ 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.

ơ ế ữ ệ ứ

ệ ượ ớ ể ễ c v i các d li u ch a nhi u: c ch phân chum thích ễ ứ ả Kh năng làm vi c đ ề ượ ớ c v i nhi u đi m nhi u. ng đ

ứ ự ữ ệ ộ ậ ứ ầ ả ớ ạ ả 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ác lĩnh v c đ i s ng, tìm ra cách phân tích chum t

ầ ọ ộ ể ầ có th c n phân ể ộ ị ọ ạ 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 chum 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 t đ i ẫ ầ ớ ữ ệ v i d li u đ u vào mà v n tôn tr ng các rang bu c ban đ u.

ệ ợ ể ể ượ ả ụ i và kh d ng: Ng

ộ ộ c, ti n l ể ể ượ ườ ộ ố ậ c và ti n l

ệ ợ ớ ậ

ế ủ ứ ậ ượ c i dùng luôn mong nh n đ ệ i. Có m t s thu t toán khi th c hi n và ả ự ế ế ấ là v n ố ể ự ế có th chi ph i

ươ ặ Tính có th hi u đ ự m t b phân chùm có th hi u đ ả ự ế ợ ớ không kh p, không h p lí. V y k t qu th c t so sánh v i các k t qu th c t ề ậ ọ ề đ quan tr ng c a thu t toán, Đi u quang tr ng là nghiên c u th c t ư 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,

ằ ậ ị ư ậ ề ư ọ

ươ ụ ng,… Có nhi u tên g i khác nhau nh v y là vì ề 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 ộ c s d ng r ng rãi và có đóng góp quan tr ng trong m i m t đ i

ượ ử ụ ụ ồ ề ượ phân tích b ng kĩ thu t đ nh l ph chùm đã và đang đ ứ ộ 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

ọ ư ặ ồ ặ ả ơ ở trong c s mua bán t ừ ữ d

ừ ệ ng đ ng nhau và đ c t ợ ệ ậ ả ậ ươ quang tr ng có các đ c tr ng t li u khách hàng. T đó nâng cao l i nhu n, c i thi n thu nh p.

ọ ươ ệ ậ ng pháp này h u d ng đ phát hi n các loài sinh v t , phân

ớ ể ậ ượ ồ ươ ấ ữ ụ ng đ ng và thu th p đ c các c u trúc trong các

Trong sinh h c: ph ứ ạ lo i các gen v i các ch c năng t m u.ẫ

ả ư ụ ả ự ồ ộ ủ ừ các hình nh ch p dduocj t

ữ ệ ủ ượ ừ c t ệ ố Trong phân tích d li u không gian: Do s đ s c a các d li u không gian ế ị t b ể ữ ệ ệ các v tinh, các thi ườ ấ i dùng r t khó ki m tra

ọ ữ ệ ươ

t rõ ràng. Ph ử

ể ộ ng pháp phân tích chùm có th ạ ự ệ ự ộ đ ng phân tích và x lí các d li u không gian nh nh n d ng ặ ư ậ ơ ở ữ ệ ể ồ ạ ữ ệ ế ấ ặ 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

nh các hình nh th đ ị khoa h c hay các h th ng thông tin đ a lí(GÍ),… làm cho ng ế các d li u không gian m t cách chi ti ợ tr giúp nguoief dùng t chi 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

ặ ươ ủ ẽ ng lai c a web mining s ngày càng phát

ể ủ ớ ụ ọ ể tr ng. có ý nghĩa theo tiêu chí đ c ra. 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 .

ứ ậ ấ ằ ộ

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à

ố ộ ằ ươ

ạ ữ ng pháp th ng kê đa bi n nh m nhóm ị

ố ượ ộ

ố ự ườ ặ ầ ử ữ ệ c coi nh là m t nhóm d li u, trong đó nh ng ph n t ề ữ ệ ng t ư nhau theo m t nghĩa nào đó. Khi có nhi u d li u, ng

ữ

ớ ủ ữ

ố ượ ừ ệ

ộ ầ ử ng t

ự ầ ử ộ

ề ệ ự ươ ữ c a chùm khác

ơ ể ườ 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, vi c xác đ nh s t

ệ ầ ử

ế ướ ể i thành các chùm theo nh ng đ c đi m đ nh tr c. Chùm ộ ữ trong cùng m t chùm thì có i ta mu n chia các ầ ng trong cùng nhóm thì g n nhau ầ ng c a nhóm khác. T yêu c u đó bài toán phân tích chùm ra ữ ệ trong d li u ban ự ươ nhau theo trong cùng m t chùm . Bài toán phân tích ượ ọ c g i là ầ ử ờ r i ự ươ ng t đó, nh ng ph n t ơ ố ớ ả ch y u d a vào kho ng cách gi a các ph n t ỏ ầ ử ủ ế ự ớ ầ ử ữ ầ ả ị ữ ượ ế khác thì g n nhau h n và đ ự ầ ử có c x p cùng

ộ

ệ ạ ủ ế ự ể

ầ ử ờ ạ r i r c: ủ ứ ậ ả Everitt et al (2001), phân tích chùm là m t ph ộ ậ ng l m t t p các đ i t ượ đ ộ ự ươ s t ề ữ ệ d li u này thành nhi u nhóm sao cho nh ng đ i t ố ượ ơ h n so v i nh ng đ i t ể ể phân tích chùm là vi c nhóm các ph n t ầ ử ờ đ i. Chúng ta có th hi u ầ trong cùng m t chùm thì t đ u thành các chùm sao cho các ph n t ượ ộ ấ c xây d ng, nh ng ph n t m t d u hi u nào đó. Khi chùm đ ầ ử ủ ớ ự ẽ nhi u h n so v i nh ng ph n t ng t s có s t ạ ậ ủ ộ ướ ng phát tri n quan tr ng c a nh n d ng th ng kê, th chùm là m t h ạ ữ nh n d ng không đ ặ ạ r c ho c các hàm m t đ xác su t. Đ i v i ph n t ữ ủ c a các ph n t ấ kho ng cách nh nh t so v i nh ng ph n t m t chùm. ươ Hi n t ng pháp th b c và ph ng pháp không th b c. Trong đó kho ng cách c a hai

ả ả đ

ợ ượ ử ụ ả ả ậ

ầ ố

ữ ề

ừ ẩ ng pháp ch y u đ xây d ng chùm cho các ph n t i có hai ph ươ ươ ứ ậ ph ủ ế ầ ử ượ ử ụ 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.

ộ ố ưở ầ ở ớ

ượ ể ượ ử ụ c s d ng đ u tiên b i Tryon (1939) v i m t s ý t ưở ng này đ

ự

ả ể ở ẩ ầ ử ờ ạ ữ ề ả ậ ả ơ ng đ n Phân tích chùm đ ụ ậ ầ c phát tri n thành các thu t toán phân tích chùm c gi n ban đ u. Các ý t ậ 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 ể đã phát tri n thu t toán r i r c. Nhi u tác gi

ế ả ổ ổ

ữ ệ ờ ạ ủ ữ ằ 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 đ

ộ ộ ả ổ ế ấ ự ắ ươ t t , xã h i…. Hartigan (1975) đã cung c p m t b ng tóm t

ứ ạ

ạ ệ ữ ệ

ế ầ ủ ữ ọ ọ ượ ả ổ ọ ấ ừ năm 1990 cho đ n ng, phân tích chùm đã phát tri n r ng rãi t ụ ằ ể ộ ạ ể

ữ ệ ử ụ ề

ả

ụ ụ ố

ể ị ề ả ấ ế ạ ộ

ấ ạ ạ ọ c ng d ng khá ph bi n trong nhi u lĩnh v c: sinh h c, y ố ọ ng đ i đa h c, kinh t ẳ ạ ự ế ủ 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 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 . Piotr Kulczycki, Malgorzata Charytanowicz, Piotr A. Kowalski, Szymon Nhóm tác gi ạ ạ ố 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

ộ ố ọ ọ ụ ượ ế c m t s nhà toán h c, tin h c

ệ ữ ệ cho bài toán phân tích chùm, tuy vi c áp d ng đã đ ự 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

ả ả ng t

ệ ữ ạ ượ ầ ử ờ ạ

ế ả ề ữ c a các chùm khi d ầ ử ộ là m t metric, ệ ỏ ầ ử x và y thì ph i th a các đi u ki n sau đây:

ả ấ

ầ ử ờ ạ r i r c ự ủ ự ươ ể ng dùng đ đánh giá s t Kho ng cách là đ i l ữ ả r i r c. Kho ng cách gi a hai ph n t li u phân tích là các ph n t ủ nghĩa là n u là kho ng cách c a hai ph n t ả i) d(x,y) 0 . D u b ng x y ra khi , ii) iii)

ề ể ị ữ

ườ ạ ượ ằ d(x,y) = d(y,x), 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 y (x, y) theo nhi u cách khác nhau. Thông th ầ ử x và ả ả ng các lo i kho ng cách sau đ c

ổ ế

ớ ậ (1.1) (1.2) (1.3) (1.4)

ử ụ ượ ấ c s d ng nh t ử ụ s d ng ph bi n: ả Kho ng cách Euclide: ả Kho ng cách city block: ả Kho ng cách Chebyshev: ả Kho ng cách Minkowski v i b c m: ậ : Nh n xét i)

Kho ng cách Euclide là kho ng cách th ẳ ả ộ ng đ ố ả ủ ể ạ ọ ả 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.

ổ ộ ả

ấ ả ỗ ề ạ

ố ớ ụ ươ ứ ế

ng ng trong n tr c chúng ta ch n làm h quy chi u. ộ ệ ấ ụ ẳ ả ạ ớ ii) Kho ng cách cityblock mô t ạ ẽ iii) Kho ng cách Chebyshev 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 ạ ả đo n th ng có đ dài l n nh t trong n đo n ấ ổ ượ ề ậ c đ c p trong kho ng cách city block. Đây là kho ng cách t ng quát g p khúc đã đ ộ ữ ớ ấ ng ng v i m t nh t, v i nh ng m khác nhau, kho ng cách Minkowski b c m s 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, .

Khoang cach Euclide mo ta do dai doan thang nay

y(2;4)

Khoang cach Chebyshev mo ta do dai duongt gap khuc lon nha

x(1;2)

-1

Khoang cach city-block mo ta do dai 2 doan gap khuc

-2

-1

ổ ế ủ ẽ ể ả ọ 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).

ầ ử ữ ạ ả 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 ầ ượ ố ạ ả t song song 2 đo n g p khúc n i x và y, chúng l n l kho ng cách cityblock mô t ế ộ ự ư ậ ộ ươ ủ ệ ọ ụ ớ ụ nh v y, n u x, y thu c không ng t v i tr c hoành và tr c tung c a h t a đ . T ầ ượ ẳ ạ ẽ t song song v i Ox, Oy, 3 đo n th ng l n l gian thì kho ng cách cityblock s mô t ấ ẳ ạ đo n th ng dài nh t trong hai Oz. Hình trên cũng ch ra kho ng cách Chebyshev mô t ườ đ 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 ầ ử x và ữ ả A và B, d(x,y) là kho ng cách gi a ph n t

ầ ử D(A;B) là kho ng cách gi a hai nhóm ph n t

ử ụ ườ ị ng ta s d ng các đ nh nghĩa sau cho D(A;B):

y (). Thông th Kho ng cách min: Kho ng cách max: Kho ng cách trung bình: (1.5) (1.6) (1.7)

ả ả ả ớ ầ ượ ầ ử ủ V i l n l ố t là s ph n t c a nhóm A và nhóm B.

ậ : Nh n xét

ữ ữ ệ ụ ộ ỉ

ụ ả ạ ộ

ẽ ả

ượ ứ

ả

i u. Trong th c 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 ế ả ạ ầ ử ữ , do đó s có nhi u k t qu khác nhau tùy vào lo i kho ng gi a hai ph n t ử ụ ư ọ ượ ườ c s d ng cách đ i ta ch a ch ng minh đ ổ ế ạ ự ế ả các lo i kho ng cách ph bi n đã kho ng cách nào là t ề ườ ở ượ c s d ng nhi u nh t. c nêu đ ề ế c ch n. Cho đ n nay, ng ố ư ng đ trên th

ượ 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 ệ nhóm (A+B) đ n m t nhóm C b t k cũng có th th c hi n kho ng cách t ể ữ 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)

ầ ượ ầ ử ủ ố t là s ph n t c a nhóm A, B và C.

Trong đó,, và l n l Ví dụ 1.1. Cho

Tính: a) gi a ữ A và B. b) gi a ữ A+C và B.

ữ ả ướ ọ iả 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:

Tr ả a)

= = 2.5

ươ ự T ng t

Dmax(A,B)

Nhom A+C

Nhom A

Nhom C

Dmin(A,B) Dmin(A+C,B)

-1

Dmax(A+C,B)

Nhom B

-2

-3

-5

-4

-3

-2

-1

-6

Nhom A

Nhom C

-1

Nhom B

-2

= ả ể ư ọ Ta có th mô t ụ hình h c ví d trên nh sau:

-3

-5

-4

-3

-2

-1

-6

ữ ả 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 đ 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. ạ 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 ề

ố ộ ữ ệ

ộ ề ư ư ề ữ ệ ề ữ ệ ặ ể ố ư

ủ ể ố ữ ệ ụ ữ ệ ng,… đ u là d li u ki u s nh ng rõ ề

ế ử ụ ệ ụ ọ

ả ả ư ả ễ ượ i là 10 kg đ

ư ạ ố i). Nh ng s 100 000 l

ệ ạ ẩ ề ớ ớ ộ

ả

ề ế ữ ệ 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 ế ả 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ó t ươ các thu c tính nh : cân n ng, chi u cao, l 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 ề ộ ẩ ệ ố ư ượ c chu n hoá d gây sai l ch v đ đo. Ví d kho ng cách tr ng li u s ch a đ ớ ườ ữ ượ c coi là l n (cách xa nhau), nh ng kho ng cách l ng gi a hai ng ỏ ố ớ ậ ể ươ i là l ng 100 000 có th coi là nh (đ i v i v t giá hi n t ậ ữ ệ ầ ượ c chu n hoá v cùng m t “thang b c” quá l n so v i 10. Do đó các d li u c n đ ế ưở ể ng đ n phân tích chùm. đ không nh h ạ ữ ệ ề ệ 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.

ạ ữ ệ ể ố ổ ế ữ ệ ườ ị ị ể ự 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ông th ,…ứ ự th t

Ầ Ử Ờ Ạ Ự 1.3 XÂY D NG CHÙM CÁC PH N T R I R C

ươ 1.3.1 Ph ộ ươ ả

ứ ậ ữ ả ủ ổ ế ạ

ạ t các l p con này l

ớ ọ ở ộ ồ ị ấ c minh h a b i m t đ th hai chi u

ặ

ệ ợ ượ ự ệ ấ ỏ

ể ể ề ề ặ ọ ị ứ ậ ng pháp th b c ươ ng pháp ng pháp ph bi n trong c phân tích chùm là ph M t trong nh ng ph ộ ố ộ ươ ế ng pháp này là t o ra m t dãy các chùm, trong đó m t s th b c. K t qu c a ph ế ượ ể ứ ứ ớ i ch a bên chùm có th ch a các l p con bên trong nó, và đ n l ớ ề ượ ỏ ơ trong nó các l p con nh h n. C u trúc chùm đ ơ ồ ơ ồ ượ ọ 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.

Hình 1.3: Cây phân tích chùm 3 ph n t ầ ử A, B, C

ươ ng pháp th b c c th nh sau:

ừ ứ ậ c 1 ớ n chùm, m i chùm ch a m t ph n t

Thu t toán phân tích chùm theo ph ỗ ướ : B t đ u v i B ậ ủ ứ ậ ụ ể ư ầ ử ộ ả ả . Tính t ng đôi kho ng ớ ố ứ ủ . Thành l p ma tr n đ i x ng c a các kho ng cách v i là

ắ ầ ầ ử ữ ả cách c a hai ph n t kho ng cách gi a hai ph n t ậ ầ ử i và j, .

ậ ấ ủ ỏ B

ướ : Trong ma tr n kho ng cách ự c 2 ứ ề ả ự ươ khác nhau, t c là hai chùm có s t ng t ả E, tìm kho ng cách nh nh t c a hai chùm ấ nhi u nh t.

ọ ả ấ B c 3 ng t

ợ ớ ự ươ U và V có s t ậ ạ ữ U và V thành chùm m i. Tính toán l ự nhau nh t. ữ ả i ma tr n kho ng cách gi a

ướ : G i là kho ng cách gi a hai chùm ấ H p nh t hai chùm các chùm m i. ớ

ặ ạ ướ ướ ầ ử ượ ế ạ B i b c 2 và b c 3 cho đ n khi các ph n t đ c nhóm l i thành

ộ ướ : L p l c 4 ấ m t chùm duy nh t.

ắ ọ

ạ ủ ữ ả ả ữ ủ ọ 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 là kho ng cách Euclide, kho ng cách gi a các t p h p là kho ng cách

ử ụ ợ ư ươ ằ ụ ố ầ Ví d 1.2. ả ả ầ ử gi a các ph n t ế 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:

ố ấ ợ ạ ấ ộ AB) và (CD) l i thành m t chùm duy nh t. Ta có

Cu i cùng, h p nh t hai chùm ( ư cây phân tích chùm nh sau:

ầ ử A, B, C, D Hình 1.4: Cây phân tích chùm 4 ph n t

ả Cho b ng sau:

ụ Ví d 1.3. ố ầ ậ ộ ủ ụ ắ ả 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 viên A B C D ắ S l n b n trúng m c tiêu c đ nh 1 2 7 9 ắ S l n b n trúng m c tiêu di đ ngộ 0 0 4 10

ữ ả

ử ụ ợ ả ả ươ ằ ữ là kho ng cách Euclide, kho ng cách gi a ng pháp

ầ ử S d ng kho ng cách gi a các ph n t ậ ế ứ ậ ư ả 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 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:

ấ ợ ố ạ ấ ộ 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

ươ ng pháp

ứ ậ ậ ấ ượ ng pháp th b c, các chùm đ c thành l p theo c p đ c a s t ng

ứ ộ ậ

a) Ph ươ Trong ph ế ề nhi u đ n ít. T p các ph n t ỏ ơ ứ ậ . Trong th c

ố ầ ầ ộ ộ ủ ự ươ ớ ớ c xem là m t chùm l n, chùm l n này ch a ự ầ ử t, do ỉ ồ k chùm m t cách riêng bi

ườ ươ i ta còn phân tích chùm theo ph ệ ng pháp

i ta có nhu c u phân chia d li u ban đ u thành ạ ứ ậ ứ ậ

ứ ậ ươ ệ ứ ộ ng pháp không th b c là quá trình phân nhóm m t t và các chùm này không ch a các chùm con khác

ầ ử ượ ự ừ đ t t ế 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 ữ ệ ế ườ t ng ươ ng pháp th b c, ng đó bên c nh ph ả ủ ế không th b c. K t qu c a ph ậ ữ ệ k chùm riêng bi t p d li u thành 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 k chùm m t cách ng u nhiên (s l ng ph n t

ướ : Chia n ph n t ỗ thành ọ ủ ỗ ẫ trong m i chùm là tùy ý). Tính tr ng tâm c a m i chùm.

ế ọ

ướ : Tính kho ng cách t ả ầ ử ế ừ ộ ủ đ n tr ng tâm c a các chùm. N u ộ ấ ỏ m t ph n t đ n tr ng tâm c a chùm nó đang thu c là nh nh t thì ta

ừ ả ầ ộ c 2 B ả kho ng cách t ữ ầ ử ph n t gi ầ ử ế ừ ỗ m i 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

ủ ỏ ầ ử ọ đ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

ỏ ể ộ đ ầ ử c di chuy n đ n

trong chùm nó đang thu c. N u ph n t ả ầ ử ượ ớ ị ọ ự ạ ổ ấ ế ủ ế ph n t ầ ử chùm này, b ph n t ầ 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 khi ta có b t

ạ ướ i b ả c 2 và d ng l ế k chùm, sao cho m t ph n 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 i d li u ví d 1.2 phân tích chùm b ng ph ứ ng pháp không th ụ Ví d 1.4

ậ ớ k = 2. b c v i

ữ ế ả là kho ng cách Euclide, ta ti n hành phân

ầ ử S d ng kho ng cách gi a các ph n t ư ả ươ ằ ử ụ tích chùm b ng ph ứ ậ ng pháp th b c nh sau:

ầ ử ẫ ộ ọ thành 2 chùm m t cách ng u nhiên: và . ộ ọ Tính t a đ tr ng

Chia các ph n t ủ ỗ ế ả 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à

ọ , , , ,

ấ ấ

ỏ ơ ặ ạ ừ ừ B đ n tr ng tâm chùm th nh t nh h n kho ng cách ứ c tính chùm 2 sang chùm 1. L p l ả ướ i các b ế ọ ể B t

ầ ượ ế ả ả Ta th y kho ng cách t ứ ế ừ B đ n chùm ch a nó nên ta chuy n t trên, ta l n l t có k t qu sau:

ả ặ B ng 1.2: Vòng l p 1

Chùm 3.33 Chùm 9

Chùm Chùm ọ Tr ng tâm ả Kho ng cách t ầ ử ế ph n t ừ ọ đ n tr ng

tâm chùm A B C D 2.33 1.33 3.67 5.67 8 7 2 0

ặ ả B ng 1.3: Vòng l p 2

ọ Tr ng tâm Chùm 1.5 Chùm 8

Kho ng cách t

Chùm Chùm

ả ừ ầ ph n ọ ử ế đ n tr ng tâm t chùm A B C D 0.5 0.5 5.5 7.5 7 6 1 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 t. Tuy nhiên, đ i v i nh ng b s li u l n, vi c xác

ộ ấ

ở ạ ứ ậ ặ

ộ

ề ụ ượ ọ ố ấ

ứ ư ự ượ ư ề ậ ữ ệ

ủ ợ ng h p

ươ ệ ỉ ố ỉ ố ự ệ

ượ ợ k chùm khác nhau, đi u này làm cho vi c

ườ c th c hi n sau khi đã ề ụ ươ ặ

ệ ng pháp ở ề ầ ượ ể ọ ị

ị ể ệ ầ

ả ớ ượ ư ẽ

ầ

ỉ ư ế ậ ươ ệ ng pháp “t ả ủ ượ ậ ỉ

ậ

ữ ệ ể ọ ủ N tr ng tâm c a chùm mà N đi m d li u đó

ượ ộ ầ ố ớ ộ ố ệ ộ ố ệ ớ k chùm riêng bi b s li u thành ố k và ch n chùm kh i t o nh th nào là m t v n đ khó khăn. Vì ư ế ọ ị ề đ nh chính xác s ữ ệ ố ớ ả ủ ụ ậ ế ộ ố ệ ớ t đ i v i nh ng b s li u l n ph k t qu c a thu t toán không th b c đ c bi ở ạ ầ ử ọ ệ ề k và cách ch n các ph n t thu c nhi u vào vi c ch n s chùm vào chùm kh i t o nên ề ể ề ấ ố ượ v n đ này đ ng pháp đ c quan tâm r t nhi u. Có nhi u ph 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 ố k khác nhau. Tuy nhiên, vi c tính các ch s này đ ệ ớ v i các s ộ ố ệ ườ ng h p phân tích b s li u thành các tr ệ ả ệ ồ ở 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 k mà l này ch có th xác đ nh g n đúng i không xác đ nh đ ạ t o nh th nào đ vi c tính toán là t ươ ủ ộ c a lu n văn s trình bày m t ph ậ ậ là ph và hi u qu c a ph ng pháp đã đ ọ thu t toán SU và ví d minh h a. ữ ệ ọ N đi m d li u, là dãy ư c trình bày nh sau: ạ c nên ch n chùm kh i ố ư ặ ề i u, không tr i qua nhi u vòng l p. Ph n này ọ c Hung và Wen Liang đ a ra g i ng pháp m i đ ắ ứ ự ộ đ ng c p nh t” SU (self update). Ph n ch ng minh tính đúng đ n ươ c trình bày trong [6], trong lu n văn ch trình bày ụ ể G i là dãy ậ thu c. Thu t toán SU đ

ở ạ ấ 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:

(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 .

ạ ự ụ ở ạ ể ậ ớ i ví d 1.4 v i thu t toán SU đ tìm chùm kh i t o ệ l Th c hi n

ượ ầ ượ ụ c và . Áp d ng công th c ứ ở ướ b c 2, ta l n l t có

ụ Ví d 1.5. ớ ữ ệ V i d li u đã cho, ta tính đ ả ượ c cho trong b ng sau: ặ ế ả ậ ế ả k t qu đ ả B ng 1.4: K t qu các vòng l p thu t toán SU

ọ A B C D

ủ Tr ng tâm c a chùm ầ ử ứ ch a ph n t Vòng l p 0ặ Vòng l p 1ặ Vòng l p 2ặ Vòng l p 3ặ Vòng l p 4ặ Vòng l p 5ặ Vòng l p 6ặ Vòng l p 7ặ Vòng l p 8ặ Vòng l p 9ặ Vòng l p 10ặ Vòng l p 11ặ Vòng l p 12ặ Vòng l p 13ặ Vòng l p 14ặ Vòng l p 15ặ 1.00 1.11 1.24 1.37 1.47 1.50 1.50 1.50 1.50 1.50 1.50 1.50 1.50 1.50 1.50 1.50 2.00 1.89 1.76 1.63 1.53 1.50 1.50 1.50 1.50 1.50 1.50 1.50 1.50 1.50 1.50 1.50 7.00 7.03 7.07 7.10 7.15 7.20 7.25 7.32 7.39 7.48 7.49 7.72 7.85 7.96 8.00 8.00 9.00 8.97 8.93 8.90 8.85 8.80 8.75 8.68 8.61 8.52 8.51 8.28 8.15 8.04 8.00 8.00

ọ ấ ủ ư ậ v 1.5,

ộ ụ ề ậ ặ Nh v y, sau 15 vòng l p, ta th y tr ng tâm c a ph n t ộ ụ ộ ề ủ 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

ế ầ ử A và B h i t ở ạ ớ ố

ủ ứ ậ

ng ng v i vòng l p cu i ỉ ớ ả ế ầ ử ế ặ ệ ự ữ ủ ệ ả ọ

Ề

ứ ủ ớ ọ còn tr ng tâm c a ả ứ ậ ồ ươ ứ không th b c g m 2 chùm là và . K t qu này cũng t ậ ụ 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 . Ấ 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

1.4 V N Đ TÍNH TOÁN ệ ự ộ ấ ộ ố ệ ớ ệ ố ớ ủ ầ ặ ậ ệ ề ạ 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

ẽ ươ ượ ư ế ầ c vi

t trên ph n m m Matlab nh m đ a bài toán ề ụ ằ ơ ở nhi u h n.

ng trình đ văn s trình bày các ch ệ ễ ự phân tích chùm tr nên d th c hi n và áp d ng trong th c t ươ ứ ậ ớ ươ ề ự ế ả ng pháp th b c v i kho ng cách min, max, trung ng trình 1.1 Ph

Ch 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)

ế ử ụ ế ả ầ ượ ằ t b ng

N u s d ng kho ng cách max, trung bình, ward thì ta thay th single l n l complete, average, ward.

ươ ươ ứ ậ ng pháp không th b c

Ch ng trình 1.2 Ph % 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')

Ụ ọ K t qu thi h c kì II các môn Khoa h c t

ồ ứ ộ ươ ườ ủ ế ớ ố ồ t m c đ t

Ứ BÀI TOÁN NG D NG ả ng THPT Tân Qu i. Nhà tr ủ ớ ủ ọ ự nhiên (g m toán, lí, hóa) c a 13 l p ố ng đ ng c a các ng mu n bi ế ế ế ể

ể ố ạ ớ ọ ế ườ kh i 10 tr ớ 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 ư c mã hóa nh

ớ 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 đ sau:

ớ 1: L p 10A1

ớ 2: L p 10A2

ớ 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 ườ 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

Phân tích chùm không m .ờ

ươ Ph ứ ậ ng pháp phân tích chùm theo th b c

ữ ả ữ ả và kho ng cách min gi a hai chùm.

ầ ử i ) S d ng kho ng cách Euclide gi a hai ph n t ướ 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)

Hình 1.6

ữ ả ả ữ ử ụ

ầ ử ướ ậ và kho ng cách max gi a hai c sau:

ướ ướ ướ ướ ướ ướ ướ ướ ướ ướ ướ ướ ướ ướ ii) S d ng kho ng cách Euclide gi a hai ph n t chùm. Theo thu t toán 1 quá trình tính toán theo các b 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)

ầ ử ử ụ ả Hình 1.7 ữ và kho ng cách trung bình

ữ ậ ả ướ iii) S d ng kho ng cách Euclide gi a hai ph n t 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)

ả ữ Hình 1.8 ữ ả ử ụ

ầ ử ướ ậ và kho ng cách ward gi a hai c sau:

ướ ướ ướ ướ ướ ướ ướ ướ ướ ướ ướ ướ ướ ướ iv) S d ng kho ng cách Euclide gi a hai ph n t chùm. Theo thu t toán 1 quá trình tính toán theo các b 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)

Hình 1.9

ươ Ph ứ ậ ng phân phân tich chùm không theo th b c

% Khai báo chuoi cac phan tu x=[7.165714286 8.048571429 7.394285714; 6.145714286 6.86 6.46; 6.302857143 6.705555556 6.486111111; 6.030555556 6.644444444 5.886111111; 7.028947368 7.313157895 6.676315789; 6.471052632 6.728947368 6.860526316; 6.858974359 7.743589744 6.717948718; 7.025641026 8.538461538 7.423076923; 6.789473684 7.736842105 6.618421053; 7.157894737 8.213157895 7.092105263; 6.660512821 8.038461538 6.487179487; 6.91025641 7.987179487 7.384615385; 7.152777778 8.222222222 6.569444444; 7.472222222 8.388888889 7.611111111 ] % Nhap vao so k chum k=3 % Thuc hien phan tich [z c]=kmeans(x,k,'Distance','sqeuclide') for i=1:14 mi=m(i,:) for j=1:3 cj=c(j,:) kc=sqrt(sum((micj).^2)) end end ả ế k t qu : x =

7.1657 8.0486 7.3943 6.1457 6.8600 6.4600 6.3029 6.7056 6.4861 6.0306 6.6444 5.8861 7.0289 7.3132 6.6763 6.4711 6.7289 6.8605 6.8590 7.7436 6.7179 7.0256 8.5385 7.4231 6.7895 7.7368 6.6184 7.1579 8.2132 7.0921 6.6605 8.0385 6.4872 6.9103 7.9872 7.3846 7.1528 8.2222 6.5694 7.4722 8.3889 7.6111

k =

z =

2 3 3 3 1 3 1 2 1 2 1 2 1 2

c =

ệ c k t qu sau:

ượ ế 10 10 A7 A6 ả 10 A8 10 A9 10 A3 10 A2 10 A4 10 A5

6.8981 7.8109 6.6139 7.1463 8.2353 7.3810 6.2375 6.7347 6.4232 Vi c phân chia làm 3 nhóm ta đ 10A 10 10 A1 N2 N3 N3 N3 N1 N3 N1 N2 N1 N2 10A 11 N1 10A 12 N2 10A 13 N1 10A 14 N2

ậ ế

K t lu n: Nhóm 1: 10A5; 10A7; 10A11; 10A13 Nhóm 2: 10A1; 10A8; 10A10; 10A12 Nhóm 3: 10A2; 10A3; 10A4; 10A6

ươ

Ờ

Ch

ng II: PHÂN TÍCH CHÙM M

2.1 GI

ầ ế ố Ớ Ệ Nh chúng ta đã bi

ấ ị ộ ề ỗ ờ t, trong phân tích chùm truy n th ng (không m ), m i ph n ỉ i; đi u này ch I THI U ư c phân vào m t chùm nh t đ nh và không thu c các chùm còn l

ữ ạ c phân chia thành nh ng

ố ng đ i riêng bi ầ ử ượ đ ự ế ấ r t đa d ng và có nhi u ph n t

ạ ầ ử ữ ệ ế

ươ ắ ố ầ ử ề ộ này thu c hoàn toàn ầ ươ

ượ ủ ể ắ ả ng đ i nh y c m và có kh năng m c sai l m cao. Ph ờ ẽ ng ề c đi m trên c a phân tích chùm truy n

ề ộ ử ượ đ t ữ ệ ự ự th c s chính xác khi d li u phân tích có các ph n t ệ ươ t. Tuy nhiên, d li u th c t vùng t ậ ữ ằ ở ị v trí biên gi a các chùm; vì v y n u phân chia các ph n t n m ạ ả ộ m t chùm nào đó là t ụ pháp phân tích chùm m s kh c ph c nh th ng.ố

ờ ươ ỗ Phân tích chùm m là ph

ề ứ ộ ớ

ở ờ ễ ng pháp phân tích chùm mà trong đó m i ph n t ứ ộ ấ ệ ố ấ ư

ể ể ữ ậ ầ ử ộ

ẽ ớ

ộ thu c vùng biên gi a các chùm cũng không ệ ố ề t mà s thu c nhi u chùm v i các h s ờ ệ ể ủ ư ậ ộ ươ ng pháp phân tích chùm m so

ươ ố ầ ử ẽ s ẽ ộ ồ thu c đ ng th i nhi u chùm khác nhau v i các m c đ khác nhau. Các m c đ này s ượ ể đ c bi u di n b i các h s c p b c thành viên (có th hi u nh là xác su t mà ầ ử thu c chùm). Do đó, các ph n t ph n t ộ ộ ụ ph thu c hoàn toàn vào m t chùm riêng bi ấ c p b c thành viên khác nhau. Đây là u đi m c a ph ớ v i các ph ng pháp phân tích chùm truy n th ng.

ự ế ề ậ ờ ề ự Phân tích chùm m đ

ư ượ c đ xu t, nh ng ph c bi

ấ ươ ề ả ề ờ ươ ng pháp phân tích chùm m ơ ở ượ ấ ề ế ế c xem là c s t đ n nhi u nh t và đ ờ ctrung bình ( Fuzzy c ng pháp phân tích chùm m

ượ ề ấ ở ươ c đ xu t b i Dunn (1973) và đ ng pháp FCM. FCM đ t là ph

ủ ự

ươ ậ ố ờ ượ c xây d ng d a trên n n t ng lý thuy t v t p m và s ế ờ ủ m c a Zadeh (1965). Cho đ n nay, tuy có nhi u ph ươ ượ ề ng pháp đ đ ươ ủ c a các ph means) hay g i t ạ ở ổ t ng quát l ọ thu t toán FCM, các nhà toán h c khác đã phát tri n thành các ph ng pháp khác là ph ượ ọ ắ c i b i Bezdek trong công trình c a mình vào các năm 1981 và 1988. D a trên ể ng pháp phân tích

ờ ặ ề ả ạ ấ

ở ạ ố ư ươ ậ ố chùm m khác b ng cách s d ng các lo i kho ng cách khác nhau, ho c đ xu t các ph ử ụ c, tìm ma tr n phân vùng kh i t o t ằ ng pháp tìm s chùm i u…

Ế Ệ Ờ 2.2 CÁC KHÁI NI M LIÊN QUAN Đ N PHÂN TÍCH CHÙM M

ờ

ợ ượ

ộ ậ ỗ ừ ạ M t t p m trên m t mi n ộ ộ ầ ử X thu c vào t p ộ ậ ề X là m t t p h p đ ộ ậ A) là m t ánh x đi t ở ị c xác đ nh b i ề X vào mi n

2.2.1 T p mậ ờ ị Đ nh nghĩa 2.1 ấ ấ xác su t (xác su t mà m i ph n t ị ơ ậ t p đ n v :

ủ ậ ấ ờ . ự ả m t cách tr c quan hình nh c a 3 t p m : th p, ụ Ví d 2.1.

Hình sau di n t ề trung bình, cao trên mi n nhi ễ ả ộ ệ ộ X. t đ

ậ ạ ờ Hình 2.1: T p m các tr ng thái nhi ệ ộ t đ

ấ

ậ ườ Trong hình trên, ba đ ờ ng g p khúc th hi n các xác su t mà các nhi ờ ầ ể ệ ậ ờ t thu c vào các t p m . Theo đó, trong t p m đ u tiên t p m nhi

ờ ớ

ậ ệ ộ ở ề

ệ ộ ầ t đ l n ệ ộ ấ t đ th p, thì ầ ả ấ i thu c hoàn toàn vào t p m v i xác su t b ng 1, xác su t gi m d n ự ư ậ ở ả nh v y, t đ lên kho ng . T ệ ộ ề ầ ử ấ ậ ấ ằ ươ ng t ộ thu c mi n nhi các t đ cũng t đ cao, thì các ph n t

ấ ị ậ ớ ộ ượ l ệ ộ ướ ộ t đ d các nhi ệ ộ t đ tăng cao và tr v 0 khi nhi khi nhi ệ ộ ệ ộ ờ ậ t đ trung bình và nhi t p m nhi ấ ộ ầ ượ l n l t thu c các t p v i các xác su t nh t đ nh.

ầ ừ ề ậ ươ ế ậ ờ ờ

ộ ớ

ầ ử ầ ề ớ ệ ng pháp Ph n trên v a đ c p đ n khái ni m t p m , phân tích chùm m là ph ấ ị ấ ầ ử ẽ s thu c các chùm v i m t xác su t nh t đ nh, ậ c n phân tích. Ta

ấ ộ ờ ươ ứ ng ng v i các t p m trên mi n các ph n t ệ t có các khái ni m và tính ch t sau: phân tích chùm mà trong đó các ph n t ư ậ nh v y, các chùm t ầ ượ l n l

2.2.2 T p d li u

ậ ữ ệ ữ ệ ủ ị ậ ng ho c đ nh tính, trong lu n

D li u c a phân tích chùm th ượ ữ ệ ỉ ị ầ ử văn ta ch xem xét d li u đ nh l ườ ng ng. Gi ặ ị ượ ở ạ d ng đ nh l ồ N ph n t ậ ữ ệ ả ử s ta có t p d li u g m ỗ , m i

ể ế ậ ữ ệ ẽ ượ ể ễ ở đ n đ c đi m ( c đo b ng n bi n), khi đó t p d li u s đ c bi u di n b i

ằ ầ ử ượ ph n t ộ m t ma tr n d li u ặ ậ ữ ệ Z v i ớ n hàng và N c t.ộ

ậ ỗ ỗ ộ ạ Trong ma tr n trên, m i c t đ i di n cho m i ph n t

ạ

-1

-2

ỗ c đo trên ượ ầ ử ớ n thu c tính, còn m i ộ N ph n t ể ệ ệ ể hàng đ i di n cho m t đ c đi m nào đó đ ầ ử ớ v i 2 bi n ộ ặ Cho 9 ph n t v i ầ ử . ở ồ ị c th hi n b i đ th sau: ượ ế X, Y đ ệ ụ Ví d 2.2.

ồ ị ầ ử ề Hình 2.2: Đ th 9 ph n t 2 chi u

ừ ồ ị ư ể ễ T đ th , bi u di n ma tr n d li u ậ ữ ệ Z nh sau:

ầ ử ạ ệ đ i di n chùm

ế ư ầ ử ữ

2.2.3 Chùm và ph n t Nh đã bi ể ố ớ ộ ự ng t trong chùm có nh ng thu c chùm khác. Trong

ờ nhau h n so v i các ph n t ờ ấ ả t c các ph n t

ầ ử ạ

ỗ ề ủ ầ ử trong chùm, ph n t

ầ ử ệ đ i di n chùm đ ầ ử ạ ộ ầ ử ầ c n phân tích. ớ ố ề ố này có s chi u cùng v i s c tính toán trong quá ầ ườ ề ng ph n

ệ ượ ủ ọ t, chùm là m t nhóm mà trong đó các ph n t ơ ầ ử ươ ặ đ c đi m gi ng nhau, t ộ ậ ỗ phân tích chùm m , m i chùm là m t t p m trên t ệ đ i di n chùm, ph n t Trong m i chùm ta có ph n t ầ ử ạ chi u c a các ph n t trình phân tích chùm, có nhi u cách tính ph n t ằ ử ạ t c tính b ng tr ng tâm c a các ph n t đ i di n đ ượ ư ệ đ i di n, nh ng thông th ầ ử trong chùm.

ậ 2.2.4 Ma tr n phân vùng

ễ ự ể ể ầ ử ằ Ta có th bi u di n s phân chia các ph n t vào

ệ ố ấ ầ ậ

ậ c chùm khác nhau b ng ma tr n ể ể ờ ế th

ủ ầ ử ứ k thu cộ th ờ ộ

ầ ử k không thu c chùm th ể ứ i. Trong phân tích chùm m , có th ề ị ấ ỳ ừ ệ ả ậ ấ phân vùng . Trong đó là h s c p b c thành viên (có th hi u là xác su t) c a ph n ứ i. Trong phân tích chùm không m , n u ph n t ố ớ ử ứ k đ i v i chùm th t chùm th ứ i, n u ph n t ế ế nh n giá tr b t k t ỏ 0 đ n 1 và ph i th a các đi u ki n sau:

, , , , , (2.1) (2.2) (2.3)

ấ ả ể ậ ờ ượ ọ Không gian t t c các ma tr n phân vùng m có th có c a ủ Z đ c g i là không

gian phân vùng m .ờ

ầ ụ Ví d 2.3.

ụ ư ể ậ ớ ậ ữ ệ V i t p d li u trong ví d 2.2, khi c n phân chia thành 2 chùm, ta có ộ th hình thành m t ma tr n phân vùng nh sau:

ờ 2.2.5 Hàm m cMeans

ề ự ế ầ ậ ệ ố ư H u h t các thu t toán phân tích chùm đ u d a trên vi c t

ờ ư ượ ị Theo Dunn (1974), Bezdek (1981), hàm m cMeans đ ờ i u hàm m cMeans. c đ nh nghĩa nh sau:

(2.4)

ậ ờ ủ Z,

ộ ậ

đ i di n cho các chùm, đ n ph n t ả ng kho ng cách t ệ đ i di n chùm,

ị

ị ủ ươ Trong đó ộ là m t ma tr n phân vùng m c a là ma tr n có các c t là các ph n t ầ ử ạ ươ là bình ph ộ ờ ủ ế ố là tham s xác đ nh đ m c a k t qu phân tích chùm. Giá tr c a hàm (2.4) có th đ ng sai t

ầ ử ạ ệ ừ ầ ử ế ph n t ả ủ ổ ư ộ c xem nh đ đo c a t ng ph ả ự ể ầ ể ượ ệ ầ ử ạ ừ ấ ả t t c ị ủ đ n các ph n t đ i di n chùm, do đó ta c n ph i c c ti u hóa giá tr c a hàm

ầ ử ế ph n t ờ m cMeans.

Ự Ờ 2.3 XÂY D NG CHÙM M

ươ 2.3.1 Ph ứ ậ ng pháp không th b c

ươ ự ư ươ ờ T ng t nh trong phân tích chùm không m , ph

ệ ở t, tuy nhiên

ớ

ộ ứ ậ c

ư ở ờ

ầ ươ ế ằ ươ ư ả ứ ậ ng pháp không th b c là đây, các ấ không thu c h n m t chùm mà cùng lúc thu c nhi u chùm v i các xác su t ờ ượ ng pháp không th b c trong phân tích chùm m đ ấ ph n trên. V n ổ ng pháp ph ộ ậ ữ ệ quá trình phân nhóm m t t p d li u thành các chùm riêng bi ộ ề ầ ử ph n t ấ ị ươ ệ nh t đ nh. Vi c th c hi n ph ế ả i quy t thông qua vi c c c ti u hóa hàm m cMean nh đã nói gi ượ ề đ này đ ộ ẳ ệ ự ệ ự ể ề i quy t b ng nhi u ph ng pháp khác nhau nh ng ph c gi

ệ ầ ề ầ

ượ ọ ơ ả

ả c g i đ n gi n là FCM (Fuzzy cMeans). Theo ph ế ậ ử Lagrange và thi

ể ươ ng t l p các ể ạ ự ể ượ ế c: n u, và , khi đó (2.4) có th đ t c c ti u

ơ ặ ấ ế bi n nh t là vòng l p đ n gi n Picard thông qua đi u ki n c n đ u tiên cho các đi m ươ ừ ng pháp này đ d ng. Ph ằ pháp này, b ng cách thêm vào hàm cMeans (2.4) nhân t ể ứ ườ i ta có th ch ng minh đ gradient, ng ỉ ch khi

(2.5) , ,

Và

ệ ầ ủ ừ ứ ể ề (2.6) Các công th c (2.5) và (2.6) là đi u ki n c n cho các đi m d ng c a hàm

ặ ạ ự ộ ụ ứ c l p đi l p l i thông qua hai công th c này. S h i t

ượ ứ ậ cMeans. Thu t toán FCM đ ậ ủ c a thu t toán đ ượ ặ ở c ch ng minh b i Bedez (1980).

ậ Thu t toán FCM

ế ẩ ố ọ ầ Cho ma tr n d li u ậ ữ ệ Z, s chùm c n phân tích , tr ng s mũ , chu n k t thúc , ma

ở ạ ẫ tr n c m sinh . Kh i t o ma tr n phân vùng m t cách ng u nhiên.

ầ ử ạ ộ ự ứ ệ ậ ả B c 1 ố ậ đ i di n chùm d a vào công th c (2.6). ướ : Tính các ph n t

ươ B c 2 ả ng kho ng cách: ướ : Tính các bình ph

ướ ậ ậ B c 3: ớ ậ C p nh t ma tr n phân vùng m i

ự ứ ế ớ ọ N u v i m i ta tính các d a trên công th c (2.5).

ạ ữ ạ ữ ạ N u t n t ế ồ ạ i sao cho thì t i ị i nh ng v trí mà , t ị i nh ng v trí còn l i, đ ượ c

ẫ ọ ch n ng u nhiên sao cho .

B c 4 ướ : Tính chu n ẩ

ướ ế ế ậ L p l

i các b ậ ỏ ơ ệ ầ ượ ặ ạ c ma tr n phân vùng và các ph n t ẩ c trên cho đ n khi chu n nh h n , khi đó thu t toán k t thúc và ầ ử ạ đ i di n chùm c n tìm. ta đ

Chú ý

ọ ậ ượ ự ở ạ c kh i t o đ ệ c th c hi n a) S chùm c và vi c ch n ma tr n phân vùng

ậ ch

ở ướ b ng 1. ộ ờ ủ ưở ả ả ọ ố b) Tr ng s mũ m m nh h

ế ờ ườ ườ ở ố ệ ề ậ ở ươ thông qua thu t toán SU đã đ c p ế ờ ng đ n đ m c a k t qu phân tích. Khi m=1, i ta ng, ng

ọ phân tích chùm tr thành phân tích chùm không m . Thông th ch n m=2.

ả ậ

ả ả ế ế ườ ả ậ ơ ọ ẽ c) S l a ch n các ma tr n c m sinh khác nhau s cho ra k t qu khác nhau, ị i ta ch n A là ma tr n đ n v , khi đó k t qu kho ng cách

ọ ườ ng, ng ể ệ ả ự ự thông th ượ đ c tính th hi n kho ng cách Euclid.

ẽ ế ả ả ộ ố ự ủ ư M t s l a ch n khác c a A nh hay s cho ra các k t qu là kho ng cách

ả ọ Diagonal hay kho ng cách Mahalanobis.

ặ ữ ấ d) Quá trình l p trong thu t toán FCM k t thúc khi s khác nhau gi a t

ầ ử ỏ ơ t các ẩ hai vòng l p k ti p nh h n chu n

ế ậ ở ậ trong hai ma tr n phân vùng U ọ ườ ự ặ ặ ự ặ ế ế ỏ ơ ng g p là =0.01 ho c nh h n. ph n t ữ ế k t thúc . Nh ng l a ch n th

ượ ụ

ụ Ví d 2.4. ậ c cho trong ví d 2.1 thành 2 chùm và kh i ớ ầ ượ ủ ở t có

ướ

ậ ữ ệ Z đ Phân tích t p d li u ụ ư ạ t o ma tr n phân vùng nh trong ví d 2.2, v i , , , tính toán th công, ta l n l ư ả ế c nh sau: k t qu các b Vòng l p 1:ặ

Ph n tầ ử ệ ạ đ i di n chùm V1 V2

2.176471 7.823529

1 1

Ma tr nậ kho ngả cách bình ngươ ph

1.384083 1.031142 1.031142 0.678201 7.972318 23.26644 34.91349 34.91349

46.56055 34.91349 34.91349 23.26644 7.972318 0.678201 1.031142 1.031142 46.5605 5 1.38408 3

Ma tr nậ phân vùng m iớ

0.971132 0.971313 0.971313 0.971676 0.5 0.028324 0.028687 0.028687 0.02886

0.028868 0.028687 0.028687 0.028324 0.5 0.971676 0.971313 0.971313 8 0.97113 2

Chu nẩ 0.028868

Vòng l p 2:ặ

Ph n tầ ử ệ ạ đ i di n chùm V1 V2

2.191382 7.808618

1 1

Ma tr nậ kho ngả cách bình ngươ

ph 1.419391 1.036627 1.0366270.653863 7.888334 23.12281 34.74004 34.74004 46.35728 46.35728 34.74004 34.74004 23.12281 7.888334 0.6538631.036627 1.036627 1.419391

Ma tr nậ phân vùng m iớ

0.970291 0.971025 0.971025 0.9725 0.029709 0.028975 0.028975 0.0275 0.5 0.5 0.0275 0.028975 0.028975 0.029709 0.9725 0.971025 0.971025 0.970291

Chu nẩ 0.000841

ư ậ ỏ ơ ế ậ ặ Nh v y, sau 2 vòng l p, ta có chu n là 0.0008 nh h n 0.01, thu t toán k t

ế ậ ẩ ả ư thúc và ta có ma tr n phân vùng k t qu nh sau:

ươ ư ờ ươ ứ ậ ủ ứ ậ 2.3.2 Ph ng pháp th b c Cũng nh phân tích chùm không m , ph ng pháp th b c c a phân tích chùm

ờ ạ ạ

ỗ ướ ờ ạ ượ ẽ i m i b

ấ c xác su t ứ ậ ẹ ẽ ưở ươ ộ ứ c chúng ta s tính đ ủ ng c a ph ng pháp th b c

ầ ử ầ ầ ượ ự ệ ớ c n phân tích chùm, ta l n l ộ ố ệ N l n ph n t t th c hi n

ộ m cũng t o nên m t cây phân lo i mà trong đó các chùm ch a các chùm con bên trong nó, tuy nhiên, trong phân tích chùm m , t ỗ mà m i chùm con thu c chùm m s là bao nhiêu. Ý t ờ ư m nh sau: ả ử s ta có b s li u Gi ướ c sau: các b

ữ B

ả ả cướ 1: Tính ma tr n kho ng cách gi a các ph n t ậ và tìm hai ph n t ầ ử ự ỏ

ầ ử ố ớ N ph n t và ầ ử ồ và 1 chùm g m 2 ph n t

ầ ử ộ ậ ấ kho ng cách nh nh t. Th c hi n thu t toán FCM đ i v i ở ạ chùm kh i t o g m ấ ỏ cách nh nh t. T đó ta tính đ ệ ồ N2 chùm g m 1 ph n t ầ ử ồ ấ ủ ượ ừ c xác su t c a 2 ph n t ầ ử có N1 chùm v iớ ả có kho ng ẹ con thu c chùm m .

ớ ế ợ ầ ử ủ cướ 2: Tính tr ng tâm c a chùm m i k t h p và xem nó là 1 ph n t . Bây

ờ ộ ố ệ B b s li u g m gi ọ ầ ử . ồ N1 ph n t

ặ ạ ướ ộ ố ệ ầ ử ế ấ B c 3 ướ : L p l i 2 b c trên cho đ n khi b s li u còn 1 ph n t duy nh t.

ạ ủ ố ầ ế ủ G i là s l n b n trúng tr ng tâm c a 4 x th . Ta ti n hành phân tích ụ Ví d 2.5

ươ ư ằ 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:

ế ấ ậ ỏ ữ A và B là nh nh t nên ta ti n hành thu t toán FCM

ấ ậ ả Ta th y kho ng cách gi a ở ạ ớ v i , , ma tr n phân vùng kh i t o là

ế ậ ả Ta có ma tr n phân vùng k t qu :

ư ậ ở ướ ầ b c đ u tiên, ta k t h p ph n t ầ ử A và B thành 1 chùm v i xác su t

Nh v y, ộ ớ ầ ử ạ ấ đ i

ớ ớ ọ ầ ử ế ụ ụ ậ là 3 và s chùm là 2, ma

ớ ố ậ ở ạ ệ ậ ế ộ ế ợ A và B thu c chùm là 0.989 và 0.985. Xem là chùm m i v i tr ng tâm là ph n t di n là 1.5, ta ti p t c áp d ng thu t toán FCM v i s ph n t tr n kh i t o có ố ả C và D cùng m t chùm, ta có ma tr n phân vùng k t qu :

ư ậ ở ướ b

Nh v y, ầ ượ ố ỉ ấ C và D thu c ộ ớ ế ợ C và D thành 1 chùm v i xác su t c này, ta k t h p ế ể Ở ướ c cu i ch còn 2 chùm và nên hi n nhiên ta k t b t là 0.967 và 0.983. chùm l n l

ế ấ ả ớ ớ

ợ h p 2 chùm này thành chùm l n v i xác su t là 1. K t qu ta có cây phân tích chùm ư nh sau:

ầ ử ờ Hình 2.3: Cây phân tích chùm m 4 ph n t

ấ ướ ượ c 1 2 3 đ

Trong cây phân tích chùm trên, ta th y rõ các b ượ ế ợ ở ừ ớ t ng b c k t h p v i nhau

ằ ệ ự c th c hi n trong ầ ử ấ ủ c và xác su t c a các ph n t ể ế t

ướ ấ ổ ể ế

ả ủ Ề 2.4 V N Đ TÍNH TOÁN TRONG PHÂN TÍCH CHÙM M

ươ ậ ầ ớ ậ thu t toán, các chùm đ ộ ư ế thu c chùm là nh th nào. B ng các phép tính xác su t c đi n, ta cũng có th bi ượ ế c k t qu c a cây phân tích chùm này chính xác đ n 92.60%. đ Ấ Ờ Trong ph n này, lu n văn gi ng trình phân tích chùm m đ

ự ế ầ ờ ượ c ầ s ta c n

ươ ế ệ ả ử t trên ph n m m Matlab d a trên thu t toán FCM và thu t toán SU. Gi ư t nh sau: i thi u các ch ậ c chùm. Các ch ậ ượ ng trình đ c vi ầ ử n chi u vào

ề vi phân tích N ph n t ươ ậ Ch ề ng trình 2.1 Thu t toán SU

ỗ ậ ầ ử ầ c n phân tích chùm];

z = [Nh p chu i ph n t zt = z; d = squareform (pdist(zt,'euclide')); %Tinh ds ds = sum(sum(d))/(length(d)*length(d)length(d)); %Tinh ma tran K lamda for i=1:length(d) for j=1:length(d) if d(i,j)

for l=1:so chieu du lieu for i=1:length(d) tu=0; mau=0; for j=1:length(d) tu=tu+zt(j,l)*k(i,j); mau=mau+k(i,j); end ztmoi(i,l)=tu/mau; end end ztmoi; %so sanh chuan va do lech toi da cho phep exilanh=0.01; while max(abs(ztmoizt))>exilanh zt=ztmoi; d= squareform(pdist(zt,'euclide')); % Tinh ma tran K lamda for i=1:length(d) for j=1:length(d) if d(i,j)

ậ end end ztmoi; end kq = ztmoi ươ Ch ng trình 2.2 Thu t toán FCM

% Nhap ma tran phan tu Z = [nhap vao ma tran n hang N cot]; %Khoi tao ma tran phan vung U = [nhap vao ma tran c hang N cot]; % Tinh phan tu dai dien chum for k=1:n for i=1:c tu=0; mau=0; for j=1:N tu=tu+(U(i,j).^2)*Z(k,j); mau=mau+U(i,j).^2; end v(k,i)=tu/mau; end end v; % Tính ma tran khoang cách for j=1:N for i=1:c d2(i,j)=0; for k=1:n d2(i,j)=d2(i,j)+(v(k,i)Z(k,j)).^2; end end end d2; % Cap nhat ma tran phan vung for j=1:N m=0; for k=1:c if d2(k,j)==0

m=m+1; end end if m==0 for i=1:c tong=0; for k=1:c tong=tong+d2(i,j)/d2(k,j); end Umoi(i,j)=1/tong; end else for l=1:c if d2(l,j)==0 Umoi(l,j)=1/m; else Umoi(l,j)=0; end end end end Umoi; % Tinh chuan chuan=0; for i=1:c for j=1:N lech(i,j)=abs(Umoi(i,j)U(i,j)); if lech(i,j)>chuan chuan=lech(i,j); end end end chuan; % Lap lai thuat toan cho den khi chuan nho hon exilanh cho truoc, gia su % exilanh=0.01 while chuan>0.01 U=Umoi;

for k=1:n for i=1:c tu=0; mau=0; for j=1:N tu=tu+(U(i,j).^2)*Z(k,j); mau=mau+U(i,j).^2; end v(k,i)=tu/mau; end end v; % Tính ma tran khoang cách for j=1:N for i=1:c d2(i,j)=0; for k=1:n d2(i,j)=d2(i,j)+(v(k,i)Z(k,j)).^2; end end end d2; % Cap nhat ma tran for j=1:N m=0; for k=1:c if d2(k,j)==0 m=m+1; end end if m==0 for i=1:c tong=0; for k=1:c tong=tong+d2(i,j)/d2(k,j); end Umoi(i,j)=1/tong; end

else for l=1:c if d2(l,j)==0 Umoi(l,j)=1/m; else Umoi(l,j)=0; end end end end Umoi; %Tinh chuan chuan=0; for i=1:c for j=1:N lech(i,j)=abs(Umoi(i,j)U(i,j)); if lech(i,j)>chuan chuan=lech(i,j); end end end chuan; end Umoi chuan

ớ ậ ầ ử ử ụ ụ ươ trong ví d 2.2, s d ng các ch ng trình 2.1 ụ Ví d 2.4.

V i ma tr n các ph n t ờ ứ ậ

và 2.2 đ phân tích chùm m không th b c. ử ụ ươ ể ứ ụ ậ ố Tr ng trình 2.1 đ ng d ng thu t toán SU tìm s chùm

ể ướ c tiên, ta s d ng ch ở ạ ố ư ậ c và ma tr n kh i t o t i u:

z = [1 1; 2 0; 2 2; 3 1; 5 1; 7 1; 8 0; 8 2; 9 1;]; zt = z; d= squareform(pdist(zt,'euclidean')); %Tinh ds ds= sum(sum(d))/(length(d)*length(d)length(d)); % Tinh ma tran K lamda for i=1:length(d) for j=1:length(d)

if d(i,j)exilanh zt=ztmoi; d=squareform(pdist(zt,'euclidean')); % Tinh ma tran K lamda for i=1:length(d) for j=1:length(d) if d(i,j)

for l=1:2 for i=1:length(d) tu=0; mau=0; for j=1:length(d) tu=tu+zt(j,l)*k(i,j); mau=mau+k(i,j); end ztmoi(i,l)=tu/mau; end end ztmoi; end kq= ztmoi

ử ổ ế

ả ủ Trong c a s chính c a Matlab, ta có k t qu : kq =

ư ậ ằ ươ ả Nh v y, k t qu tính toán b ng ch ng trình 2.1 cho th y

ứ ấ ồ ạ ớ ầ ử ứ ứ ộ ị ấ ở ướ b ầ ử thành 3 chùm v i chùm th nh t g m các ph n t còn l ở ạ c kh i t o, ta ầ 1, 2, 3, 4, ph n i thu c chùm th 3. Ta xác đ nh ma

ư 2.0144 1.0000 2.0145 1.0000 2.0145 1.0000 2.0145 1.0000 5.0000 1.0000 7.9855 1.0000 7.9855 1.0000 7.9855 1.0000 7.9856 1.0000 ế ầ ử ẽ s phân các ph n t ộ ử ứ t th 5 thu c chùm th 2 và các ph n t ở ạ ậ tr n kh i t o nh sau:

ế ụ ử ụ ở ạ ừ ớ ượ Ti p t c s d ng ch ậ ng trình 2.2 v i ma tr n kh i t o v a tìm đ c:

ươ % Nhap ma tran phan tu Z= [1 2 2 3 5 7 8 8 9; 1 0 2 1 1 1 0 2 1]; % Khoi tao ma tran phan vung U = [1 1 1 1 0 0 0 0 0; 0 0 0 0 1 0 0 0 0; 0 0 0 0 0 1 1 1 1;];

% Tinh phan tu dai dien chum for k=1:2 for i=1:3 tu=0; mau=0; for j=1:9 tu=tu+(U(i,j).^2)*Z(k,j); mau=mau+U(i,j).^2; end v(k,i)=tu/mau; end end v; % Tính ma tran khoang cách for j=1:9 for i=1:3 d2(i,j)=0; for k=1:2 d2(i,j)=d2(i,j)+(v(k,i)Z(k,j)).^2; end end end d2; % Cap nhat ma tran phan vung for j=1:9 m=0; for k=1:3 if d2(k,j)==0 m=m+1; end end if m==0 for i=1:3 tong=0; for k=1:3 tong=tong+d2(i,j)/d2(k,j); end Umoi(i,j)=1/tong;

end else for l=1:3 if d2(l,j)==0 Umoi(l,j)=1/m; else Umoi(l,j)=0; end end end end Umoi; % Tinh chuan chuan=0; for i=1:3 for j=1:9 lech(i,j)=abs(Umoi(i,j)U(i,j)); if lech(i,j)>chuan chuan=lech(i,j); end end end chuan; % Lap lai thuat toan cho den khi chuan nho hon exilanh cho truoc, gia su % exilanh=0.01 while chuan>0.0001 U=Umoi; for k=1:2 for i=1:3 tu=0; mau=0; for j=1:9 tu=tu+(U(i,j).^2)*Z(k,j); mau=mau+U(i,j).^2; end v(k,i)=tu/mau; end

end v; % Tính ma tran khoang cách for j=1:9 for i=1:3 d2(i,j)=0; for k=1:2 d2(i,j)=d2(i,j)+(v(k,i)Z(k,j)).^2; end end end d2; % Cap nhat ma tran for j=1:9 m=0; for k=1:3 if d2(k,j)==0 m=m+1; end end if m==0 for i=1:3 tong=0; for k=1:3 tong=tong+d2(i,j)/d2(k,j); end Umoi(i,j)=1/tong; end else for l=1:3 if d2(l,j)==0 Umoi(l,j)=1/m; else Umoi(l,j)=0; end end end end

Umoi; % Tinh chuan chuan=0; for i=1:3 for j=1:9 lech(i,j)=abs(Umoi(i,j)U(i,j)); if lech(i,j)>chuan chuan=lech(i,j); end end end chuan; end Umoi chuan

ử ổ ủ ế ả Trong c a s chính c a Matlab, ta có k t qu :

ầ ử Umoi = Columns 1 through 7 0.9384 0.8869 0.8869 0.7390 0.0000 0.0347 0.0234 0.0468 0.0897 0.0897 0.2263 1.0000 0.2263 0.0897 0.0148 0.0234 0.0234 0.0347 0.0000 0.7390 0.8869 Columns 8 through 9 0.0234 0.0148 0.0897 0.0468 0.8869 0.9384 chuan = 3.2513e005 K t qu trên cho ta th y rõ ma tr n phân vùng các ph n t

ậ ố vào các chùm cũng ứ ậ ố ớ

Ở ươ ph ể

ậ ấ ở vòng l p cu i cùng. ử ụ ặ ớ ở ế ng pháp th b c đ i v i các ầ ử ng trình 2.2 đ tính xác su t k t h p 2 ph n t ầ ử ượ ế ấ ả c k t đ ấ ế ợ t c các ph n t

ả ế ặ ư ẩ ủ nh chu n c a thu t toán ươ ầ ử ờ ạ ph n t r i r c, ta cũng s d ng ch ậ các vòng l p, và thu t toán k t thúc khi t vào chùm m i ợ h p thành 1 chùm.

ƯƠ

Ự

Ẩ

CH

NG

III :TIÊU CHU N XÂY D NG CHÙM CÁC HÀM M T Đ

Ậ Ộ

XÁC SU TẤ

Ệ 3.1GI

ệ ớ ậ ữ ệ ớ ế ừ ề ồ ườ Ớ I THI U Khi làm vi c v i t p d li u l n, đ n t nhi u ngu n khác nhau, ng i ta có

ớ ữ ữ

ầ ử ầ đó bài toán phân tích chùm ra đ i.

ợ ậ

ự ng t

ự ọ ự ự ươ ấ ộ ự trong cùng m t chùm s có s t

ộ “g n” nhau theo m t ờ Phân tích chùm là ầ ử trong t p h p đã cho thành các chùm sao cho các ph n t c ch n l a. Khi chùm ng t ụ ể ữ ấ

ề ứ ọ ự ọ

ệ ơ

ự ả ư ỏ ộ c đòi h i. M t s tác gi

ữ ữ

ữ ệ ờ ạ ế ộ ố ậ ế ụ ể ươ ữ ư ổ

ữ ệ ờ ạ ớ ẩ ỉ

ầ ố ủ ữ ệ ự ề ả ở ố

nhu ầ c u phân chia chúng thành nh ng nhóm v i nh ng ph n t ọ ự ừ ấ ệ ượ c ch n l a, t d u hi u đ ầ ử ệ vi c nhóm các ph n t ươ ệ ượ ữ trong cùng chùm t nhau theo nh ng d u hi u đ ữ ượ ẽ ầ ử ơ ề c xây d ng, nh ng ph n t đ nhi u h n ầ ử ủ ữ ớ ụ c a chùm khác so v i nh ng ph n t . Có r t nhi u ng d ng c th trong nh ng ủ ậ ế ỹ lĩnh v c khác nhau c a bài toán phân tích chùm: y h c, sinh h c, kinh t , k thu t, ầ ử ạ ớ ữ ấ ỳ xã h i,…và trong b t k lĩnh v c nào n i vi c nhóm nh ng ph n t l i v i nhau ượ đ nh Sibson (1973), Defays (1977), Rohlf (1982),…đã ư đ a ra nh ng thu t toán c th cho nh ng d li u r i r c. Fukunaga (1990), Webb ấ (2002) đã t ng k t nh ng ph ng pháp liên quan đ n phân tích chùm. Nh ng v n ề đ phân tích chùm cũng ch xét cho d li u r i r c v i tiêu chu n đánh giá “g n” và “xa” b i kho ng cách truy n th ng mà không d a vào s phân b c a d li u. ả ộ ố ườ ầ ử ạ ợ ị ự ự ng h p nó t o ra s ngh ch lý: ph n t Do đó, trong m t s tr đúng lý ph i

ả ạ ượ ế Võ c x p vào chùm kia. Năm 2010 nhóm tác gi

ẩ ộ ộ i đ ư

ệ đ r ng chùm ượ ị

ậ ộ ộ ấ c a các ng t

làm tiêu chu n phân c đ nh nghĩa qua tích phân ự ươ ể ệ ự ợ ề ph ự ạ ủ ầ ử ế ố ươ , y u t

ế

ấ ừ ố ệ ờ ạ ấ ấ ộ

ề ẫ

ộ ộ ng

ự ề ể ả ượ ế ề ế ầ ộ

ụ ớ ố ệ ự ọ ậ ủ ườ ọ

ươ ứ ậ ầ s li u r i r c và vi c tính đ ế t này chúng tôi có b sung ươ ề ế t trên ph n m m Matlab. M t ví d v i s li u th c v đi m rèn ạ ọ ng Đ i h c ế t và c đ a ra đ ki m ch ng các thu t toán, các ch ng trình đã vi

c vi ể ơ ượ ư ể ủ ọ

Ự ƯƠ Ậ Ộ Ự Ấ cượ đ ư ế x p vào chùm này nh ng l ụ ạ Văn Tài, Ph m Gia Th đã đ a ra khái ni m ấ ậ ộ tíchchùm các hàm m t đ xác su t. Đ r ng chùm đ ự ủ ậ ộ hàm c c đ i c a các hàm m t đ xác su t, vì v y khi đánh giá s t ơ ượ ng sai đã đ ph n t c xem xét. Đi u này th hi n s h p lý h n trong ậ ộ ả ệ phân tích chùm. Tuy nhiên, trong vi c gi i quy t bài toán chùm các hàm m t đ ệ ậ ộ ề ướ ượ c l xác su t, v n đ ng hàm m t đ xác su t t ổ ặ ộ r ng chùm v n còn g p nhi u khó khăn. Trong bài vi ấ ế k t qu lý thuy t liên quan đ n đ r ng chùm và v n đ tính toán qua các ch trình đ ệ luy n và đi m h c t p c a sinh viên Khoa Khoa h c T nhiên, Tr ể ể C n Th đ ứ ụ cũng đ minh h a cho các ng d ng c a bài toán phân tich chùm. Ộ Ộ 3.2 S T NG T VÀ Đ R NG CHÙM CÁC HÀM M T Đ XÁC SU T

3.2.1 S t

ng t ẩ ầ ử ờ ạ ự ủ ề ự ươ ự ủ Tiêu chu n đánh giá s t ấ ậ ộ c a các hàm m t đ xác su t ng t

ườ

ự ươ ị ề ả ố ư ể ệ ố th ng. Ng ọ ờ ạ , tuy nhiên vi c ch n kho ng cách nào là t r i r c c a hai ph n t ề i ta cũng có nhi u đ nh nghĩa khác nhau v kho ng cách c a hai chùm ự ủ c a ả r i r c là kho ng cách truy n ủ ả ự ươ i u đ đánh giá s t ng t

ư ượ ệ r i r c là câu h i đã đ c nhi u nhà toán h c quan tâm, nh ng hi n

ườ ỏ ợ ọ ấ ự ươ c a chúng thông ng t

ườ ự ủ ả ư ả c đánh giá qua khái ni m kho ng cách nh : Kho ng cách

ự ủ ươ

ổ ể ượ ư ọ ề c các ợ ng h p

ộ ư ượ c a nó ch a đ ở ườ c đ a ra tr ủ affinity c a Matusita

ượ ọ ộ ộ ờ ị c g i là đ đo k ể (k ≥ 2) đi m tách r i ề ầ ử ờ ạ các ph n t ậ ộ ỏ ng h p 2 hàm m t đ xác su t, s t còn b ngõ. Trong tr ệ ượ ng cũng đ th ả ả Chernoff, kho ng cách Bhattacharyya, kho ng cách Divergence,…Khi có nhi u ứ ề ấ ậ ộ ơ h n hai hàm m t đ xác su t, nghiên c u v tính t ng t ệ ề nhà toán h c quan tâm nhi u. Có hai khái ni m c đi n đ ủ ờ c a Glick (1973) và này. Đó là khái ni m ệ đ đo tách r i ư ủ (1967) cũng nh c a Toussaint (1972). ố ứ Đ nh nghĩa 1: M t hàm đ i x ng s đ

ế ớ ầ ử ọ v i chu n a a a S k ẩ . n u v i m i ph n t , , ..., ∈ S

ề ỏ cho ậ t p S trong không gian véc t nó th a mãn đi u ki n ơ ớ ệ (1)

ụ ể ề ừ T (1) có nhi u đ nh nghĩa c th v hàm

s đã đ ấ ậ ộ ị ỉ c ch ra. , f ,..., f 1 2 , ( k ≥ 2 ), ta có các ượ 2: Cho k hàm m t đ xác su t k f

: (2) : (3)

ề ị Đ nh nghĩa ư ị đ nh nghĩa affinity nh sau: ủ i) Affinity c a Matusita ủ ii) Affinity c a Toussaint Trong đó

ườ ủ ặ ợ Trong tr t ở thành affinity c a ủ

ệ k thì affinity c a Toussaint tr ủ ng h p đ c bi ở Matusita, và khi k = 2 thì nó tr thành affinity c a Hellinger.

ộ ộ 3.2.2 Đ r ng chùm ị a) Đ nh nghĩa

ấ ộ ộ , đ r ng Đ nh nghĩa ậ ộ 3: Cho k hàm m t đ xác su t trên

ư ị ượ ị c đ nh nghĩa nh sau :

ủ c a chùm đ (4)

ậ ộ ấ ị ộ 4: Cho là các hàm m t đ xác su t,chúng ta đ nh nghĩa đ

ủ là .

ị

ổ ể ấ ủ k +1 t ng th . Chúng ta có các

ị Đ nh nghĩa ủ ộ là r ng c a chùm ộ ộ và đ r ng c a chùm ề ộ ộ b) Đ nh lý v đ r ng chùm ậ ộ Cho là hàm m t đ xác su t c a ủ ề ộ ộ ả ế k t qu sau v đ r ng c a chùm: i) (5) Trong đó . ii) (6) Trong đó n, k ≥ 3, n < k và v i ớ iii) (7)

ở đây.

: ứ Ch ng minh (5), (6) và (7) khá dài, chúng tôi xin phép không trình bày ậ Nh n xét

ế ả ư i) K t qu (6) đ

c hi u nh sau: ủ ượ ộ ộ ổ ướ ể là t ng đ r ng c a hai chùm tr

1 – A là kho ng cách ngoài hay kho ng cách gi a hai chùm.

ả ộ ộ ữ ả c khi ghép. ữ ủ ả ự ầ Đ r ng chùm ph n ánh s g n nhau c a nh ng ph n t trong chùm, trong khi

ầ ử ở ả ả ằ ố

ả ướ ộ

ng trái ng ộ ộ ữ

ự ạ ệ ệ ớ ố ả ở ượ c trình bày b i

ƯƠ Ự ự ộ ộ ữ kho ng cách ngoài ph n ánh s xa nhau gi a hai chùm. B i vì là h ng s , nên đ r ng ế chùm và kho ng cách ngoài bi n ượ c nhau. Khi ghép hai chùm thành m t chùm, chúng ta thiên theo h ự ể ổ ậ c c ti u t ng đ r ng vì v y cũng có nghĩa c c đ i kho ng cách gi a hai chùm. ộ ộ ii) Đ r ng chùm có m i quan h v i các khái ni m đ (1), (2) và (3). 3.3 PH NG PHÁP XÂY D NG CHÙM

ươ 3. 3.1 Ph

ế ầ ử Có n ph n t t. Chúng ta chia nh ng ph n t này thành

ứ ậ ng pháp th b c a) Bài toán (Bài toán 1) ầ ử ớ ớ ố ượ ả ầ ữ ữ ỗ ướ c. T i m i b c ta ghép 2 chùm

ng gi m d n theo t ng b ộ ộ ạ ệ

ướ ớ ầ ử ẽ ượ ế ợ ấ ả ế ộ ế v i bi n quan sát đã bi ừ ấ Ở ả ự c k t h p thành m t chùm. K t qu th c

ể ạ nh ng chùm v i s l ỏ ớ thành 1 chùm m i có đ r ng chùm nh nh t so v i vi c ghép 2 chùm khác. ố ướ s đ c cu i cùng, t b ộ ệ ẽ ượ ử ụ hi n s đ

ộ ố ượ ứ ỗ B t c các ph n t ậ c s d ng đ thành l p m t cây phân lo i. ậ ậ Thu t toán b) Thu t toán ( ắ ầ c ướ 1: B t đ u v i 1) ớ n chùm, m i chùm ch a m t đ i t ộ ừ ng. Tính t ng đôi đ

ủ ộ ộ ủ ậ ậ . Thành l p ma tr n đ i x ng ố ứ D c a các đ r ng chùm

r ngộ ầ ử chùm c a hai ph n t v i ớ j, i =1…n, j ≠ i .

ấ ủ ỏ

ự ươ nhau, t c hai chùm có s t ng t

c ướ 2: Trong ma tr n ậ D, tìm đ r ng chùm nh nh t c a hai chùm khác ộ ộ B ấ ề ự ứ nhi u nh t. ữ ả c ướ 3: G i ọ w(u, v) là kho ng cách gi a hai chùm B ấ ấ ớ ự ươ U và V có s t ạ UV). Tính toán l U và V thành chùm m i là ( ự ng t ậ i ma tr n

ớ c:

ộ U và V,

ệ ộ ộ ữ UV), tìm đ r ng chùm gi a

ế ầ i b i ố ặ ạ n – 1 l n) cho đ n khi các đ i

ượ ấ ợ nhau nh t. H p nh t chùm ướ ộ ộ đ r ng chùm m i theo hai b ứ i) Xóa dòng và c t ch a chùm ộ ạ ii) Thêm dòng và c t đ i di n cho chùm ( ớ ạ chùm (UV) v i các chùm còn l i. ướ ặ ạ ướ c ướ 4: L p l B c 3 (l p l ộ ạ ượ c nhóm l t c 2 và b i thành m t chùm duy nh t. ng đ

ươ 3.3.2 Ph ứ ậ ng pháp không th b c

ế ế ầ ầ ử ữ k a) Bài toán (Bài toán 2) ầ ử ớ Có n ph n t v i bi n quan sát đã bi t c n chia nh ng ph n t này thành

ầ ử ộ ộ ộ ế trong chùm có đ r ng đ n chùm nó đang

c, sao cho m t ph n t ế ướ ỏ ơ ộ ộ ộ chùm v i ớ k cho tr thu c nh h n đ r ng đ n các chùm khác.

ộ ẫ ầ ố ượ ng ph n ậ Thu t toán thành k chùm m t cách ng u nhiên (s l

ộ ộ ừ ỗ ế m i ph n t

m t ph n t

ỏ ộ ộ ộ ầ ử ế ấ ả t c các chùm. N u đ đ n t ấ ộ đ n chùm nó đang thu c là nh nh t thì ta gi ế ồ ạ i m t chùm khác mà đ r ng chùm t

ộ ữ ầ ử ph n t ừ ầ ử ph n t ỏ ế đang xét vào chùm này, b

ể ế

ự

ủ ạ ừ ị ọ c 2 và d ng l

ầ ử k chùm, sao cho m t ph n t ả ả ộ

Ụ Ụ Ấ Ề ậ b) Thu t toán ( c ướ 1: Chia n ph n t ầ ử B ỗ ử t trong m i chùm là tùy ý). c ướ 2: Tính đ r ng chùm t B ầ ử ế ừ ộ ộ r ng chùm t ầ đó trong chùm ban đ u. N u t n t ầ ử ấ ỏ đang xét đ n chùm đo là nh nh t thì ta gán ph n t ầ ử ượ ộ ầ ử ế đ trong chùm nó đang thu c. N u ph n t ph n t c di chuy n đ n chùm khác thì ổ ớ ạ ả ầ i giá tr tr ng tâm c a hai chùm m i có s thay đ i. c n ph i tính l ộ ạ ướ c ướ 3: Quay l B i khi ta có i b ỏ ơ ế ấ ỳ 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. 3.4 V N Đ TÍNH TOÁN VÀ VÍ D ÁP D NG

ấ ừ ữ ệ ờ ạ d li u r i r c

ề ướ ượ c l ự ế ầ ậ ộ ng hàm m t đ xác su t t ư ọ ữ ệ ữ ệ ờ ấ 3.4.1 V n đ Trong th c t ầ , h u nh m i d li u có nhu c u phân tích chùm là d li u r i

ể ậ ộ ậ ự

ả ươ

ướ ượ c l ố ấ ừ ữ ệ ờ ạ ậ ộ ng hàm m t đ xác su t t c l

ươ

r c,ạ ấ ệ ầ do đó đ phân tích chùm các hàm m t đ xác su t có ý nghĩa th t s , vi c đ u tiên ề d li u r i r c. Có nhi u ph ph i làm là ng ậ ộ ố ể ướ ượ ấ ng hàm m t đ xác su t. Trong bài pháp tham s cũng nh phi tham s đ ề ươ ộ ạ vi ng pháp hàm h t nhân, m t ph ng pháp có nhi u ư t này, chúng tôi s d ng ph ệ ể ư ế ử ụ ấ u đi m nh t hi n nay.

ề ầ ướ ậ ộ G i ọ là các d li u r i r c c hàm m t đ xác

ữ ệ ờ ạ n chi u c n ấ ầ ướ ượ ấ ươ ạ ạ ng theo ph ng pháp h t nhân có d ng

ậ ộ su t. Hàm m t đ xác su t c n c l (8)

ủ ế ế ạ ứ j.

ứ là hàm h t nhân c a bi n th ư ề ệ ố ơ ệ ề ấ ọ ố ơ Trong đó là tham s tr n cho bi n th ậ Có r t nhi u bàn lu n v vi c ch n tham s tr n, nh ng cũng không có vi c

ọ ỏ ng s không đ c l

ả ẽ c l

ọ ọ ượ c ủ ướ ượ ng. Tham ế t này chúng tôi ch n ng. Trong bài vi ướ ượ c l

ố ơ

ộ ệ ế ẩ ch nọ ậ ộ ướ ượ ố ơ ố ư i u. Khi ch n tham s tr n nh thì hàm m t đ nào là t ố ơ ớ ẽ ư ơ tr n, nh ng khi tham s tr n l n s làm gi m tính chính xác c a ố ơ s tr n đóng vai trò quan tr ng trong tham s tr n theo Scott (1992): (9) v i ớ j ứ j.

ượ ề c đ ngh nh d ng tam giác,

ượ Ở ị ư ạ ạ ọ đây chúng tôi ch n hàm h t nhân

ề ế ầ ươ ng trình ướ ượ c l ậ ng hàm m t

ươ ấ ậ ộ ộ Ướ ượ c l ề ng hàm m t đ xác su t m t chi u σ ẫ ủ là đ l ch chu n m u c a bi n th ề ạ Theo Webb có nhi u hàm h t nhân khác nhau đ ữ ậ ng, Epanechnikov,... hình ch nh t, song l ẩ ạ d ng chu n: (10) ử ụ t các ch S d ng ph n m m Matlab, chúng tôi đã vi ư ấ ộ đ xác su t nh sau: ng trình 1: a) Ch

ỉ ầ ử ậ ộ ấ ủ ộ ổ ể ng hàm m t đ xác su t c a m t t ng th nào đó ta ch c n s

ữ ệ ầ ướ ượ ng]) c l

ậ ộ ươ ề ấ ng hàm m t đ xác su t hai chi u. Ướ ượ c l ng trình 2:

function fa=uocluong(dla); syms x; fa=sym('x'); sa=sym('x'); ha=1.06*std(dla)*(length(dla)^0.2); sa=0; for i=1:length(dla) sa=sa+1/(2*pi)^.5*exp((((xdla(1,i))/ha)^2/2)); end; sa; fa=(1/ha/length(dla)*sa); ầ ướ ượ Khi c n c l ệ ụ d ng l nh: syms x uocluong([d li u c n b) Ch function f = uocluong2c(dl1,dl2) syms x1 x2 s = sym('s(x1,x2)'); f = sym('f(x1,x2)'); h1 = std(dl1)/(length(dl1))^(1/6); h2 = std(dl2)/(length(dl2))^(1/6); s = 0; for i = 1:length(dl1) s = s + (1/(2*pi)^.5*exp(-(((x1-dl1(1,i))/h1)^2/2)))*(1/(2*pi)^.5*exp(- (((x2- dl2(1,i))/h2)^2/2))); end s; f = 1/(length(dl1)*h1*h2)*s;

ỉ ầ ử ộ ổ ể ậ ộ ấ ủ ng hàm m t đ xác su t c a m t t ng th nào đó ta ch c n s c l

ứ ề ề ầ ướ ượ Khi c n ệ ụ d ng l nh: syms x1 x2 ; ứ ấ uocluong2([chi u th nh t],[chi u th hai])

3.4.2 Tính đ r ng chùm

ộ ộ ượ ấ ệ ậ ộ ể ự c các hàm m t đ xác su t, đ th c hi n bài toán phân tích chùm

ề ả c đ r ng chùm. Gi

ượ ộ ộ ả ệ ộ i quy t v n đ này là m t vi c ậ ộ

ế ấ ự ạ ủ ự ạ ượ ươ c tích phân trên ng trình tìm

ụ ể ứ ề ấ ả ộ

ườ ế đó tính đ r ng chùm đã đ t, tuy nhiên tr

ậ ộ ợ ộ ộ ề ự ế ả ẫ ề ng h p nhi u chi u v n t này, chúng tôi tính đ r ng chùm d a trên

c gi ầ ươ Khi có đ v n đấ ề ọ ả quan tr ng là ph i tính đ ị ở ễ không d dàng, b i vì chúng ta ph i xác đ nh hàm c c đ i c a các hàm m t đ xác ấ ủ ả Rn c a hàm c c đ i này. Ch su t và ph i tính đ ể ự ạ ủ i tích c th cho hàm c c đ i c a các hàm m t đ xác su t m t chi u bi u th c gi ượ ộ ộ ể ừ c vi đ t ế ư ượ ch a đ i quy t. Trong bài vi ự ạ ằ ệ vi c tính g n đúng tích phân hàm c c đ i b ng ph ng pháp Moncte Carlo.

ử ụ ậ ộ ầ

ộ ộ ươ ự ạ ủ S d ng cách tính g n đúng hàm c c đ i c a các hàm m t đ xác su t b ng ế t các ch

ậ ộ ề ộ ng pháp MoncteCarlo, chúng tôi đã vi ườ ấ ằ ươ ng trình tính đ r ng chùm ộ ư ng h p m t chi u, cũng nh nhi u chi u. Sau đây là m t

ề ổ ề ớ ợ ợ ườ ề ể ng h p hai chi u v i ba t ng th :

ươ ươ

Ụ

ự ổ ph các hàm m t đ cho tr ọ ng trình minh h a cho tr ch ộ ộ Ch ng trình 3: Tính đ r ng chùm function A =drchumnc(f1,f4) syms x1 x2 tpfmax m f = sym('f(x1,x2)'); f = [f1 f4]; m = 0; %700,900,1100,1600,5000,50,8000 t1 = 4.5+5.5*rand(1,2000); t2 = 3.5+6.5*rand(1,2000);%50 tu cho ft = 0+0.055*rand(1,2000);%chieu cao do thi for i =1:2000 c=subs(subs(f,x1,t1(1,i)),x2,t2(1,i)); d=double(c); e=max(d); if ft(1,i)<=e %max(subs(subs(f,x1,t1(1,i)),x2,t2(1,i))) m = m + 1; end end m; tpfmax =(m/2000)*4.5*4.5*0.055 kcL1 = tpfmax-1; A = double(kcL1) Ứ BÀI TOÁN NG D NG ệ ể ệ T ng th vi c th c hi n

ố ệ S li u

ể ệ ượ ấ ủ ự ườ c cung c p c a 1 tr

ớ ượ ồ ể ố ng THPT c a kh i 10 g m đi m ớ ậ ố ệ S li u ti u lu n th c hi n đ ố s 3 môn Toán (X), Lý(Y), Hóa(Z), g m các l p đ ồ ủ c mã hóa sau 1: L p 10A1

ớ 2: L p 10A2

ớ 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

ụ ự ệ M c tiêu th c hi n

ỗ ọ ườ M i h c sinh đ ố ng mu n xem

ự ọ ậ ủ ọ ượ ủ ừ ớ

ườ

c đánh giá m c đ h c t p qua 3 môn. Nhà tr ứ ộ ươ ng đ ng c a t ng l p, nh m đánh giá năng l c h c t p c a h c sinh và ả ự ể ng có th xem ỉ ề ứ ộ ọ ậ ằ ượ c phân tích hoàn ch nh nhà tr ọ ớ ủ ứ ạ ộ ồ m c đ t năng l c qu n lý l p c a GV. Khi đ xét đi u ch nh hình th c đào t o cho h c sinh m t cách t ỉ ấ ố t nh t.

ươ ự ệ Ph ng pháp th c hi n

[8.5 7 8.3 6.5 7.5 9 9.3 7.3 8.3 9.1 8.7 8.6 8.1 7.8 7.6 8.6 9 9.1 7 8 6 8 7.5 5.5 6 6 5.5 4.5 5 5 4 6.5 6.5 5.5 6],[6.8 7.5 9.2 6.4 8.7 7.3 7.5 7.7 9.2 8.3 7.8 7.7 8.3 8.7 6.3 9.2 6.3 8.7 8.2 6.9 9 8.5 7.5 5 7.5 8.5 8 9 7 7.5 10 10 9 9.5 9] [6.5 5.5 6.1 5.9 7.2 6.5 7.2 4.7 5.3 5.6 7.2 6.1 7 7 6.2 5 6.3 6.3 4.9 5.6 6.5 9 7.5 6.5 7 3.5 5.5 3 7 7 5 5.5 8.5 6.5 5],[7.2 6.3 5.3 6.7 5.8 5.2 8.3 7.2 6.7 7 5.3 5.8 4.5 5.2 6.6 7.2 5.4 7.4 5.3 7.2 5.5 9 9 8.5 7.5 6.5 7.5 8 8.5 8.5 7 6 6 9 8] [6 7.2 6.5 5.9 5.7 6.1 5.9 4.7 7.2 5.8 6.3 6.2 5.3 5.7 5.4 5.1 5.7 6.3 7.2 4.9 4.5 6 5.5 7.5 7 6 8 6 8.5 6.5 7 5.5 8.5 7 8],[ 5.8 5 6.5 7.2 6 5.8 5.5 5.3 5 7.2 6.8 4.5 5.3 6.7 7.2 6.3 5.4 5.3 6.2 5.4 7.5 6 8.5 6 8.5 9 7 7 9.5 10 9 6.5 6.5 9 5.5 7.5] [4.5 5.5 4.2 3.7 5.3 4.5 5.3 4.9 5.3 4.8 6.3 4.6 5 6.7 6.4 6.3 4.1 4.7 5.7 4.3 5 3.5 8 9 6.5 7.5 7 7.5 8 9.5 8 8 8 7.5 5 7],[6 4.8 5.6 4.5 4.6 4.7 4.7 5.2 5.2 5.2 5.7 5.4 4.4 7 3.9 3.9 2.9 3.8 5.5 2.7 8.5 9 9.5 8.5 9.5 10 10 7 8.5 9.5 8.5 9 9 9 9.5 8.5] [7 8.2 7.3 8.2 6.5 7.3 6.7 7.2 7.1 5.4 8.3 5.7 7.8 6.5 7.2 5.4 7.3 4.5 7.8 6.7 9 8 7.5 7.5 7.5 6 8.5 9 8 6 8 5.5 6.5 5.5 5 7 7 7.5],[6.5 5.4 5.4 7.5 5.7 7.8 6.9 8 5.3 5.7 7.4 8.1 6.7 5.7 5.7 7.1 5.3 5 8.5 7.2 9 7.5 7.5 8 9 6.5 8.5 8.5 10 7 9 8 9 6.5 7.5 9.5 6.5 9.5] [6 5.3 6.3 4.5 6.3 4.7 6.3 6.3 5.6 5.6 6.3 6.4 5.7 7.2 4.5 5.1 6.3 5.3 5.4 6.5 9 9 9 9.5 9 6.5 8 8.5 5.5 8.5 7.5 9.5 9 4 8.5 8.5 7 9],[3.7 5.8 6.4 5.6 5.8 5.6 6.7 6.3 6.2 6.3 5.4 6.4 5.5 5 7.6 5.7 6.3 5.3 5.6 5.5 9 6 8.5 8.5 9.5 9.5 9 9 9 8 6.5 7.5 7.5 7 8.5 8 7 6] [6.5 8.5 5.5 8 10 9.5 9.5 7 9 8 9.5 7 8 6.5 8 7.5 8.5 6 8 9.5 9 6 6.5 6.5 4.5 5 10 7.5 9 7 9.5 8.5 5.5 6.5 9.5 8 8 8 7.5],[ 6 7 7 6 6.5 9 7.5 6 7.5

ọ ủ ữ ệ ớ D li u ba môn h c c a 14 l p 10

6.5 7 6.5 6.5 5.5 6.5 6.5 6.5 9 6.5 7 6.5 5 6.5 6.5 6 5.5 8 6.5 8 5.5 7 8.5 7 6.5 7 5.5 7 6.5 6.5] [8.5 8 8 9.5 8.5 9.5 9.5 9.5 7.5 8.5 6 8 9.5 6.5 8 8.5 9 9.5 9.5 10 9 8 9 9.5 8 8.5 8 9 9.5 8.5 10 9.5 9.5 8 8.5 7 8 7 7],[4.5 6.5 7 8 6.5 7.5 6.5 7 7 6.5 5.5 6.5 8.5 6.5 6 5 6.5 6.5 9 8 6 9.5 8.5 8.5 6.5 7.5 8 7.5 9.5 9 8.5 8.5 9 10 8.5 5.5 7 9 8] [7.5 7 6.5 6.5 9.5 9 7 8.5 7 9 6.5 6.5 9 9 8 6.5 7.5 9.5 7.5 5.5 10 6.5 9 8.5 8.5 8.5 4.5 7 8.5 7 9 8 6.5 9 9 8.5 8 5],[7.5 6 6 5.5 6.5 7.5 7.5 7 6.5 7.5 6.5 6.5 6 7 6 8 6.5 8.5 6.5 5.5 7 5.5 6 6.5 6.5 6.5 6 7 6.5 8 6.5 7 6.5 5.5 7 7.5 5.5 6] [8.5 7.5 9 7.5 8 8 6 7 7.5 7 7.5 7.5 6 7.5 6 5.5 5 7.5 6.5 4 7 6 9 6.5 5.5 5 8.5 7.5 5.5 9 7.5 8.5 9 6.5 7 8 7.5 9.5],[8.5 9.5 8.5 6.5 9.5 9.5 9 9 6.5 9.5 9 9 7.5 9.6 6 7.5 8.5 8 7 8.5 8.5 7 8.5 7.5 9 9.5 7 7.5 8 8.5 9 8.5 8.5 9.5 7.5 8.5 9 4] [6.56 8 6.5 7.5 6.5 6.5 6 6.6 6 6 6.5 6.5 6.5 7.6 6 6.5 5.5 6.5 8 8 7.5 6 6 7.5 7 7 8 5.5 6.5 6.5 7 7 6.5 7.5 7.5 4.5 6 7 5.5],[6 8 4.5 9 6.5 5 8.5 8.5 8.5 10 8.5 9 9.5 7.5 9.5 8.5 8.5 10 9 7.5 8.5 7 7.5 7.5 7.5 6.5 8.5 6 6.5 6 7.5 8 9 9 9.5 9 8.5 9.5 10] [5.5 6.5 2.5 8.5 6.5 7.5 6 5 7 7 6.5 9 7 7.5 7 7 9 7 9 9 7.5 8 5 7 6.5 9 9 7 7.5 4 7.5 8 6 9.5 8.5 4 5 6.5 4],[7.5 4 9 8.5 7 6.5 9.5 8 5.5 9.5 9.5 9 9 9 8 8.5 9.5 5.5 9.5 9 8 8.5 8 9 7 9.5 7 7 7.5 8 8.5 9.5 8 9 10 8 8 6 3.5] [8 8 8 8 6.5 9.5 7.5 5.5 7.5 7.5 7 5 7.5 6.5 8 6.5 6.5 7.5 7.5 8 8 7.5 8.5 6 7 8.5 7.5 7.5 5.5 5.5 7.5 6.5 6.5 6 7.5 6],[9 8.5 8 8 8 9 9 8 9 8.5 9 8 9.5 8 8 7 8.5 6.5 6 8.5 8 9 9.5 9 8 9 8 9 8.5 8.5 9 4 8.5 8 9 7] [7.5 6.5 8.5 6 8.5 7.5 8 6.5 8 6 9.5 7 7.5 7.5 7.5 8 8.5 7 7 9 6 8 8 8 8.5 8 8 8.5 6.5 8 7.5 7 6 5 8 6.5],[9 9.5 7 9 8 9.5 9 8 9.5 8.5 9 8.5 9 8.5 9.5 7.5 8 8 9 10 9.5 8.5 8.5 7 7.5 6.5 6.5 6.5 9 7.5 9.5 8 9.5 7 9 8] ướ B c 1

0 0.418 1 0.44 20 0.48 04 0.39 69 0.39 36 0.397 5 0.433 7 0.36 24 0.407 5

0.50 55 0.45 65 0.428 1 0.38 69 0.375 2 0.25 88 0.35 85 0.35 96

0.453 1 0.401 9 0.391 9 0.38 20 0.25 99 0.373 0 0.32 34

0.42 25 0.417 0 0.43 53 0.417 5 0.419 2 0.391 9

0.49 38 0.404 7 0.32 95 0.379 1 0.401 4

0.412 5 0.321 8 0.38 35 0.410 8

0.46 99 0.515 0 0.345 1

0.443 1 0.36 29

0.321 2

0.373 0 0.39 02 0.38 97 0.378 2

0.40 92 0.399 1 0.387 4 0.361 8

0.407 5 0.381 9 0.387 4 0.361 8

0.44 09 0.46 26 0.474 3 0.46 82

0.40 69 0.43 03 0.42 59 0.40 08

0.370 7 0.371 8 0.34 96 0.375 2

0.30 28 0.33 45 0.63 96 0.40 69

0.379 6 0.34 62 0.33 68 0.35 24

0.46 65 0.49 38 0.511 6 0.479 9

0.45 54 0.510 0 0.48 60

0.52 94 0.472 1

0,50 55

0 0.24 10 0.26 50 0.23 15 0.23 82 0.24 49 0.24 32 0.25 60 0.19 20 0.18 53 0.22 26 0.21 65 0.18 25

0.44 20 0.48 04 0.42 81 0.39 36 0.39 75 0.43 37 0.40 75 0.37 30 0.39 02 0.38 97 0.37 82

0.45 31 0.40 19 0.39 19 0.38 30 0.37 30 0.32 34 0.40 75 0.38 19 0.30 72 0,45 04

0.42 25 0.41 70 0.43 53 0.41 92 0.39 19 0.44 09 0.46 26 0.47 43 0.46 82

0.49 38 0.40 47 0,37 91 0.40 14 0.41 92 0.42 31 0.39 69 0.40 08

0.41 25 0.38 35 0.41 08 0.40 69 0.43 03 0.42 59 0.40 08

0.51 50 0.34 51 0.37 07 0.37 18 0.34 96 0.37 52

0.32 12 0.37 96 0.34 62 0.33 68 0.35 24

0.46 65 0.49 35 0.51 16 0.47 99

0.45 54 0.51 00 0.48 60

0.52 94 0.47 21

0.50 55

ướ B c 2

0 0.18 03 0.16 08 0.14 85 0.18 86 0.17 81 0.17 86

0.44 20 0.48 04 0.39 69 0.39 36 0.39 75

0.45 31 0.40 19 0.39 19 0.38 30

0.42 25 0.41 70 0.43 53

0.49 38 0.40 47

0.41 25

ướ B c 3

0.18 36 0.17 81 0.17 97 0.18 75 0.19 59

0.36 24 0.40 75 0.39 02 0.38 97 0.37 02

0.37 30 0.32 34 0.40 75 0.38 19 0.30 72

0.41 92 0.39 19 0.44 09 0.46 26 0.47 43

0.37 91 0.40 14 0.41 92 0.42 31 0.40 08

0.38 35 0.41 08 0.40 69 0.43 03 0.42 59

0.51 50 0.34 51 0.37 07 0.37 18 0.34 96

0.36 29 0.30 28 0.33 45 0.63 96

0.46 65 0.49 38 0.51 16

0.45 54 0.51 00

0.52 94

0 0.1491 0.1307

0.1463

0.1368

0.1497

0.1519

0.1424

0.1625

0.1441

0.1380

0 0.44 20 0.39 69 0.39 36 0.39 75 0.36 24 0.40 75 0.37 30 0.39 02 0.38 97

0.40 19 0.39 19 0.38 30 0.37 30 0.32 34 0.40 75 0.38 19 0.30 72

0.49 38 0.40 47 0.37 91 0.40 14 0.41 92 0.42 31 0.39 69

0.41 25 0.38 35 0.41 08 0.40 69 0.43 03 0.42 59

0.51 50 0.34 51 0.37 07 0.37 18 0.34 96

0.32 12 0.37 96 0.34 62 0.33 68

0.46 65 0.49 38 0.51 16

0.45 54 0.51 00

0.52 94

ướ B c 4

0 0.1597 0.1402

0.1324

0.1190

0.1324

0.1285

0.1296

0.493 8 0.404 7 0.379 1 0.401 4 0.419 2

0.412 5 0.383 5 0.410 8 0.406 9

0.515 0 0.345 1 0.370 7

0.321 2 0.379 6

0.466 5

0.1419

0 0.396 9 0.393 6 0.397 5 0.362 4 0.407 5 0.373 0 0.399 0.423 0.430 0.371 0.346 0.493 0.455 0

ướ B c 5

0.1314

1 0.389 7

1 0.396 9

3 0.425 9

8 0.349 6

2 0.336 8

5 0.511 6

4 0.510 0

0.529 4

0 0.1452 0.1346

0.1147

0.1224

0.1413

0.1246

0.1263

0.1279

0 0.39 69 0.39 36 0.36 24 0.40 75 0.37 30 0.39 02 0.38 97

0.493 8 0.379 1 0.401 4 0.419 2 0.423 1 0.396 9

0.383 5 0.410 8 0.406 9 0.430 3 0.425 9

0.321 2 0.379 6 0.346 2 0.336 8

0.466 5 0.493 8 0.511 6

0.455 4 0.510 0

0.529 4

ướ B c 6

0 0.1240 0.1341

0.1224

0.1329

0.1129

0.1420

0.1151

0 0.396 9 0.362 4 0.407 5 0.373 0 0.390 2 0.389 7

0.379 1 0.401 4 0.419 2 0.423 1 0.396 9

0.321 2 0.379 6 0.346 2 0.336 8

0.466 5 0.493 5 0.511 6

0.455 4 0.510 0

0.529 4

ướ B c 7

0 0.1190 0.1179

0.1040

0.3791

0.1174

0 0.39 69 0.36 24 0.49

0.4014

0.3212

ướ B c 8

0.1318

0.4231

0.3462

0.4935

0.1151

0.3969

0.3368

0.5116

0.5294

75 0.39 02 0.38 97

0 0.1213 0.0984 0.1034 0.1045 0.1146

0 0.3969 0 0.4075 0.4014 0 0.3902 0.4231 0.4935 0 0.3897 0.3969 0.5116 0.5294 0

ướ B c 9

0 0.1129 0.0917 0.1029 0.1196

0 0.4075 0.3902 0.3897

0 0.4935 0.5116

0 0.5294

ướ B c 10

0 0.0923 0.0995 0.1185

0 0.3902 0.3897

0 0.5294

ướ B c 11

0 0.1084 0.0967

0 0.5294

ướ B c 12

ướ B c 13

0 0.1001

ạ ạ f12 thành chùm.

i thành chùm i

ế

ả ụ ể ư K t qu c th nh sau: ướ ế ợ ạ B c 1: K t h p l i thành chùm ( ). ướ ạ ế ợ B c 2: K t h p() l ). i thành chùm ( ướ ạ ế ợ B c 3: K t h p ()l ). i thành chùm ( ướ ạ ế ợ ). B c 4: K t h p() l i thành chùm ( ế ợ ướ ạ i thành chùmv(, B c 5: K t h p ()l ). ạ ế ợ ướ i thành chùm B c 6: K t h p (,) l ). K t h p) l ạ ế ợ ướ ). i thành chùm B c 7: ạ ế ợ ướ ). i thành chùm B c 8: K t h p) l K t h p )l ạ ế ợ ướ ). i thành chùm B c 9: ạ ế ợ ướ ). i thành chùm B c10: K t h p) l K t h p) ế ợ ướ B c 11: ạ i thành chùm l ). K t h p) l ế ợ ướ B c 12: K t h p) l ế ợ ướ B c 13:

ẽ ượ ư ạ Ta v đ c cây phân lo i nh sau:

Hình 3.1

ượ Ta đ c chùm .

ồ ị ế Đ th phân tán bi n.

Hình 3.3

ả ố ượ ệ ả ộ Hình 3.3 mô t các đ i t ng trong b ng dũ li u theo 3 thu c tính X, Y và Z.

ế

ậ

K t lu n

ữ ệ ự ộ

ứ ộ ề ọ ụ ụ ề ớ ữ ệ ộ Phân tích chùm d li u nhi u chi u là m t lĩnh v c khai thác d li u, m t lĩnh ự ế ư ề ứ nh giáo d , y

ế ề ự ể v c nghiên c u r ng l n, nhi u tri n v ng v ng d ng trong th c t ế , kinh t t ,… .

ệ ề ấ ươ ể ề Hi n nay có r t nhi u ph ng pháp phân tích chùm nhi u chi u, ti u lu n

ộ ố ươ ậ ả ụ

ể ấ ượ ng pháp c b n có tính kh d ng ề ố ề ơ ả ầ phát tri n r t nhi u trong các ph n m m th ng kê thông

ỉ ậ chúng tôi ch t p trung vào phân tích m t s ph ề ậ cao, các thu t toán này đ d ng .ụ

ờ ế ế

ậ ể ẽ ế ụ ứ ờ ứ ề ấ ế ừ ạ Vì th i gian và ki n th c còn h n ch nên ti u lu n ch a phân tích sâu, đi vào ể ớ t t ng v n đ . Trong th i gian t ư i chúng tôi s ti p t c nghiên c u và phát tri n chi ti

ữ ệ ự duy trong thông kê nói chung và trong lĩnh v c phân tích d li u nói riêng

ứ ư ư ữ ứ ế ằ ụ ki n th c t nh m đ a ra nh ng ng d ng vào th c t ự ế .