Bài giảng Lý thuyết nhận dạng

TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI VIỆN TOÁN ỨNG DỤNG VÀ TIN HỌC - - - - - - - - - - - - - - - - - - - - - - - - -

BÀI GIẢNG

LÝ THUYẾT NHẬN DẠNG

( TÀI LIỆU LƯU HÀNH NỘI BỘ )

Đếu có nhà xuất bản :v

Bài Giảng

Lý thuyết nhận dạng

Mục lục

1 Cơ sở lý luận của lý thuyết nhận dạng

6 6

1.1.1

7 8

9 9

11 12 12 12

13 13

14 14

1.1 Khái niệm cơ bản về nhận dạng . . . . . . . . . . . . . . Sự ra đời của khoa học nhận dạng và hai định hướng trong khoa học nhận dạng(KHND) . . . . 1.1.2 Một số ví dụ về nhận dạng dẫn đến định nghĩa tổng quát về dạng . . . . . . . . . . . . . . . . . . 1.1.3 Định nghĩa tổng quát về dạng . . . . . . . . . . . 1.2 Một số bài toán cơ bản làm cơ sở cho việc xây dựng hệ nhận dạng . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2.1 Bài toán mã hóa dạng . . . . . . . . . . . . . . . 1.2.2 Bài toán về việc xử lý sơ bộ và lựa chọn các dấu hiệu . . . . . . . . . . . . . . . . . . . . . . . . . 1.2.3 Bài toán xây dựng hệ nhận dạng . . . . . . . . . 1.2.4 Bài toán đánh giá tham số . . . . . . . . . . . . . 1.2.5 Bài toán mô phỏng dạng . . . . . . . . . . . . . . 1.3 Một số nguyên tắc và phương pháp luận làm cơ sở để xây dựng hệ nhận dạng . . . . . . . . . . . . . . . . . . . . . 1.3.1 Mội số nguyên tắc cơ bản . . . . . . . . . . . . . 1.3.2 Một số phương pháp luận làm cơ sở cho việc xây dựng hệ nhận dạng tự động . . . . . . . . . . . . 1.4 Về một số phương pháp toán học xây dựng tiêu chuẩn nhận dạng cho hệ nhận dạng tự động . . . . . . . . . . . 1.4.1 Một số khái niệm cơ bản . . . . . . . . . . . . . . 1.4.2 Xây dựng tiêu chuẩn nhận dạng cho hệ nhận dạng tự động . . . . . . . . . . . . . . . . . . . . . . . 15

2 Các hàm quyết định phân lớp dạng

18 18 21

2.1 Hàm quyết định và các yếu tố xác định hàm quyết định . 2.2 Nhận dạng bằng các hàm quyết định tuyến tính . . . . . 2.3 Một số trường hợp phân lớp dạng bằng hàm quyết định tuyến tính . . . . . . . . . . . . . . . . . . . . . . . . . . 23

Giáp Văn Hiệp - Toán Tin 2 - K54

28 2.4 Nhận dạng bằng hàm quyết định suy rộng . . . . . . . . 28 2.4.1 Dạng tổng quát của các hàm suy rộng . . . . . . 2.4.2 Một số biến dạng quan trọng của các hàm suy rộng 29 31 2.5 Các phép lưỡng phân tập dạng

31 34

35 35

. . . . . . . . . . . . . . 2.5.1 Khái niệm về phép lưỡng phân và có ý nghĩa của phép lưỡng phân . . . . . . . . . . . . . . . . . . 2.5.2 Xác định bậc lưỡng phân bằng hàm suy rộng . . . 2.6 Phương pháp xâu dựng hàm tuyến tính trên cơ sở xấp xỉ bởi 1 hệ các đa thức trực giao, trực chuẩn . . . . . . . . 2.6.1 Xây dựng hệ trực giao, trực chuẩn các hàm 1 biến 2.7 Xây dựng hệ trực giao, trực chuẩn đầy đủ, các hàm nhiều biến trên cở sở hệ trực giao, trực chuẩn đầy đủ các hàm 1 biến . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.7.1 Xây dựng một số hệ đa thức trực giao, trực chuẩn đầy đỷ 1 biến đặc biệt và áp dụng xây dựng hệ đa . . . . . . thức trực giao, trực chuẩn nhiều chiều. 2.8 Phương pháp xây dựng các hàm quyết định dựa trên cở sở xấp xỉ bởi hệ các đa thức trực giao, trực chuẩn. . . . . 43

3 Phân lớp dạng bằng các hàm khoảng cách 45

45 45

46 46 49

3.1 Đặc trưng của việc phân lớp dạng bằng các hàm khoảng cách . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.1.1 Khái niệm khoảng cách, hàm khoảng cách . . . . 3.1.2 Đăc trưng của việc phân lớp dạng bằng các hàm khoảng cách . . . . . . . . . . . . . . . . . . . . . 3.2 Một số phương pháp phân lớp dạng theo tiêu chuẩn cực tiểu khoảng cách . . . . . . . . . . . . . . . . . . . . . . 3.2.1 Phương pháp 1 . . . . . . . . . . . . . . . . . . . 3.2.2 Phương pháp 2 . . . . . . . . . . . . . . . . . . . 3.3 Một số thuật toán phân hoạch tập dạng theo tiêu chuẩn cực tiểu khoảng cách . . . . . . . . . . . . . . . . . . . . 3.3.1 Khái niệm độ đo đồng dạng và một số độ đo đồng dạng tiêu biểu . . . . . . . . . . . . . . . . . . . . 3.3.2 Một số thuật toán phân hoạch dạng theo tiêu chuẩn cực tiểu khoảng cách. . . . . . . . . . . . . . . . . 55

4 Phân lớp dạng bằng các hàm xác suất 66

4.1 Phân lớp dạng như là một bài toán về lý thuyết các phép . . . . . . . . . . . . . . . . . . . . . . . . giải thống kê 66

Giáp Văn Hiệp - Toán Tin 2 - K54

mang đặc trưng thống kê. 66

dạng theo nghĩ xác suất. 68

theo quy tắc phân lớp Bayets 70

81 81 81

83 85

4.1.1 Xác định bài toán phân lớp dạng như là 1 trò chơi . . . . . . . . . . . . . 4.1.2 Xây dựng tiêu chuẩn nhận dạng cho việc phân lớp . . . . . . . . . . . . . . 4.1.3 Large Xây dựng các hàm quyết định phân lớp dạng . . . . . . . . . . . 4.2 Phân lớp dạng theo quy tắc phân lớp Bayets trong trường hợp các dạng tuân theo luật phân phối chuẩn . . . . . . 4.2.1 Nhắc lại đặc trưng của các biến ngẫu nhiên có phân phối chuẩn . . . . . . . . . . . . . . . . . . 4.2.2 Xây dựng tiêu chuẩn nhận dạng, hàm quyết định theo quy tắc phân lớp Bayets có các dạng có phân phối chuẩn . . . . . . . . . . . . . . . . . . . . . . 4.3 Một số đánh giá xác suất sai số của phân lớp Bayets trong một số trường hợp đặc biệt . . . . . . . . . . . . . . . . . 4.3.1 Đánh giá sai số của phân lớp Bayets trong trường hợp phân phối chuẩn . . . . . . . . . . . . . . . . 4.3.2 Mở rộng đánh giá cho trường hợp phân lớp dạng được thưc hiện bởi các hàm tuyến tính . . . . . . 4.4 Giới thiệu một số hàm mật đọ phân phối quan trọng trong nhận dạng . . . . . . . . . . . . . . . . . . . . . . . . . . 4.4.1 Hàm mật độ dạng tổng quát . . . . . . . . . . . . 4.4.2 Một số hàm mật độ dạng Peason . . . . . . . . . 4.5 Phương pháp xây dựng các hàm quyết định phân lớp dạng theo quy tắc phân lớp Bayets trên cơ sở xấp xỉ các hàm mật độ phân phốix ác suất . . . . . . . . . . . . . . . . . 4.5.1 Xây dựng các công thức truy toán tính kỳ vọng, ma trận hiệp biến của các dạng thuộc cùng 1 lớp 4.5.2 Xây dựng xấp xỉ mật độ phân phối bởi hệ hàm . 4.5.3 Xây dựng các hàm quyết định phân lớp dạng theo quy tắc phân lớp Bayets trên cơ sở xâp xỉ các hàm mật độ phân phối . . . . . . . . . . . . . . . . . . 88

Tài liệu tham khảo 92

Lời nói đầu

Theo như yêu cầu của 1 số anh em, mình đã biên soạn xong quyển này, trong quá trình tang gia bối rối viết không tránh khỏi những sai sót và phải nói là mệt mỏi không biết diễn tả bằng từ gì nữa =)), vì vậy bạn nào có ý kiến thì vả vỡ mồm luôn :v

Chương 1

Cơ sở lý luận của lý thuyết nhận dạng

1.1.1 Sự ra đời của khoa học nhận dạng và hai định hướng

1.1 Khái niệm cơ bản về nhận dạng

trong khoa học nhận dạng(KHND)

a. Sự ra đời của KHND

Có thể giải thích sự ra đời của KHND dựa trên hai nguyên nhân sau đây:

– KHND ra đời bắt nguồn từ việc quan sát sự nhận dạng tự nhiên

của con người và một số sinh vật sống khác.

∗ Con người và một số sinh vật sống khác nhận dạng các đối

tượng cụ thẻ thông qua các giác quan:

· Thị giác: Nhận biết được các hình dạng to nhỏ, ví dụ như

ô tô, nhà cửa ...

· Thính giác: Nhận biết (dạng) âm thanh, tiếng động như

tiếng sấm, động cơ, tiếng hát, cười ...

· Khứu giác: Nhận biết được các dạng mùi... · Vị giác: Nhận biết các dạng vị như chua, chát, thối rữa ... · Xúc giác: Nhận biết dạng tròn, nhẵn, xù xì, ghồ ghề ... ∗ Đặc biệt, con người còn nhận được các đối tượng trừu tượng thông qua các phán đoán, lý luận, suy diễn, nhận dạng không chỉ một đối tượng cụ thể mà cả một lớp đối tượng có cùng tính chất đặc trưng chung. Ví dụ 1.1. Nhận dạng thời tiết của một ngày (tháng, năm)

Giáp Văn Hiệp - Toán Tin 2 - K54

· Sức gió · Độ ẩm · Thủy văn

⇒ Dạng thời tiết ngày A: Sáng nhiều sương mù, trưa chiều giảm mây trời nắng. ⇒ Dạng thời tiết ngày B: Tương tự ngày A nếu các thông số đo đạc xấp xỉ các thông số đo đạc ngày A.

– KHND ra đời còn do các yêu cầu cấp bách của việc sử lý thông tin ngày càng phát triển, gia tăng do nền văn mình của con người ngày càng hiện đại.

b. Hai định hướng cơ bản trong KHND

– Định hướng 1: Nghiên cứu các khả năng ND và bản chất tự

nhiên của con người và một số vật sống khác có. Hướng này liên quan đến ngành nghiên cứu:tâm lý học, sinh học, vật lý học.

1.1.2 Một số ví dụ về nhận dạng dẫn đến định nghĩa tổng quát

– Định hướng 2: Phát triển lý thuyết và các phương pháp xây dựng các thiết bị nhằm giải các bài toán nhận dạng riêng biệt cho từng lĩnh vực ứng dụng nhất định. Hướng này liên quan đến các KH công nghệ, các ứng dụng tin học, máy tính điện tử, khoa học máy tính, kỹ thuật học.

về dạng

Ví dụ 1.2. Dự báo thời tiết là một sợ nhận dạng trên cơ sở các dữ liệu đầu vào

Bản tin về thời tiết cho một ngày:

• Sức gió

• Độ ẩm

• Mực nước thủy văn

• Hình dạng mây

• Nhiệt độ

Giáp Văn Hiệp - Toán Tin 2 - K54

Quán trình nhận dạng ⇒ Dạng thời tiết của ngày A.

Ngày B có các thông số xấp xỉ thông số ngày A hay với các điều kiện mà tương tự như ngày A ⇒ Dạng thời tiết ngày B tương tự dạng thời tiết ngày A.

Ví dụ 1.3. Chuẩn đoán bệnh y học là một sự nhận dạng. Bệnh nhân A đến bác sĩ, bác sĩ cần phải biết được các triệu chứng bệnh trên các dấu hiệu:

• Nhiệt độ cơ thể

• Thực hiện các xét nghiệm

– Máu

– Nước tiểu, phân

– Điện tim, não đồ

– Đo huyết áp

– Chụp X- Quang

Quá trình nhận dạng ⇒ Dạng bệnh của người A

1.1.3 Định nghĩa tổng quát về dạng

Bệnh nhân B có triệu chứng tương tự như người A thì bệnh nhân B mắc bệnh tương tự như bệnh nhân A.

Tất cả các đối tượng (phần tử) có cùng chung một số tính chất đặc trưng điển hình và chỉ những đối tượng đó nhóm họp với nhau tạo thành từng lớp xác định. Dạng là sự mô tả một phần tử bất kỳ được lấy làm đại diện cho những phần tử khác trong cùng một lớp mà được đồng nhất với phần tử đại diện (dạng mẫu) bởi các tính chất chung đó. Do đó, nhận dạng chính là đoán nhận cả một lớp dạng, phân biệt lớp dạng này với các lớp dạng khác.

a. Chức năng cơ bản của hệ nhận dạng tự động

– Định nghĩa Chức năng cơ bản của hệ nhận dạng tự động là phát hiện và tách ra các dấu hiệu đặc trưng cho các dạng trong tập dạng, đồng thời phân hoạch tập dạng thành từng lớp xác định sao cho mỗi lớp có ít nhật một dạng mẫu (dạng đại diện cho lớp) được lưu trữ trong bộ nhớ của hệ nhận dạng.

Giáp Văn Hiệp - Toán Tin 2 - K54

Nhận ra các dạng mới và xếp phân lớp chúng hoăc xây dựng thêm các lớp dạng mới.

– Ví dụ minh họa cho chức năng của hệ nhận dạng Giả suwe có tập dạng gồm tất cả dạng đường cong trong mặt phẳng và hệ nhận dạng tự động đã phân hoạch được chúng thành từng lớp xác định, mỗi lớp có những dạng mẫu đã được bao quản (lưu trữ) trong bộ nhớ của hệ nhận dạng. Vấn đề đặt ra là nhận dạng chữ COINS. Ta có sơ đồ sau:

1.2 Một số bài toán cơ bản làm cơ sở cho việc xây dựng hệ

1.2.1 Bài toán mã hóa dạng

nhận dạng

Định nghĩa

Bài toán mã hóa dạng là bài toán mà mỗi 1 đại lượng vật lý đo được từ dạng đều được xem là 1 dấu hiệu đặc trưng cho dạng và dạng sẽ được

Giáp Văn Hiệp - Toán Tin 2 - K54

đồng nhất với 1 bộ các dấu hiệu đặc trưng cho chúng.

Giả sử có 1 dạng x và từ x ta xác định 1 bộ n dấu hiệu đặc trưng x1, · · · , xn từ kết quả của n phép đo thì x đồng nhất (x1, · · · , xn)T xem như một véc tơ trong KG Euclid n chiều Rn nào đó. Vậy 1 đường bất kỳ có thể mã hóa được thành 1 véc tơ trong không gian KG Euclid n chiều Rn.

Một số ví dụ

Ví dụ 1.4. Mã hóa dạng chữ số 5. Trên mặt phẳng chứa chữ số 5, ta dựng hệ tọa độ 0xy, sau đó vẽ 1 họ các đường thẳng song song với 0x, 0y tạo thành một hệ mắt lưới hình chữ nhật phủ số 5.

Giả sử có n mắt lưới phủ chữ số 5, ký hiệu:

xj = (cid:26) 1nếu mắt lưới thứ j ∩ 5 = φ 0nếu mắt lưới thứ j ∩ 5 (cid:54)= φ

⇒ 5 ≡ (x1, · · · , xn)T trong đó xj nhận các giá trị là 0 hoặc 1. Như vậy, 1 chữ số có thể đồng nhất với 1 véc tơ nhị phân.

Ví dụ 1.5. Mã hóa 1 dạng sóng âm thanh. Giả sử cho một sóng âm f=f(t) như hình vẽ. Giả sử tại mỗi thời điểm ti ta đo được bước sóng f (ti) với mọi i=1,2,...,n. ⇒ Sóng âm f = (f (t1, · · · , f (tn))) ∈ Rn.

Giáp Văn Hiệp - Toán Tin 2 - K54

Ví dụ 1.6. Mã hóa 1 dạng thời tiết. Để có được dạng thời tiết của 1 ngày A, ta cần phải biết được (đo được) các đại lượng sao:

• Sứ gó x1

• Độ ẩm x2

• Đo mức nước thủy văn x3

• Đo nhiệt độ x4

1.2.2 Bài toán về việc xử lý sơ bộ và lựa chọn các dấu hiệu

⇒ Thời tiết ngày A=(x1, x2, x3, x4)T .

Định nghĩa

Là bài toán tiếp sau bài toán mã hóa, mục đích nhằm lựa chọn ra các dấu hiệu đặc trưng điển hình, loại bỏ các dấu hiệu phụ để giảm bới kích thước của dạng, giảm mức đo phức tạp trong tính toán.

Ví dụ 1.7. Đối với dạng sóng âm f=f(t) chỉ cần đo bước sóng cực đại và các bước sóng cực tiểu cũng đủ tạo ra được 1 bộ dấu hiệu đặc trưng cho f.

Giáp Văn Hiệp - Toán Tin 2 - K54

1.2.3 Bài toán xây dựng hệ nhận dạng

Định nghĩa

Bài toán xây duwjngj hệ nhận dạng tự động là bài toán xây dựng các

thiết bị cho hệ nhận dạng sao cho các yêu cầu sau được thỏa mãn:

• Yêu cầu 1: Phải phát hiện và tách ra được các dấu hiệu đặc trưng cho các dạng đồng thời phân hoạch tập dạng ra thành từng lớp xác định.

• Yêu cầu 2: Tiếp nhận dạng mới, phân lớp chúng, hoặc xây dựng lớp

mới.

Bài toán xây dựng hệ nhận dạng là bài toán được đặt ra sau hai bài toán trên và bài toán được giải quyết qua hai giai đoạn

• Giai đoạn 1: Căn cứ vào các dấu hiệu đặc trưng của các dạng phân

hoạch tập dạng ra thành từng lớp xác định.

1.2.4 Bài toán đánh giá tham số

• Giai đoạn 2: Nhận dạng các dạng mới và xếp lớp chúng.

1.2.5 Bài toán mô phỏng dạng

Trong quá trình giải quyết bài toán dạng có thể nảy sinh một loạt các thông số cần phải được xử lý 1 cách tối ưu. Như vậy, ta thường có bài toán đánh giá thông số. Các thông số thường được đánh giá thông qua các công cụ của lý thuyết tối ưu.

Là bài toán liên quan đến việc sử lý thông tin chứa trong văn cảnh, lời nói hoặc chữ viết. Nếu thông tin chỉ được chứa trong văn cảnh hoặc mô tả bằng lời thì hệ nhận dạng tự động cần phải xác định ra 1 loạt các dấu hiệu đặc trưng để trên cở sở đó mô phỏng được dạng. Có thể xác định được các dấu hiệu đặc trưng này nhờ các xác suất có điều kiện, các thống kê ngôn ngữ học và các phương pháp xấp xỉ,... và bộ các dấu hiệu đặc trưng thu được được gọi là ngữ pháp của dạng.

Giáp Văn Hiệp - Toán Tin 2 - K54

1.3 Một số nguyên tắc và phương pháp luận làm cơ sở để xây

1.3.1 Mội số nguyên tắc cơ bản

dựng hệ nhận dạng

1. Nguyên tắc liệt kê bộ phận.

Là nguyên tắc liệt kê các thành phần của dạng mà theo đó chỉ những thành phần có tính chất đặc trưng điển hình cho dạng được giữ lại, còn sẽ được ... (đếu dịch được).. những thành phần không cần thiết. Khi 1 dạng đã mã hóa được dựa vào hệ nhận dạng thì hệ nhận dạng sẽ liệt kê và so sánh các dấu hiệu đặc trưng của dạng với các dấu hiệu đặc trưng của dạng mẫu đã được lưu trữ trong bộ nhớ của hệ nhận dạng.

2. Nguyên tắc đồng nhất các tính chất.

Các dạng mới sẽ được so sánh với các dạng mẫu thuộc từng lớp xác định của hệ nhận dang, hệ nhận dạng sẽ đồng nhất các dấu hiệu đặc trưng của dạng mới với các dấu hiệu đặc trưng của dạng mẫu và tiến hành phân lớp dạng mới (nhận dạng).

3. Nguyên tắc "Classteration":

1.3.2 Một số phương pháp luận làm cơ sở cho việc xây dựng

Là nguyên tắc chuyển từng lớp dạng đã được mã hóa xác định của tập dạng vào trong những tập compact tách biệt của không gian Euclid tương ứng (chẳng hạn là yêu cầu tách biệt) và được gọi là những "Classter". Từ những Classter tách biệt này việc phân lớp các dạng mới được thực hiện mang tính định hướng và rõ ràng hơn.(Chính xác hơn những lớp này được bao bọc trong những biểu cầu tách biệt gọi là nhữn "Classter").

hệ nhận dạng tự động

1. Phương pháp Heuristic (tìm kiếm)

Trực giác và kinh nghiệm của con người được lấy làm cơ sở của phương pháp này, trong đó các nguyên tắc liệt kê và đồng nhất, các tính chất được sử dụng.

2. Phương pháp toán học.

Thông thường có 2 phương pháp.

Giáp Văn Hiệp - Toán Tin 2 - K54

