Tài liệu Phân tích phân biệt, phân loại và phân tích cụm

BỘ GIÁO DỤC VÀ ĐÀO TẠO ĐẠI HỌC ĐÀ NẴNG LÊ THỊ TUYẾT NHUNG PHÂN TÍCH PHÂN BIỆT, PHÂN LOẠI VÀ PHÂN TÍCH CỤM Chuyên ngành: Phương pháp Toán sơ cấp Mã số: 60.46.01.13 TÓM TẮT LUẬN VĂN THẠC SĨ KHOA HỌC Đà Nẵng - Năm 2016 Công trình được hoàn thành tại ĐẠI HỌC ĐÀ NẴNG Người hướng dẫn khoa học: TS. LÊ VĂN DŨNG Phản biện 1: TS. LÊ QUỐC TUYỂN Phản biện 2: PGS.TS. HUỲNH THẾ PHÙNG Luận văn được bảo vệ tại Hội đồng chấm Luận văn tốt nghiệp thạc sĩ khoa học họp tại Đại học Đà Nẵng vào ngày 13 tháng 8 năm 2016. Có thể tìm Luận văn tại: - Trung tâm Thông tin - Học liệu, Đại học Đà Nẵng - Thư viện trường Đại học sư phạm, Đại học Đà Nẵng 1 Mé ĐAU 1. Tính cap thiet cúa đe tài Ngày nay là thòi đai cna bùng no thông tin, sn phát trien cna các ngành khoa hoc và đ¾c bi¾t là sn phát trien cna ngành khoa hoc máy tính đã giúp chúng ta thu th¾p đưoc lưong du li¾u rat khong lo. Vói m®t so lưong du li¾u lón như v¾y thì vi¾c tìm hieu thông tin tù đó là rat khó khăn và phúc tap. Vì v¾y van đe xú lý so li¾u không nhung đưoc các ngành khoa hoc nghiên cúu mà còn đưoc cá xã h®i quan tâm. Đó cũng là lý do cho sn ra đòi và phát trien cna ngành phân tích thong kê. Nhò úng dung cna b® môn phân tích thong kê này mà các ngành sinh hoc, y hoc, kinh te, báo hiem, phân loai ánh. . . đã có nhieu bưóc phát trien vưot b¾c. Phương pháp phân tích phân bi¾t và phân loai cùng vói phương pháp phân tích cum là m®t trong nhung phương pháp xú lý du li¾u trong phân tích thong kê đưoc sú dung pho bien. Vì lý do đó, dưói sn hưóng dan cna thay Lê Văn Dũng, tôi chon nghiên cúu đe tài “Phân tích phân bi¾t, phân loai và phân tích cnm” làm lu¾n văn thac sĩ khoa hoc cna mình. 2. Mnc đích nghiên cNu: Chúng tôi mong muon tìm kiem đưoc nhieu tài li¾u tù các nguon khác nhau, nghiên cúu kĩ các tài li¾u đó, co gang lĩnh h®i m®t so ky thu¾t phân tích thong kê. Hy vong lu¾n văn có the đưoc sú dung như m®t tài li¾u tham kháo bo ích cho sinh viên các trưòng Đai hoc, Cao đang. 3. Đoi tưang nghiên cNu - Ky thu¾t phân tích phân bi¾t và phân loai. - Ky thu¾t phân tích cum. 4. Pham vi nghiên cNu: Lu¾n văn nghiên cúu các khái ni¾m, đ%nh nghĩa, đ%nh lý liên quan. 5. Phương pháp nghiên cNu: Cơ bán sú dung phương pháp nghiên cúu tài li¾u (sách, báo và các tài li¾u trên internet có liên quan đen đe tài cna lu¾n văn) đe thu th¾p thông tin nham h¾ thong lai các van đe lý thuyet. 6. Bo cnc đe tài: N®i dung lu¾n văn gom hai chương: Chương 1: Kien thúc chuan b%. Trình bày lai các kien thúc can thiet cho chương 2, đó là các kien thúc ve vectơ, ma tr¾n, bien ngau nhiên và phân bo chuan nhieu chieu. Chương 2: Phân tích phân bi¾t, phân loai và phân tích cnm. Trong chương này có hai nhi¾m vu chính: thú nhat là giái quyet bài toán phân bi¾t, phân loai; thú hai là giái quyet bài toán phân cum. CHƯƠNG 1 KIEN THÚC CHUAN B± 1.1. VECTƠ VÀ MA TR¾N 1.1.1. Vectơ 1.1.2. Ma tr¾n 1.1.3. Căn b¾c hai cúa ma tr¾n 1.1.4. Các bat đang thNc ma tr¾n và maximum 1.2. VECTƠ NGAU NHIÊN Đ%nh nghĩa 1.2.1. Cho X1, X2, ..., Xn là các bien ngau nhiên cùng xác đ%nh trên không gian xác suat (Ω, F, P ). Kí hi¾u X = (X1, X2, ..., Xn) đưoc goi là vectơ ngau nhiên n chieu. Dang ma tr¾n cna X như sau  1 X X  2 = [X1, X2, ..., Xn] X= T  ...  ho¾c X Xn Đ%nh nghĩa 1.2.2. Cho Xij vói i = 1, 2, ..., m; j = 1, 2, ..., n là mn bien ngau nhiên cùng xác đ%nh trên không gian xác suat (Ω, F, P ) thì X = [Xij ]m×n đưoc goi là ma tr¾n ngau nhiên. 1.2.1. Hàm xác suat đong thài Neu X = (X1, X2, ..., Xn) là vectơ ngau nhiên ròi rac có mien giá tr% X(Ω) = {xi = (x1i, x2i, ..., xni) : i ≥ 1} thì hàm xác suat đong thòi cna X là hàm p : X(Ω) → R xác đ%nh bói p(xi) = P (X = xi). Neu X = (X1, X2, ..., Xn) gom n bien ngau nhiên liên tuc và neu ton tai hàm so không âm f (x) xác đ%nh trên Rn sao cho vói moi A = [a1; b1] × ...[an; bn] ⊂ Rn, P (X ⊂ A) = ¸ f (x)dx thì f (x) đưoc goi là hàm m¾t đ® xác suat đong thòi A cna X. 1.2.2. Vectơ trung bình và ma tr¾n hi¾p phương sai Cho vectơ ngau nhiên X = (X1, X2, ..., Xn). Giá sú E(Xi) = µi là kỳ vong cna Xi, V ar(Xi) = σii = E(Xi − µi)2 là phương sai cna Xi và Cov(Xi; Xj ) = σij = E(Xi − µi)(Xj − µj ) là hi¾p phương sai cna bien Xi và Xj . Khi đó µ = [µ1, µ2, ..., µn]T đưoc goi là vectơ trung bình và Σ = [σij ]n đưoc goi là ma tr¾n hi¾p phương sai. σij Goi ρij = là h¾ so tương quan cna Xi và Xj . Khi √ ii σj j σ đó ρ = [ρij ]n đưoc goi là ma tr¾n tương quan cna vectơ X. 1.2.3. Chia khoi ma tr¾n hi¾p phương sai 1.2.4. Vectơ trung bình và ma tr¾n hi¾p phương sai cúa to hap tuyen tính các vectơ ngau nhiên Neu X1 và X2 là hai bien ngau nhiên, a và b là các so thnc thì (i) E(aX1 + bX2) = aE(X1) + bE(X2) (ii) V ar(aX1 + bX2) = a2σ11 + b2σ22 + 2abσ12 (iii) Cov(aX1, bX2) = abσ12 Neu C T = [c1, c2, ..., cn] là vectơ các hang so và XT = [X1, X2, ..., Xn] là vectơ ngau nhiên thì E(C T X) = C T E(X) = C T µ, V ar(CT X) = C T cov(X)C = C T ΣC. Neu C = [cij ]m×n là ma tr¾n các hang so thì E(CX) = CE(X), cov(CX) = Ccov(X)CT 1.3. PHÂN BO CHUAN NHIEU CHIEU Đ%nh nghĩa 1.3.1. Vectơ ngau nhiên X = [X1, X2, ..., Xp]T đưoc goi là có phân bo chuan p chieu vói tham so µT = [µ1, µ2, ..., µp] và Σ = [σij ]p×p (Σ > 0) neu X có hàm m¾t đ® xác suat đong thòi 1 f (x) = ex (2π)p/2|Σ|1/2 p Kí hi¾u X ⊂ Np(µ; Σ). . . −1 (x − µ)T Σ−1(x − µ) . 2 1.4. VECTƠ TRUNG BÌNH MAU, MA TR¾N HIfiP PHƯƠNG SAI MAU Giá sú x 1, x 2,...,x n là mau đưoc chon ngau nhiên tù tong the X T = [X1, X2, ..., Xp]. Đ¾t 1 xj = (x1j + x2j + ... + xnj ), j = 1, 2, ..., p. n 1 . (xki − xi)(xkj − xj ) sij = n − 1 k=1 sij rij = √ ii sjj n s Vectơ xT = [x1, x2, ..., xp] đưoc goi là vectơ trung bình mau. Ma tr¾n S = [sij ]p đưoc goi là ma tr¾n hi¾p phương sai mau. Ma tr¾n R = [rij ]p đưoc goi là ma tr¾n h¾ so tương quan mau. 1.5. ƯéC LƯeNG KHÔNG CHfiCH Cho X = [Xij ]n×p là mau ngau nhiên cna T = [X1, X2, ..., Xp] X vói E(X) = µ và Cov(X) = Σ. Khi đó E(X) = µ; E(S) = Σ. H¾ quá 1.5.1. Cho X1, X2, ..., Xn là m®t mau ngau nhiên tù m®t phân bo đong thòi có vectơ trung bình µ và ma tr¾n hi¾p 1 Σ. n Và [n/(n − 1)]Sn là m®t ưóc lưong không ch¾ch cúa Σ phương sai Σ. Khi đó E(X) = E(X) = µ; Cov(X) = 1.6. PHÂN BO MAU TRUNG BÌNH MAU Đ%nh lý 1.6.1. Cho X = [Xij ]n×p là mau ngau nhiên cúa tong the X có phân bo chuan p chieu Np(µ; Σ). Khi đó X có phân Σ bo chuan Np(µ; ). n Đ%nh lý 1.6.2 (Đ%nh lí giói han trung tâm). Cho X = [Xij ]n×p là mau ngau nhiên cúa tong the X có E(X) = µ và cov(X) = Σ. Khi đó vói n đú lón, X có xap xs phân bo chuan Σ Np(µ; ). n 1.7. NH¾N DANG PHÂN BO CHUAN NHIEU CHIEU 1.7.1. SN dnng bieu đo xác suat chuan Tù bieu đo xác suat chuan cna các thành phan x 1, x 2,...,x p có the chap nh¾n X1, X2,...,Xp có phân bo chuan 1 chieu thì lúc đó ta có the chap nh¾n X có phân bo chuan. 1.7.2. Kiem đ%nh χ - bình phương 1.8. KIEM бNH GIÁ THIET VE VECTƠ TRUNG BÌNH CHƯƠNG 2 PHÂN TÍCH PHÂN BIfiT, PHÂN LOAI VÀ PHÂN TÍCH CUM 2.1. KHÁI NIfiM PHÂN TÍCH PHÂN BIfiT VÀ PHÂN LOAI Tien hành phân loai là m®t trong nhung nhi¾m vu cơ bán cna khoa hoc đe đưa the giói ve tr¾t tn. Và muc đích cna phân loai là xác đ%nh xem m®t đoi tưong quan sát đưoc se xep vào lóp nào. Khác vói vi¾c phân loai là phân tích phân bi¾t. Phân tích phân bi¾t là m®t ky thu¾t phân tích sú dung cho vi¾c phân bi¾t giua các lóp. 2.2. PHÂN LOAI HAI LéP Giá sú tong the đưoc phân hoach thành 2 lóp π1 và π2 và X T = (X1, ..., Xp) là vectơ đo p chieu xác đ%nh trên các đoi tưong cna tong the. Kí hi¾u Ω là mien giá tr% cna X. R1 và R2 lan lưot là mien giá tr% cna X giói han trên π1 và π2. Khi đó ta có Ω = R1 ∪R2 và R1 ∩ R2 = ⊂. Ta cũng giá sú rang f1(x) và f2(x) lan lưot là hàm m¾t đ® cna X trên π1 và π2 (neu X là vectơ ròi rac thì f1(x) và f2(x) là hàm xác suat). Xác suat phân loai sai m®t đoi tưong thu®c lóp π1 vào lóp π2 là ¸ f1(x)dx. (2.1) P (2/1) = P (X ⊂ R2/π1) R2 = Xác suat phân loai sai m®t đoi tưong thu®c lóp π2 vào lóp π1 là ¸ f2(x)dx. (2.2) P (1/2) = P (X ⊂ R1/π2) R1 = Kí hi¾u p1 là xác suat tien nghi¾m cna lóp π1. Tương tn, kí hi¾u p2 là xác suat tien nghi¾m cna lóp π2. Ta có p1 + p2 = 1. Kí hi¾u c(2/1) là ton that gây ra khi xep đoi tưong thu®c lóp π1 vào lóp π2, c(1/2) là ton that gây ra khi xep đoi tưong thu®c lóp π2 vào lóp π1. Ta có ma tr¾n ton that cho trong báng. π1 Thnc te π2 Xep vào lóp π1 π2 c(1/1) = 0 c(2/1) c(1/2) c(2/2) = 0 Khi đó ton that trung bình se là E(CM ) = c(2/1)P (2/1)p1 + c(1/2)P (1/2)p2. (2.3) Đ%nh lý 2.2.1. M®t đoi tưong đưoc xep vào lóp π1 hay π2 đe có ton that trung bình E(CM ) nhó nhat khi mien R1, R2 đưoc xác đ%nh như sau: . R1 = f1 ( x) c(1/2) 2 . ≥ p x⊂ Ω: . f (x) c(2/1) 1 2 p . R2 = f1 ( x) 2 c(1/2) p 2. 1 (2.4) x⊂Ω: f (x) . c(2/1) p < . Tong xác suat phân loai sai (TPM ) ¸ ¸ T P M = p1 f1(x)dx + p2 f2(x)dx R2 (2.5) R1 Ta có the xep m®t đoi tưong mói x0 vào m®t lóp bói xác suat h¾u nghi¾m lón nhat P (πi/x0). Theo quy tac Bayès p 1 f1 ( x 0 ) 1 P (π /x0 ) = p f (x ) + p f (x ) 1 1 và 0 2 2 (2.6) 0 p 2 f2 ( x 0 ) P (π /x ) = 1 P (π /x ) = − p f (x ) + p f (x ) 2 0 1 0 1 1 0 2 2 0 Dna vào tiêu chuan xác suat h¾u nghi¾m, ta xep x0 vào lóp π1 khi P (π1/x0) > P (π2/x0). 2.3. PHÂN LOAI HAI LéP CÓ PHÂN BO CHUAN Giá sú f1(x), f2(x) là hàm m¾t đ® cna phân bo chuan lan lưot liên ket vói lóp π1, π2 có vectơ trung bình µ1, µ2 và ma tr¾n hi¾p phương sai Σ1, Σ2. Ta xét các trưòng hop sau: 2.3.1. Σ1 = Σ2 = Σ Giá sú hàm m¾t đ® cna XT = [X1, X2, ..., Xp] trong π1 và π2 đưoc cho bói công thúc . . ex − 1(x − µi)T Σ−1(x − µi) , i = 1, 2 2 (2π)p/2|Σ|1/2 p (2.7) trong đó các tham so µ1, µ2 và Σ đã biet. fi(x) = 1 Đ%nh lý 2.3.1. Cho hai lóp π1 và π2 lan lưot có hàm m¾t đ® cho bói công thúc 2.7. Khi đó ta có phân bo sau: Xep x0 vào π1 neu (µ1 − µ2)T Σ−1x0 − 1 (µ1 − µ2)T Σ−1(µ1 + µ2) ≥ 2 ln . c(1/2) . p2 c(2/1) p1 (2.8) Ngưoc lai thì xep x0 vào π2. Giá sú ta có n1 đoi tưong cna bien ngau nhiên nhieu chieu XT = [X1, X2, .., Xp] tù lóp π1 và n2 đoi tưong cna XT tù lóp π2, vói n1 + n2 − 2 ≥ p. Khi đó các ma tr¾n du li¾u tương úng  T  x11 X 1 =  xT  , X 2 =    12  ...  xT 1 1n   xT 21  xT     22   ...  xT 2 2n Tù ma tr¾n du li¾u, vectơ trung bình mau và ma tr¾n hi¾p phương sai đưoc xác đ%nh như sau n 1 1 . x1 = x1j , S1 = 1 1 n −1 1 j=1 n n 1 2 . x2 = x2j , S2 = 2 1 n −1 2 j=1 n Khi đó . Sp = S (n1 n1 − 1 n1 . j= 1 T (x1j − x1)(x1j − x1) n2 . j= 1 . . + T (x2j − x2)(x2j − x2) n2 − 1 . − 1) + (n2 − 1) (n1 − 1) + − 1) 1 (n2 là m®t ưóc lưong không ch¾ch cna Σ. 2 Ưác lưang E(CM) nhó nhat . Ta xep x0 vào π1 neu c(1/2) p2 . 1 2 (x1 − x2)T S−1x0 p − p (x1 − x2)T S−1(x1 + x2) ≥ ln Ngưoc lai xep x0 vào π2 H¾ quá 2.3.2. Ket hop tuyen tính yˆ = c(2/1) p1 (2.9) aˆT x = (x¯1 − x¯2 )T S −1 x toi đa hóa tý so p (aˆT x¯1 − (y¯1 − y¯2 )2 2 sy = aˆT x¯2 )2 aˆT Sp aˆ = (aˆT d)2 (2.10) aˆT Sp aˆ trên tat cá các vectơ h¾ so aˆ vói d = (x¯1 − x¯2 ). Giá tr% lón nhat cúa tý so trên là D2 = (x¯1 − x¯2 )T S −1 (x¯1 − x¯2 ). p Chú ý rang . n1 + s2 y vói y1j = aˆ T j=1 (y1j − = x1j và y2j = aˆ T 2 y¯1 ) . n2 j=1 (y2j 2 − y¯2 ) n1 + n2 − 2 x2j . Lu¾t phân bo dNa vào hàm phân bi¾t Fisher Xep x0 vào lóp π1 neu yˆ0 = (x¯1 − x¯2 )T S −1 x0 = 1 (x¯1 − x¯2 )T S −1 (x¯1 + x¯2 ) p p ≥ mˆ 2 (2.11) 2.3.2. Σ1 ƒ= Σ2 Đ%nh lý 2.3.3. Cho lóp π1 và π2 đưoc mô tá bói hàm m¾t đ® cúa phân bo chuan lan lưot có vectơ trung bình µ1, µ2 và ma tr¾n hi¾p phương sai Σ1, Σ2. Khi đó + Xep x0 vào π1 neu 1 T −1 T −1 −1 − 2 ≥ ln . . c(1/2) p2 T −1 x0 (Σ1 − Σ2 )x0 + (µ1 Σ1 − µ2 Σ2 )x0 − k trong đó k = 1 ln . . c(2/1) p1 1 (µT Σ−1µ1 − µT Σ−1µ2) |Σ1| (2.12) + 2 | 2 Σ2| + Ngưoc lai thì xep x0 vào π2. 1 1 2 2 Quy tac phân loai b¾c hai Xep x0 vào π1 neu 1 T −1 T −1 −1 − ln 2 . T −1 x0 (S1 − S2 )x0 + (x1 S1 − x2 S2 )x0 − k ≥ c(1/2) p2 c(2/1) p1 (2.13) Ngưoc lai thì xep x0 vào π2. 2.4. ĐÁNH GIÁ HÀM PHÂN LOAI Giá tr% nhó nhat cna TPM đưoc goi là tý l¾ loi toi ưu (OER), thu đưoc bang cách khéo chon các R1 và R2. Như v¾y, OER là tý l¾ loi cho TPM toi thieu. Ve nguyên tac vi¾c thnc hi¾n hàm phân loai mau có the đưoc đánh giá bang cách tính toán tý l¾ loi thnc te (AER) AER = p1 ¸ ¸ R ˆ2 f1(x)dx + p2 R ˆ1 f2(x)dx . vói Rˆ 1 và Rˆ 2 là mien phân loai xác đ%nh bói mau có kích thưóc lan lưot là n1 và n2. Ta đ%nh nghĩa tý l¾ loi rõ ràng (APER) là tý l¾ các đoi tưong b% phân loai sai bói hàm phân loai mau. Cho lóp π1 có n1 đoi tưong và lóp π2 có n2 đoi tưong thì ma tr¾n nham lan có dang Thành viên thnc te π1 π2 Thành viên dn đoán π1 π2 n1C n1M = n1 − n2M = n2 − n1C n2C n1 n2 trong đó n1C : So các đoi tưong lóp π1 xep đúng vào lóp π1 n1M : So các đoi tưong lóp π1 xep sai vào lóp π2 n2C : So các đoi tưong lóp π2 xep đúng vào lóp π2 n2M : So các đoi tưong lóp π2 xep sai vào lóp π1 Khi đó ta có tý l¾ loi rõ ràng AP ER = n1M + n2M n1 + n2 2.5. PHÂN LOAI NHIEU LéP Ton that trung bình nhó nhat Cho fi(x) là hàm m¾t đ® liên ket vói lóp πi, i = 1, 2, .., g, pi là xác suat tien nghi¾m cna lóp πi và c(k/i) là ton that gây ra khi xep đoi tưong thu®c lóp πi vào lóp πk , đ¾c bi¾t vói k = i, c(i/i) = 0. Goi Rk là t¾p các đoi tưong thu®c lóp πk , khi đó ta có xác suat phân loai sai m®t đoi tưong thu®c lóp πi vào lóp πk là ¸ fi(x)dx. (2.14) P (k/i) = P (X ⊂ Rk /πi) = Rk