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 1MỞ ĐẦU 1. Tớnh cấp thiết của đề tài Ngày nay là thời đại của bựng nổ thụng tin, sự phỏt triển của cỏc ngành khoa học và đặc biệt là sự phỏt triển của ngành khoa học mỏy tớnh đó giỳp chỳng ta thu thập được lượng dữ liệu rất khổng lồ. Với một số lượng dữ liệu lớn như vậy thỡ việc tỡm hiểu thụng tin từ đú là rất khú khăn và phức tạp. Vỡ vậy vấn đề xử lý số liệu khụng những được cỏc ngành khoa học nghiờn cứu mà cũn được cả xó hội quan tõm. Đú cũng là lý do cho sự ra đời và phỏt triển của ngành phõn tớch thống kờ. Nhờ ứng dụng của bộ mụn phõn tớch thống kờ này mà cỏc ngành sinh học, y học, kinh tế, bảo hiểm, phõn loại ảnh. . . đó cú nhiều bước phỏt triển vượt bậc. Phương phỏp phõn tớch phõn biệt và phõn loại cựng với phương phỏp phõn tớch cụm là một trong những phương phỏp xử lý dữ liệu trong phõn tớch thống kờ được sử dụng phổ biến. Vỡ lý do đú, dưới sự hướng dẫn của thầy Lờ Văn Dũng, tụi chọn nghiờn cứu đề tài “Phõn tớch phõn biệt, phõn loại và phõn tớch cụm” làm luận văn thạc sĩ khoa học của mỡnh. 22. Mục đớch nghiờn cứu: Chỳng tụi mong muốn tỡm kiếm được nhiều tài liệu từ cỏc nguồn khỏc nhau, nghiờn cứu kĩ cỏc tài liệu đú, cố gắng lĩnh hội một số kỹ thuật phõn tớch thống kờ. Hy vọng luận văn cú thể được sử dụng như một tài liệu tham khảo bổ ớch cho sinh viờn cỏc trường Đại học, Cao đẳng. 3. Đối tượng nghiờn cứu - Kỹ thuật phõn tớch phõn biệt và phõn loại. - Kỹ thuật phõn tớch cụm. 4. Phạm vi nghiờn cứu: 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 cứu: Cơ bản sử dụng 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 đến đề tài của luận văn) để thu thập thụng tin nhằm hệ thống lại cỏc vấn đề lý thuyết. 6. Bố cục đề tài: Nội dung luận văn gồm hai chương: Chương 1: Kiến thức chuẩn bị. Trỡnh bày lại cỏc kiến thức cần thiết cho chương 2, đú là cỏc kiến thức về vectơ, ma trận, biến ngẫu nhiờn và phõn bố chuẩn nhiều chiều. Chương 2: Phõn tớch phõn biệt, phõn loại và phõn tớch cụm. Trong chương này cú hai nhiệm vụ chớnh: thứ nhất là giải quyết bài toỏn phõn biệt, phõn loại; thứ hai là giải quyết bài toỏn phõn cụm. 3CHƯƠNG1 KIẾN THỨC CHUẨN 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 bất đẳng thức ma trận và maximum 1.2.VECTƠ NGẪU NHIấN Định nghĩa 1.2.1. Cho X1, X2, ..., Xn là cỏc biến ngẫu nhiờn cựng xỏc định trờn khụng gian xỏc suất (Ω,F , P ). Kớ hiệu X = (X1, X2, ..., Xn) được gọi là vectơ ngẫu nhiờn n chiều. Dạng ma trận của X như sau X = X1X2... Xn  hoặc XT = [X1, X2, ..., Xn] Định nghĩa 1.2.2. ChoXij với i = 1, 2, ...,m; j = 1, 2, ..., n là mn biến ngẫu nhiờn cựng xỏc định trờn khụng gian xỏc suất (Ω,F , P ) thỡ X = [Xij ]mìn được gọi là ma trận ngẫu nhiờn. 1.2.1.Hàm xỏc suất đồng thời Nếu X = (X1, X2, ..., Xn) là vectơ ngẫu nhiờn rời rạc cú miền giỏ trị X(Ω) = {xi = (x1i, x2i, ..., xni) : i ≥ 1} thỡ hàm 4xỏc suất đồng thời của X là hàm p : X(Ω) → R xỏc định bởi p(xi) = P (X = xi). Nếu X = (X1, X2, ..., Xn) gồm n biến ngẫu nhiờn liờn tục và nếu tồn tại hàm số khụng õm f(x) xỏc định trờn Rn sao cho với mọi A = [a1; b1]ì ...[an; bn] ⊂ Rn, P (X ∈ A) = ∫ A f(x)dx thỡ f(x) được gọi là hàm mật độ xỏc suất đồng thời của X. 1.2.2.Vectơ trung bỡnh và ma trận hiệp phương sai Cho vectơ ngẫu nhiờnX = (X1, X2, ..., Xn). Giả sửE(Xi) = ài là kỳ vọng của Xi, V ar(Xi) = σii = E(Xi − ài)2 là phương sai của Xi và Cov(Xi;Xj) = σij = E(Xi − ài)(Xj − àj) là hiệp phương sai của biến Xi và Xj . Khi đú à = [à1, à2, ..., àn] T được gọi là vectơ trung bỡnh và Σ = [σij ]n được gọi là ma trận hiệp phương sai. Gọi ρij = σij√ σiiσjj là hệ số tương quan của Xi và Xj . Khi đú ρ = [ρij ]n được gọi là ma trận tương quan của vectơ X. 1.2.3. Chia khối 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 tổ hợp tuyến tớnh cỏc vectơ ngẫu nhiờn Nếu X1 và X2 là hai biến ngẫu nhiờn, a và b là cỏc số thực thỡ (i) E(aX1 + bX2) = aE(X1) + bE(X2) (ii) V ar(aX1 + bX2) = a 2σ11 + b 2σ22 + 2abσ12 5(iii) Cov(aX1, bX2) = abσ12 Nếu CT = [c1, c2, ..., cn] là vectơ cỏc hằng số và X T = [X1, X2, ..., Xn] là vectơ ngẫu nhiờn thỡ E(C TX) = CTE(X) = CTà, V ar(CT X) = CT cov(X)C = CTΣC. Nếu C = [cij ]mìn là ma trận cỏc hằng số thỡ E(CX) = CE(X), cov(CX) = Ccov(X)CT 1.3. PHÂN BỐ CHUẨN NHIỀU CHIỀU Định nghĩa 1.3.1. Vectơ ngẫu nhiờnX = [X1, X2, ..., Xp] T được gọi là cú phõn bố chuẩn p chiều với tham số àT = [à1, à2, ..., àp] và Σ = [σij ]pìp (Σ > 0) nếu X cú hàm mật độ xỏc suất đồng thời f(x) = 1 (2pi)p/2|Σ|1/2 exp { −1 2 (x− à)TΣ−1(x− à) } . Kớ hiệu X ∼ Np(à; Σ). 1.4.VECTƠ TRUNG BèNH MẪU, MA TRẬN HIỆP PHƯƠNG SAI MẪU Giả sử x1, x2,...,xn là mẫu được chọn ngẫu nhiờn từ tổng thể XT = [X1, X2, ..., Xp]. Đặt xj = 1 n (x1j + x2j + ...+ xnj), j = 1, 2, ..., p. sij = 1 n− 1 n∑ k=1 (xki − xi)(xkj − xj) rij = sij√ siisjj 6Vectơ xT = [x1, x2, ..., xp] được gọi là vectơ trung bỡnh mẫu. Ma trận S = [sij ]p được gọi là ma trận hiệp phương sai mẫu. Ma trận R = [rij ]p được gọi là ma trận hệ số tương quan mẫu. 1.5.ƯỚC LƯỢNG KHễNG CHỆCH ChoX = [Xij ]nìp là mẫu ngẫu nhiờn củaXT = [X1, X2, ..., Xp] với E(X) = à và Cov(X) = Σ. Khi đú E(X) = à; E(S) = Σ. Hệ quả 1.5.1. Cho X1, X2, ..., Xn là một mẫu ngẫu nhiờn từ một phõn bố đồng thời cú vectơ trung bỡnh à và ma trận hiệp phương sai Σ. Khi đú E(X) = E(X) = à; Cov(X) = 1 n Σ. Và [n/(n− 1)]Sn là một ước lượng khụng chệch của Σ 1.6. PHÂN BỐ MẪU TRUNG BèNH MẪU Định lý 1.6.1. Cho X = [Xij ]nìp là mẫu ngẫu nhiờn của tổng thể X cú phõn bố chuẩn p chiều Np(à; Σ). Khi đú X cú phõn bố chuẩn Np(à; Σ n ). Định lý 1.6.2 (Định lớ giới hạn trung tõm). Cho X = [Xij ]nìp là mẫu ngẫu nhiờn của tổng thể X cú E(X) = à và cov(X) = Σ. Khi đú với n đủ lớn, X cú xấp xỉ phõn bố chuẩn Np(à; Σ n ). 1.7.NHẬN DẠNG PHÂN BỐ CHUẨN NHIỀU CHIỀU 1.7.1. Sử dụng biểu đồ xỏc suất chuẩn Từ biểu đồ xỏc suất chuẩn của cỏc thành phần x1, x2,...,xp cú thể chấp nhận X1, X2,...,Xp cú phõn bố chuẩn 1 chiều thỡ lỳc 7đú ta cú thể chấp nhận X cú phõn bố chuẩn. 1.7.2.Kiểm định χ - bỡnh phương 1.8.KIỂMĐỊNHGIẢ THIẾT VỀ VECTƠ TRUNGBèNH 8CHƯƠNG2 PHÂN TÍCH PHÂN BIỆT, PHÂN LOẠI VÀ PHÂN TÍCH CỤM 2.1.KHÁI NIỆM PHÂN TÍCH PHÂN BIỆT VÀ PHÂN LOẠI Tiến hành phõn loại là một trong những nhiệm vụ cơ bản của khoa học để đưa thế giới về trật tự. Và mục đớch của phõn loại là xỏc định xem một đối tượng quan sỏt được sẽ xếp vào lớp nào. Khỏc với việc phõn loại là phõn tớch phõn biệt. Phõn tớch phõn biệt là một kỹ thuật phõn tớch sử dụng cho việc phõn biệt giữa cỏc lớp. 2.2. PHÂN LOẠI HAI LỚP Giả sử tổng thể được phõn hoạch thành 2 lớp pi1 và pi2 và XT = (X1, ..., Xp) là vectơ đo p chiều xỏc định trờn cỏc đối tượng của tổng thể. Kớ hiệu Ω là miền giỏ trị của X. R1 và R2 lần lượt là miền giỏ trị củaX giới hạn trờn pi1 và pi2. Khi đú ta cú Ω = R1∪R2 và R1 ∩ R2 = ∅. Ta cũng giả sử rằng f1(x) và f2(x) lần lượt là hàm mật độ của X trờn pi1 và pi2 (nếu X là vectơ rời rạc thỡ f1(x) 9và f2(x) là hàm xỏc suất). Xỏc suất phõn loại sai một đối tượng thuộc lớp pi1 vào lớp pi2 là P (2/1) = P (X ∈ R2/pi1) = ∫ R2 f1(x)dx. (2.1) Xỏc suất phõn loại sai một đối tượng thuộc lớp pi2 vào lớp pi1 là P (1/2) = P (X ∈ R1/pi2) = ∫ R1 f2(x)dx. (2.2) Kớ hiệu p1 là xỏc suất tiền nghiệm của lớp pi1. Tương tự, kớ hiệu p2 là xỏc suất tiền nghiệm của lớp pi2. Ta cú p1 + p2 = 1. Kớ hiệu c(2/1) là tổn thất gõy ra khi xếp đối tượng thuộc lớp pi1 vào lớp pi2, c(1/2) là tổn thất gõy ra khi xếp đối tượng thuộc lớp pi2 vào lớp pi1. Ta cú ma trận tổn thất cho trong bảng. Xếp vào lớp pi1 pi2 pi1 c(1/1) = 0 c(2/1) Thực tế pi2 c(1/2) c(2/2) = 0 Khi đú tổn thất trung bỡnh sẽ 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 đối tượng được xếp vào lớp pi1 hay pi2 để cú tổn thất trung bỡnh E(CM) nhỏ nhất khi miền R1, R2 được xỏc định như sau: R1 = { x ∈ Ω : f1(x) f2(x) ≥ c(1/2) c(2/1) . p2 p1 } R2 = { x ∈ Ω : f1(x) f2(x) < c(1/2) c(2/1) . p2 p1 } . (2.4) 10 Tổng xỏc suất phõn loại sai (TPM ) TPM = p1 ∫ R2 f1(x)dx+ p2 ∫ R1 f2(x)dx (2.5) Ta cú thể xếp một đối tượng mới x0 vào một lớp bởi xỏc suất hậu nghiệm lớn nhất P (pii/x0). Theo quy tắc Bayốs P (pi1/x0) = p1f1(x0) p1f1(x0) + p2f2(x0) (2.6) và P (pi2/x0) = 1− P (pi1/x0) = p2f2(x0) p1f1(x0) + p2f2(x0) Dựa vào tiờu chuẩn xỏc suất hậu nghiệm, ta xếp x0 vào lớp pi1 khi P (pi1/x0) > P (pi2/x0). 2.3. PHÂN LOẠI HAI LỚP Cể PHÂN BỐ CHUẨN Giả sử f1(x), f2(x) là hàm mật độ của phõn bố chuẩn lần lượt liờn kết với lớp pi1, pi2 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 hợp sau: 2.3.1.Σ1 = Σ2 = Σ Giả sử hàm mật độ của XT = [X1, X2, ..., Xp] trong pi1 và pi2 được cho bởi cụng thức fi(x) = 1 (2pi)p/2|Σ|1/2 exp [ −1 2 (x− ài)TΣ−1(x− ài) ] , i = 1, 2 (2.7) trong đú cỏc tham số à1, à2 và Σ đó biết. Định lý 2.3.1. Cho hai lớp pi1 và pi2 lần lượt cú hàm mật độ cho bởi cụng thức 2.7. Khi đú ta cú phõn bổ sau: 11 Xếp x0 vào pi1 nếu (à1 − à2)TΣ−1x0 − 1 2 (à1 − à2)TΣ−1(à1 + à2) ≥ ln [ c(1/2) c(2/1) p2 p1 ] (2.8) Ngược lại thỡ xếp x0 vào pi2. Giả sử ta cú n1 đối tượng của biến ngẫu nhiờn nhiều chiều XT = [X1, X2, .., Xp] từ lớp pi1 và n2 đối tượng của X T từ lớp pi2, với n1 + n2 − 2 ≥ p. Khi đú cỏc ma trận dữ liệu tương ứng X1 =  xT11 xT12 ... xT1n1  ,X2 =  xT21 xT22 ... xT2n2  Từ ma trận dữ liệu, vectơ trung bỡnh mẫu và ma trận hiệp phương sai được xỏc định như sau x1 = 1 n1 n1∑ j=1 x1j , S1 = 1 n1 − 1 n1∑ j=1 (x1j − x1)(x1j − x1)T x2 = 1 n2 n2∑ j=1 x2j , S2 = 1 n2 − 1 n2∑ j=1 (x2j − x2)(x2j − x2)T Khi đú Sp = [ n1 − 1 (n1 − 1) + (n2 − 1) ] S1 + [ n2 − 1 (n1 − 1) + (n2 − 1) ] S2 là một ước lượng khụng chệch của Σ. 12 Ước lượng E(CM) nhỏ nhất Ta xếp x0 vào pi1 nếu (x1 − x2)TS−1p x0 − 1 2 (x1 − x2)TS−1p (x1 + x2) ≥ ln [ c(1/2) c(2/1) p2 p1 ] (2.9) Ngược lại xếp x0 vào pi2 Hệ quả 2.3.2. Kết hợp tuyến tớnh yˆ = aˆTx = (x¯1 − x¯2) TS−1p x tối đa húa tỷ số (y¯1 − y¯2)2 s2y = (aˆT x¯1 − aˆT x¯2)2 aˆTSpaˆ = (aˆTd)2 aˆTSpaˆ (2.10) trờn tất cả cỏc vectơ hệ số aˆ với d = (x¯1 − x¯2). Giỏ trị lớn nhất của tỷ số trờn là D2 = (x¯1 − x¯2)TS−1p (x¯1 − x¯2). Chỳ ý rằng s2y = ∑n1 j=1(y1j − y¯1)2 + ∑n2 j=1(y2j − y¯2)2 n1 + n2 − 2 với y1j = aˆ Tx1j và y2j = aˆ Tx2j . Luật phõn bố dựa vào hàm phõn biệt Fisher Xếp x0 vào lớp pi1 nếu yˆ0 = (x¯1 − x¯2)TS−1p x0 ≥ mˆ = 1 2 (x¯1 − x¯2)TS−1p (x¯1 + x¯2) (2.11) 2.3.2.Σ1 6= Σ2 Định lý 2.3.3. Cho lớp pi1 và pi2 được mụ tả bởi hàm mật độ của phõn bố chuẩn lần lượt cú vectơ trung bỡnh à1, à2 và ma trận hiệp phương sai Σ1, Σ2. Khi đú 13 + Xếp x0 vào pi1 nếu −1 2 xT0 (Σ −1 1 − Σ−12 )x0 + (àT1 Σ−11 − àT2 Σ−12 )x0 − k ≥ ln [ c(1/2) c(2/1) p2 p1 ] (2.12) trong đú k = 1 2 ln ( |Σ1| |Σ2| ) + 1 2 (àT1 Σ −1 1 à1 − àT2 Σ−12 à2) + Ngược lại thỡ xếp x0 vào pi2. Quy tắc phõn loại bậc hai Xếp x0 vào pi1 nếu −1 2 xT0 (S −1 1 − S−12 )x0 + (xT1 S−11 − xT2 S−12 )x0 − k ≥ ln [ c(1/2) c(2/1) p2 p1 ] (2.13) Ngược lại thỡ xếp x0 vào pi2. 2.4.ĐÁNH GIÁ HÀM PHÂN LOẠI Giỏ trị nhỏ nhất của TPM được gọi là tỷ lệ lỗi tối ưu (OER), thu được bằng cỏch khộo chọn cỏc R1 và R2. Như vậy, OER là tỷ lệ lỗi cho TPM tối thiểu. Về nguyờn tắc việc thực hiện hàm phõn loại mẫu cú thể được đỏnh giỏ bằng cỏch tớnh toỏn tỷ lệ lỗi thực tế (AER) AER = p1 ∫ Rˆ2 f1(x)dx+ p2 ∫ Rˆ1 f2(x)dx với Rˆ1 và Rˆ2 là miền phõn loại xỏc định bởi mẫu cú kớch thước lần lượt là n1 và n2. Ta định nghĩa tỷ lệ lỗi rừ ràng (APER) là tỷ lệ cỏc đối tượng bị phõn loại sai bởi hàm phõn loại mẫu. Cho lớp pi1 cú n1 đối tượng và lớp pi2 cú n2 đối tượng thỡ ma trận nhầm lẫn cú dạng 14 Thành viờn dự đoỏn pi1 pi2 Thành viờn pi1 n1C n1M = n1 − n1C n1 thực tế pi2 n2M = n2 − n2C n2C n2 trong đú n1C : Số cỏc đối tượng lớp pi1 xếp đỳng vào lớp pi1 n1M : Số cỏc đối tượng lớp pi1 xếp sai vào lớp pi2 n2C : Số cỏc đối tượng lớp pi2 xếp đỳng vào lớp pi2 n2M : Số cỏc đối tượng lớp pi2 xếp sai vào lớp pi1 Khi đú ta cú tỷ lệ lỗi rừ ràng APER = n1M + n2M n1 + n2 2.5. PHÂN LOẠI NHIỀU LỚP Tổn thất trung bỡnh nhỏ nhất Cho fi(x) là hàm mật độ liờn kết với lớp pii, i = 1, 2, .., g, pi là xỏc suất tiền nghiệm của lớp pii và c(k/i) là tổn thất gõy ra khi xếp đối tượng thuộc lớp pii vào lớp pik, đặc biệt với k = i, c(i/i) = 0. Gọi Rk là tập cỏc đối tượng thuộc lớp pik, khi đú ta cú xỏc suất phõn loại sai một đối tượng thuộc lớp pii vào lớp pik là P (k/i) = P (X ∈ Rk/pii) = ∫ Rk fi(x)dx. (2.14) 15 với i = 1, 2, ..., g và P (i/i) = 1−∑gk=1,k 6=i P (k/i). Từ đú ta cú tổn thất trung bỡnh E(CM) = p1E(CM)(1) + p2E(CM)(2) + ...+ pgE(CM)(g) = p1 ( g∑ k=2 P (k/1)c(k/1) ) + p2  g∑ k=1,k 6=2 P (k/2)c(k/2)  + ...+ pg ( g−1∑ k=1 P (k/g)c(k/g) ) = g∑ i=1 pi  g∑ k=1,k 6=i P (k/i)c(k/i)  Luật phõn loại để E(CM) nhỏ nhất với tổn thất phõn loại sai bằng nhau Xếp x0 vào pik nếu pkfk(x) > pifi(x), với mọi i 6= k (2.15) Xếp x0 vào pik nếu ln pkfk(x) > ln pifi(x), với mọi i 6= k (2.16) Phõn loại cỏc lớp cú phõn bố chuẩn Xếp x vào pik nếu ln pkfk(x) = ln pk − p 2 ln 2pi − 1 2 ln |Σk| − 1 2 (x− àk)TΣ−1k (x− àk) = max ln pifi(x) Ta định nghĩa tỉ số phõn biệt bậc hai cho lớp thứ i như sau dQi (x) = − 1 2 ln |Σi| − 1 2 (x− ài)TΣ−1i (x− ài) + ln pi, i = 1, 2, .., g (2.17) 16 TPM nhỏ nhất khi cỏc Σi khụng bằng nhau Xếp x vào lớp pik nếu dQk (x) = max(d Q 1 (x), d Q 2 (x), ..., d Q g (x)) (2.18) với dQk (x) được cho bởi cụng thức 2.17. Ước lượng tỉ số phõn biệt bậc hai dˆQi (x) = − 1 2 ln |Si| − 1 2 (x− x¯i)TS−1i (x− x¯i) + ln pi, i = 1, 2, .., g (2.19) Ước lượng TPM trong trường hợp Σi khụng bằng nhau Xếp x vào lớp pik nếu dˆQk (x) = max(dˆ Q 1 (x), dˆ Q 2 (x), ..., dˆ Q g (x)) (2.20) với dˆQi (x) được xỏc định bởi cụng thức 2.19. Một trường hợp đơn giản là ma trận hiệp phương sai của lớp Σi là bằng nhau. Đặt Σi = Σ, i = 1, 2, ..., g, ta định nghĩa tỉ số phõn biệt tuyến tớnh như sau di(x) = à T i Σ −1x− 1 2 àTi Σ −1ài + ln pi, i = 1, 2, ..., g Ước lượng dˆi(x) của tỉ số phõn biệt tuyến tớnh di(x) dựa trờn ước lượng gộp của Σ. Sp = 1 n1 + n2 + ...+ ng − g [(n1−1)S1+(n2−1)S2+...+(ng−1)Sg] và được cho bởi dˆi(x) = x¯ T i S −1 p x− 1 2 x¯Ti S −1 p x¯+ ln pi, i = 1, 2, .., g (2.21) 17 Ước lượng TPM trong trường hợp Σi bằng nhau Xếp x vào lớp pik nếu dˆk(x) = max(dˆ1(x), dˆ2(x), ..., dˆg(x)) với dˆi(x) được cho bởi cụng thức 2.21. Xếp x vào lớp pik nếu dˆki(x) = (x¯k − x¯i)TS−1p x− 1 2 (x¯k − x¯i)TS−1p (x¯k + x¯i) ≥ ln ( pi pk ) ,∀i 6= k 2.6.ỨNG DỤNG CỦA PHÂN TÍCH PHÂN BIỆT VÀ PHÂN LOẠI Vớ dụ 2.6.1. Bộ phận tuyển sinh đào tạo thạc sĩ quản trị kinh doanh ở một trường đại học đó cú kết quả tuyển sinh đào tạo và họ muốn dựa vào điểm GPA (Grade Point Average) và điểm GMAT (Graduate Management Admission Test) trong kết quả tuyển sinh để tiến hành sơ tuyển phục vụ cụng tỏc tuyển sinh những năm tiếp theo. Dựa vào kết quả tuyển sinh năm vừa qua, bộ phận tuyển sinh đó phõn thành 3 nhúm như sau: pi1 (được nhận hồ sơ), pi2 (khụng được nhận hồ sơ) và pi3 (là biờn của hai nhúm pi1 và pi2 ). Bộ phận tuyển sinh sẽ chỉ nhận hồ sơ của cỏc thớ sinh thuộc nhúm pi1 và pi3 để tham dự kỡ thi ở vũng 2. Giả sử năm tuyển sinh tiếp theo, một thớ sinh cú GPA = 3,21 và GMAT = 497. Khi đú, bộ phận tuyển sinh sẽ phõn loại thớ sinh này vào nhúm nào? 18 Vớ dụ 2.6.2. Trường THPT chuyờn ở tỉnh A muốn dựa vào điểm tổng kết Toỏn và điểm trung bỡnh chung của năm học lớp 9 để tiến hành sơ tuyển. Dựa vào kết quả tuyển sinh của 1 năm nào đú trường sẽ tiến hành phõn thớ sinh vào 3 nhúm: nhúm 1 (được nhận hồ sơ), nhúm 2 (khụng được nhận hồ sơ) và nhúm 3 là nhúm trung gian giữa 2 nhúm trờn. Ở kỡ tuyển sinh tiếp theo nhà trường sẽ dựa vào điểm tổng kết Toỏn và điểm trung bỡnh chung của năm học lớp 9 để tiến hành phõn loại để chỉ nhận những thớ sinh thuộc nhúm 1 và nhúm 3 vào thi tuyển ở vũng 2. 2.7.KHÁI NIỆM PHÂN TÍCH CỤM Phõn tớch cụm là cỏc quy trỡnh tỡm cỏch nhúm cỏc đối tượng đó cho vào cỏc cụm, sao cho cỏc đối tượng trong cựng một cụm tương tự nhau (gần nhau) và cỏc đối tượng khỏc cụm thỡ khụng tương tự nhau (khụng gần nhau) xột theo cỏc đặc tớnh lựa chọn để nghiờn cứu. 2.8. CÁC KHOẢNG CÁCH THƯỜNG DÙNG 2.9. PHƯƠNG PHÁP PHÂN CỤM THEO THỨ BẬC Luận văn sẽ tập trung nghiờn cứu phương phỏp gộp theo thứ bậc và cụ thể là phương phỏp kết nối. Cỏch thực hiện: 1. Chia thành n cụm đơn C1, C2,..., Cn; mỗi cụm chỉ chứa một phần tử. Lập một ma trận khoảng cỏch giữa cỏc cụm này. 2. Tỡm cặp cụm cú khoảng cỏch ngắn nhất, chẳng hạn cụm 19 Ci và cụm Cj , nhập hai cụm này thành một cụm mới (Ci, Cj) đồng thời xúa bỏ cụm Ci và Cj . 3. Lặp lại hai bước trờn cho đến khi cũn lại một cụm thỡ dừng lại. 2.9.1. Phương phỏp phõn cụm theo thứ bậc kết nối đơn Cụng thức tớnh khoảng cỏch giữa hai cụm theo phương phỏp phõn cụm theo thứ bậc kết nối đơn: dA,B = min{dij}, (2.22) trong đú dij là khoảng cỏch giữa hai đối tượng i ∈ A và j ∈ B. Vớ dụ 2.9.1. Cho ma trận khoảng cỏch của 5 phần tử 1 2 3 4 5 D = [dik] = 1 2 3 4 5  0 9 0 3 7 0 6 5 9 0 11 10 2 8 0  Bước 1. Từ ma trận khoảng cỏch ta cú khoảng cỏch giữa hai phần tử 3 và 5 là nhỏ nhất nờn ghộp 3 và 5 thành một cụm (3, 5) Tớnh khoảng cỏch từ cỏc phần tử cũn lại đến cụm (3, 5). Như vậy ma trận khoảng cỏch giữa cỏc cụm (3, 5), (1), (2), (4) là (3, 5) 1 2 4 D = [dik] = (3, 5) 1 2 4  03 07 9 0 8 6 5 0  Bước 2. Khoảng cỏch giữa cụm (3, 5) và (1) là ngắn nhất 20 nờn ghộp hai cụm này thành một cụm là (1, 3, 5). Ma trận khoảng cỏch giữa cỏc cụm (1, 3, 5), (2), (4) là (1, 3, 5) 2 4 D = [dik] = (1, 3, 5) 2 4 [ 0 7 0 6 5 0 ] Bước 3. Khoảng cỏch giữa cụm (2) và (4) là ngắn nhất nờn ghộp hai cụm này thành một cụm là (2, 4). Ma trận khoảng cỏch giữa cỏc cụm (1, 3, 5), (2, 4) là (1, 3, 5) (2, 4) D = [dik] = (1, 3, 5) (2, 4) [ 0 6 0 ] Bước 4. Ghộp hai cụm (1, 3, 5) và (2, 4) thành một cụm duy nhất (1, 2, 3, 4, 5). 2.9.2. Phương phỏp phõn cụm theo thứ bậc kết nối đầy đủ Cụng thức tớnh khoảng cỏch giữa hai cụm theo phương phỏp phõn cụm theo thứ bậc kết nối đầy đủ: dA,B = max{dij}, (2.23) trong đú dij là khoảng cỏch giữa hai đối tượng i ∈ A và j ∈ B. 2.9.3. Phương phỏp phõn cụm theo thứ bậc kết nối trung bỡnh Cụng thức tớnh khoảng cỏch giữa hai cụm theo phương phỏp phõn cụm theo thứ bậc kết nối trung bỡnh: dA,B = 1 nA.nB ∑ i∈A ∑ j∈B dij , (2.24) 21 trong đú dij là khoảng cỏch giữa hai đối tượng i ∈ A và j ∈ B, nA và nB lần lượt là số đối tượng cú trong cụm A và B . 2.10. PHƯƠNG PHÁP PHÂN CỤM K - TRUNG BèNH Cỏch thực hiện 1. Phõn chia cỏc đối tượng thành K cụm ban đầu. 2. Tớnh toỏn khoảng cỏch giữa cỏc đối tượng đến tõm cỏc cụm (khoảng cỏch Euclide). 3. Từ toàn bộ đối tượng, phõn phối lại cỏc đối tượng vào cụm cú khoảng cỏch từ tõm của cụm đến đối tượng đú nhỏ nhất. 4. Tớnh toỏn lại cỏc trung tõm của cỏc cụm mới. 5. Lặp lại bước 2 cho đến khi khụng cũn sự phõn phối lại. Vớ dụ 2.10.1. Cho bảng số liệu hai chiều sau: Đối tượng Giỏ trị quan sỏt x1 x2 A 5 3 B -1 1 C 1 -2 D -3 -2 Phõn chia cỏc đối tượng thành K = 2 cụm sao cho khoảng cỏch từ đối tượng đến tõm của cụm chứa nú là nhỏ nhất. Bước 1. Giả sử ta chọn A là tõm của nhúm thứ nhất c1(5, 3) và B là tõm nhúm thứ hai c2(−1, 1). Bước 2. Tớnh khoảng cỏch giữa cỏc đối tượng đến tõm cỏc 22 cụm. Ta được ma trận khoảng cỏch D0 = [ 0 6, 32 6, 4 9, 43 6, 32 0 3, 61 3, 61 ] Bước 3. Nhúm cỏc đối tượng vào cụm gần nhất G0 = [ 1 0 0 0 0 1 1 1 ] Ta thấy rằng sau vũng lặp thứ nhất, cụm 1 gồm một đối tượng A và cụm 2 gồm cỏc đối tương B, C, D. Bước 4. Cụm 1 chỉ cú một đối tượng A nờn tõm cụm khụng đổi. Tõm cụm 2 được tớnh như sau: c2 = (−1 + 1− 3 3 ; 1− 2− 2 3 ) = (−1, 5;−1, 5). Bước 5. Tớnh lại khoảng cỏch từ đối tượng đến tõm mới. Ta cũng được ma trận khoảng cỏch như sau D1 = [ 0 6, 32 6, 4 9, 43 6, 67 2, 55 2, 55 1, 58 ] Bước 6. Phõn phối cỏc đối tượng vào cụm G1 = [ 1 0 0 0 0 1 1 1 ] Ta thấy G0 = G1 nờn thuật toỏn dừng và kết quả phõn cụm như sau Đối tượng Giỏ trị quan sỏt Cụm x1 x2 A 5 3 1 B -1 1 2 C 1 -2 2 D -3 -2 2 Cuối cựng hai cụm cần tỡm là (A) và (B,C,D). 23 2.11.ỨNG DỤNG CỦA PHÂN TÍCH CỤM Vớ dụ 2.11.1. Trong xếp loại học lực, học sinh được xếp thành 5 loại Giỏi (GIOI), Khỏ (KHA), Trung bỡnh (TB), Yếu (YEU), Kộm (KEM). Trong vớ dụ này chỳng tụi sử dụng thờm phương phỏp phõn tớch cụm để cú thờm một gúc nhỡn khỏc trong đỏnh giỏ, xếp loại học sinh. Vớ dụ 2.11.2. Trường THPT A muốn dựa vào kết quả học tập lớp 9 của cỏc thớ sinh trỳng tuyển vào lớp 10 để phõn vào 8 lớp học sao cho cỏc học sinh trong 1 lớp cú kết quả học tập tương đối đồng đều nhất. Khi đú cú thể sử dụng phương phỏp K - trung bỡnh phõn tớch thành 8 cụm. 24 KẾT LUẬN Sau một khoảng thời gian thu thập tài liệu, nghiờn cứu và tổng hợp, luận văn “Phõn tớch phõn biệt, phõn loại và phõn tớch cụm” đó hoàn thành, luận văn giải quyết được hai bài toỏn sau: 1. Bài toỏn phõn biệt và phõn loại : Phương phỏp đưa ra để giải quyết bài toỏn này là dựa vào xỏc suất tiền nghiệm và hàm mật độ xỏc suất để đưa ra hàm phõn biệt, từ đú tớnh được xỏc suất sai lầm trong phõn loại. 2. Bài toỏn phõn cụm: Để giải quyết bài toỏn phõn cụm, luận văn đó đưa ra hai phương phỏp - Phương phỏp phõn cụm theo thứ bậc kết nối - Phương phỏp phõn cụm K-trung bỡnh. Mặc dự đó cố gắng nhưng do trỡnh độ cú hạn nờn luận văn khụng trỏnh khỏi sai sút, kớnh mong sự đúng gúp ý kiến của quý thầy cụ và cỏc bạn để luận văn được hoàn thiện hơn.