– Phương pháp đơn hình: là phương pháp xây dựng các thuật toán

lặp trong việc phân hoạch tập dạng và nhận dạng.

– Phương pháp thống kê : Là phương pháp sử dụng lý thuyết xác suất thống kê để phân lớp dạng có mức rủi ro (tổn thất) trung bình thấp nhất.

3. Phương pháp ngôn ngữ

Nếu việc mô ta các dạng được thực hiện bằng phương pháp mô phỏng, thì để xây dựng hệ nhận dạng, người ta thường sử dụng phương pháp ngôn ngữ đồng thời với việc sử dụng nguyên tắc đồng nhất các tính chất, yếu tố then chốt của phương pháp này là ở việc lựa chọn các phần tử mô phỏng của dạng, đồng thời kết hợp các phần tử này với các mối tương quan của chúng tạo thành ngữ pháp của dạng và cuối cùng thực hiện trong ngôn ngữ tương ứng quá trình phân tích và đón nhận.

1.4 Về một số phương pháp toán học xây dựng tiêu chuẩn

1.4.1 Một số khái niệm cơ bản

nhận dạng cho hệ nhận dạng tự động

1. Khái niệm về các bộ phận cấu thành hệ nhạn dạng.

a. Khối cảm biến: Là 1 thiết bị dùng để biến các đặc trưng vật lý của dạng thành 1 bộ dấu hiệu đặng trưng cho dạng. Nói cách khacs, khối cảm biến là thiết bị dùng để mã hóa dạng (dạng được mã hóa thành những véc tơ).

b. Khối phân lớp: Là thiết bị dùng để tiếp nhận các dạng đã được mã hóa từ khối cảm biến phân hoạch thành từng lớp xác định cùng với những dạng mẫu tương ứng được lưu trữ vào bộ nhớ nhận dạng mới và xếp lớp các dạng mới.

2. Khái niệm về sai số trong hệ nhận dạng

Một số hệ nhận dạng được gọi là phạm sai số nếu 1 dạng thực chất thuộc vào 1 lớp nào đó nhưng hệ nhận dạng lại xếp (phân) dạng đó sang 1 lớp khác. Ví dụ: Cho 2 hệ nhận dạng R1, R2. Ta nói hệ R1 tốt hơn R2 nếu xác suất phạm sai (sai số) của hệ R1 nhỏ hơn xác suất sai số của hệ

Giáp Văn Hiệp - Toán Tin 2 - K54

R2 khi phân lớp dạng.

3. Một số khái niệm xác suất trên nghiệm, mật đọ phân phối xác suất

1.4.2 Xây dựng tiêu chuẩn nhận dạng cho hệ nhận dạng tự động

(PPXS), xá suất phân lớp chúng Giả sử 1 dạng Ω ⊂ Rn đã được phân hoạch thành m lớp xác định Ω1, Ω2, · · · , Ωm, x là 1 dạng cần được phân lớp. Khi đó, xác suất xuất hiện dạng x trong lớp Ωi ký hiệu là p(Ωi) được gọi là xác suất tiên nghiệm (xác suất ban đầu)của Ωi với mọi i=1,2,...,m. Nếu sự xuất hiện của x trong các lớp đồng khả năng thì các xác suất tiên nghiệm p(Ωi)= 1/m. với i=1,2,...m. Xác suất có điều kiện p(Ωi/x) được gọi là xác suất phân lớp đúng dạng x vào lớp Ωi. Xác suất có điều kiện p(Ωi/x) là MĐPPXS dạng x vào lớp Ωi. Xác suất p(x) để chỉ xác suất xuất hiện dạng x trong tập dạng.

1. Xây dựng tiêu chuẩn tổng quát Giả sử tập dạng ΩØcphnhchthnhm lớp Ω1, Ω2, · · · , Ωm, x là dạng mới cần được phân lớp. Để tiện lợi, ta giới thiệu các xác suất tiên nghiệm bằng nhau, tức là

(∗) p(Ω1) = p(Ω2) = · · · = p(Ωm)

= = pi = p(Ωi/x) = p(xΩi) p(x) p(x/Ωi)p(Ωi) p(xΩ) p(x Ωk)

(∗) =

p(x/Ωi)p(Ωi) = =

m (cid:80) k=1

p(x/Ωk)p(Ωk) p(x/Ωk) p(xΩk) Nếu x được phân lớp Ωi thi ta có xác suất phân lớp đúng. p(xΩi)p(Ωi) m (cid:80) k=1 p(x/Ωi) m (cid:80) k=1 p(x/Ωi)p(Ωi) m (cid:80) k=1

Từ đó suy ra xác suất phân sai x vào lớp Ωi là 1-pi Với i (cid:54)= j ta có 1-pi < 1- pj ⇔ pi > pj

⇔ >

p(x/Ωk) p(x/Ωk) p(x/Ωi) m (cid:80) k=1 p(x/Ωj) m (cid:80) k=1

Giáp Văn Hiệp - Toán Tin 2 - K54

⇔ p(x/Ωi) > p(x/Ωj) Từ đó người ta xây dựng được 1 tiêu chuẩn nhận dạng tổng quát Dạng mới x sẽ được phân vào lớp mà có xác suất sai số đối với lớp đó là bé x’ so với tất cả các xác suất sai số đối với các lớp còn lại. Nói các khác x được phân lớp có MĐPPXS là lớn x’ so với tất cả các MĐPPXS đối với các lớp khác. ⇒ Điều đó có nghĩa là x ∈ D nếu p(x/Ωi) > p(x/Ωj) với mọi i (cid:54)= j, j =1,2,...,m. Trường hợp tồn tại lớp Ωk sao cho p(x/Ωi) = p(x/Ωk), đồng thời p(x/Ωk) > p(x/Ωj) với mọi j (cid:54)= k , j (cid:54)= i thì máy sẽ phân 1 cách tùy ý vào Ωi hoặc Ωk.

2. Ví dụ về xây dựng tiêu chuẩn nhận dạng trong TH các dạng tuân

theo phân phối chuẩn.

a. Nhắc lại định nghĩa về biến ngẫu nhiên tuân theo luật phân phối

chuẩn (ppc) Dạng x = (x1, · · · , xn) ∈ Rn xem như là 1 biến ngẫu nhiên n chiều được gọi là tuân theo luật ppc nếu hàm MĐPPXS (ppxs) của nó có dạng

p(x) = exp{− (x − m)(cid:48)c−1(x − m)} 1 2 1/2 1 n/2|det(c)| (2π)

trong đó m = (m1, · · · , mn)(cid:48) là véc tơ kỳ vọng toán học (trị trung bình) của x, mi = Exi, ∀i = 1, · · · , n, C = (cij)n×n - ma trận hiệp biến vuông cấp n. Với

cij = cov(xi − xj) = E {(xi − mi)(xj − mj)}

⇒ c = E {(x − m)(x − m)(cid:48)} (C- MT đối xứng xác định dấu) Giả sử Ω - tập dạng đã được phân hoạch thành M lớp Ω1, · · · , ΩM gồm các dạng tuân theo luật chuẩn. Giả sử x là 1 dạng cần được phân lớp. Từ định nghĩa ⇒ MĐPPXS của dạng x đối với lớp Ωi là:

(cid:48)(x − mj)

(cid:26) (cid:27) exp − p(x/Ωi) = (x − mi)(cid:48)ci 1 2 1 (2a)n/2|det(ci)|1/2

trong đó

1, · · · , mi

n)(cid:48), mi

j = E(xj/Ωi), ∀i = 1, · · · , M.

mi = (mi

Giáp Văn Hiệp - Toán Tin 2 - K54

pq = E (cid:8)(xp − mi

q)(cid:9).

Ma trận hiệp biến : ci = (ci p)(xq − mi pq)n×n với ci Để tiện lý luậ ta giả giử các xác suất trên nghiệm bằng nhau p(Ωi) = 1/M, ∀i = 1, · · · , M . Các ma trận hiệp biến như nhau cho tất cả các lớp, tức là

c1 = · · · = cM = c

Theo tiêu chuẩn nhận dạng tổng quát, x được phân vào lớp Ωi nếu p(x/Ωi) > p(x/Ωj), ∀i (cid:54)= j, j = 1, · · · , M

(∗) ⇔ > 1 ⇔ ln > 0 p(x/Ωi) p(x/Ωj) p(x/Ωi) p(x/Ωj)

= − (x − mi)(cid:48)c−1(x − mi) + (x − mj)(cid:48)c−1(x − mj) Đặt dij(x) = ln p(x/Ωi) p(x/Ωj) 1 2 1 2

(cid:48)c−1x −

(cid:48)c−1mi

x(cid:48)c−1x + = − mi mi 1 2 1 2

(cid:48)c−1x +

(cid:48)c−1mj

+ 1 2 x(cid:48)c−1x − mj mj 1 2 1 2 x(cid:48)c−1mi + 1 2 1 2

(cid:48)c−1mj+

(cid:48)c−1mi+

(cid:48)c−1mj

= x(cid:48)c−1(mi−mj)− mi mj mj mj 1 2 x(cid:48)c−1mj − 1 2 1 2 1 2

(cid:48)c−1(mi + mj)

c−1=(c−1)(cid:48)

(cid:48)c−1mi− 1 2 = x(cid:48)c−1(mi − mj) −

= x(cid:48)c−1(mi − mj) − (mi + mj)(cid:48)c−1mi + mj

1 2 1 2 (mi + mj)(cid:48)c−1mi + (mi + mj)(cid:48)c−1mj 1 2 1 2 Hay

dij(x) = x(cid:48)c−1(mi − mj) − (mi + mj)c−1(mi − mj) 1 2

công thức trên là tổ hợp tuyến tính của các biến

dij(x) = x(cid:48)c−1(mi−mj)− (mi+mj)c−1(mi−mj) > 0∀i (cid:54)= j, j = 1, · · · , M b. Phát biểu tiểu chuẩn nhận dạng Dạng x được phân vào lớp Ωi (trong trường hợp các dạng tuân theo luật chuẩn với cùng ma trân hiệp biến cho các lớp và xác suất trên nghiệm bằng nhau) nếu 1 2

Trường hợp tồn tại lớp Ωk sao cho dik(x) = 0 còn dki > 0 với mọi j (cid:54)= k, i, j = 1, · · · , M thì hệ nhận dạng sẽ đưa x vào Ωi hay Ωk tùy ý.

Chương 2

Các hàm quyết định phân lớp dạng

2.1 Hàm quyết định và các yếu tố xác định hàm quyết định

1. Khái niệm hàm quyết định

a. Định nghĩa:

n (cid:88)

Một hàm thực n biến xác định trong không gian Euclid Rn chứa 1 tập dạng nào đó được gọi là hàm quyết định phân lớp tập dạng, nêu căn cứ vào dấu của nó có thể xác định được khả năng phân 1 dạng bất kỳ của tập dạng vào lớp nào đó trong số các lớp đã được phân hoạch của tập dạng. Khi đó, nếu d = d(x) là 1 hàm quyết (đoạn này không dịch được) là tập dạng thì phương trình d(x)=0 biểu dienj 1 (cái gì đó ý cũng ko bit luôn :-)) )trong không gian Rn được goi là siêu mặt quyết định phân lớp dạng. (Trường hợp đặc biệt). Khi

j=1

d(x) = ωjxj + ωn+1

hàm tuyến tính thì d(x) = 0 là siêu phẳng trong Rn

b. Một số ví dụ

Ví dụ 2.1. Giả sử Ω là tập dạng được mã hóa vào R2 gồm 2 lớp

(cid:26) Ω1 = (cid:8)các cầu thủ bóng đá(cid:9)

Ω2 = (cid:8)các vận động viên đua ngựa(cid:9)

bởi bộ 2 dấu hiệu đặc trưng x1 = chiều cao và x2 = cân nặng.

Giáp Văn Hiệp - Toán Tin 2 - K54

Ω1 ⊂ claster S1 -hình tròn tập I1(a1, b1), bán kinh R1. Ω2 ⊂ claster S2 -hình tròn tập I2(a2, b2), bán kinh R2. Giả thiết I1I2 > R2 + R2, đường thằng trung trực của đoạn thẳng I1I2 có phương trình:

2 − a2

1 + b2

2 − b2

1) = 0

(a2 d12(x) = (a2 − a1)x1 + (b2 − b1)x2 − 1 2

12 = (cid:8)x ∈ R2|d12(x) > 0(cid:9) d+ 12 = (cid:8)x ∈ R2|d12(x) < 0(cid:9) d−

M hàm quyết định lớp tập dạng

Nếu trung điểm I nằm ngoài 2 đường tròn thì d12(x) là hàm quyếtđịnh phân lớp 2 lớp dạng Ω1, Ω2. d12(x) chia mặt phẳng ra làm 2 nửa

(cid:27) x thuộc Ω1 nếu d12(x) < 0, x thuộc Ω2 nếu d12(x) > 0. d12(x) = 0 là đường quyết định tách lớp Ω1 ra khởi Ω2. Ví dụ 2.2. Lấy lại Ví dụ ở chương I, trong trường hợp ppc và tập dạng Ω được phân hoạch thành M lớp với các xác suất tiên nghiệm và ma trận hiệp biến như nhau cho từng lớp thì cần tới C 2 (cid:26)

M siểu phẳng quyết định được cho bởi các phương trình

(mi + mj)c−1(mi − mj), ∀1 ≤ i < j ≤ M dij(x) = x(cid:48)c−1(mi − mj) − 1 2

⇒ C 2 dij(x) = 0 cho phép tách lớp Ωi ra khỏi lớp Ωj.

Giáp Văn Hiệp - Toán Tin 2 - K54

2. Các yếu tố xác định hàm quyết định

Để xác định hàm quyết định cần 2 yếu tố sau:

a. Dạng hàm quyết định

∗ Dạng tuyến tính ∗ Dạng phi tuyến

b. Khả năng thực tế xác định các hệ số của hàm quyết định

Hệ số của hàm quyết định tức là các hằng số tham gia vào việc quyết định dạng hàm quyết định.

Ví dụ 2.3. Giả sử 1 tập dạng Ω ⊂ R2 được phân hoạch thành 2 lớp Ω1, Ω2, biết được 2 lớp này có thể tách được bởi 1 hàm quết định tuyến tính dạng tổng quát

d(x) = ω1x1 + ω2x2 + ω3

Bám vào dạng mẫu chứa trong Ω1, Ω2, căn cứ đầu tiên vào các dạng mẫu của Ω1, Ω2, ví dụ: Ω1 gồm 2 dạng:

– x1 = (α11, α12)(cid:48) – x2 = (α21, α22)(cid:48)

Ω2 gồm 2 dạng:

– x3 = (α31, α32)(cid:48) – x4 = (α41, α42)(cid:48)

Tiêu chuẩn nhận dạng được cho như sau: x ∈ Ω1 nếu d(x) > 0 x ∈ Ω2 nếu d(x) < 0 ⇒ Hệ phương trình xác định ω1, ω2, ω3:

 

 α11ω1 + α12ω2 + ω3 > 0 α21ω1 + α22ω2 + ω3 > 0 α31ω1 + α32ω2 + ω3 < 0 α41ω1 + α42ω2 + ω3 < 0

Giáp Văn Hiệp - Toán Tin 2 - K54

2.2 Nhận dạng bằng các hàm quyết định tuyến tính

1. Dạng tổng quát của các hàm tuyến tính

a. Định nghĩa

n (cid:88)

Một hàm thực n biến xác định trong không gian Euclid Rn được gọi là hàm tuyến tính nếu nó có dạng

j=1

(2.1) d = d(x) = ω1x1 + · · · + ωnxn + ωn+1 = ωjxj + ωn+1

trong đó ωj, j = 1, · · · , n + 1 là các hằng số thực tùy ý và x = (x1, · · · , xn)(cid:48) ∈ Rn.

b. Chú ý

∗ Chú ý 1.

Không gian Rn ∼= Rn = {x = (x1, · · · , xn, 1)(cid:48)} qua phép tương ứng 1-1.

x = (x1, · · · , xn)(cid:48) ⇔ x = (x1, · · · , xn, 1)(cid:48)

⇒ Có thể đồng nhất x ∼= x, do đó

d(x) ∼= W(cid:48)x

trong đó W = (ω1, · · · , ωn+1)(cid:48) và x = (x1, · · · , xn, 1)(cid:48).

∗ Chú ý 2.

Phương trình d(x)=0 biểu diễn 1 siêu phẳng trong Rn. Nếu d(x) là hàm quyết định tuyến tính tham gia vào việc phân lớp dạng 1 tập dạng Ω nào đó thuộc Rn thì siêu phẳng d(x)=0 được gọi là siêu phẳng quyết định. Siêu phẳng quyết định d(x)=0 chia không gian Rn ra làm 2 nửa

d+ = {x ∈ Rn|d(x) > 0} d− = {x ∈ Rn|d(x) < 0}

−→ W = (ω1, · · · , ωn)(cid:48) gọi là véc tơ pháp tuyến của siểu

Véc tơ phẳng d(x)=0

Ví dụ 2.4. • n=1, trong không gian R là một siêu phẳng không chiều dạng x0 (1 điểm) (đếu đọc được =)) Điểm x = x0 chia R ra làm 2 nửa

d+ = {x > x0} d− = {x < x0}

Giáp Văn Hiệp - Toán Tin 2 - K54

• n=2, trong không gian R2, ta được các siêu phẳng 1 chiều dạng d(x) = ω1x1 + ω2x2 + ω3 = 0 (đường thẳng thông thường)

• n=3, trong không gian R3 được các siêu phẳng 2 chiều

d(x) = ω1x1 + ω2x2 + ω3x3 + ω4 = 0

(mặt phẳng thông thường)

c. Tiêu chuẩn nhận dạng bởi hàm tuyến tính đối với 2 lớp dạng

Giáp Văn Hiệp - Toán Tin 2 - K54

Giả sử Ω1, Ω2 là 2 lớp dạng bất kỳ của 1 tập dạng Ω nào đó. Khi đó, hàm tuyến tính d = d(x) = W(cid:48)x là hàm quyết định tách 2 lớp Ω1, Ω2 nếu tiêu chuẩn nhận dạng sau thỏa mãn. x được phân vào lớp Ω1 nếu d(x)>0 , được phân vào lớp Ω2 nếu d(x) <0. (d(x) còn được gọi là hàm quyết định đối với lớp Ωx)

2.3 Một số trường hợp phân lớp dạng bằng hàm quyết định tuyến tính

1. TH1: Mỗi lớp đều được tách ra khỏi tất cả các lớp còn lại bằng

1 siêu phẳng quyết định. Giả sử dạng Ω ⊂ Rn được phân hoạch tthanhf M lớp Ω1, · · · , ΩM và các lớp này tách nhau theo TH1. Khi đó, tồn tại M hàm (cid:48)x quyết định tuyến tính d1(x), · · · , dM (x) trong đó di(x) = wi với wi = (ωi1, · · · , ωin+1)(cid:48) ∈ Rn+1, ∀i = 1, · · · , M sao cho di(x) là hàm quyết định đối với lớp Ωi (tách lớp Ωi ra khỏi M-1 lớp còn lại). Từ đó ⇒ tiêu chuẩn nhận dạng sau: x ∈ Ωi nếu di(x) > 0 và dj(x) < 0 với mọi i (cid:54)= j, j = 1, · · · , M.

Giáp Văn Hiệp - Toán Tin 2 - K54

Chú ý: Nếu các lớp dạng của Ω tách nhau theo TH1 thì đối với lớp Ωi bất kỳ ta luôn có

i ∩

j=1

(cid:33) (cid:32) M (cid:92) Ωi ⊂ d+ d− j

Ví dụ 2.5. Giả sử trong R2 cho tập dạng Ω được phân thành 3 lớp Ω1, Ω2, Ω3 và 3 lớp này tách nhau theo TH1 bởi hàm quyết định tuyến tính

d1(x) = −x1 + x2, d2(x) = x1 + x2 − 5, d3(x) = −x2 + 1

a. Xác định các đường quyết định cho phép tách 3 lớp trên và

các miền tương ứng cho 3 lớp đó.

b. Biết x∗ = (6, 5)(cid:48) là 1 dạng thuộc Ω. Hãy nhận dạng x∗ Lời giải

a. Các đường quyết định chính là các đường thẳng.

d1(x) = −x1 + x2 = 0 d2(x) = x1 + x2 − 5 = 0 d3(x) = −x1 + 1 = 0

⇒ Các đường quyết định như hình vẽ. Từ đó suy ra

Giáp Văn Hiệp - Toán Tin 2 - K54

1 ∩ d− 2 ∩ d− 3 ∩ d−

2 ∩ d− 1 ∩ d− 1 ∩ d−

3 ⇒ Ω1 như hình vẽ 3 ⇒ Ω2 như hình vẽ 2 ⇒ Ω3 như hình vẽ

Ω1 ⊂ d+ Ω2 ⊂ d+ Ω1 ⊂ d+

b. Ta có

2 ∩ d−

1 ∩ d−

3 ⇒ x∗ ∈ Ω2 2. TH2: Mỗi lớp tách ra khỏi 1 lớp bất kỳ bởi 1 hàm quyết định tuyến tính (1 siêu phẳng quyết định) riêng biệt. Giả sử tập dạng Ω ⊂ Rn được phân thành M lớp Ω1, · · · , ΩM . Từ giả thiết ⇒ với bất kỳ 2 lớp dạng Ωi, Ωj, i (cid:54)= j đều tồn tại 1 hàm quyết định phân biệt

d1(x∗)=-6+5<0 d2(x∗)=6+5-5>0 d3(x∗)=-5+1<0 ⇒ x∗ ∈ Ω ∩ d∗

M hàm quyết định tuyến tính dij(x),

dij=dij(x) = w(cid:48)x, wj = (ωij1, · · · , ωijn+1), x = (x1, · · · , xn, 1)(cid:48)

tách lớp Ωi ra khỏi lớp Ωj, tương ứng được siêu phẳng quyết định dij(x) = 0 là biên phân tách của 2 lớp này. Đối với 2 lớp Ωi, Ωj ta có: x ∈ Ωi nếu dij(x) > 0 và x ∈ Ωj nếu nếu dij(x) < 0 ⇒ Nếu dij là hàm quyết định tuyến tính tách Ωi ra khỏi Ωj thì dji = dji(x) = −dij(x) lại là hàm quyết định tuyến tính tách Ωj ra khỏi tập Ωi. Từ đó để phân biệt được dạng tập Ω thì cần sử dụng C 2 ∀1 ≤ i < j ≤ M . Tiêu chuẩn nhận dạng:Dạng x ∈ Ω được phân vào lớp Ωi nếu dij(x) > 0∀j (cid:54)= i, ∀j = 1, · · · , M . TH tồn tại Ωk (i (cid:54)= k) sao cho dik(x) = 0 và dki(x) > 0 ∀j (cid:54)= k, j (cid:54)= i thì hệ nhận dạng tự động sẽ phân x vào 1 trong hai lớp Ωi hoặc Ωk tùy ý.

M (cid:84) j=1,j(cid:54)=i

Chú ý: Trong TH này, miền Ωi ⊂ dk ij, ∀i = 1, · · · , M

Ví dụ 2.6. Giả sử tập dạng Ω ⊂ R2 được phân thành 3 lớp Ω1, Ω2, Ω3, theo TH2 bởi 3 hàm quyết định tuyến tính

d12(x) = −x1 − x2 + 5 d13(x) = −x1 + 3 d23(x) = −x1 + x2

Giáp Văn Hiệp - Toán Tin 2 - K54

a. Xác định các đường quyết định cho phép tách 3 lớp trên và

các miền tương ứng chứa 3 lớp đó. b. Biết x∗=(4, 3)(cid:48) ⊂ Ω, hãy nhận dạng x∗. Lời giải:

a. Vẽ 3 đường quyết định

12 ∩ d+ 13

Ω1 ⊂ d+ 1j = d+

21 ∩ d+

23 = d−

12 ∩ d+ 23

Ω2 ⊂ d+ 2j = d+

31 ∩ d+

32 = d+

13 ∩ d− 23

3 (cid:84) j=1,j(cid:54)=1 3 (cid:84) j=1,j(cid:54)=2 3 (cid:84) j=1,j(cid:54)=3

Ω3 ⊂ d+ 3j = d+

b. Tính

d12(x∗) = −4 − 3 + 5 < 0 d13(x∗) = −4 + 3 < 0 d23(x∗) = −4 + 3 < 0 ⇒ d32(x∗) > 0, d31(x∗) > 0 ⇒ x ∈ Ω3

3. TH3: Tồn tại M hàm tuyến tính sao cho tiêu chuẩn nhận dạng

sau thỏa mãn: "x ∈ Ω_i nếu di(x) > dj(x) với mọi j (cid:54)= i, j = 1 · · · , M "

Giáp Văn Hiệp - Toán Tin 2 - K54

ix, ∀i = 1, · · · , M với wi = (ωi1, · · · , ωin+1)(cid:48)

trong đó di = di(x) = w(cid:48) là các hàm tuyến tính cho trước. Chú ý : Nếu đặt dij(x) = di(x) − dj(x), ∀1 ≤ i < j ≤ M thì ta được C 2 M hàm quyết định tuyến tinh cho phép tách Ωi ra khỏi Ωj với j (cid:54)= i và thu dược tiêu chuẩn nhận dạng như trong TH2. Tuy nhiên , TH2 không thể suy ra TH3. Ví dụ 2.7. Giả sử tập dạng Ω ⊂ R2 được phân hoạch thành 3 lớp Ω1, Ω2, Ω3 theo TH3 bởi 3 hàm tuyến tính:

d1(x) = −x1 + x2 d2(x) = x1 + x2 − 1 d3(x) = −x2

a. Xác định hàm quyết định các đường quyết định tương ứng

tách 3 lớp trên và các miền của R2 chứa 3 lớp đó

b. Biết x∗=(1,1)’ ⊂ Ω. Nhận dạng x∗. Lời giải:

a. Từ 3 hàm quyết định tuyến tính phân lớp tập dạng Ω

Giáp Văn Hiệp - Toán Tin 2 - K54

13, Ω2 ⊂ d+

12 ∩ d+

13 ∩ d− 23

⇒ Ω1 ⊂ d+ d12(x) = d1(x) − d2(x =) − 2x1 + 1 d13(x) = d1(x) − d3(x) = −x1 + 2x2 d23(x) = d2(x) − d3(x) = x1 + 2x2 − 1 23, Ω3 ⊂ d−

chú ý: Nếu tồn tại Ωk : di(x) = dk(x) > dj(x) với mọi j (cid:54)= i, j (cid:54)= k thì x được phân vào Ωi tùy ý.

b. Nhận dạng x∗=(1,1)’

d12(x∗) = −2 + 1 < 0 d13(x∗) = −1 + 2 > 0 d23(x∗) = 1 + 2 − 1 > 0 ⇒ x∗ ∈ Ω2

{di(x∗)} = max {0, 1, −1} = 1 = d2(x∗), ⇒ x ∈ (Tính max 1≤i≤3

Ω2)

2.4.1 Dạng tổng quát của các hàm suy rộng

2.4 Nhận dạng bằng hàm quyết định suy rộng

1. Sự cần thiết của việc xây dựng các hàm quyết định suy rộng.

Trong thực tế, các hàm quyết định tuyến tính khong đủ để phân lớp 1 tập dạng bất kỳ. Ví dụ 2.8. Cho 1 tập dạng Ω = {x1, · · · , x4} ⊂ R2 được phân thành 2 lớp:

Ω1 = {x1, x3} Ω2 = {x3, x4}

Giáp Văn Hiệp - Toán Tin 2 - K54

1 + bx2

2 + c

không thể táchs Ω1 ra khỏi Ω2 bằng 1 đường thẳng (hàm quyết định tuyến tính) ⇒ Chỉ có thể tách bằng 1 đường phi tuyến, chẳng hạn đường elip d(x) = ax2

2. Xây dựng hàm suy rộng tổng quát

K (cid:88)

Thông thường, người ta xây dựng như sau: Trước hết chọn 1 bộ K hàm thực đơn trị nào đó {f1(x), · · · , fK(x)}, sau đó xây dựng các tổ hợp tuyến tính của bộ K hàm trên, chẳng hạn:

i=1

d(x) = ωifi(x) + ωK+1, ωi ∈ R, ∀i = 1, · · · , K + 1

2.4.2 Một số biến dạng quan trọng của các hàm suy rộng

là các hẳng số bất kỳ. Thì hàm d(x) được gọi là hàm suy rộng, và nếu hàm này tham gia vào việc phân lớp dạng 1 tập dạng Ω ⊂ Rn thì được gọi là hàm quyết định suy rộng.

1. Biến dạng tuyến tính.

Nếu chọn các hàm

fi(x) = xi ⇔ fi : Rn → R (x1, · · · , xn) → xi

n (cid:88)

Phép chiếu véc tơ x xuống trục x1. K=n thì thu được hàm tuyến tính:

i=1

d(x) = ωixi + ωn+1 = W(cid:48)x

Giáp Văn Hiệp - Toán Tin 2 - K54

2. Biến dạng toàn phương (biến dạng bậc 2)

n (cid:88)

a. Biến dạng toàn phương của hàm suy rộng là hàm có biểu thức

n (cid:88)

j +

j=1

1≤i

j=1

(cid:88) d(x) = ωjjx2 ωijxixj + ωjxj + ωn+1

n, x1, · · · , xn, x1, · · · , xn

i=1 = (cid:8)x2

n + n

(cid:9) {fi(x)}k

Trong trường hợp này, hệ hàm 1, · · · , x2 K = n + C 2 Số ác hệ số tham gia vào dàm d là:

n+2

= = C 2 K + 1 = 2n + 1 + n + 1 2 (n + 1)(n + 2) 2

b. Chú ý:

Nếu đặt ma trận A = (aij)n×n sao cho

2ωij = aji, ∀1 ≤ i < j ≤ n

aii = ωii, ∀i = 1, · · · , n aij = 1

và b = (ω1, · · · , ωn)(cid:48), c = ωn+1 thì

d(x) = x(cid:48)Ax + x(cid:48)b + cA là ma trận đối xứng

Từ đó suy ra: • Nếu A là ma trận đơn vị thì phương trình d(x) = 0 biểu diễn

1 siêu cầu trong Rn.

• Nếu A là ma trận đối xứng xác định dương thì d(x) = 0 biểu

diễn 1 siêu elipcoid trong Rn

• Nếu A là ma trận đối xứng nửa xác định dương thì d(x) = 0

biểu diễn 1 siêu parobolic eliptic

• Nếu A là ma trận xác định âm thì d(x) = 0 biểu diễn 1 siêu

hypebolic

n (cid:88)

3. Biến dạng đa thức hàm suy rộng thành 1 đan thức bậc n nào r nào đó của n biến x1, · · · , xn và được cho bởi công thức truy toán sau:

p2=p1

pn=pn−1

p1=1

dr(x) = · · · ωp1···prxp1 · · · xpr + dr−1(x)

trong đó quy ước d0 = ωn+1 = hằng số.

Giáp Văn Hiệp - Toán Tin 2 - K54

n (cid:88)

Ví dụ 2.9. a. Với r=1

j=1

p1=1

d1(x) = ωjxj + ωn+1 ωp1xp1 + ωn+1 =

(đa thức bậc 1 là hàm tuyến tính)

n (cid:80) j=1

n (cid:80) p2=p1

n (cid:80) p1=1

n (cid:88)

b. Với r=2 d2(x) = ωjxj + ωn+1 ωp1p2xp1xp2 +

j=1

p2=n

p2=2

p2=1

= ωjxj+ωn+1 ω1p2x1xp2+ ω2p2x2xp2+· · ·+ ωnp2xnxp2+

j + (cid:80)

1≤i

n (cid:80) j=1

n (cid:80) j=1 là dạng toàn phương đã biết.v.v tương tự xây dựng được các đa thức bậc cao hơn.

= ωjxj + ωn+1 ωijxixj + ωjjx2

· · · xsr pr

n+r − 1.

Chú ý: dr(x) là hàm suy rộng với hệ hàm cơ bản sau: {f1(x), · · · , fk(x)} trong đó fi(x) = xs1 với p1, · · · , pr ∈ [1, n],s1, · · · , sr = {0, 1}. p1 Bằng quy nạp có thể chứng minh được số các hệ số của đa thức bậc r : K = C r

2.5.1 Khái niệm về phép lưỡng phân và có ý nghĩa của phép

2.5 Các phép lưỡng phân tập dạng

lưỡng phân

1. Định nghĩa 1

Giả sử cho tập dạng Ω ⊂ Rn, khi đó 1 phép phân hoạch bất kỳ tập Ω ra lamf2 lớp phân bietj được gọi là 1 phép lưỡng phân. Mỗi một lớp được tách ra bởi 1 phép lưỡng phân gọi là 1 phép lưỡng phân (ứng với 1 phép lưỡng phân gọi là 1 lưỡng phân). Phép lưỡng phân được thực hiện bởi 1 siêu phẳng quyết định gọi là 1 phép lưỡng phân tuyến tính, ngược lại ta được phép lưỡng phân phi tuyến.

2. Định nghĩa 2 (Khái niệm tập dạng được phân phối tốt)

Tập dạng Ω ⊂ Rn được gọi là phân phối tốt nếu bất kỳ n+1 dạng nào của Ω cũng đều không cùng thuộc 1 siêu phẳng bất kỳ n-1 chiều.

Giáp Văn Hiệp - Toán Tin 2 - K54

Chú ý : Trong thực tiễn các tập dạng ẫu luôn được chọn sao cho nó được phân phối tốt.

Ví dụ 2.10. Với n=1: Định nghĩa trên có nghĩa là bất kỳ 2 dạng ⊂ cũng đều khôn trùng nhau

Với n=2: Ba dạng bất kỳ ⊂ Ω cũng không thẳng hàng.

Với n=3: Bốn dạng bất kỳ ⊂ Ω cũng không đồng phẳng.

3. Số lượng các lưỡng phân tuyến tính 1 tập dạng

Giả sử ⊂ Rn gồ N dạng, khi đó người ta chứng minh được khẳng định sau:

Số lượng các lưỡng phân tuyến tính tập dạng Ω, ký hiệu là D(N, n) (số dạng, số chiều không gian) và được tính bằng công thức

N −1 khi N > n

n (cid:80) k=1

  2 C k D(N, n) =

 2N khi N ≤ n

Từ khẳng định trên, ta có chú ý sau:

Số lượng tất cả các lưỡng phân (kể cả tuyến tính lẫn phi tuyến) luôn đúng bằng 2N với mọi N,n. (Giả sử 1 phép lưỡng phân bất kỳ chia Ω ra làm 2 lớp Ω1, Ω2 thì Ω_1

có thể đồng nhất với bộ (x1, · · · , xN ) trong đó xi = (cid:26) 1 0 nếuxj ∈ Ω1 nếuxj /∈ Ω1

N −1 > 0, còn trái lại nếu N ≤ n thì có thể tách Ω

n (cid:80) K=0

với Ω = {x1, · · · , xN } ⊂ Rn ) ⇒ Số tất cả các bộ (x1, · · · , xN ) = số tất cả các lưỡng phân Ω = 2N ) Từ đó suy ra: Nếu N>n thì không thể tách Ω bằng tất cả các phép lưỡng phân tuyến tính, vì khi đó số số các lưỡng phân phi tuyến =2N − 2 C K

bằng tất cả các phép lưỡng phân tuyến tính.

4. Một số ví dụ

Ví dụ 2.11. Với n=1, Ω = {x1, · · · , x5} ⊂ R có bao nhiêu phép lưỡng phân tuyến tính

Giáp Văn Hiệp - Toán Tin 2 - K54

Số các phép lưỡng phân tuyến tính phân hoạch Ω sao cho có 1 lưỡng phân không chứa 1 dạng nào đó là 1. Số các phép lưỡng phân tuyến tính phân hoạch sao cho 1 lưỡng phân có chứa đúng 1 dạng là 2. Số các phép lưỡng phân tuyến tính phân hoạch Ω sao cho có 1 lưỡng phân không chứa 2 dạng nào đó là 1. Số các phép lưỡng phân tuyến tính phân hoạch sao cho 1 lưỡng phân có chứa đúng 2 dạng là 2. ⇒ Từ đó suy ra số các lưỡng phân tuyến tính tập Ω là 2(1+2+2)=10 (<25=32)

4 ) = 2(1 + 4) = 10

4 + C 1

4 = 2(C 0

1 (cid:80) K=0 Ví dụ 2.12. Với n=2, Ω = {x1, · · · , x4} ⊂ R2.

Kiểm tra: D(5, 2) = 2 C K

Số các phép lưỡng phân tuyến tính phân hoạch Ω sao cho có 1 lưỡng phân không chứa 1 dạng nào đó của Ω là 1. Số các phép lưỡng phân tuyến tính phân hoạch Ω sao cho 1 lưỡng phân chứa đúng 1 dạng là 4.

Giáp Văn Hiệp - Toán Tin 2 - K54

Số các phép lưỡng phân phân hoạch Ω sao cho 1 lưỡng phân chưa đúng 2 dạng là 2

⇒ Số các lưỡng phân tuyến tính là 2(1+4+2)=14.

3 ) = 2(1 + 3 + 3) = 14

3 + C 2

3 + C 1

3 = 2(C 0

2 (cid:80) K=0

Kiểm tra: D(4, 2) = 2 C K

⇒ Số các lưỡng phân phi tuyến tập Ω là 24-D(4, 2)=16-14=2 chính là phép lưỡng phân tách Ω thành 2 lớp {x1, x3} và {x2, x4} ⇒ phải dùng hàm hi tuyến để tách

5 . Ý nghĩa của phép lưỡng phân.

Các phép lưỡng phân tập dạng dùng để đo khả năng phân biệt lớp dạng bằng các hàm quyết định tuyến tính. Nêu số các dạng của tập Ω (ký hiệu là |Ω| < n), thì có thể phân hoạch Ω bằng tất cả các hàm quyết định tuyến tính. Ngược lại, nếu |Ω| > n thì nó cũng cho ta biết được khả năng dùng tối đa bao nhiêu hàm quyết định tuyến tính để phân hoạch tập dạng

n → K ≥ N = |Ω|

2.5.2 Xác định bậc lưỡng phân bằng hàm suy rộng

để tách tập Ω bằng các hàm quyết định tuyến tính.

1. Thác triển tuyến tính 1 tập dạng bằng hàm suy rộng.

ωifi(x) + ωn+1 là 1 hàm suy rộng nào đó.

Giả sử Ω là 1 tập dạng gồm N dạng trong Rn. Giả sử d = d(x) = K (cid:80) i=1 Khi đó, với mọi x thuộc Ω ta có thể đặt tương ứng với 1 véc tơ x∗ = (f1(x), fk(x), 1)(cid:48) ∈ Rk+1 qua hàm d = d(x) = W(cid:48)x∗, W = (ω1, · · · , ωk+!)(cid:48) và do đó Rn ⊃ Ω → Ω∗ ⊂ Rk Vì vậy thay cho việc xét Ω ta có thể xét Ω∗ ⊂⊂ Rk. Chú ý: Phép thác triển Rn ⊃ Ω → Ω∗ ⊂ Rk qua hàm suy rộng d là phép thác triển tuyến tính vì d đối với Ω là hàm suy rộng phi tuyến, nhưng với Ω∗, d = W(cid:48)x∗, ∀x∗ ∈ Ω∗ lại là hàm tuyến tính. Việc biến tập dạng Ω ⊂ Rn thành tập Ω∗Rk qua hàm suy rộng d được gọi là thác triển tuyến tính tập dạng Ω thành Ω∗.

Giáp Văn Hiệp - Toán Tin 2 - K54

2. Xác định bậc lưỡng phân của Ω∗ qua hàm suy rộng d.

Theo phần trước, số lưỡng các lưỡng phân tuyến tính của Ω trong Rk là

N −1 khi N > n

n (cid:80) k=1

  2 C k D(N, n) =

 2N khi N ≤ n

Từ đó suy ra xác suất PN,K sao cho phương án phân hoạch Ω∗ được lựa chọn 1 cách ngẫu nhiên là phương án lưỡng phân tuyến tính được tính theo công thức

N −1 khiN > K

1 2N −1

K (cid:80) j=0

  C j PN.K =  1 khiN ≤ K

Vậy chỉ khi N ≤ K thì chắc chắn phân hoạch được Ω∗ bằng các phép lưỡng phân tuyến tinh. Do đó để biết được có thể phân hoạch được Ω∗ bằng tất cả các phép lưỡng phân tuyến tính, người ta cần xác định được K, mà K chính là số các hệ số của hàm suy rộng d thác triển Ω thành Ω∗. Vì vậy, người ta gọi số CK = 2(K + 1) là bậc lưỡng phân tập dạng Ω qua hàm suy rộng d.

Ví dụ 2.13. Xây dựng 1 số bậc lưỡng phân qua hàm suy rộng

n+r

Dạng hàm suy rộng 1. Hàm tuyến tính (siêu phẳng) 2. Hàm cầu (siêu cầu) 3. Hàm toàn phương (siêu mặt bậc 2) 4. Hàm đa thức bậc r( siêu mặt đa thức) Bậc lưỡng phân CK = 2(n + 1) CK = 2(2n + 1) CK = (n + 1)(n + 2) CK = 2C r

2.6 Phương pháp xâu dựng hàm tuyến tính trên cơ sở xấp xỉ

2.6.1 Xây dựng hệ trực giao, trực chuẩn các hàm 1 biến

bởi 1 hệ các đa thức trực giao, trực chuẩn

1. Tích vô hướng (TVH) theo trọng số của các hàm

a. Định nghĩa 1:

Giả sử f và g là 2 hàm cùng xác dịnh trên [a, b], u = u(x) là 1

Giáp Văn Hiệp - Toán Tin 2 - K54

hàm xác định dương trên [a, b]. Khi đó , tích phân

(cid:90) u(x)f (x)g(x)dx

được gọi là TVH theo trọng số u của 2 hàm f, g và ký hiệu là (cid:104)f, g(cid:105)u. Vậy theo định nghĩa

(cid:90) u(x)f (x)g(x)dx (cid:104)f, g(cid:105)u =

Nếu u(x) = 1 với mọi x ∈ [a, b] thì (cid:104)f, g(cid:105)u = (cid:104)f, g(cid:105) - TVH theo nghĩa thông thường.

b. Định nghĩa 2:

Đối với f xác định trên đoạn [a, b], đại lượng

(cid:90) u(x)f 2(x)dx (cid:107)f (cid:107)u = (cid:104)f, f (cid:105)u =

ta được được gọi là chuẩn của hàm f theo trọng u. Đặc biệt, nếu (cid:107)f (cid:107)u = 1 thì ta gọi f là hàm chuẩn tắc. Nhận xét: Nếu (cid:107)f (cid:107)u (cid:54)= 0 thì có thể lấy g = f (cid:107)f (cid:107)u

(cid:19)2 (cid:90) u(x) dx = = 1 (cid:107)g(cid:107)u = (cid:107)f (cid:107) (cid:107)f (cid:107) (cid:18) f (x) (cid:107)f (cid:107)u

hàm g được gọi là hàm chuẩn hóa của f . Nói cách khác, bất kỳ 1 hàm nào có chuẩ khác 0 thì đều có thể chuẩn hóa được thành 1 hàm chuẩn tắc.

2. Tính trực giao, trực chuẩn theo trọng của các hàm. Hệ hàm trực

giao, trực chuẩn.

a. Định nghĩa 1: 2 hàm f và g được gọi là trực giao trên [a, b] theo

trọng u nếu

(cid:90) u(x)f (x)g(x) = 0 (cid:104)f, g(cid:105)u =

Giáp Văn Hiệp - Toán Tin 2 - K54

hai hàm trực giao ký hiệu là f ⊥ug Nếu f ⊥ug và (cid:107)f (cid:107)u = (cid:107)g(cid:107)u = 1 thì ta nói f và g là 2 hàm trực chuẩn theo trọng lượng u trên [a, b]

b. Định nghĩa 2:

Hệ hàm Φ= { các hàm φ xác định trên [a, b]} được gọi là hệ hàm trực giao theo trọng u trên [a, b] nếu các hàm của họ Φ trực giao với nhau từng đôi 1 theo trọng lượng u trên [a, b]. Nếu Φ là hệ hàm trực giao, đồng thời (cid:107)φ(cid:107)u = 1, ∀φ ⊂ Φ thì ta nói hệ Φ là hệ trực chuẩn theo trọng u trên [a, b].

c. Một số nhận xét

∗ Mọi hàm trực giao theo trọng có chuẩn của các hàm khác 0

đều có thể chuẩn hóa thành 1 hệ trực chuẩn theo trọng.

∗ Nếu Φ= φj xác định trên [a, b] j ∈ Γ (|Γ| ≤ +∞) thì hệ hàm Φ trực giao trên [a, b] theo trọng u, nếu (cid:104)φi, φj(cid:105)u = Aijδij, ∀i, j ∈ Γ trong đó Aij = (cid:112)(cid:107)φi(cid:107)u(cid:107)φj(cid:107)u, còn δij là ký hiệu Kronecker, tức là

δij = (cid:26) 1 nếu i = j 0 nếu i (cid:54)= j

Từ đó suy ra hệ Φ là hệ trực chuẩn theo trọng u trên [a, b]

j =

⇔ (cid:104)φi, φj(cid:105) = δij, ∀i, j ∈ Γ

(cid:113) u Aj

∗ Hệ trực giao theo trọng u trên [a, b] Φ = {φj, j ∈ Γ} mà (cid:107)φj(cid:107) (cid:54)= 0 luôn có thể biến đổi thành 1 hệ trực chuẩn theo nghĩa thông thường bằng cách đặt φ∗ φj, ∀j ∈ Γ j |j ∈ Γ(cid:9) - hệ trực chuẩn theo nghĩa thông thường ⇒ Φ∗ = (cid:8)φ∗ trên [a, b], trong đó Aj = (cid:107)φj(cid:107)u, ∀j ∈ Γ vì

i , φ∗

j(cid:105) =

i (x)φ∗ φ∗

j(x)dx

(cid:90) (cid:104)φ∗

  (cid:115) (cid:32)(cid:115) (cid:33) (cid:90) = dx φi(x) φj(x)   u(x) Ai u(x) Aj

(cid:90) = u(x)φi(x)φj(x)dx 1 (cid:112)AiAj

Giáp Văn Hiệp - Toán Tin 2 - K54

= (cid:104)φi, φj(cid:105)u = (Aij, δij) = δij, ∀i, j 1 Aij 1 Aij

3. Hệ độc lập tuyến tính (đltt), hệ đầy đủ.

a. Định nghĩa 1: Hệ hàm Φ = {ϕ1, · · · , ϕn cùng xác định trên [a, b]} được gọi là độc lập tuyến tính trên [a, b] nếu tồn tại n hằng số c1, · · · , cn sao cho

c1ϕ1(x) + · · · + cnϕn(x) ≡ 0

với mọi x ∈ [a, b] thì c1 = · · · = cn = 0. Nếu hệ Φ là 1 hệ vô hạn thì ta nói hệ độc lập tuyến tính trên (−∞, +∞) vì với mọi hệ con hữu hạn của nó có tổ hợp tuyến tính là 1 đa thức bậc hữu hạn cho nên độc lập tuyến tính trên (−∞, +∞). Hệ {1, sin x, cos x, sin 2x, cos 2x, · · · , sin nx, cos nx, · · ·} cũng là hệ độc lập tuyến tính trên R = (−∞, +∞)

b. Định nghĩa 2:

Hệ Φ = {φj, j ∈ Γ} gồm các hàm xác định trên [a, b] được gọi là 1 hệ đầy đủ nếu nó độc lập tuyến tính trên [a, b] đồng thời với mọi hàm f liên tục từng khúc trên [a, b] đều có thể xấp xỉ trung bình phương khả tích theo trọng u nào đó bởi 1 hệ con hữu hạn của hệ hàm Φ. Giải thích: Giả sử f là hàm liên tục từng khúc trên [a, b], ta nói gàm f có thể xấp xỉ được theo nghĩa trung bình bình phương khả tích bởi hệ hàm Φ theo trọng u trên [a, b] nếu với mọi ε > 0 đều tồn tại 1 hệ con hữu hạn của hệ hàm Φ, ký hiệu là {Φi1, · · · , Φim} và các hằng số c1, · · · , cm sao cho

m (cid:88)

j=1

(cid:34) (cid:35)2 (cid:90) = u(x) f (x) − dx < ε f − cjφij cjφij (cid:13) (cid:13) (cid:13) (cid:13) (cid:13) (cid:13) (cid:13) (cid:13) (cid:13) (cid:13)u

m (cid:88)

Xấp xỉ đều: Hàm f được gọi là xấp xỉ ddeuf bởi hệ hàm Φ trên [a, b] nếu với mọi ε > 0, tồn tại hệ con {φi1, · · · , φim} ⊂ Φ và các hằng số c1 · · · , cm:

j=1

f (x) − < ε max a≤x≤b (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) cjφij(x) (cid:12) (cid:12)

Giáp Văn Hiệp - Toán Tin 2 - K54

2.7 Xây dựng hệ trực giao, trực chuẩn đầy đủ, các hàm nhiều biến trên cở sở hệ trực giao, trực chuẩn đầy đủ các hàm 1 biến

1. Xây dựng hệ trực giao, trực chuẩn các hàm 2 biến

Giả sử Φ = {φi, j ∈ Γ} là hệ trực chuẩn các hàm 1 biến trên [a, b] theo trọng số u.

⇔ (cid:104)Φi, Φj(cid:105)u = δij, ∀i, j ∈ Γ

Trên cơ sở hệ Φ, ta xây dựng 1 hệ các hàm 2 biến sau:

ϕ = {φ1φ1, φ1φ2, φ2φ1, φ2φ2, φ3φ1, φ3φ2, · · ·}

sao cho ∀ϕi ⊂ ϕ thì ϕi có dạng: ϕi = φ1φ2, ∀i1, i2 ∈ Γ ⇔ ϕi(x) = φi1(x1)φi2(x2), ∀i1, i2 ∈ Γ, x = (x1, x2)T và x ∈ [a, b]2. Với mọi hàm

⇒ ϕi = ϕj ⇔

⇒ ϕi (cid:54)= ϕj ⇔ ϕi = φi1φi2, ϕj = φj1φj2 (cid:26) i1 = j1 i2 = j2 (cid:20) i1 (cid:54)= j1 i2 (cid:54)= j2

Ta sẽ chứng minh ϕ là hệ hàm trực chuẩn đầy đủ trên hình vuông [a, b]2 theo trọng số u∗(x) = u(x1)u(x2). ∀ϕ1, ϕ2 ∈ ϕ ta có: (cid:90)

[a,b]2

(cid:104)ϕi, ϕj(cid:105)u∗ = u∗(x)ϕ1(x)ϕ2(x)dx

x1=a

x2=a

(cid:90) (cid:90) = u(x1)u(x2)φi1(x1)φi2(x2)φj1(x1)φj2(x2)dx1dx2

    (cid:90) (cid:90) = u(x1)φi1(x1)φj1(x1)dx1 u(x2)φi2(x1)φj2(x2)dx2    

= (cid:104)φi1, φj1(cid:105)u(cid:104)φi2, φj2(cid:105)u = δi1j1δi2j2 = δij

⇒ Hệ ϕ là hệ trực chuẩn theo trọng u.

Giáp Văn Hiệp - Toán Tin 2 - K54

2. Xây dựng hệ trực chuẩn các hàm 3 biến

Một các tương tự xuất phát từ hệ Φ ta cũng có thể xây dựng được hệ trực chuẩn các hàm 3 biến trên hình lập phương [a, b]3 theo trong u∗:

u∗(x) = u(x1)u(x2)u(x3), ∀x = (x1, x2, x3)T ∈ [a, b]3

bằng cách đặt

ϕ = {φ1φ1φ1, φ1φ1φ2, φ1φ2φ1, φ1φ2φ2, · · ·}

sao cho ϕi ∈ ϕ thì ϕi có dạng

ϕi = φi1φi2φi3 ⇔ ϕi(x) = φi1(x1)φi2(x2)φi3(x3), ∀i1, i2, i3 ∈ Γ Một cách tổng quát, từ hệ trực chuẩn các hàm 1 biến Φ, ta có thể xây dựng hệ trực chuẩn các hàm n biến trên hình lập phương n chiều [a, b]n theo trọng u∗(x) = u(x1) · · · u(xn) với cách đặt

2.7.1 Xây dựng một số hệ đa thức trực giao, trực chuẩn đầy đỷ 1 biến đặc biệt và áp dụng xây dựng hệ đa thức trực giao, trực chuẩn nhiều chiều.

ϕ = {ϕi(x) = φi1(x) · · · φin(x) |i ↔ (i1, · · · , in) ∈ Γ}

1. Một số hệ đa thức trực giao đặc biệt

a. Hệ Legiesdrer (L)

Là hệ các đa thức trực giao trên [−1, 1] theo trọng u = 1 và được xây dựng theo công thức truy toán:

(1) (k + 1)pk+1(x) − (2k + 1)xpk(x) + kpk−1(x) = 0

trong đó p0(x) = 1, p1(x) = x ((cid:104)pk, pm(cid:105) = Akmδkm) Hệ này trực giao trên [−1, 1]- ( hệ hữu hạn) theo trọng u = 1 và có chuẩn

, ∀k Ak = (cid:107)pk(cid:107) = 2 22k + 1

Ví dụ 2.14. Với k=1, thay vào (1) ta được:

2p2(x) − 3x2 + 1 = 0 ⇒ p2(x) = 3x2 − 1 2

2 + 2x = 0 = 5

Với k=2:

2x3 − x

6 , · · ·

3p3(x) − 5x 3x2−1 ⇒ p3(x) = 15x3−5x+4x

Giáp Văn Hiệp - Toán Tin 2 - K54

Chú ý : i) Từ hệ Legiendrer có thể xây dựng được các đa thức trực chuẩn

(cid:41) (cid:114) (cid:27) (cid:26) Φ = = φk = pk φk(x) = pk(x), ∀k = 1, 2, · · · 2k + 1 2 trên [−1, 1] bằng cách đặt: (cid:40) (cid:114) u Ak

ii) Từ hệ (L) ta cũng có thể xây dựng được hệ đa thức trực giao, trực chuẩn trên [a, b] bất kỳ nhờ phép biến đổi tuyến tính.

[a, b] ↔ [−1, 1] : (cid:26) aα + β = −1 bα + β = 1 x ↔ t = αx + β

⇒ t = x − 2 b − a a + b b − a

⇒ Từ hệ (L) {pk(t), t ∈ [−1, 1], k = 1, 2, · · ·} trực giao trên [−1, 1] xây dựng được hệ trực giao đầy đủ trên [a, b] là

(cid:26) (cid:27) x − ), a ≤ x ≤ b, k = 1, 2, · · · p∗ k(x) = pk( 2 b − a a + b b − a

b. Hệ Lagger

Định nghĩa: Hệ Lagger là hệ các đa thức trực giao trên [0, +∞] theo dạng u = exp(−x) và được xác định bởi công thức truy toán sau:

(2) Lk+1(x) − (2k + 1 − x)Lk(x) + k2Lk−1(x) = 0, k ≥ 1

trong đó L0(x) = 1, L1(x) = 1 − x Ví dụ 2.15. Với k=1:

L2(x) = (3 − x)(1 − x) − 1 = x2 − 4x + 2

Với k=2:

L3(x) = (5 − x)(x2 − 4x + 2) − 4(1 − x) = −x3 + 9x2 − 18x + 6, · · ·

Chú ý: Với mọi Lk ta có Ak = (cid:107)Lk(cid:107)u = (k!)2. Do đó, bằng phép chuẩn hóa từ hệ Lagger ta xác định được hệ các hàm trực chuẩn trên [0, +∞] theo định nghĩa thông thường:

(cid:26) (cid:27) Φ = φk(x) = Lk(x) |k ≥ 0 exp(−x/2) k!

Giáp Văn Hiệp - Toán Tin 2 - K54

c. Hệ Hermit

Định nghĩa: Là hệ đa thức trực giao trong không gian vô hạn −∞, +∞ (trực giao trên R) theo trọng u =exp(−x2) và được xác định bởi công thức truy toán sau:

(3) Hk+1(x) − 2xHk(x) + 2kHk−1(x) = 0, (k ≥ 1)

√

trong đó H0(x) = 1, H1(x) = 2x. Từ đó suy ra: H2(x) = 4x2 − 2 -tam thức bậc 2. H3(x) = 8x3 − 16x -da thức bậc 3. π2kk!, do đó, từ hệ Chú ý : Với mọi Hk ta có Ak = (cid:107)Hk(cid:107)u = Hermit, ta cũng xác định được hệ hàm trực chuẩn thông thường trên −∞, +∞

(cid:41) (cid:40)

Φ = Hk(x), k ≥ 0 φk(x) = exp(−x2(cid:14)2) (cid:112)√ π2kk!

2. Áp dụng xây dựng các đa thức trực giao, trực chuẩn nhiều biến.

Áp dụng phương pháp xây dựng hệ trực giao, trực chuẩn các hàm nhiều biến ở mục trước, từ các hệ đa thực trực giao Lgiendrer, Lag- ger, Hermit luôn có thể xác định các hệ đa thức trực giao, trực chuẩn đầy đủ n biến.

Ví dụ 2.16. Từ hệ Lagiendrer, bawngf cách chọn 2 hàm p0(x) = 1, p1(x) = x. Hãy xác định hệ hàm đa thức trực giao 3 biến. Trên cơ sở đó, xây dựng hàm suy rộng có dạng 1 đa thức bậc 3.

Lời giả: Đặt φ1(t) = p0(t) = 1, φ2(t) = p1(t) = t. Từ đó ta có thể xác định

ϕ1(x) = φ1(x1)φ1(x2)φ1(x3) = 1 ϕ2(x) = φ2(x1)φ2(x2)φ1(x3) = x1 ϕ3(x) = φ1(x1)φ2(x2)φ1(x3) = x2 ϕ4(x) = φ1(x1)φ1(x2)φ2(x3) = x3 ϕ5(x) = φ2(x1)φ2(x2)φ1(x3) = x1x2 ϕ6(x) = φ2(x1)φ1(x2)φ2(x3) = x1x3 ϕ7(x) = φ1(x1)φ2(x2)φ2(x3) = x2x3 ϕ8(x) = φ2(x1)φ2(x2)φ2(x3) = x1x2x3

Giáp Văn Hiệp - Toán Tin 2 - K54

Từ đó có thể xây dựng 1 hàm suy rộng dạng đa thức bậc 3 từ 8 hàm trên:

d(x) = Ax1x2x3 + Bx1x2 + Cx1x3 + Dx2x3 + Ex1 + F x2 + Gx3 + H

1 (cid:90)

Thật vậy, ta có:

t=αx+β =

(cid:90)

k(x)p∗ p∗

e(x)dx

−1

pk(t)pe(t)dt (cid:104)pk, pe(cid:105)[−1,1] =

k, p∗

e(cid:105)[a,b](α =

k, p∗

e(cid:105)[a,b] = 0

= α(cid:104)p∗ ) ⇒ (cid:104)p∗

k(cid:107) = 1

k, k = 0, 1, · · ·}

2k+1. Nghĩa là hệ {p∗

2 (cid:107)pk(cid:107) = 2

2 = b−a

2k+1

2 b − a b−a

k(cid:107) = b−a 2k+1.

khi k (cid:54)= e và (cid:107)p∗ là hệ đa thức trực giao trên [a, b] theo trọng u=1 với (cid:107)p∗

2.8 Phương pháp xây dựng các hàm quyết định dựa trên cở sở xấp xỉ bởi hệ các đa thức trực giao, trực chuẩn.

Giả sử 1 tập dạng Ω ⊂ Rn được phân hoạch thành M lớp Ω1, · · · , ΩM . Để có thể phân lớp Ω cần tới M hàm d1(x), · · · , dM (x). Vấn đề đặt ra: Cần tìm hàm (cid:98)di(x) xấp xỉ trung bình bình phương khả tích hàm di sao cho có thể thay thế các hàm di bằng các hàm (cid:98)di(x) để phân lớp dạng Ω.

Phương pháp tổng quát: Bước 1 : Chọn 1 hệ đa thức trực giao đầy đủ 1 biên Φ (Legiendrer,

Lagger, Hermin,...)

Bước 2 : Xây dựng hệ đa thức trực giao đầy đủ n biến từ Φ , gọi là hệ

ϕ = {ϕi |i}.

Bước 3 : Chọn từ hệ ϕ ra M hàm sao cho đầy đủ, chẳng hạn là

M (cid:88)

{ϕ1, · · · , ϕM }, sau đó đặt:

j=1

cijϕj(x), ∀i = 1, · · · , M (cid:98)di(x) =

trong đó với mỗi i cố định, các hằng dố cij, ∀j = 1, · · · , M sẽ được xác định sao cho

→ min (cid:13) (cid:13) (cid:13)di − (cid:98)di (cid:13) (cid:13) (cid:13)u

Giáp Văn Hiệp - Toán Tin 2 - K54

(cid:107)di − f (cid:107)u (cid:13) (cid:13) (cid:13)di − (cid:98)di = min f tức là (cid:98)di(x) được chọn sao cho (cid:13) (cid:13) (cid:13)u

M (cid:88)

j=1

[a,b]n

(cid:34) (cid:35)2 (cid:90) dx = u(x) di(x) − cijϕj(x) (cid:13) (cid:13) (cid:13)di − (cid:98)di (cid:13) (cid:13) (cid:13)u

Chương 3

Phân lớp dạng bằng các hàm khoảng cách

3.1 Đặc trưng của việc phân lớp dạng bằng các hàm khoảng

3.1.1 Khái niệm khoảng cách, hàm khoảng cách

cách

1. Định nghĩa 1: Xét 1 ánh xạ

D : Rn × Rn → R

(x, z) (cid:55)→ D(x, z)

sao cho các điều kiện sau thỏa mãn: i) D(x, z) ≥ 0∀x, z ∈ Rn và D(x, z) = 0 ⇔ x = z (tính chất xác

định dương của D)

ii) D(x, z) = D(z, x) (tính chất đối xứng) iii) D(x, y) ≤ D(x, z) + D(z, y) (bất đẳng thức tam giác) được gọi là 1 khoảng cách trên Rn.

2. Ví dụ

a. Khoảng cách Euclid:

n (cid:88)

∀x = (x1, · · · , xn)(cid:48), z = (z1, · · · , zn)(cid:48).

2 (xi − zi)

i=1

= (cid:107)x − z(cid:107) = (cid:112)(x − z)(cid:48)(x − z) D(x, z) = (cid:118) (cid:117) (cid:117) (cid:116)

(với (cid:107)x(cid:107) = x2 i ) (cid:115) n (cid:80) i=1

Giáp Văn Hiệp - Toán Tin 2 - K54

n (cid:88)

b. Khoảng cách tổng tuyệt đối

i=1

D(x, z) = |xi − zi|

c. Khoảng cách max

|xi − zi| D(x, z) = max 1≤i≤n

3. Định nghĩa 2:

3.1.2 Đăc trưng của việc phân lớp dạng bằng các hàm khoảng

Nếu cố định z và cho x biến thiên thì ta được hàm Dz(x) = D(x, z) xác định ∀x ∈ Rn và Dz(x) được goi là khoảng cách tâm z biến x.

cách

Đặc trưng của việc phân lớp dạng bằng 1 hàm khoảng cách là việc phân lớp dạng dựa trên nguyên tắc: Xác định "độ gần gũi" của dạng cần được phân lớp với các dạng mẫu được xác định cho từng lớp được phân hoachhj của tập dạng. Trên cơ sở đó, dạng cần được phân lớp sẽ được phân vào lớp nào đó có khoảng cách từ nó đến các dạng mẫu của lớp đó là gần nhất (ngắn nhất) so với các khoảng cách từ nó đến các dạng mẫu của tất cả các lớp còn lại.

Đặc trưng trên còn được gọi là tiêu chuẩn cực tiểu khoảng cách trong

phân lớp dạng.

3.2 Một số phương pháp phân lớp dạng theo tiêu chuẩn cực

3.2.1 Phương pháp 1

tiểu khoảng cách

Phân lớp dạng bằng cách xác định trực tiếp khoảng cách cực tiểu từ

dạng cần được phân lớp đến các dạng mẫu của từng lớp.

1. Trường hợp 1: Mỗi lớp chỉ chứa duy nhất 1 mẫu

a. Xây dựng tiêu chuẩn nhận dạng tổng quát

Giả sử tập dạng Ω ⊂ Rn được phân hoạch thành M lớp Ω1, · · · , ΩM và mỗi lớp có 1 mẫu xác định, chẳng hạn lớp Ωi có mẫu zi, ∀i =

Giáp Văn Hiệp - Toán Tin 2 - K54

1, · · · , M , xác định x là 1 dạng của Ω cần được phân lớp. Theo tiêu chuẩn cực tiểu khoảng cách D(x, zi), ∀i = 1, · · · , M và xác định khoảng cách gần nhất. Từ đó, ta có tiêu chuẩn nhận dạng tổng quát: "Dạng x được phân vào lớp Ωi nếu D(x, zi) < D(x, zj)∀i (cid:54)= j, j = 1, · · · , M , Nếu tồn tại lớp Ωk để D(x, zi) = D(x, zk), còn D(x, zk) < D(x, zj)∀i (cid:54)= j, j (cid:54)= k, j = 1, · · · , M thì dạng x được phân vào Ωi hoăc Ωk tùy ý". Ta có

(cid:48)+(cid:107)zi(cid:107)2

D2(x, zi) = (cid:107)x − zi(cid:107)2 = (x−zi)(cid:48)(x−zi) = (cid:107)x(cid:107)2−x(cid:48)zi−xzi

2(cid:107)zi(cid:107)2, ∀i = 1, · · · , M

= (cid:107)x(cid:107)2 − 2x(cid:48)zi + (cid:107)zi(cid:107)2 = (cid:107)x(cid:107)2 = 2(x(cid:48)zi − (cid:107)zi(cid:107)2) = (cid:107)x(cid:107)2 − 2di(x) 1 2

trong đó di(x) = x(cid:48)zi − 1 Từ đó

D(x, zi) < D(x, zj) ⇔ D2(x, zi) < D2(x, zj) ⇔ (cid:107)x(cid:107)2 − 2di(x) < (cid:107)x(cid:107)2 − 2dj(x) ⇔ di(x) > dj(x)

((cid:107)zi(cid:107)2 − (cid:107)zj(cid:107)2) > 0 dij(x) ≡ di(x) − dj(x) ≡ x(cid:48)(zi − zj) − 1 2

mà dij(x) là những hàm tuyến tính. Vì vậy, việc nhận dạng theo TH1 tương đương với việc phân lớp dạng Ω bằng C 2 M các hàm quyết định tuyến tính dij(x) tương đương với việc tách các lớp Ωi từng đôi 1 bằng các siêu phẳng quyết định dij(x) = 0, ∀1 ≤ i < j ≤ M . Vậy với TH1 ta có tiêu chuẩn nhận dạng sau: "Dạng x được 2((cid:107)zi(cid:107)2 − (cid:107)zj(cid:107)2) > phân vào lớp Ωi nếu dij(x) = x(cid:48)(zi − zj) − 1 0∀j (cid:54)= i, j = 1, · · · , M . Trường hợp nếu tồn tại 1 lớp Ωk sao cho dik(x) = 0 và dkj(x) > 0∀j (cid:54)= k, i và j = 1, · · · , M thì x sẽ được phân vào 1 trong 2 lớp Ωi hoặc Ωk".

b. Ví dụ:

Giả sử tập dạng Ω ⊂ R2 được phân hoạch thành 3 lớp Ω1, Ω2, Ω3 với 3 mẫu tương ứng z1 = (0, 4)(cid:48); z2 = (−5, 1)(cid:48); z3 = (5, 11)(cid:48).

Giáp Văn Hiệp - Toán Tin 2 - K54

2((cid:107)zi(cid:107)2 −

∀1 ≤< j ≤ 3.

Xây dựng các hàm quyết định phân ly dạng Ω. Biết dạng x∗ = (1, 4)(cid:48) ⊂ Ω. Hãy nhận dạng x∗. Lời giải: Xây dựng các hàm quyết định dij(x) = x(cid:48)(zi − zj) − 1 (cid:107)zj(cid:107)2), Ta có:

2(16 − 26) = 5x1 + 3x2 + 5

(cid:19) − 1 d12(x) = x(cid:48)

(cid:19)

2(16 − 26) = 5x1 + 3x2 + 5

d13(x) = x(cid:48)

2(26 − 26) = −10x1

− 1 (cid:19) − 1 d23(x) = x(cid:48) (cid:18) −5 3 (cid:18) −5 3 (cid:18) −10 0

⇒ d12(x∗) = 5.1 + 3.4 + 5 = 22 > 0 d13(x∗) = −5.1 + 3.4 + 5 = 12 > 0

tức là dij(x∗) > 0, ∀j = 2, 3 ⇒ x∗ ∈ Ω1.

c. Chú ý:

Siêu phẳng quyết định

((cid:107)zi(cid:107)2 − (cid:107)zj(cid:107)2) = 0 dij(x) ≡ x(cid:48)(zi − zj) − 1 2

chính là siêu phẳn trung trực của đoạn thẳng [zi, zj] nối 2 mẫu z1, z2 (trong Rn đoạn [zi, zj] = {x ∈ R |x = (1 − t)zi + tzj, 0 ≤ t ≤ 1})

Giáp Văn Hiệp - Toán Tin 2 - K54

Rõ ràng:

(cid:19) (cid:19)(cid:48) (cid:16) = dij (cid:107)zi(cid:107)2 − (cid:107)zj(cid:107)2(cid:17) (zi − zj) − (cid:18)zi + zj 2 (cid:18)zi + zj 2

(cid:16) (cid:16) − = = 0 (cid:107)zi(cid:107)2 − (cid:107)zj(cid:107)2(cid:17) 1 2 (cid:107)zi(cid:107)2 − (cid:107)zj(cid:107)2(cid:17) 1 2 1 2

⇒ Trung điểm đoạn [zi, zj] thuộc siêu phẳng dij(x) = 0 mà véc tơ zi − zj nối 2 đầu mút zi, zj của đoạn [zi, zj] là véc tơ pháp tuyến của siêu phẳng dij(x) = 0 ⇒ (Đá Phải Con Mèo (đpcm)) =))

j, ∀j = 1, · · · , l1, ∀i = 1, · · · , M . Đối với mỗi j), ∀j = 1, · · · , l1 và chọn

2. Trường hợp 2: Mỗi lớp chứa 1 số mẫu nhất định

Giả sử Ωi chứa li mẫu zi lớp Ωi ta tính tất cả các khoảng cách D(x, zi ra 1 khoảng cách ngắn nhất chẳng hạn là:

j), ∀i = 1, · · · , M

D(x, zi D(x, zi li0 ) = min 1≤j≤li

⇒ Chọn được hàm

M hàm quyết định tuyến tính cho phép phân lớp

, ∀i = 1, · · · , M − di(x) = x(cid:48)zi li0 (cid:13) (cid:13)zi (cid:13) li0 (cid:13) 2 (cid:13) (cid:13) 1 2

2(cid:19)

⇒ Chọn ra được C 2 Ω, đó là các hàm:

)− − , ∀1 ≤ i < j ≤ M (3.1) dij(x) ≡ x(cid:48)(zi li0 −zj lj0 (cid:18)(cid:13) (cid:13)zi (cid:13) li0 (cid:13) 2 (cid:13) (cid:13) (cid:13) (cid:13)zj (cid:13) lj0 (cid:13) (cid:13) (cid:13) 1 2

3.2.2 Phương pháp 2

⇒ Tiêu chuẩn nhận dạng: ∀j (cid:54)= i, j = 1, · · · , M , còn nếu tồn "Dạng x ∈ Ωi nếu dij(x) > 0, tại Ωk để dik(x) = 0 và dkj(x) > 0, ∀j (cid:54)= i, j (cid:54)= k, j = 1, · · · , M thì x được phân vào Ωi hoặc Ωk trong các hàm dij(d) được xác định bởi công thức (3.1)".

Phân lớp dạng theo nguyên tắc "người hàng xóm gần nhất."

1. Xây dựng các quy tắc phân ly dạng theo nguyên tắc "người hàng

xóm gần nhất."

Giáp Văn Hiệp - Toán Tin 2 - K54

a. Khái niệm: "Người hàng xóm gần nhất".

M (cid:88)

Giả sử tập dạng Ω ⊂ Rn được phân hoạch làm M lớp Ω1, · · · , ΩM , x là một dạng cần được phân lớp. Từ các lớp đã được phân hoạch của Ω, ta chọn ngẫu nhiên ra 1 mẫu cỡ N dạng, ký hiệu là

i=1

N được gọi là "người hàng xóm gần nhất"

ζN = {x1, · · · , xN } ⊂ Ω = Ωi

Khi đó 1 dạng x∗ ∈ ζ i=1 (nearest neighbour) của dạng x, ký hiệu:

D(x, xj) D(x, x∗) = min 1≤j≤N

b. Xây dựng các quy tắc phây lớp dạng theo nguyên tắc "người

q ∈ ζN sao cho

1, · · · , x∗

hàng xóm gần nhất." Phân lớp dạng theo BS - quy tắc: Quy tắc phân lớp dạng sao cho dạng cần được phân lớp x sẽ được phân vào lớp nào chứa "người hàng xóm gần nhất" của nó được gọi là BS - quy tắc. Phân lớp theo 1- BS-quy tắc: Nếu như tập ζN chỉ chứa duy nhất "1 người hàng xóm gần nhất" của x thì việc phân lớp dạng x theo BS-quy tắc trong trường hợp này được gọi là phân lớp theo 1-BS-quy tắc. Phân lớp theo q-BS-quy tắc: Nếu ζN chứa q "người hàng xóm gần nhất" của x (q > 1) tức là trong ζN tồn tại đúng q dạng, ký hiệu là x∗

∗) = min 1≤j≤N

D(x, xj) D(x, xk

với mọi k = 1, · · · , q thì quy tắc phân lớp dạng x vào lớp chứa số đông nhất "những người hàng xóm gần nhất" của x được gọi là phân lớp theo q-BS-quy tắc.

2. Đánh giá sai số của việc phân ly dạng theo nguyên tắc "người hàng

xóm gần nhất" (Xét với M=2).

a. Sai số phân ly dạng khi được áp dụng 1-BS-quy tắc

Giả sử Ω được phân ra làm 2 lớp Ω1, Ω2. Từ 2 lớp trên đã chọn được tập ζN gồm N dạng. x - dạng cần được phân lớp.

Giáp Văn Hiệp - Toán Tin 2 - K54

Nhận xét: Xác suất pα sao cho phương án lựa chọn ngẫu nhiên α dạng của ζN vào Ω1 và N − α dạng còn lại vào Ω2 được tính theo công thức

pα = C α N 2N

Trong trường hợp này, giải sử x∗ là người hàng xóm gần nhất của x, việc phân x vào lớp Ω1 chỉ sai khi x∗ ∈ Ω2 ⇒ ζN ⊂ Ω2, ký hiệu: pe1 là xác suất sai số hi phân x vào Ω1 thì

pe1 = p0 = C 0 N 2N = 1 2N

2 người.

b. Sai số phân ly dạng khi áp dụng q-BS-quy tắc

(q−1)/2 (cid:88)

Giả sử tập ζN có q "người hàng xóm gần nhất" của x, để cho tiện ta xem q là lẻ. Trong trường hợp này, việc phân x vào Ω1 chỉ có thể sai khi số đông nhất những "người hàng xóm gần nhất" của x thuộc Ω2 ⇔ số những người hàng xóm gần nhất của x thuộc Ω1 chỉ có thể nhiều nhất là q−1 Ký hiệu Bk = { có đúng k người hàng xóm gần nhất của x thuộc vào Ω1}, k = 0, · · · , q−1 2 . B là sự kiện. B = { số người hàng xóm gần nhất của x thuộc Ω1 nhiều nhất là q−1 2 }

k=0

⇒ B = Bk

Vì vậy, nếu ký hiệu peq là xác suất sai số khi phân dạng x vào lớp Ω1 thì

(q−1)/2 (cid:88)

 

k=0

(q−1)/2 (cid:88)

Bk p(Bk) = pk peq = p(B) = p   =

N (< 1)

k=0

= C α C k N 2N = 1 2N

Giáp Văn Hiệp - Toán Tin 2 - K54

3.3 Một số thuật toán phân hoạch tập dạng theo tiêu chuẩn

3.3.1 Khái niệm độ đo đồng dạng và một số độ đo đồng dạng

cực tiểu khoảng cách

tiêu biểu

1. Khái niệm độ đo đồng dạng

Một tập dạng trong Rn được phân hoạch thành M lớp Ω1, · · · , ΩM . theo quy tắc Clasteration, mỗi lớp Ωi thác triển vào trong 1 tập compact Si nào đó gọi là claster. Vói mỗi Si ta xác định 1 tâm (center) zi(i = 1, · · · , M ), (zi có thể là 1 dạng mẫu của Ωi, cũng có thể là "điểm trung tâm" của cả claster S − i). Đối với dạng cần được phân lớp x bất kỳ, ký hiệu là D(x, zi) được gọi là 1 độ đo đồng dạng của x đối với cả lớp Ωi (theo nguyên tắc đồng nhất các tính chất). Theo tiêu chuẩn cực tiểu khoảng cách, rõ ràng khoảng cách D(x, zi) càng ngắn ⇔ độ đồng dạng của x với lớp Ωi càng lớn, x ∈ Ωi nếu nồng độ dạng D(x, zi) là lớn nhất.

2. Một số độ đo đồng dạng tiêu biểu

a. Độ đo đồng dạng được đặc trưng bằng khoảng cách Euclid (độ

n (cid:88)

đo Euclid) Là độ đo được xác định bởi công thức:

i=1

D(x, z) = (xi − zi)2 (cid:118) (cid:117) (cid:117) (cid:116)

∀i = 1, · · · , n.

Độ đo càng lớn ⇔ D(x, z) → 0 ⇔ xi → zi, Khái niệm chuẩn: (D(x, z) = (cid:107)x − z(cid:107))

b. Độ đo được đặc trưng bằng khoảng cách Makhalanobis (độ đo

Makhalanobis) Là độ đo được xác định bởi công thức:

D(x, m) = (x − m)(cid:48)C −1(x − m)

trong đó m- véc tơ bất kỳ của x đối với 1 lớp nào đó, và C là ma trận hiệp biến của x. Độ đo này thường được sử dụng cho tập dạng có phân phối chuẩn.

Giáp Văn Hiệp - Toán Tin 2 - K54

Ví dụ 3.1. Ω là tập gồm các dạng có phân phối chuẩn được phân hoạch thành M lớp Ω1, · · · , ΩM , x là dạng cần được phân lớp. ⇒ Mật độ phân phối xác suất: (cid:26) (cid:27) exp − (x − mi)(cid:48)C −1(x − mi) p(x/Ωi) − 1 2

1 (2a)n/2|det(Ci)|1/2 Khi đó độ đo Makha của x đối với Ωi là:

D(x, mi) = (x − mi)(cid:48)C −1(x − mi) ⇒ Độ đồng dạng của x đối với lớp Ωi càng lớn ⇔ D(x, mi) càng nhỏ ⇔ mật độ phân phối xác suất p(x/Ωi) càng nhỏ và do đó càng có khả nẳng chắc chắn x được phân vào Ωi.

c. Độ đo được xác định bằng góc của dạng cần được phân lớp với

tâm claster. (độ đo góc) Là độ đo được xác định bằng công thức

D(x, z) = cos(x, z) = x(cid:48)z (cid:107)x(cid:107) (cid:107)z(cid:107)

trong đó: x- dạng cần được phân lớp. z- tâm của 1 claster nào đó.

Nhớ lại bất đẳng thức Swarz:

|x(cid:48)z| ≤ (cid:107)x(cid:107) (cid:107)z(cid:107)

Giáp Văn Hiệp - Toán Tin 2 - K54

Lưu ý : Trong trường hợp tổng quá, độ đo thường không chính xác, các độ đo này co ý nghĩa lớn đặc biệt đối với các dạng nhị phân, tức là các dạng: x = (x1, · · · , xn)(cid:48) mà xj nhận các giá trị 0 hoặc 1. Nếu xj = 1 thì ta nói xj là 1 tín hiệu thứ j của x. Ký hiệu: τx = {j |xj = 1} và gọi là tập các tín hiệu của x. |τx| = { Số các chỉ số j sao cho xj = 1} = Số lượng các tín hiệu của x.

Tương tự với tâm z, ta cũng có:

τz = {j |zj = 1}

n (cid:88)

|τz| = Số các tím hiệu của z. ⇒ τx ∩ τz là tập các tín hiệu chung của x và z. ⇒ x(cid:48)z = |τx ∩ τz| là số các tín hiệu chung của x và z.

j=1

n (cid:88)

(cid:107)x(cid:107)2 = x2 j = |τx|

j=1

(cid:107)z(cid:107)2 = z2 j = |τz|

⇒ (cid:107)x(cid:107) (cid:107)z(cid:107) = (cid:112)|τx| |τz|

(trung bình nhân của số các tín hiệu riêng của x và z). Vậy: Độ đo D(x, z) = Tỷ số giữa các tín hiệu chung của dạng cần được phân lớp với tâm với trung bình nhn của các tín hiệu riêng của chúng.

d. Độ đo Tanimoto (Thường đươc dùng trong PLD động vật, thực

vật) Là độ đo được xác định bởi công thức:

D(x, z) = x(cid:48)z x(cid:48)x + z(cid:48)z − x(cid:48)z

Trong TH các dạng nhị phan độ đo nỳ có thể viết dưới dạng

D(x, z) = |τx ∩ τz| |τx| + |τz| − |τx ∩ τz|

Giáp Văn Hiệp - Toán Tin 2 - K54

3.3.2 Một số thuật toán phân hoạch dạng theo tiêu chuẩn cực

tiểu khoảng cách.

1. Thuật toán cực tiểu khoảng cách.

a. Nội dung thuật toán

Giả sử dạng Ω = {x1, · · · , xn} ⊂ Rn. Cần phân hoạch Ω thành từng lớp xác định. Trước hết, ta xác định 1 số T > 0 gọi là ngưỡng phân hoạch (T xác định do thực tế bài toán).

Bước 1: Chọn 1 dạng bất kỳ thuộc Ω làm tâm của 1 lớp nào đó, ký hiệu là Ω1. Chẳng hạn chọn z1 = x1 làm tâm của Ω1. Sau đó, tính D(x1, z1), nếu D(x1, z1) ≤ T thì phn x2 vào Ω1 và xét tiếp D(x3, z1). Ngược lại, nếu D(x1, z1) > T , chuyển sang Bước 2.

Bước 2: Chọn x2 làm tâm của lớp Ω2 và ký hiệu x2 = z2. Sau đó tính khoảng cách D(x3, z1), D(x3, z2).Nếu D(x3, z1) ≤ T hoặc D(x3, z2) ≤ T thì x3 sẽ được phân vào 1 trong 2 lớp Ω1 hoặc Ω2 theo tiêu chuẩn khoảng cách. Ngược lại nếu D(x3, z1) > T và D(x3, z2) > T thì ta chuyển sang Bước 3.

Bước 3: Lấy x3 làm tâm của lớp Ω3 (x3 = z3) và tính các khoảng cách D(x4, zi)∀i = 1, 2, 3 Lặp lại liên tục quá trình trên ta phân hoạch được Ω.

b. Ví dụ áp dụng

Chọn ngưỡng phân hoạch T=3 hoặc T=5. Hãy phân hoạch tập dạng sau: Ω = {(1, 1)(cid:48), (2, 8)(cid:48), (3, 3)(cid:48), (1, 2)(cid:48), (5, 3)(cid:48), (3, 9)(cid:48), (6, 3)(cid:48),

(5, 4)(cid:48), (7, 5)(cid:48), (6, 6)(cid:48)}

Đặt: x1 = (1, 1)(cid:48), x2 = (2, 8)(cid:48), x3 = (3, 3)(cid:48), x4 = (1, 2)(cid:48), x5 = (5, 3)(cid:48), x6 = (3, 9)(cid:48), x7 = (6, 3)(cid:48), x8 = (5, 4)(cid:48), x9 = (7, 5)(cid:48), x10 = (6, 6)(cid:48). b1) Chọn ngưỡng T=3.

√ 12 + 72 = Bước 1 : Chọn z1 = x1 = (1, 1)(cid:48) làm tâm lớp Ω1 (claster Ω1). √ Tính D(x2, z1) = 50 > 3, chuyển sang Bước 2.

Giáp Văn Hiệp - Toán Tin 2 - K54

√ √ 22 + 22 = 12 + 52 = 8 < 3 26 > 3 ⇒ x3 ∈ Ω1.

√ √

02 + 12 = √ 12 + 62 1 < 3 37 > 3 ⇒ x4 ∈ Ω1.

√ √ √ √ 42 + 22 32 + 52

  ⇒ x6 ∈ Ω2 √ √ √  60 > 3 2 < 3 40 > 3 22 + 82 = 12 + 12 = 22 + 62 =

  ⇒ x7 ∈ Ω3 √ √ √ √ √ √  52 + 22 = 42 + 52 = 12 + 02 = 29 > 3 41 > 3 1 < 3

  ⇒ x8 ∈ Ω3 √ √ √ √ √ √  42 + 32 = 32 + 42 = 02 + 12 = 25 > 3 25 > 3 1 < 3

  ⇒ x9 ∈ Ω3 √ √ √ √ √ √ 

  ⇒ chuyển sang Bước 4. 62 + 42 = 52 + 32 = 22 + 22 = √ √ √ 52 > 3 34 > 3 8 < 3 √ √ √  52 + 52 = 42 + 22 = 12 + 32 = 50 > 3 20 > 3 10 > 3 Bước 2 : Lấy z2 = x2 = (2, 8)(cid:48) làm tâm của lớp Ω2. Tính: √ D(x3, z1) = √ D(x3, z2) = Tính: D(x4, z1) = √ D(x4, z2) Tính: 20 > 3 D(x5, z1) = 34 > 3, chuyển sang Bước 3. D(x5, z2) = Bước 3 : Lấy z3 = x5 = (5, 3)(cid:48) làm tâm của lớp Ω3. Tính: √ D(x6, z1) = √ D(x6, z2) = √ D(x6, z3) = Tính D(x7, z1) = D(x7, z2) = D(x7, z3) = Tính: D(x8, z1) = D(x8, z2) = D(x8, z3) = Tính: D(x9, z1) = D(x9, z2) = D(x9, z3) = Tính: D(x10, z1) = D(x10, z2) = D(x10, z3) =

4 (cid:80) j=1

Bước 4 : Lấy z4 = x10 làm tâm của Ω4. Kết thức Ω = Ωj.

Ω1 = {z1, x3, x4} Ω3 = {z3, x7, x8, x9}

Ω2 = {z2, x6} Ω4 = {z4}

Giáp Văn Hiệp - Toán Tin 2 - K54

b2) Chọn ngưỡng T=5

Đệt viết nữa. Tự làm đê =))

Giáp Văn Hiệp - Toán Tin 2 - K54

2. Thuật toán cực đại khoảng cách

a. Nội dung thuật toán

Giả sử tập dạng Ω ⊂ Rn gồm N dạng x1, · · · , xN ,. Ký hiệu: ℵ = {1, · · · , N }. Thuật toán cực đại khoảng cách được thực hiện qua các bước sau:

Bước 1 : Chọn 1 dạng bất kỳ làm tâm của lớp Ω1 nào đó, chẳng hạn, chọn z1 = xj1 làm tâm Ω1, trong đó j1 ∈ ℵ, sau đó chuyển sang Bước 2.

max tức là

Bước 2 : Tính các khoảng cách D(xj), z1 chọn 1 khoảng cách lớn nhất, ký hiệu là d1

D(xj, z1) = D(xj2, z1) d1 max = max j∈ℵ\j1

ta chọn z2 = xj2 làm tâm của lớp Ω2, chuyển sang Bước 3.

j∈ℵ\{j1,j2}

max ≤ 1

2D(z1, z2) thì ta lấy z3 = xj3 làm tâm của Ω3 và

{min {D(xj, z1), D(xj, z2)}} = D(xj3, zi), (i = 1, 2) Bước 3 : Tính tất cả các cặp khoảng cách D(xj, zi)(i = 1, 2) mỗi cặp chọn lấy 1 khoảng cách bé nhất, sau đó chọn 1 khoảng cách lớn nhất vừa được chọn, kêt quả được 1 khoảng cách, ký hiệu là d2 max. Như vậy d2 max = max

Nếu d2 max tạo 1 khoảng cách không đáng kể so với 0.5 khoảng cách giữa 2 tâm (tức là d2 2D(z1, z2)) thì thuật toan kết thúc và Ω được phân hoạch thành 2 lớp Ω1, Ω2, còn sau đó các dạng của Ω được phân vào Ω1, Ω2 theo tiêu chuẩn cực tiểu khoảng cách (tức là xi được phân vào Ω1 nếu D(xi, z1) < D(xi, z2)) và ngược lại thì xi ∈ Ω2. max > 1 Nếu D2 chuyển sang Bước 3.

max, và:

Bước 4 : Tính tất cả các bộ 3 khoảng cách D(xj, zi), i = 1, 2, 3, rồi chọn lấy 1 khoảng cách bé nhất trong tất cả trong mỗi bộ i với D(xj, zi), i = 1, 2, 3, rồi lại chọn lấy 1 khoảng cách lớn nhất, ký hiệu là d3

j∈ℵ\{j1,j2,j3}

{min {D(xj, z1), D(xj, z2), D(xj, z3)}} d3 max = max

Giáp Văn Hiệp - Toán Tin 2 - K54

hay là

d3 max = D(xj4, zi), i = 1, 2, 3

Nếu

(D(z1, z2) + D(z2, z3), D(z3, z1)) d3 max ≤ 1 3

thì thuật tón kết thúc và Ω được phân hoạch thành 3 lớp Ω1, Ω2, Ω3 còn các dạng của Ω sẽ được phân phối vào 3 lớp này theo tiêu chuẩn cực tiểu khoảng cách. Nếu

(D(z1, z2) + D(z2, z3), D(z3, z1)) d3 max > 1 3

thì ta lại lấy z4 − xj4 làm tâm của lớp Ω4 và chuyển sang Bước 5.

Bước 5 :.... Quá trình tiếp tục, thuật toán sẽ kết thúc tại BM +1 nào đó mà ở BM +1 ta tính được

{min {D(xj, zi)}} = D(xjM +1, zi), i = 1, · · · , M dM max = max j∈ℵ\{j1,··· ,jM }

1≤i

mà (cid:88) D(zi, zj), i = 1, · · · , M dM max ≤ 1 C 2 M

(tiêu chuẩn phân hoạch) và Ω được phân hoạch thành M lơp Ω1, · · · , ΩM và các dạng của Ω sẽ được phân vào các Ωi, i = 1, · · · , M theo tiêu chuản cực tiểu khoảng cách.

b. Ví dụ

Lấy lại ví dụ trên, Tập Ω = {(1, 1)(cid:48), (2, 8)(cid:48), (3, 3)(cid:48), (1, 2)(cid:48), (5, 3)(cid:48), (3, 9)(cid:48), (6, 3)(cid:48),

(5, 4)(cid:48), (7, 5)(cid:48), (6, 6)(cid:48)}

Phân hoạch Ω theo tiêu chuẩn cực đại khoảng cách.

Lời giải

Giáp Văn Hiệp - Toán Tin 2 - K54

Bước 1 : Chọn z1 = x1 = (1, 1) làm tâm của Ω1, chuyển sang Bước 2.

Bước 2 : Tính

√ √ 2(cid:9) 36(cid:9) 50, 8, √

53(cid:9) √ √ √ √

40(cid:9) 45(cid:9) 29(cid:9) 32(cid:9) √ 18(cid:9) 50, {D(x2, z1), D(x2, z2)} = (cid:8)√ {D(x3, z1), D(x3, z2)} = (cid:8)√ {D(x4, z1), D(x4, z2)} = (cid:8)1, {D(x5, z1), D(x5, z2)} = (cid:8)√ 20, {D(x7, z1), D(x7, z2)} = (cid:8)√ 29, {D(x8, z1), D(x8, z2)} = (cid:8)√ 25, {D(x9, z1), D(x9, z2)} = (cid:8)√ 52, {D(x10, z1), D(x10, z2)} = (cid:8)√

(thiếu cái thứ 6 tự tính nhá =)))

max = max

√ √ √ √ √ √ √ (cid:110)√ (cid:111) ⇒ d2 2, 8, 1, 20, 29, 25, 32, 18 = 32

= D(x9, z2).

Giáp Văn Hiệp - Toán Tin 2 - K54

Ta có: √ √ < 32 D(z1, z2) = 1 2

68 2 do đó chọn z3 = x9 làm tâm của Ω3.

max = max (cid:8)√

√ √ √ √ √ √ √ 20, 40, 8}, √ √ 36, √ 53, √ 2, 45, 8, 25, √ 29, √ Bước 4 : Tính √ √ √ { 34}, { 50, √ √ √ 5}, { 29, { ⇒ d3 20}, {1, √ √ 5}, { √ √ 5, 50, √ 5, 18, 2(cid:9) = 45}, { √ 2} √ 8 8, 1,

8, 2, = D(x3, z1) = D(x5, z3)

Tính √ √ (cid:16)√ (cid:17) 68 + 32 + 52 > 8 1 3

⇒ thuật toán dừng và Ω được phân hoạch thành 3 lớp Ω1, Ω2, Ω3. Ω1 = {z1, x4, x3} Ω2 = {z2, x2} Ω3 = {z3, x5, x7, x8, x10

3. Thuật toán phát hiện tâm claster (thuật toán K-trung bình nội

nhóm)

a. Tâm và tiêu chuẩn nhận biết tâm

• Định nghĩa

Giả sử S là 1 claster chứa 1 lớp dạng nào đó của tận dạng Ω ⊂ Rn. Ta nói rằng điểm z0 ∈ S là tâm của S (z0 cũng được gọi là tâm của lớp dạng chứa S) nếu nó đảm bảo cực tiểu hóa tổng các bình phương khoảng cách từ tất cả các dạng của Ω nằm trong S. Nói cách khác, nếu đặt

x∈S∩Ω

(cid:88) f (z) = D2(x, z)

tổng bình phương các khoảng cách của tất cả các dạng Ω ⊂ S → z thì z0 là tâm ⇔ f (z0) = minf (z). Ví dụ 3.2. Với n = 1, S = [a, b] chứa 2 dạng a và b của tập dạng Ω ⊂ R.

Giáp Văn Hiệp - Toán Tin 2 - K54

Đặt f (x) = (x − a)2 + (x − b)2 Tìm min f (x)

f (x) = 2x2 − 2(a + b)x + a2 + b2

(cid:18) (cid:19)2 = 2 x − + a2 + b2 −

a + b 2 (cid:19)2 (cid:18) , ∀x ∈ R ≥ = 2 x − + (a + b)2 2 (a − b)2 2 (a − b)2 2

a + b 2 ⇒ min f (x) = (a−b)2 đạt được tại x0 = a+b 2 . Vậy tâm của S là a+b 2 .

• Tiêu chuản nhận biết tâm

|S∩Ω|

x z0 là tâm của claster S ⇒ z0 = 1 (cid:80) x∈S∩Ω

⇔ z0 là điểm bình cộng của tất cả các dạng của Ω thuộc S.

b. Nội dung thuật toán phát hiện tâm claster.

Giả sử bằng các thuật toán phân hoạch tập dạng Ω đã biết, ta đã phân hoạch được Ω ra làm K lớp Ω1, · · · , ΩK với các tâm tương ứng là z1, · · · , zK. Đây là 1 thuật toán lặp bao gồm 1 số bước lặp cơ bản sau:

Bước 1 : Ký hiệu các lớp và các tâm bởi các ký hiệu:

Ωi = Ωi(1), zi = zi(1), ∀i = 1, · · · , K.

Giáp Văn Hiệp - Toán Tin 2 - K54

Các dạng của Ω được phân hoạch vào các lớp Ωi(1) theo các "tâm" zi(1), ∀i = 1, · · · , K theo tiêu chuẩn cực tiểu khoảng cách, chuyển sang Bước 2.

Bước 2 : Tính

x∈Ω1(1)

(cid:88) x, ∀i = 1, · · · , K zi(2) = 1 |Ωi(1)|

Nếu zi(2) = zi(1)∀i = 1, · · · , K thì thuật toán kết thúc. Ngược lại, lấy zi(2) làm tâm của các lớp Ωi và phân phối lại các dạng của Ω vào các lớp Ωi theo tâm zi(2) và được các lớp mới:

∀i = 1, · · · , K Ωi = Ωi(2),

và chuyển sang Bước 3.

Bước 3 : Tính

x∈Ω1(2)

(cid:88) x, ∀i = 1, · · · , K zi(3) = 1 |Ωi(2)|

Nếu zi(3) = zi(2), ∀i = 1, · · · , K thì thuật toán kết thúc. Ngược lại, xem zi(3) làm tâm mới của các Ωi, phân phối lại các dạng của Ω vào các Ωi theo tâm zi(3) để được các lớp

Ωi = Ωi(3), ∀i = 1, · · · , K

và chuyển sang Bước 4. v.v... Ví dụ 3.3 (Ví dụ áp dụng). Cho Ω = {(0, 0)(cid:48), (1, 0)(cid:48), (0, 1)(cid:48), (1, 1)(cid:48) (2, 1)(cid:48), (1, 2)(cid:48), (2, 2)(cid:48), (3, 2)(cid:48), (6, 6)(cid:48), (7, 6)(cid:48), (8, 6)(cid:48), (6, 7)(cid:48), (7, 7)(cid:48), (8, 7)(cid:48) (9, 7)(cid:48), (7, 8)(cid:48), (8, 8)(cid:48), (9, 8)(cid:48), (8, 9)(cid:48), (9, 9)(cid:48)} Giả sử đã biết Ω được phân làm 2 lớp Ω1, Ω2, (K = 2). Xác định tâm của 2 lớp này.

Giáp Văn Hiệp - Toán Tin 2 - K54

Lời giải:

Bước 1 : Chọn z1(1) = (0, 0)(cid:48), z2(1) = (1, 0)(cid:48) làm tâm của 2 lớp Ω1, Ω2 tương ứng. ⇒ Ω1 = Ω1(1) = {z1(1) = (0, 0)(cid:48), (0, 1)(cid:48)} và Ω2 = {z2(1) = (1, 0)(cid:48), (1, 1)(cid:48), · · · , (9, 9)(cid:48).

Bước 2 : Tính (cid:19) (cid:19) = z1(2) =

(cid:19) (cid:19) = z2(2) = (cid:18) 0 1 1 2 (cid:18) 102 96 (cid:18) 0 1/2 (cid:18) 5.67 5.33 1 18

Sau đó, phân các dạng của Ω vào 2 lớp theo tâm mới được.

Ω1 = Ω1(2) = {(0, 0)(cid:48), · · · , (3, 2)(cid:48)} Ω2 = Ω2(2) = {(6, 6)(cid:48), · · · , (9, 9)(cid:48)}

và chuyển sang Bước 3.

Giáp Văn Hiệp - Toán Tin 2 - K54

Bước 3 : Tính

(cid:19) (cid:19) = z1(3) = 1 8

(cid:19) (cid:19) = z2(3) = 1 12 (cid:18) 10 9 (cid:18) 92 88 (cid:18) 1.25 1.10 (cid:18) 7.67 7.33

phân phối lại:

Ω1(3) = {(0, 0)(cid:48), · · · , (3, 2)(cid:48)} = Ω1(2) Ω2(3) = {(6, 6)(cid:48), · · · , (9, 9)(cid:48)} = Ω2(2)

⇒ thuật toán kết thúc.

Chương 4

Phân lớp dạng bằng các hàm xác suất

4.1 Phân lớp dạng như là một bài toán về lý thuyết các phép

4.1.1 Xác định bài toán phân lớp dạng như là 1 trò chơi mang

giải thống kê

đặc trưng thống kê.

1. Định nghĩa trò chơi 2 mặt với tổng không.

Một trò chơi mà phần thắng của 1 người tham gia (đối thủ) về giá trị chính xác bằng phần thua của 1 người tham gia khác được gọi là trò chơi 2 mặt với tổng không.

2. Mô hình toán học.

Một cách tổng quát, mô hình toán học cho trò chơi 2 mặt với tổng không là 1 bộ ba (L, Y, Z) trong đó Y là tập các chiến lược của đối thủ A được sử dụng trong cuộc chơi, Z là tập các chiến lược của đối thủ B, còn L là 1 hàm thực xác định trên tập Y × Z(L, Y, Z → R) được gọi là hàm thẳng (hàm tổn thất- hàm này thay đổi tùy thuộc vào tính chất trò chơi) sao cho ứng với cặp chiến lược (y, z) ∈ Y × Z, giá trị L(y, z) chính là phần thắn của đối thủ A thu được từ B nếu B thua A, hay là phần tổn thất của B phải trả cho A khi thua. TH nếu Y = {y1, · · · , hm}, Z = {z1, · · · , zn} thì ta có thể xác định được ma trận

L = (Ly)m×n, Ly = L(yi, zj)

L được gọi là ma trận thắn (ma trận ccs tổn thất)

Giáp Văn Hiệp - Toán Tin 2 - K54

3. Áp dụng quy luạt trò chơi 2 mặt với tổng không vào việc phân lớp

dạng theo nghĩa xác suất.

a. Định nghĩa bài toán phân lớp dạng theo nghĩa xác suất.

Bài toán phân lớp dạng theo nghĩa xác suất là bài toán xác định lời giải tối ưu nhằm đảm bảo cực tiểu hóa các độ tổn thất trung bình hay là độ mạo hiểm trung bình trong việc phân lớp dạng.

Giải thích: Giả sử Ω là 1 tập dạng cho trước nào đó và đã được phân thành M lớp Ω1, · · · , ΩM , x là 1 dạng của Ω cần được phân lớp. Nếu hệ nhận dạng tự động phân x vào lớp Ωi nhưng thực tế x thuộc Ωj khác thì việc phân sai x vào lớp Ωi gay ra 1 tổn thất cho hệ nhận dạng. Do đó, nếu bài toán phân lớp dạng tìm được lời giải tối ưu có nghĩa là dạng x sẽ được phân vào lớp nào đó có độ tổn thất trung bình (kỳ vọng theo nghĩa xác suất) cho lớp đó là thấp nhất so với tất cả các lớp còn lại.

b. Xây dựng công thức tính các độ tổn thất trung bình trong việc

phân lớp dạng. Ta coi đối thủ A là môi trường phân lớp (không gian Rn chứa tập dạng Ω) và có tập các chiến lược Y = {Ω1, · · · , ΩM . Đối thủ B là hệ nhận dạng tự động với tập các chiến lược Z = {zj}, zj là chiến lược phân dạng x vào lớp Ωj. Nếu đối thủ A chọn chiến lược y1, tức là x ∈ Ω1, còn B chọn chiến lược zj ⇔ được phân vào Ωj thì việc phân x vào Ωj gây ra 1 tổn thất L1j cho B ứng với xác suất phân lớp đúng p(Ω1/x).

Nếu A chọn chiến lược y2 ⇔ thực tế x ∈ Ω2 còn B chọn chiến lược zj thì việc phân x vào Ωj gây ra một tổn thất L2j cho B ứng với xác suất phân vào lớp đúng p(Ω2|x). Nếu A chọn chiến lược yM ⇔ thực tế x ∈ ΩM mà B vẫn chọn zj thì việc phân x vào Ωj gây ra 1 tổn thất LM j cho B ứng với xác suất phân lớp đúng p(ΩM |x). Từ đó suy ra, có thể xem zj là 1 biến ngẫu nhiên rời rạc nhận các giá trị Lij ⇔ p(Ωi|x), ∀i = 1, · · · , M tương đương với bảng

Giáp Văn Hiệp - Toán Tin 2 - K54

phân phối xác xuất.

· · · zj LM j L1j

L2j p(zj) p(Ω1 |x) p(Ω2 |x) · · · p(ΩM |x)

M (cid:88)

⇒ độ tổn thất trung bình của việc phân x vào lớp Ωj được tính bằng công thức:

i=1

4.1.2 Xây dựng tiêu chuẩn nhận dạng cho việc phân lớp dạng

rj(x) = Lijp(Ωi |x), ∀j = 1, · · · , M

theo nghĩ xác suất.

1. Định nghĩa quy tắc phân lớp Bayets và khối phân lớp Bayets.

a. Quy tắc phân lớp Bayets:

Quy tắc phân lớp mà theo đó dạng cần được phân vào lớp nào đó có độ tổn thất trung bình là thấp nhất so với các độ tổn thất trung bình của các lớp còn lại được gọi là quy tắc phân lớp Bayets.

b. Khối phân lớp Bayets:

Khối phân lớp mà đảm bảo cực tiểu hóa các độ tổn thất trung bình cho bài toán phân lớp dạng theo nghĩa xác suất được gọi là khối phân lớp Bayets.

2. Tiêu chuẩn nhận dạng theo quy tắc phân lớp Bayets.

a. Xây dựng tiêu chuẩn nhận dạng trong trường hợp chỉ có 2 lớp

2 (cid:88)

dạng. Giả sử tập dạng Ω được phân thành 2 lớp Ω1, Ω2. x là dạng cần được phân lớp. Ta có công thức độ tổn thất trung bình là:

i=1

rj(x) = Lijp(Ωi |x), j = 1, 2

Theo tiêu chuẩn nhận dạng theo Bayets là: "x ∈ Ω1 nếu r1(x) < r2(x), x ∈ Ω2 nếu r1(x) > r2(x). Trường hợp nếu r1(x) = r2(x)

Giáp Văn Hiệp - Toán Tin 2 - K54

thì x được phân tùy ý vào 1 trong 2 lớp". Ta có:

p(Ωi |x) = p(x |Ωi )p(Ωi) p(x)

2 (cid:88)

Vậy

i=1

< r1 < r2 ⇔ Li1 Li2 p(x |Ωi )p(Ωi) p(x) p(x |Ωi )p(Ωi) p(x)

i=1 (cid:26) 1 nếui = j 0 nếui (cid:54)= j

ij = nên ta có:

L11p(x |Ω1 )p(Ω1) + L21p(x |Ω2 )p(Ω2) < L12p(x |Ω1 )p(Ω1)

+L22p(x |Ω2 )p(Ω2).

⇔ (L12 − L11)p(x |Ω1 )p(Ω1) > (L21 − L22)p(x |Ω2 )p(Ω2)

Vì L11 − L12 > 0 và L21 − L22 > 0 nên

⇔ ≡ r12(x) > = θ12 p(x |Ω1 ) p(x |Ω2 ) L21 − L22 L12 − L11 p(Ω2) p(Ω1)

gọi là ngưỡng phân lớp cho 2 lớp Ω1, Ω2. Vậy ta có tiêu chuển nhận dạng trong trường hợp 2 lớp là: "x sẽ được phân vào lớp Ω1 nếu tỷ số giữa 2 mật độ phân phối xác suát r12(x) > θ12, ngược lại nếu r12(x) < θ12 thì x được phân vào Ω2, nếu r12(x) = θ12 thì x sẽ được phân tùy ý vào 1 trong 2 lớp."

b. Xây dựng tiêu chuẩn nhận dạng tổng quát.

M (cid:88)

Giả sử tập dạng Ω được phân hoạch làm M lớp Ω1, · · · , ΩM , x là 1 dạng cần được phân lớp của Ω. Với mỗi lớp Ω1, ta có độ tổn thất trung bình tương ứng:

k=1

r1(x) = Lkip(Ωk |x), ∀i = 1, · · · , M

Theo tiêu chuẩn phân lớp Bayets, ta có tiêu chuẩn nhận dạng: "x được phân vào lớp Ωi nếu ri(x) < rj(x), ∀j (cid:54)= i, j (cid:54)= k thì x sẽ được phân vào 1 trong 2 lớp Ωi hoặc Ωk".

Giáp Văn Hiệp - Toán Tin 2 - K54

c. Chú ý

Trong thực tế, các xác suát p(Ωk|x) thường được chuyển sang mật độ phân phối xác suất.

p(x |Ωk )p(Ωk) = p(Ωk |x)p(x)

⇒ p(Ωk |x) = p(x |Ωk )p(Ωk) p(x)

M (cid:88)

Khi đó: ri(x) < rj(x) tương đương với

m=1

k=1

M (cid:88)

< Lki Lmj p(x |Ωk )p(Ωk) p(x) p(x |Ωm )p(Ωm) p(x)

m=1

k=1

Lkip(x |Ωk )p(Ωk) < Lmjp(x |Ωm )p(Ωm), ∀j (cid:54)= i, j = 1, · · · , M

M (cid:88)

Trường hợp các xác suất tiên nghiệm như nhau thì

m=1

k=1

Lkip(x |Ωk ) < Lmjp(x |Ωm ), ∀j (cid:54)= i, j = 1, · · · , M

4.1.3 Large Xây dựng các hàm quyết định phân lớp dạng theo quy tắc

phân lớp Bayets

Có thể phát biểu: x được phân vào lớp Ω...

Trong thực tế nhận dạng, người ta thường quy ước các độ tổn thất là những hằng số, đặc trưng chung cho cả 1 không gian dạng, do đó người ta thường chọn đặc biệt.

Độ tổn thất

Lij = (cid:26) 1 nếu i = j 0 nếu i (cid:54)= j

- ký hiệu: Kronecker δij = ⇒ Lij = 1 − δij trong đó (cid:26) 1 nếu i = j 0 nếu i (cid:54)= j

M (cid:88)

Khi đó, độ tổn thất trung bình

k=1

ri(x) = Lkip(Ωk |x) = (1 − δki)p(Ωk |x)

Giáp Văn Hiệp - Toán Tin 2 - K54

M (cid:88)

k=1

= p(Ωk |x) − p(Ωi |x) = 1 − p(Ωi |x) = 1 − p(x |Ωi )p(Ωi) p(x)

Vậy ri(x) < rj(x) tương đương với

p(x |Ωi )p(Ωi) > p(x |Ωj )p(Ωj)

(cid:34)

p(x|Ωj ) > p(Ωj)

p(Ωi) = θij

⇔ dij(x) = p(x |Ωi )p(Ωi) − p(x |Ωj )p(Ωj) > 0 (cid:102)dij(x) = p(x|Ωi )

Vì vậy có thể chọn hàm quyết định phân lớp dạng theo quy tắc Bayets là hệ hàm (cid:34)

p(x|Ωj ), 1 ≤ i < j ≤ M

dij(x), 1 ≤ i < j ≤ M (cid:102)dij(x) = p(x|Ωi )

Trường hợp đặc biệt: Các xác suất tiên nghiệm bằng nhau thì δij = 1, ∀i, j, do đó có thể chọn các hàm quyết định

, ∀1 ≤ i < j ≤ M dij(x) = ln p(x |Ωi ) p(x |Ωj )

Khi đó tiêu chuẩn nhận dạng là: "nếu x ∈ Ωi nếu dij > 0, ∀j (cid:54)= i, j = 1, · · · , M ...".

4.2 Phân lớp dạng theo quy tắc phân lớp Bayets trong trường

4.2.1 Nhắc lại đặc trưng của các biến ngẫu nhiên có phân phối

hợp các dạng tuân theo luật phân phối chuẩn

chuẩn

1. Đối với biến ngẫu nhiên 1 chiều

Biến ngẫu nhiên 1 chiều x được gọi là kỳ vọng ( trị trung bình củ biến ngẫu nhiên x), σ là độ lệch chuẩn nếu mật độ phân phối xác suất của nó có dạng

(cid:40) (cid:41)

√ exp − p(x) = (x − σ)2 σ2 1 2 1 2πσ

2. Đối với biến ngẫu nhiên n chiều

Giáp Văn Hiệp - Toán Tin 2 - K54

Biến ngẫu nhiên n chiều x = (x1, · · · , xn)(cid:48) ∈ Rn được gọi là tuân theo luật phân phối chuẩn (có phân phối chuẩn) với kỳ vọng m = (m1, · · · , mn)(cid:48) và ma trận hiệp biến:

C = E {(x − m)(x − m)(cid:48)} = (cij)n×n cij = E {(xi − mi)(xj − mj)}

là ma trận đối xứng, xác định dấu.

Nếu mật độ phân phối xác suất của nó có dạng

i (x − mi)

(cid:27) (cid:26) p(x) = exp − (x − mi)C −1 1 2 1 (2π)n/2|det(ci)|1/2

Trường hợp phải hạn chế x trên 1 lớp Ωi được tính theo công thức

i (x − mi)

(cid:26) (cid:27) exp − p(x |Ωi ) = (x − mi)C −1 1 2 1 (2π)n/2|det(ci)|1/2

4.2.2 Xây dựng tiêu chuẩn nhận dạng, hàm quyết định theo quy tắc phân lớp Bayets có các dạng có phân phối chuẩn

trong đó mi = (mi1, · · · , min) là kỳ vọng của x hạn chế trên Ωi tức mik = E(xk|Ωi), ∀k = 1, · · · , n và Ci = E{(x − mi)(x − mi)(cid:48)}.

1. Xây dựng tiêu chuẩn nhận dạng

Trong trường hợp tổng quát, ta có tiêu chuẩn nhận dạng. Giả sử Ω được phân hoạch thành M lớp Ω1, · · · , ΩM , x là dạng cần được phân lớp thì x ∈ Ωi nếu

> (4.1) = θij, ∀j (cid:54)= i, j = 1, · · · , M (cid:101)dij(x) = p(x |Ωi ) p(x |Ωj ) p(Ωj) p(Ωi)

Do x có phân phối chuẩn nên

i (x − mi)

(cid:26) (cid:27) exp − p(x |Ωi ) = (x − mi)C −1 1 2 1 (2π)n/2|det(ci)|1/2

với mọi i = 1, · · · , M . Khi đó (4.1) tương đương với

i (x − mi)

ln − (x − mi)C −1 1 2 1 2 (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) det(Cj) det(Ci)

Giáp Văn Hiệp - Toán Tin 2 - K54

j (x − mj) − αij > 0

+ 1 2

j − C −1

i )x

⇔ ln x(cid:48)(C −1 − αij + 1 2 1 2 (x − mj)(cid:48)C −1 (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) det(Cj) det(Ci)

jC −1

iC −1

j mj −

i mi > 0

i mi − C −1

j mj) +

m(cid:48) m(cid:48) +x(cid:48)(C −1 1 2 1 2

Do đó nếu đặt

j − C −1

i )x + x(cid:48)(C −1

i mi − C −1

j mj)

x(cid:48)(C −1 dij(x) =

iC −1

jC −1

i mi)

j mj − m(cid:48)

+ ln (m(cid:48) (4.2) − αij + 1 2 (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) 1 2 det(Cj) det(Ci)

1 2 thì ta thu được C 2 M hàm quyết định dạng toàn phương (đa thức bậc 2 n biến) dij(x)∀1 ≤ i < j ≤ M cho phép phân lớp tập dạng Ω và thỏa mãn tiêu chuẩn nhận dạng: "x ∈ Ωi nếu dij(x) > 0∀j (cid:54)= i, j = 1, · · · , M . Trường hợp tồn tại Ωk : dik(x) = 0 và dkj(x) > 0∀j (cid:54)= k(j (cid:54)= i)j = 1, · · · , M thì x được phân vào 1 trong 2 lớp Ωi hoặc Ωk".

2. Các trường hợp đặc biệt

a. Các ma trận hiệp biến như nhau:Ci = C, ∀i = 1, · · · , M .

Trong trường hợp này, các hàm quyết định phân lớp dạng có dạng:

dij(x) = x(cid:48)C −1(mi − mj) − (mi + mj)(cid:48)C −1(mi + mj) − αij (4.3) 1 2

với 1 ≤ i < j (cid:54)= M , là các hàm quyết định tuyến tính. Đặc biệt hơn nữa, các xác suát tiên nghiệm bằng nhau (p(Ωi) = 1 M , ∀i = 1, · · · , M ) thì ta có:

dij(x) = x(cid:48)C −1(mi−mj)− 1 2 (mi+mj)C −1(mi−mj), 1 ≤ i < j ≤ M (4.4)

b. Ví dụ áp dụng

Giả sử Ω ⊂ R3 là tập các dạng được phân hoạch thành 2 lớp Ω1, Ω2 với 1 số dạng mẫu sau:

Ω1 = {(0, 0, 0)(cid:48), (1, 0, 0)(cid:48), (1, 0, 1)(cid:48), (1, 1, 0)(cid:48)} Ω2 = {(0, 0, 1)(cid:48), (0, 1, 0)(cid:48), (0, 0, 1)(cid:48), (1, 1, 1)(cid:48)}

Giáp Văn Hiệp - Toán Tin 2 - K54

sử dụng quy tắc phân lớp Bayets, xác định tiêu chuẩn nhận dạng, hàm quyết định, mặt quyết định cho phép phân lớp Ω. Lời giải: Giả sử x là 1 dạng của Ω cần được phân lớp, ta có 2 kết quả sau (chứng minh sau): x được phân vào lớp Ωi thì kỳ vọng

x∈Ωi

(cid:88) x mi = 1 |Ωi|

ma trân hiệp biến

(cid:101)x∈Ωi

(cid:88) Ci = (cid:101)x(cid:101)x(cid:48) − mim(cid:48) 1 |Ωi|

• Xét Ω1    

m1 =    =  1 4 3/4 1/4 1/4 3 1 1

    

(cid:0) 1 0 0 (cid:1) (cid:0) 0 0 0 (cid:1) + C1 =      1 4 1 0 0 0 0 0

    

(cid:0) 1 1 0 (cid:1) (cid:0) 1 0 1 (cid:1) + +     

1 1 0 1 0 1

 

− (cid:0) 3 1 1 (cid:1)   1 16

3 1 1    

=  −    1 4 1 16 3 1 1 1 1 0 1 0 1 9 3 3 3 1 1 3 1 1

 

−1

  = 1 16 3 1 1 −1 1 1 3 −1 3

 

1 = 16

C −1 = 16A−1  

3 1 1 −1 1 1 3 −1 3

Giáp Văn Hiệp - Toán Tin 2 - K54

 

= 16   1 det(A)

 D11 −D21 D31 −D12 D22 −D32 D13 −D23 D33   

= 16    =  1 16 8 −4 −4 4 8 −4 8 4 −4 8 −4 −4 4 8 −4 8 4 −4

Vậy ta có:

  

1 =

   , C −1   , m1 = 1 4 3 1 1 8 −4 −4 4 8 −4 8 4 −4

 

C1 =   1 16 3 1 1 −1 1 1 3 −1 3

• Xét Ω2:  

  m2 = 1 4 1 3 3     

(cid:0) 0 1 0 (cid:1) + (cid:0) 0 0 1 (cid:1) + C2 =      1 4 0 0 1

0 1 0       

(cid:0) 1 1 1 (cid:1) (cid:0) 0 1 1 (cid:1) + (cid:0) 1 3 3 (cid:1) −       1 16 0 1 1 1 3 3

  

   1 1 1   − 1 16 = 1 4 1 3 3 3 9 9 3 9 9  

  = C1 = 1 16

1 1 1 1 3 2 1 2 3 1 1 3 3 −1 1 3 1 −1  

2 = C −1

1 =

⇒ C −1  

8 −4 −4 4 8 −4 8 4 −4 Để tiện tính toán, ta giả thiết thêm các xác suất tiên nghiệm bằng nhau, tức là p(Ω1) = p(Ω2) = 0.5. Từ lý thuyết tổng

Giáp Văn Hiệp - Toán Tin 2 - K54

quát, áp dụng cho ví dụ ⇒ hàm quyết định cho phép phân lớp Ω có dạng:

d12(x) = x(cid:48)C −1(m1 − m2) − (m1 + m2)(cid:48)C −1(m1 + m2) 1 2

   

(cid:1) ⇔ d12(x) = (cid:0) x1 x2 x3     1 4 2 −2 −2 8 −4 −4 4 8 −4 8 4 −4

   

− (cid:0) 1 1 1 (cid:1)     1 2 1 4 2 −2 −2

 8 −4 −4 4 8 −4 8 4 −4   

(cid:1) = (cid:0) x1 x2 x3    

2 −2 −2 2 −1 1 1 2 −1 2 1 −1

   

− (cid:0) 1 1 1 (cid:1)     1 2 2 −2 −2

2 −1 −1 1 2 −1 −1 2 1 = 8x1 − 8x2 − 8x3 + 4

Tiêu chuẩn nhận dạng: x được phân vào lớp Ω! nếu 2x1 − 2x2 − 2x3 + 1 > 0 và được phân vào lớp Ω2 nếu 2x1 − 2x2 − 2x3 + 1 < 0. Mặt quyết định tách 2 lớp Ω1, Ω2 chính là mặt phẳng 2x1 − 2x2 − 2x3 + 1 = 0.

Giáp Văn Hiệp - Toán Tin 2 - K54

4.3 Một số đánh giá xác suất sai số của phân lớp Bayets trong

4.3.1 Đánh giá sai số của phân lớp Bayets trong trường hợp

một số trường hợp đặc biệt

phân phối chuẩn

Giả sử tập dạng Ω ⊂ Rn là tập gồm các dạng có phân phối chuẩn với cùng 1 ma trạn hiệp biến C được phân thành M lớp Ω!, · · · , ΩM , tức là nếu x ∈ Ω thì x có mật độ phân phối xác suất đối với từng lớp Ωi là

(cid:26) (cid:27) exp − p(x |Ωi ) = (x − mi)(cid:48)C −1(x − mi) 1 2 1 (2π)n/2|det(C)|1/2

1. Xây dựng công thức tính logarit của tỷ số giữa 2 mật độ phân phối

xác suất đối với 2 lớp dạng Đối với 2 lớp Ωi, Ωj bất kỳ, ta có:

uij := uij(x) = ln p(x |Ωi ) p(x |Ωj )

= − (x − mi)(cid:48)C −1(x − mi) + (x − mj)(cid:48)C −1(x − mj) 1 2 1 2

= x(cid:48)C −1(mi − mj) − (mi + mj)(cid:48)C −1(mi − mj), ∀1 ≤ i < j ≤ M 1 2

2. Xây dựng tiêu chuẩn nhận dạng tổng quát

x ∈ Ωi nếu

uij > ln = αij, ∀j (cid:54)= i, j = 1, · · · , M p(Ωj) p(Ωi)

M , ∀i thì αij = 0 với mọi i.

nếu p(Ωi) = 1

3. Xây dựng công thức đánh giá xác suát sai số của việc phân lớp dạng

theo quy tắc Bayets: Xét riêng đối với 2 lớp Ωi, Ωj. Gọi e là sự kiện x bị phân sai vào lớp Ωi, có nghĩa là x ∈ Ωi cùng với uij < αij hoặc x ∈ Ωj cùng với uij > αij.

⇒ e = {uij < αij} Ωi + {uij > αij} Ωj

⇒ p(e) = p({uij < αij} Ωi) + p({uij > αij} Ωj)

Giáp Văn Hiệp - Toán Tin 2 - K54

= p(uij < αij |Ωi )p(Ωi) + p(uij > αij |Ωj )p(Ωj)

Hệ nhận dạng tự động nhận sai dạng x vào lớp Ωi, điều đó có nghĩa là tiêu chuẩn không thỏa mãn tại ít nhất 1 cặp lớp (Ωi, Ωj) nào đó. Do đó, nếu gọi e là sự kiện phân sai x vào Ωi thì

e = {uij < αij} Ωi + {uij > αij} Ωj

⇒ Xác suất sai số

p({uij < αij} Ωi) + p({uij > αij} Ωj)

= p(uij < αij |Ωi )p(Ωi) + p(uij > αij |Ωj )p(Ωj)

a. Tính p(uij < αij|Ωi)

uij là tổ hợp tuyến tính của các thành phần x1, · · · , xn của ĐLNN x cs phân phối chuẩn ⇒ uij là ĐLNN 1 chiều có phân phối chuẩn ⇒ cần tính kỳ vọng và phương sai của uij hạn chế trên lớp Ωi.

Tính kỳ vọng Ei(uij) (kỳ vọng của uij hạn chết trên lớp Ωi)

(cid:19) (cid:18)

(mi + mj)(cid:48)C −1(mi − mj) Ei(uij) = Ei x(cid:48)C −1(mi − mj) − 1 2

= (Eix(cid:48))C −1(mi − mj) − (mi + mj)(cid:48)C −1(mi − mj) 1 2

iC −1(mi − mj) −

2(mi − mj)(cid:48)C −1(mi − mj)

= m(cid:48) (mi + mj)(cid:48)C −1(mi − mj) 1 2

= 1 Nếu ký hiệu

rij = (mi − mj)(cid:48)C −1(mi − mj) là khoảng cách Mkhalanobis giữa 2 kỳ vọng của 2 lớp Ωi và Ωj thì Ei(uij) = 1 2rij là 1 nửa khoảng cách Makhalanobis giữa 2 kỳ vọng.

Tính phương sai Di(uij) của uij hạn chế trên lớp Ωi Ta có Di(uij) = Ei (uij − E(uij))2(cid:111) (cid:110)

(cid:26)(cid:20)

= Ei x(cid:48)C −1(mi − mj) − (mi + mj)(cid:48)C −1(mi + mj) 1 2

Giáp Văn Hiệp - Toán Tin 2 - K54

(cid:21)2(cid:41) − (mi − mj)(cid:48)C −1(mi − mj) 1 2

= Ei

(cid:110)(cid:2)x(cid:48)C −1(mi − mj) − m(cid:48)C −1(mi − mj)(cid:3)2(cid:111) (cid:110)(cid:2)(x − mi)(cid:48)C −1(mi − mj)(cid:3)2(cid:111) = Ei (cid:8)(cid:2)(mi − mj)C −1(x − mi)(x − mi)(cid:48)C −1(mi − mj)(cid:3)(cid:9) = Ei = (mi − mj)(cid:48)C −1 {Ei [(x − mi)(x − mi)(cid:48)]} C −1(mi − mj) = (mi − mj)(cid:48)C −1CC −1(mi − mj) = (mi − mj)(cid:48)C −1(mi − mj) = rij

(bằng cả khoảng cách Makhalanobis giữa 2 kỳ vọng)

(cid:19) √ rij, rij ⇒ uij |Ωi ∼ ℵ(α, σ) = ℵ (cid:18)1 2

Từ đó suy ra

(cid:19) (cid:19) = + L p(uij < αij |Ωi ) = Φ 1 2 (cid:18)αij − 1 2rij √ rij (cid:18)αij − 1 2rij √ rij

+∞ (cid:90)

trong đó

−∞

dt = exp Φ(ξ) = + L(ξ) (cid:17) (cid:16)t2(cid:14) 2 1 2 1 √ 2π

ξ (cid:90)

với

dt exp L(ξ) = (cid:17) (cid:16)t2(cid:14) 2 1 √ 2π

gọi là hàm Laplace.

b. Tính xác suất p(uij > α|Ωi)

2rij, Dj(uij) = rij √

2rij,

Hoàn toàn tương tự câu a, ta tính được

2 − L

(cid:17) (cid:17) = 1 Ej(uij) = − 1 ⇒ uij |Ωi ∼ ℵ (cid:0)− 1 rij ⇒ p(uij > α |Ωi ) = 1 − Φ (cid:1) (cid:16) α+ 1 2 rij√ rij (cid:16) α+ 1 2 rij√ rij

Từ đó ta suy ra xác suất sai số cần tìm là

(cid:19)(cid:21) (cid:19)(cid:21) + L − L p(e) = p(Ωi) + p(Ωi) (cid:20)1 2 (cid:20)1 2 (cid:18)α − 1 2rij √ rij (cid:18)α + 1 2rij √ rij

Giáp Văn Hiệp - Toán Tin 2 - K54

2 − L

2 rij√ rij

2 rij√ rij (cid:1)(cid:3)

(cid:16) 1 (cid:17) Trường hợp đặc biệt, nếu các xác suất tiên nghiệm bằng nhau p(Ωi) = 1 M , ∀i = 1, · · · , M thì công thức sai số đó là: (cid:17)(cid:105) (cid:16) − 1 + 1

4.3.2 Mở rộng đánh giá cho trường hợp phân lớp dạng được

(cid:104) 1 2 + L √ (cid:2)1 − 2L (cid:0) 1 rij p(e) = 1 M = 1 M

thưc hiện bởi các hàm tuyến tính

ijx > 0(cid:9) Ωj

ijx < 0(cid:9) Ωi + (cid:8)W (cid:48)

Giả sử tập dạng Ω được phân hoạch thành M lớp Ω1, · · · , ΩM và việc phân lớp dạng Ω được thực hiện bởi các hàm tuyến tính tách nhau theo trường hợp 3 bởi M hàm di(x) = W (cid:48) i x, ∀i = 1, · · · , M ⇒ Nhận được C 2 M hàm quyết định dij(x) = W (cid:48) i x, 1 ≤ i < j ≤ M . Khi đó hệ nhận dạng phân sai x vào lớp Ωi tương đương với tồn tại cặp lớp (Ωi, Ωj) để sk sai số

ijx > 0 |Ωj )p(Ωj)

ijx < 0 |Ωi )p(Ωi) + p(W (cid:48)

e = (cid:8)W (cid:48) ⇒ p(e) = p(W (cid:48)

ijx < 0|Ωi)

a. Tính p(W (cid:48)

ijmi

ijx − W (cid:48)

(cid:1)2(cid:111) Ei(W (cid:48) Di(W (cid:48)

ij(x − mi)(cid:1)(cid:48)(cid:111)

= Ei

= Ei = Ei = W (cid:48) = W (cid:48)

ijx) = W (cid:48) ijmi (cid:110)(cid:0)W (cid:48) ijx) = Ei ij(x − mi)(cid:1)2(cid:111) (cid:110)(cid:0)W (cid:48) (cid:110) ij(x − mi) (cid:0)W (cid:48) W (cid:48) (cid:9) (cid:8)W (cid:48) ij(x − mi)(x − mi)(cid:48)Wij ijEi {(x − mi)(x − mi)(cid:48)} Wij ijCiWij ijx ∼ ℵ(W (cid:48)

ijmi,

(cid:113) ⇒ W (cid:48) W (cid:48)

ijx < 0 |Ωi ) = 1

2 − L

ijCiWij (cid:18) W (cid:48) W (cid:48)

ijmi ijCiWij

ijx > 0|Ωj)

(cid:19) √ ⇒ p(W (cid:48)

2. Tính p(W (cid:48) Tương tự

 

ijmj

ijx > 0 |Ωj ) =

ijCjWij

W (cid:48) + L p(W (cid:48) (cid:113)     1 2 W (cid:48)

Giáp Văn Hiệp - Toán Tin 2 - K54

Vậy    

ijmi

W (cid:48) p(e) = − L (cid:113)         p(Ωi)+ 1 2 W (cid:48)

ijCiWij  

 

ijmi

ijCjWij

W (cid:48) + L (cid:113)         p(Ωj) 1 2 W (cid:48)

4.4 Giới thiệu một số hàm mật đọ phân phối quan trọng trong

4.4.1 Hàm mật độ dạng tổng quát

nhận dạng

Là hàm được cho bởi công thức

(4.5) p(x) = Kn|det(W )|1/2f ((x − m)(cid:48)W (x − m))

trong đó x là ĐLNN n chiều, m là kỳ vọng của x, W là ma trận đối xứng, xác định dấu, Knlà hằng số chuẩn tắc.

Nếu hạn chế hàm mật độ trên 1 lớp Ω nào đó:

p(x |Ω) = Kn|det(W )|1/2f ((x − mΩ)(cid:48)W (x − mΩ))

Nếu x tuân theo luật phân phối chuẩn, thì hàm mật độ p(x) của nó thỏa mãn công thức (4.5)

p(x) = Kn|det(W )|1/2f ((x − m)(cid:48)W (x − m))

trong đó

(2π)n/2 , W = C −1, f = exp(− 1 2)

4.4.2 Một số hàm mật độ dạng Peason

Kn = 1

1. Hàm mật độ Peason loại 2

Là hàm dạng (4.5), đối xứng và được cho bởi công thức

(cid:26) h(x) x ∈ R (|W | = det(W )) p(x) = 0 x /∈ R W đối xứng, xác định dương

Giáp Văn Hiệp - Toán Tin 2 - K54

trong đó

2n + k + 1(cid:1) Γ (cid:0) 1 πn/2Γ(k + 1)

h(x) = |W |1/2 [1 − (x − m)(cid:48)W (x − m)]−k

+∞ (cid:82)

R là miền trong của siêu elipcoid (x − m)(cid:48)W (x − m) = 1 còn Γ là hàm Gamma:

0 1

n+2(k+1)C −1, (k > 0) W = C − ma trận hiệp biến của x

e−xxp−1dx Γ(p) =

2. Hàm mật độ Peason loại 7 Là hàm mật độ có dạng

p(x) = |W |1/2[1 + (x − m)(cid:48)W (x − m)]−k, k > + 1 n 2

Γ(k) an/2Γ(k − n 2 ) Ma trận W được xác định bởi công thức

W = C −1, (k > + 1) 1 2k − (n + 2) n 2

C là ma trận hiệp biến của x. Chú ý : Với k đủ lớn, mật độ p(x) tiệm cận đến mật độ phân phối chuẩn.

3. Ví dụ áp dụng mật độ phân phối Peason

Giả sử 1 tập dạng Ω ⊂ Rn gồm các dạng có phân phối Peason loại 7 được phân hoạch thành 2 lớp Ω1, Ω2 với cùng 1 thông số k. Xác định hàm quyết định và mặt quyết định phân lớp dạng Ω.

Γ(k) π1/2Γ(k− π Γ(k) π1/2Γ(k− π

p(x |Ω1 ) = p(x |Ω2 ) = Lời giải: Theo giả thiết với x ∈ Ω là 1 dạng cần được phân lớp, suy ra 2 )|W1|1/2[1 + (x − m1)(cid:48)W1(x − m1)]−k 2 )|W2|1/2[1 + (x − m2)(cid:48)W2(x − m2)]−k

Xem các xác suất tiên nghiệm bằng nhau p(Ω1) = p(Ω2) = 0.5. Theo quy tắc phân lớp Bayets, ta lập 2 hàm

d1(x) = p(x |Ω1 )p(Ω1), d2(x) = p(x |Ω2 )p(Ω2)

Giáp Văn Hiệp - Toán Tin 2 - K54

Khi đó x ∈ Ω1 nếu d1(x) > d2(x) x ∈ Ω2 nếu d1(x) < d2(x) Trường hợp d1(x) = d2(x) thì x được phân vào 1 trong 2 lớp tùy ý. Xét d1(x) > d2(x)

1βkW1m1 + αk − βk > 0

2αkW2m2 − m(cid:48)

⇔ p(x |Ω1 )p(Ω1) > p(x |Ω2 )p(Ω2) ⇔ p(x |Ω1 ) > p(x |Ω2 ) ⇔ |W1|1/2[1 + (x − m1)(cid:48)W1(x − m1)]−k > |W2|1/2[1 + (x − m2)(cid:48)W2(x − m2)]−k ⇔ [1 + (x − m2)(cid:48)W2(x − m2)]k|W1|1/2k > [1 + (x − m1)(cid:48)W1(x − m1)]k|W2|1/2k ⇔ αk + (x − m2)(cid:48)αkW2(x − m2) > βk + (x − m1)(cid:48)βkW1(x − m1) ⇔ x(cid:48)(αkW2 − βkW1)x − 2x(cid:48)(αkW2m2 − βkW1m1)+ m(cid:48)

Từ đó suy ra hàm quyết định cho phép phân lớp dạng Ω là hàm

2αkW2m2 − m(cid:48)

d12(x) = x(cid:48)(αkW2 − βkW1)x − 2x(cid:48)(αkW2m2 − βkW1m1)+ m(cid:48) 1βkW1m1 + αk − βk > 0

d12(x) là hàm đa thức bậc 2. ⇒ Siêu mặt quyết định cho phép phân lớp Ω là siêu mặt bậc 2: d12(x) = 0.

4.5.1 Xây dựng các công thức truy toán tính kỳ vọng, ma trận

4.5 Phương pháp xây dựng các hàm quyết định phân lớp dạng theo quy tắc phân lớp Bayets trên cơ sở xấp xỉ các hàm mật độ phân phốix ác suất

hiệp biến của các dạng thuộc cùng 1 lớp

1. Xây dựng công thức tính kỳ vọng

Giả sử Ω = {x1, · · · , xN } là 1 dạng bất kỳ gồm N dạng trong không gian dạng n chiều, x là 1 dạng được phân vào Ω. Theo quy tắc đồng nhất các tính chất suy ra x = xj tương ứng với xác suất

Giáp Văn Hiệp - Toán Tin 2 - K54

1 N , ∀j = 1, · · · , N , suy ra có thể xem x như là 1 ĐLNN rời rạc nhận N giá trị xj ↔ p(xj) ﬄ N , ∀j = 1, · · · , N . Suy ra x có bảng phân phối xác suất đều

x p(x = xj) x1 x2 1 1 N · · · N · · · xN 1 N

N (cid:88)

⇒ Kỳ vọng

j=1

m(x |Ω) = xj 1 N

Ký hiệu: m(x|Ω) = m(N ), xem x như dạng thứ N + 1 của Ω, tưc là x = xN +1. Giả sử lại có dạng x khác được phân vào Ω, thì lý luận tương tự ta cũng có:

N +1

N +1 (N m(N ) + xN +1)

m(N + 1) = 1 xj = 1

N +1 (cid:80) j=1 N +1xN +1

N +1m(N ) + 1

= N

Từ đó thu được công thức truy toán tính kỳ vọng

m(N + 1) = m(N ) + xN +1 N N + 1 1 N + 1

2. Xây dựng công thức tính ma trận hiệp biến

Một các tổng quát, ma trân hiệp biến của dạng x với lớp Ω là:

C(x |Ω) = E {(x − m)(x − m)(cid:48)} , (m = m(x |Ω)) = E {xx(cid:48) − 2xm(cid:48) + mm(cid:48)} = E(xx(cid:48)) − 2mm(cid:48) + mm(cid:48) = E(xx(cid:48)) − mm(cid:48)

j tương đương

Theo (4.1), x được xem như là ĐLNN rời rạc nhận N giá trị xj ↔ p(xj) = 1 N , ∀j = 1, · · · , N , do đó xx(cid:48) cũng là 1 ĐLNN rời rạc nhận N giá trị xjx(cid:48)

j) =

, ∀j = 1, · · · , M p(xjx(cid:48) 1 N

Giáp Văn Hiệp - Toán Tin 2 - K54

Vì vậy

N (cid:80) j=1

xjx(cid:48) j E(xx(cid:48)) = 1 N

j − mm(cid:48)

N (cid:80) j=1

xjx(cid:48) ⇒ C(x |Ω) = 1 N

Xem x = xN +1 ∈ ΩN +1, ta có C(x|) = C(N )

j − m(N + 1)m(cid:48)(N + 1)

N +1

N +1 (cid:80) j=1

⇒ C(N + 1) = 1

N +1

(cid:3)

N +1 N +1xN +1 N +1

(cid:3) xjx(cid:48) (cid:2)N C(N ) + N m(N )m(cid:48)(N ) + xN +1x(cid:48) N +1m(N ) + 1

N +1m(N ) + 1 N +1C(N ) + N

N +1xN +1x(cid:48)

N +1

(N +1)2 m(N )m(cid:48)(N ) − 2N

(N +1)2 m(N )x(cid:48)

(cid:3) (cid:2) N N +1xN +1 N +1m(N )m(cid:48)(N ) + 1 (cid:1)2

(N +1)2xN +1x(cid:48)

N +1

m(N )m(cid:48)(N ) − 2N N = 1 − (cid:2) N = N −(cid:0) N +

N +1C(N ) +

N (N +1)2m(N )m(cid:48)(N )

N +1

Vậy công thức truy toán là:

N +1 − 2m(N )x(cid:48)

N +1 + m(N )m(cid:48)(N )(cid:3)

(cid:2)xN +1x(cid:48)

(N +1)2 (2m(N ) − xN +1) x(cid:48) N +1C(N ) + N N +1C(N ) + N

(N +1)2 (N +1)2 (xN +1 − m(N )) (xN +1 + m(N ))

4.5.2 Xây dựng xấp xỉ mật độ phân phối bởi hệ hàm

C(N + 1) = N − N = N = N

1. Ý nghĩa và tiêu chuẩn xấp xỉ

Giả sử Ω = {x1, · · · , xN là 1 dạng bất kỳ trong không gian dạng n chiều, theo quy tắc phân lớp Bayets, để có thể phân 1 dạng x bất kỳ vào Ω cần phải biết được mật độ phân phối xác suất p(x) = p(x|Ω). Trong thực tế, hàm mật độ phân phối xác suất p(x) khó xác định, do đó nảy sinh ra là cần tìm 1 hàm (cid:101)p = (cid:101)p(x) cho phép xấp xỉ p(x) và được dùng thay cho p(x) trong quá trình phân lớp dạng.

Tiêu chuẩn xấp xỉ : Hàm (cid:101)p = (cid:101)p(x) được gọi là xấp xỉ "tốt nhất" hàm p trên siêu lập phương n chiều (cid:3)n. Nếu nó đảm bảo cực tiểu hóa sai số trung bình bình phương khả tích của hiệu p − (cid:101)p, có nghĩa à đại lượng.

Giáp Văn Hiệp - Toán Tin 2 - K54

R = sai số trung bình bình phương khả tích ( theo trọng số u)

(cid:3)n

(cid:90) = ux()[p(x) − (cid:101)p(x)]2dx → min

(cid:107)p − q(cid:107)u (cid:101)p = p

(cid:101)p = min p

Nói cách khác (cid:107)p − (cid:101)p(cid:107)u = min R Rp

2. Phương pháp xây dựng hàm xấp xỉ (cid:101)p.

m (cid:88)

Giả sử ta có 1 họ hàm độc lập tuyến tính, đầy đủ n biến ϕ trên (cid:3)n. Từ hệ hàm ϕ tính ra m hàm (m tìm được từ thực tế đòi hỏi của bài toán), ký hiệu là ϕ1, · · · , ϕm. Khi đó hàm (cid:101)p = p được chọn là 1 tổ hợp tuyến tính nào đó của m hàm trên, tức là:

j=1

cjϕj (cid:101)p =

(cid:101)p, ta được 1 hàm m biến c1, · · · , cm.

trong đó cj là các hằng số cần được xác định. Thay vào R

m (cid:88)

(cid:101)p(c1, · · · , cm) =

j=1

(cid:3)n

(cid:34) (cid:35)2 (cid:90) R u(x) p(x) − dx cjϕj(x)

(cid:101)p → min cần thỏa mãn phương trình đạo hàm riêng:

Theo nguyên lý cực trị hàm m biến, các hằng số c1, · · · , cm làm cho R

= 0, ∀k = 1, · · · , m (4.6) δR δck

Ta có (4.6) tương đương với

(cid:34) (cid:35)

m (cid:80) j=1

u(x).2 p(x) − cjϕj(x) ϕk(x)dx = 0, ∀k = 1, · · · , k (cid:82) (cid:3)n

m (cid:80) j=1

⇔ cj u(x)ϕj(x)ϕk(x)dx = (cid:104)ϕk, ϕj(cid:105)u,∀k = 1, · · · , k (cid:82) (cid:3)n

Ta nhận thấy

(cid:90)

(cid:3)n

u(x)ϕj(x)ϕk(x)dx = (cid:104)ϕk, ϕj(cid:105)u, ∀k, j = 1, · · · , m

Giáp Văn Hiệp - Toán Tin 2 - K54

còn (cid:90)

(cid:3)n

u(x)ϕk(x)p(x)dx

N , suy ra

là kỳ vọng của ĐLNN u(x)ϕk(x) hạn chế trên lớp Ω, mà ta đã biết ở mục trươc,x là ĐLNN rời rạc nhận N giá trị xj(j = 1, · · · , N ) với xác suất đồng khả năng 1 N , do đó u(x)ϕk(x) cũng là 1 ĐLNN rời rạc nhận giá trị u(x)ϕk(x) ↔ 1

N (cid:88)

(cid:90)

j=1

(cid:3)n

u(x)ϕk(x)p(x)dx = u(xj)ϕk(xj), ∀k = 1, · · · , m 1 N

N (cid:88)

m (cid:88)

Vậy hệ (4.6) tương đương với hệ phương trình tuyến tính

j=1

u(xj)ϕk(xj), ∀k = 1, · · · , m (cid:104)ϕk, ϕj(cid:105)ucj = 1 N

Nếu đặt A = (akj)m×n, akj = (cid:104)ϕk, ϕj(cid:105)u, ∀k, j = 1, · · · , m

 

C =   cột ẩn

 

b =   cột VP

c1 ... cm b1 ... bm

m (cid:88)

với

j=1

bk = u(xj)ϕk(xj) 1 N

thì ta được hệ phương trình tuyến tính tìm các hệ số c1, · · · , cm

Ac = b

(cid:90)

(cid:3)n

(cid:101)p = p ⇔ R = u(x)[p(x) − (cid:101)p(x)]2dx → min

m (cid:80) j=1

cjϕj(x) ⇒ các hệ số cj được tìm từ hệ phương trình (cid:101)p =

Ac = b.

Giáp Văn Hiệp - Toán Tin 2 - K54

trong đó A = (akj)m×n, akj = (cid:104)ϕk, ϕj(cid:105)u, ∀k, j = 1, · · · , m

 

C =  cột ẩn 

 

b =   cột VP

c1 ... cm b1 ... bm

với

m (cid:80) j=1

u(xj)ϕk(xj) N = |Ω| bk = 1 N

3. Nhận xét

Trong thực tế, hệ hàm ϕ độc lập tuyến tính đầy đủ thường được chọn là hệ trực giao, trực chuẩn theo trọng số (xem bài trước), do đó k = j (cid:26) Ak = (cid:107)ϕk(cid:107) ˚khi akj = 0 ˚khi k (cid:54)= j

N (cid:80) j=1

u(xj)ϕk(xj), ∀k = 1, · · · , m ⇒ 1 N Ak

N (cid:88)

Để cho đơn giản quá trình tính toán thì có thể bỏ các đại lượng cố định Ak cũng như hàm trọng u(x) đối với hệ trực giao ϕ, cuối cùng ta thu được công thức xác định hằng số ck

j=1

4.5.3 Xây dựng các hàm quyết định phân lớp dạng theo quy tắc phân lớp Bayets trên cơ sở xâp xỉ các hàm mật độ phân phối

ϕk(xj), ∀k = 1, · · · , m ck = 1 N

Giả sử không gian dạng Ω ⊂ Rn được phân hoạch thành M lớp Ω1, · · · , ΩM . Theo tiêu chuẩn nhận dạng tổng quát, các lớp Ωi được tách ta bởi M hàm

di(x) = p(x |Ωi )p(Ωi), i = 1, · · · , M

Giáp Văn Hiệp - Toán Tin 2 - K54

Theo tiêu chuẩn xấp xỉ và cách xác định các hàm xấp xỉ, hàm mật độ phân phối xác suất, ta có thê chọn các hàm

(cid:101)p(x |Ωi ) ≈ p(x |Ωi ), ∀i = 1, · · · , M

m (cid:88)

trong đó

k=1

cikϕk(x), ∀i = 1, · · · , M (cid:101)p(x |Ωi ) =

với {ϕ1, · · · , ϕm được chọn từ 1 hệ trực giao đầy đủ nào đó ϕ.

x∈Ωi

(cid:88) cik = ϕk(x), ∀i, k = 1, · · · , M 1 |Ωi|

Từ đó xác định được M các hàm xấp xỉ

M hàm

(cid:101)di(x) = (cid:101)p(x |Ωi )p(Ωi), ∀i = 1, · · · , M

dùng để phân lớp dạng Ω thay cho M hàm di, từ đó thu được C 2 quyết định phân lớp dạng:

dij(x) = (cid:101)p(x |Ωi )p(Ωi) − (cid:101)p(x |Ωj )p(Ωj), ∀1 ≤ i < j ≤ M

theo tiêu chuẩn nhận dạng x ∈ Ωi:

Nếu dij(x) > 0, ∀j (cid:54)= i, j = 1, · · · ,, nếu tồn tại Ωk : dik(x) = 0 còn

dkj(x) > 0, ∀j (cid:54)= i, j (cid:54)= k thì x được phân vào 1 trong 2 lớp Ωi, Ωk.

Ví dụ áp dụng: Giả sử 1 không gian dạng Ω ⊂ R2 được phân thành 2

lớp Ω1, Ω2 và mỗi lớp có 1 số dạng mẫu sau:

Ω1 = {(2, 2)(cid:48), (3, 2)(cid:48), (2, 3)(cid:48), (3, 3)(cid:48), (4, 3)(cid:48), (3, 4)(cid:48), (4, 4)(cid:48)} Ω2 = {−3, −2)(cid:48), (−2, −3)(cid:48), (−3, −3)(cid:48), (−4, −3)(cid:48), (−3, −4)(cid:48), (−3, −5)(cid:48)}

a. Xác định các xấp xỉ mật độ phân phối xác suất tương ứng với 2 lớp trên bởi hệ các đa thức trực giao 2 biến trên cở sở hệ đa thức trực giao Hermit lấy với m = 4.

b. Xác định các hàm quyết định , đqđ cho phép tách 2 lớp trên biết

xác suất tiên nghiệm bằng nhau

Lời giải:

Giáp Văn Hiệp - Toán Tin 2 - K54

Để đơn giản ta chọn 2 hàm H0(x) = 1, H1(x) = 2x làm cơ sở xác định

4 hàm đa thức trực giao 2 biến, có thể xác định như sau:

(cid:19) ∈ R2 ϕ1(x) = H0(x1)H0(x2) = 1.1 = 1, x = (cid:18) x1 x2

ϕ2(x) = H0(x1)H0(x2) = 2x1 ϕ3(x) = H0(x1)H0(x2) = 2x2 ϕ4(x) = H1(x1)H1(x2) = 2x1.2x2 = 4x1x2

4 (cid:88)

a. Xác định hàm xấp xỉ mđppxs p(x|Ω1) theo công thức:

k=1

c1kϕk(x) (cid:101)p1(x) =