TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU VÀ PHÁT HIỆN TRI THỨC
Giới thiệu tổng quan
Trong thời đại công nghệ thông tin phát triển mạnh mẽ, các hệ thống thông tin có khả năng lưu trữ khối lượng lớn dữ liệu từ hoạt động hàng ngày Mọi lĩnh vực đều cần sự hỗ trợ của công nghệ thông tin, và thành công của chúng phụ thuộc vào khả năng nắm bắt thông tin nhanh chóng và hiệu quả Việc sử dụng thao tác thủ công truyền thống không đảm bảo độ chính xác và tốn thời gian Các kỹ thuật Khai Phá Dữ Liệu (KPDL) và Máy Học (MH) có thể trích xuất thông tin hữu ích từ khối dữ liệu này, giúp cải thiện hiệu quả hoạt động của hệ thống thông tin Do đó, việc khai phá tri thức từ dữ liệu trong các tập tài liệu lớn đóng vai trò quan trọng trong việc đáp ứng nhu cầu thông tin, khiến kỹ thuật khai phá dữ liệu trở thành lĩnh vực nổi bật trong nền CNTT toàn cầu hiện nay.
Khai phá dữ liệu (Data Mining) là một lĩnh vực mới nổi, giúp tự động khai thác thông tin và tri thức tiềm ẩn từ cơ sở dữ liệu lớn, hỗ trợ các tổ chức và doanh nghiệp nâng cao khả năng sản xuất, kinh doanh và cạnh tranh Những thành tựu khoa học và ứng dụng thành công trong lĩnh vực này chứng minh rằng khai phá dữ liệu không chỉ bền vững mà còn mang lại nhiều lợi ích vượt trội so với các công cụ phân tích dữ liệu truyền thống Hiện nay, khai phá dữ liệu đã được áp dụng rộng rãi trong nhiều lĩnh vực như thương mại, tài chính, y học, viễn thông và công nghệ thông tin.
1.1.1 Khái niệm khai phá dữ liệu
Khai phá dữ liệu (data mining) là quá trình trích xuất các mẫu từ bộ dữ liệu lớn, kết hợp giữa máy học, thống kê và hệ thống cơ sở dữ liệu Mục tiêu của khai thác dữ liệu là chuyển đổi thông tin từ dữ liệu thành cấu trúc dễ hiểu, giúp tối ưu hóa quá trình “làm sạch” dữ liệu Quá trình này không chỉ bao gồm phân tích thô mà còn liên quan đến quản lý và xử lý dữ liệu, suy xét mô hình, và thống kê Khai thác dữ liệu là bước quan trọng trong “khám phá kiến thức trong cơ sở dữ liệu” (KDD), nhằm phát hiện những tri thức mới, tiềm ẩn và hữu dụng trong các cơ sở dữ liệu lớn.
Khai phá tri thức trong CSDL (KDD) là mục tiêu chính của khai phá dữ liệu, dẫn đến việc các nhà khoa học coi hai khái niệm này là tương đương Tuy nhiên, nếu phân tích sâu hơn, khai phá dữ liệu chỉ là một bước quan trọng trong quy trình KDD.
1.1.2 Nhiệm vụ của khai phá dữ liệu
Những nhiệm vụ cơ bản nhất của KPDL là:
• Phân cụm, phân loại, phân nhóm, phân lớp
• Khai phá luật kết hợp
• Lập mô hình dự báo
• Phân tích đối tượng ngoài cuộc
• Phân tích sự tiến hóa
1.1.3 Một số ứng dụng khai phá dữ liệu
KPDL (Khai Phá Dữ Liệu) đang được nghiên cứu để giải quyết nhiều vấn đề, nhưng tiềm năng của nó đã được chứng minh qua sự phát triển của nhiều ứng dụng Các công ty phần mềm lớn như Oracle và IBM đang đầu tư mạnh mẽ vào nghiên cứu và phát triển kỹ thuật khai phá dữ liệu, với Oracle tích hợp các công cụ vào bộ Oracle 9i và IBM tiên phong với các ứng dụng như Intelligence Miner KPDL đã được ứng dụng rộng rãi trong nhiều lĩnh vực khác nhau.
• Thương mại: Phân tích dữ liệu bán hàng và thi trường, phân tích đầu tư, quyết định cho vay, phát hiện gian lận
• Thông tin sản xuất: Điều khiển và lập kế hoạch, hệ thống quản lý, phân tích kết quả thử nghiệm
• Thông tin khoa học: dự báo thời tiết, CSDL sinh học: Ngân hàng gen, khoa học địa lý: dự báo động đất
• Trong y tế, marketing, ngân hàng, viễn thông, du lịch, internet
1.1.4 Bước phát triển của việc tổ chức và khai thác các CSDL
Với sự gia tăng liên tục của khối lượng dữ liệu, các hệ thống thông tin ngày càng được chuyên môn hóa theo các lĩnh vực như sản xuất, tài chính và thương mại Thành công trong kinh doanh không chỉ dựa vào năng suất của hệ thống thông tin mà còn phụ thuộc vào tính linh hoạt và khả năng đáp ứng nhanh chóng các yêu cầu thực tế Để đưa ra quyết định chính xác và kịp thời, việc khai thác tri thức từ dữ liệu trở nên quan trọng hơn bao giờ hết Các mô hình cơ sở dữ liệu truyền thống và ngôn ngữ SQL đã cho thấy sự hạn chế trong việc xử lý khối lượng dữ liệu lớn Do đó, các kỹ thuật tạo kho dữ liệu đã được phát triển nhằm hợp nhất dữ liệu từ các hệ thống giao dịch khác nhau, tạo ra các cơ sở dữ liệu ổn định và chất lượng cho mục đích cụ thể Công nghệ phát hiện tri thức từ cơ sở dữ liệu đã được đề xuất như một phương pháp mới để đáp ứng nhu cầu trong cả khoa học và thực tiễn.
1.1.5 Quá trình phát hiện tri thức
Một yếu tố quan trọng dẫn đến thành công là khả năng sử dụng thông tin hiệu quả Điều này có nghĩa là từ các dữ liệu có sẵn, cần phát hiện những thông tin tiềm ẩn giá trị và nhận diện các xu hướng phát triển cùng các yếu tố tác động Quá trình này được gọi là phát hiện tri thức trong cơ sở dữ liệu (Knowledge Discovery in Database – KDD), trong đó kỹ thuật khai phá dữ liệu (KPDL) đóng vai trò quan trọng trong việc trích xuất tri thức.
Quá trình phát hiện tri thức tiến hành qua 6 giai đoạn như Hình 1.1
Hinh 1.1: Quá trình phát hiện tri thức
Quá trình khám phá tri thức từ cơ sở dữ liệu (CSDL) là một hoạt động tương tác giữa con người và công nghệ, trong đó con người giữ vai trò trung tâm Đây không phải là hệ thống phân tích tự động mà là sự kết hợp giữa nhiều phương pháp và công cụ tin học Người sử dụng cần có kiến thức cơ bản về lĩnh vực để lựa chọn đúng tập con dữ liệu và lớp mẫu phù hợp với mục tiêu cụ thể Tri thức được rút ra từ CSDL thường nhằm phục vụ cho việc giải quyết các nhiệm vụ trong một lĩnh vực nhất định, do đó, quá trình phát hiện tri thức mang tính chất hướng nhiệm vụ, tập trung vào việc giải quyết vấn đề cụ thể thay vì phát hiện mọi tri thức một cách ngẫu nhiên.
Quá trình phát hiện tri thức bắt đầu từ kho dữ liệu thô và kết thúc với tri thức được chiết xuất Mặc dù lý thuyết có vẻ đơn giản, nhưng thực tế đây là một quá trình phức tạp, gặp nhiều khó khăn như quản lý các tập dữ liệu và yêu cầu lặp lại toàn bộ quy trình.
Tập hợp dữ liệu là bước khởi đầu quan trọng trong quy trình khai phá dữ liệu, được thực hiện từ các cơ sở dữ liệu, kho dữ liệu, và cả những nguồn dữ liệu từ ứng dụng Web.
1.1.5.2 Lựa chọn dữ liệu (Selection) Ở giai đoạn này dữ liệu được lựa chọn hoặc phân chia theo một số tiêu chuẩn nào đó phục vụ mục đích khai thác, ví dụ chọn tất cả những người có tuổi đời từ 25
- 35 và có trình độ đại học
1.1.5.3 Làm sạch, tiền xử lý và chuẩn bị dữ liệu (Cleaning, Pre-processing and Preparation)
Giai đoạn thứ ba trong quá trình khai phá dữ liệu thường bị sao lãng nhưng lại rất quan trọng Trong giai đoạn này, việc xử lý dữ liệu không đủ chặt chẽ và logic là cần thiết, vì dữ liệu có thể chứa các giá trị vô nghĩa như điểm = -1 Những dữ liệu này được xem là thông tin dư thừa và không có giá trị Nếu không được làm sạch, tiền xử lý và chuẩn bị kỹ lưỡng, chúng có thể dẫn đến những kết quả sai lệch nghiêm trọng.
1.1.5.4 Chuyển đổi dữ liệu (Transformation)
Giai đoạn chuyển đổi dữ liệu là quá trình tổ chức lại dữ liệu để nó có thể sử dụng và điều khiển hiệu quả Dữ liệu sẽ được chuyển đổi thành dạng phù hợp cho việc khai thác, thông qua các thao tác nhóm hoặc tập hợp.
1.1.5.5 Khai phá dữ liệu (Data mining) Đây là bước mang tính tư duy trong khai phá dữ liệu Ở giai đoạn này nhiều thuật toán khác nhau đã được sử dụng để trích ra các mẫu từ dữ liệu Thuật toán thường dùng là nguyên tắc phân lớp, nguyên tắc kết, v.v
1.1.5.6 Đánh giá các luật và biểu diễn tri thức (Evaluation of Result) Đây là giai đoạn cuối trong quá trình khai phá dữ liệu Ở giai đoạn này, các mẫu dữ liệu được chiết xuất, không phải bất cứ mẫu dữ liệu nào cũng đều hữu ích, đôi khi nó còn bị sai lệch Vì vậy, cần phải ưu tiên những tiêu chuẩn đánh giá để chiết xuất ra các tri thức (Knowlege) cần thiết Đánh giá sự hữu ích của các mẫu biểu diễn tri thức dựa trên một số phép đó Sau đó sử dụng các kỹ thuật trình diễn và trực quan hoá dữ liệu để biểu diễn tri thức khai phá được cho người sử dụng
Một số kỹ thuật khai phá dữ liệu cơ bản
1.2.1 Khai phá dữ liệu dự đoán
Nhiệm vụ của KPDL dự đoán là tạo ra các dự đoán dựa trên phân tích dữ liệu hiện có, sử dụng các kỹ thuật như phân lớp và hồi quy.
Mục tiêu của phương pháp phân lớp dữ liệu là dự đoán nhãn lớp cho các mẫu dữ liệu Quá trình này bao gồm hai bước chính: đầu tiên là xây dựng mô hình, sau đó là sử dụng mô hình để phân loại dữ liệu.
Để xây dựng mô hình, bước đầu tiên là phân tích các mẫu dữ liệu đã có, mỗi mẫu thuộc về một lớp được xác định bởi thuộc tính lớp Những mẫu dữ liệu này được gọi là tập dữ liệu huấn luyện, và các nhãn lớp phải được xác định trước khi tiến hành xây dựng mô hình Do đó, phương pháp này được biết đến là học có giám sát.
Bước 2 trong quy trình phân loại dữ liệu là sử dụng mô hình để xác định độ chính xác Nếu độ chính xác đạt yêu cầu, mô hình sẽ được áp dụng để dự đoán nhãn lớp cho các mẫu dữ liệu tương lai Nói cách khác, phân lớp là quá trình học một hàm ánh xạ mục dữ liệu vào các lớp đã được xác định trước.
Phương pháp hồi quy khác với phân loại dữ liệu ở chỗ hồi quy dự đoán các giá trị liên tục, trong khi phân loại chỉ dự đoán các giá trị rời rạc Hồi quy học cách ánh xạ một mục dữ liệu vào biến dự báo giá trị thực Các ứng dụng của hồi quy rất đa dạng, chẳng hạn như đánh giá xác suất tử vong của bệnh nhân dựa trên kết quả xét nghiệm chẩn đoán, hoặc dự báo nhu cầu tiêu dùng cho sản phẩm mới dựa trên hoạt động quảng cáo.
1.2.2 Khai phá dữ liệu mô tả
Kỹ thuật mô tả các tính chất và đặc điểm chung của dữ liệu trong cơ sở dữ liệu hiện có bao gồm các phương pháp như phân cụm (clustering) và khai phá luật kết hợp (association rules).
Phương pháp phân cụm dữ liệu nhằm mục tiêu nhóm các đối tượng tương tự trong tập dữ liệu thành các cụm, với các đối tượng trong cùng một cụm có sự tương đồng cao, trong khi các đối tượng ở các cụm khác nhau thì không Đây là một ví dụ của học không giám sát, khác với phân lớp dữ liệu, không yêu cầu định nghĩa trước mẫu huấn luyện Phân cụm dữ liệu được xem như là học bằng quan sát, trong khi phân lớp là học bằng ví dụ Kết quả của các cụm thu được không thể được biết trước, do đó thường cần có chuyên gia đánh giá Phân cụm dữ liệu được ứng dụng rộng rãi trong phân đoạn thị trường, phân đoạn khách hàng, nhận dạng mẫu và phân lớp trang Web, cũng như có thể được sử dụng như bước tiền xử lý cho các thuật toán khai phá dữ liệu khác.
Hình 1.3 minh họa sự phân chia tập dữ liệu cho vay thành ba cụm, trong đó các cụm có thể chồng chéo lên nhau, cho phép một điểm dữ liệu có thể thuộc về nhiều hơn một cụm.
Hinh 1.3: Phân cụm tập dữ liệu cho vay thành 3 cụm
1.2.2.2 Khai phá luật kết hợp
Mục tiêu của phương pháp khai phá dữ liệu là phát hiện và xác định các mối liên hệ giữa các giá trị trong cơ sở dữ liệu Kết quả đầu ra của thuật toán KPDL là các luật kết hợp được tìm thấy, và quá trình khai thác luật kết hợp được thực hiện qua hai bước.
Bước đầu tiên trong quy trình là xác định tất cả các tập mục phổ biến, mà một tập mục được coi là phổ biến khi nó đạt được mức độ hỗ trợ tối thiểu và thỏa mãn tiêu chí về độ hỗ trợ.
• Bước 2: sinh ra các luật kết hợp mạnh từ tập mục phổ biến, các luật phải thỏa mãn độ hỗ trợ cực tiểu và độ tin cậy cực tiểu
Phương pháp này được sử dụng rất hiệu quả trong các lĩnh vực như marketing có chủ đích, phân tích quyết định, quản lí kinh doanh, …
Một số so sánh giữa khai phá dữ liệu và các phương pháp cơ bản khác
Khai phá dữ liệu là một lĩnh vực liên quan đến nhiều ngành học như hệ cơ sở dữ liệu và thống kê Tùy thuộc vào cách tiếp cận, khai phá dữ liệu có thể áp dụng các kỹ thuật như mạng nơ ron, lý thuyết tập thô, tập mờ và biểu diễn tri thức Điều này cho thấy khai phá dữ liệu dựa trên các phương pháp cơ bản đã có Tuy nhiên, sự khác biệt và ưu thế của khai phá dữ liệu so với các phương pháp truyền thống cần được xem xét và giải thích rõ ràng.
1.3.1 So sánh với phương pháp hệ chuyên gia (Expert Systems)
Hệ chuyên gia (Expert System) là chương trình máy tính thông minh, được định nghĩa bởi Theo E Feigenbaum, sử dụng tri thức và các thủ tục suy luận để giải quyết những bài toán phức tạp mà chỉ các chuyên gia mới có khả năng xử lý.
Hệ chuyên gia là một hệ thống tin học có khả năng mô phỏng năng lực quyết định và hành động của con người, thuộc lĩnh vực ứng dụng của trí tuệ nhân tạo (AI).
Hinh 1.4: Một số lĩnh vực ứng dụng của trí tuệ nhân tạo
Hệ chuyên gia là công cụ sử dụng tri thức của các chuyên gia để giải quyết những vấn đề đa dạng trong nhiều lĩnh vực khác nhau Tri thức trong hệ chuyên gia được hình thành từ sự tích lũy kinh nghiệm, tài liệu từ sách vở, tạp chí và sự đóng góp của các nhà bác học Các thuật ngữ như hệ chuyên gia, hệ thống dựa trên tri thức hay hệ chuyên gia dựa trên tri thức thường được hiểu là tương đồng.
Các kỹ thuật thu thập giúp khai thác tri thức từ các chuyên gia Mỗi phương pháp trong hệ chuyên gia đều có khả năng suy diễn các quy tắc từ các ví dụ và giải pháp cụ thể.
Trí tuệ nhân tạo đóng vai trò quan trọng trong việc giải quyết các bài toán chuyên gia Phương pháp hệ chuyên gia khác biệt với khai thác dữ liệu ở chỗ các ví dụ từ chuyên gia có chất lượng cao hơn nhiều so với dữ liệu trong cơ sở dữ liệu Những ví dụ này thường chỉ bao gồm các trường thông tin quan trọng, và các chuyên gia sẽ xác nhận giá trị cũng như tính hữu ích của các mẫu phát hiện được.
1.3.2 So sánh với phương pháp thống kê (Statistics)
Mặc dù phương pháp thống kê cung cấp nền tảng lý thuyết vững chắc cho phân tích dữ liệu, nhưng chỉ dựa vào thống kê thuần túy là chưa đủ.
● Các phương pháp thống kê không phù hợp với các kiểu dữ liệu có cấu trúc trong rất nhiều các cơ sở dữ liệu
● Thống kê hoàn toàn tính toán trên dữ liệu, nó không sử dụng tri thức sẵn có về lĩnh vực quan tâm
● Các kết quả của phân tích thống kê có thể rất nhiều và khó có thể làm rõ được
● Các phương pháp thống kê cần có sự hướng dẫn của người dùng để xác định phân tích dữ liệu như thế nào và ở đâu
Phương pháp thống kê là nền tảng lý thuyết của khai phá dữ liệu, nhưng điểm khác biệt chính là khai phá dữ liệu phục vụ người sử dụng cuối, không chỉ dành cho các nhà thống kê Khai phá dữ liệu đã khắc phục những hạn chế của thống kê bằng cách tự động hóa quy trình một cách hiệu quả, giảm bớt công việc cho người dùng và tạo ra công cụ dễ sử dụng hơn.
1.3.3 So sánh với phương pháp học máy (Machine Learning)
Trong những năm gần đây, trí tuệ nhân tạo và học máy đã phát triển mạnh mẽ nhờ khả năng ứng dụng đa dạng Học máy, một nhánh của trí tuệ nhân tạo, nghiên cứu và phát triển các kỹ thuật cho phép hệ thống tự động "học" từ dữ liệu để giải quyết các vấn đề cụ thể Hiện nay, học máy được áp dụng rộng rãi trong nhiều lĩnh vực và đạt được thành công lớn, như xử lý ngôn ngữ tự nhiên, hệ thống gợi ý, xử lý dữ liệu lớn, robot, và xe tự lái.
Khai phá dữ liệu vượt trội hơn phương pháp học máy nhờ khả năng xử lý các cơ sở dữ liệu động, không đầy đủ, bị nhiễu và quy mô lớn hơn nhiều so với các tập dữ liệu học máy thông thường Trong khi đó, phương pháp học máy chủ yếu được áp dụng cho các cơ sở dữ liệu đầy đủ, ít biến động và kích thước dữ liệu hạn chế.
Trong học máy, cơ sở dữ liệu đề cập đến một tập hợp các mẫu lưu trữ trong tệp, thường là các vectơ có độ dài cố định, kèm theo thông tin về đặc điểm và giá trị của chúng Các thuật toán học sử dụng tập dữ liệu này làm đầu vào để biểu thị kết quả học Học máy có thể áp dụng cho cơ sở dữ liệu, nhưng thường gặp khó khăn do cơ sở dữ liệu thường động, không đầy đủ và nhiễu, lớn hơn nhiều so với các tập dữ liệu học máy thông thường Những yếu tố này khiến nhiều thuật toán học máy trở nên kém hiệu quả Khai phá dữ liệu sẽ giải quyết những vấn đề này, cho phép xử lý các cơ sở dữ liệu chứa nhiều nhiễu, dữ liệu không đầy đủ hoặc biến đổi liên tục.
1.3.4 So sánh với phương pháp học sâu (Deep Learning)
Học sâu, một nhánh của máy học, sử dụng các thuật toán phức tạp để trừu tượng hóa dữ liệu ở mức cao thông qua nhiều lớp xử lý Phương pháp này bao gồm việc áp dụng nhiều biến đổi phi tuyến, giúp cải thiện khả năng mô hình hóa và phân tích dữ liệu.
Học sâu là một nhánh của các phương pháp học máy, dựa trên việc học đại diện của dữ liệu Một quan sát, như hình ảnh, có thể được biểu diễn dưới nhiều dạng khác nhau, chẳng hạn như vector cường độ điểm ảnh hoặc các hình dạng trừu tượng Một số đại diện giúp việc học các nhiệm vụ như nhận diện khuôn mặt hoặc biểu hiện cảm xúc trở nên dễ dàng hơn Hứa hẹn lớn của học sâu là thay thế các tính năng thủ công bằng các thuật toán hiệu quả cho học không giám sát hoặc nửa giám sát, cùng với tính năng phân cấp.
Hinh 1.5: Học sau nhận dạng khuôn mặt hoặc biểu hiện cảm xúc trên khuân mặt
Các nghiên cứu trong lĩnh vực này nhằm cải thiện các đại diện và phát triển mô hình để hiểu các đại diện từ dữ liệu không dán nhãn lớn Nhiều đại diện được lấy cảm hứng từ những tiến bộ trong khoa học thần kinh, dựa trên các lý thuyết về xử lý và truyền thông thông tin trong hệ thống thần kinh Điều này bao gồm mã hóa thần kinh nhằm xác định mối quan hệ giữa các kích thích khác nhau và các phản ứng thần kinh trong não.
Nhiều kiến trúc Deep Learning như mạng nơ-ron sâu, mạng nơ-ron tích chập sâu, mạng niềm tin sâu và mạng nơ-ron tái phát đã được áp dụng thành công trong các lĩnh vực như thị giác máy tính, nhận dạng giọng nói, xử lý ngôn ngữ tự nhiên, nhận dạng âm thanh và tin sinh học, mang lại kết quả xuất sắc cho nhiều nhiệm vụ khác nhau.
Tổng kết chương
Chương này tổng hợp kiến thức lý thuyết cơ bản về khai phá dữ liệu, giới thiệu các kỹ thuật khai phá dữ liệu như phân lớp và phân cụm Đồng thời, chương cũng phân tích và so sánh khai phá dữ liệu với các phương pháp cơ bản khác.
MỘT SỐ PHƯƠNG PHÁP VÀ KỸ THUẬT PHÂN LỚP DỮ LIỆU
Tổng quan về phân lớp dữ liệu
Phân lớp là một yếu tố quan trọng trong việc sắp xếp và tìm kiếm đối tượng, giúp nâng cao hiệu quả làm việc Trong các cơ sở dữ liệu, thuộc tính "Lớp" thường được sử dụng để biểu diễn tính chất của đối tượng, như trong hệ thống quản lý tư liệu của thư viện với các loại tư liệu như "Tin học" hay "Vật lý" Trước đây, việc gán giá trị cho thuộc tính lớp thường được thực hiện thủ công, nhưng với sự gia tăng nhanh chóng của thông tin và dữ liệu, phương pháp này đã trở nên khó khăn và gần như không khả thi Do đó, các phương pháp phân lớp tự động trở nên cần thiết và là một trong những chủ đề chính trong lĩnh vực khai phá dữ liệu.
Cơ sở dữ liệu thường chứa nhiều thông tin ẩn có thể sử dụng cho quá trình phân lớp Các thuật toán phân lớp phân tích dữ liệu để tìm ra các mô hình mô tả lớp dữ liệu, từ đó xác định lớp của một phần tử dữ liệu mới.
Việc xác định lớp của một phần tử dữ liệu mới là rất quan trọng, hỗ trợ cho quá trình ra quyết định thông minh và đôi khi mang tính sống còn Chẳng hạn, trong lĩnh vực ngân hàng, nhân viên cho vay cần một hệ thống tự học từ dữ liệu lịch sử để phân loại đơn vay vốn mới thành “an toàn” hoặc “mạo hiểm”, từ đó đưa ra quyết định phù hợp Tương tự, mô hình phân lớp dự báo thời tiết có thể dự đoán thời tiết ngày mai như mưa hay nắng dựa vào các thông số như độ ẩm, sức gió và nhiệt độ của hôm nay và những ngày trước.
Hay là một bác sỹ mong muốn có hệ thống phân tích dữ liệu điều trị lịch sử để dự đoán bệnh cho bệnh nhân mới dựa trên triệu chứng Trong những năm qua, phân lớp dữ liệu đã thu hút sự chú ý của các nhà nghiên cứu trong nhiều lĩnh vực như học máy, hệ chuyên gia và thống kê Công nghệ này được ứng dụng rộng rãi trong thương mại, ngân hàng, marketing, nghiên cứu thị trường, bảo hiểm, y tế và giáo dục Các thuật toán trước đây thường sử dụng cơ chế dữ liệu cư trú trong bộ nhớ, thao tác với lượng dữ liệu nhỏ, trong khi các thuật toán mới đã áp dụng kỹ thuật cư trú trên đĩa, cải thiện khả năng mở rộng cho các tập dữ liệu lớn lên tới hàng tỉ bản ghi.
Bài toán phân lớp liên quan đến việc dự đoán các nhãn hoặc lớp cho các phần tử dữ liệu đầu vào, với các nhãn này là các giá trị rời rạc Các giải thuật phân lớp thường hoạt động qua hai bước chính.
• Bước thứ nhất (learning step)
Quá trình học nhằm xây dựng mô hình mô tả các lớp dữ liệu hay khái niệm định trước, với đầu vào là tập dữ liệu có cấu trúc được mô tả bằng thuộc tính Mỗi phần tử dữ liệu, hay còn gọi là bộ giá trị, có thể được xem là mẫu, ví dụ, đối tượng, bản ghi hay trường hợp Trong tập dữ liệu, mỗi phần tử được giả định thuộc về một lớp định trước, với lớp là giá trị của thuộc tính gán nhãn lớp Đầu ra của quá trình này thường là các quy tắc phân lớp dưới dạng luật if-then, cây quyết định, công thức logic, hoặc mạng nơron.
Quá trình này được mô tả như trong hình 2.1
Hình 2.1: Quá trình phân lớp dữ liệu - (a) Bước xây dựng mô hình phân lớp
• Bước thứ hai (classification step)
Bước thứ hai là sử dụng mô hình đã xây dựng để phân lớp dữ liệu mới Đầu tiên, độ chính xác dự đoán của mô hình được ước lượng bằng kỹ thuật Holdout, sử dụng tập dữ liệu kiểm tra với các mẫu đã được gán nhãn lớp Các mẫu này được chọn ngẫu nhiên và độc lập với dữ liệu đào tạo Độ chính xác được tính bằng tỷ lệ phần trăm mẫu phân lớp đúng so với thực tế Nếu độ chính xác ước lượng từ tập dữ liệu đào tạo, kết quả có thể khả quan nhưng dễ dẫn đến hiện tượng "quá vừa" dữ liệu, tức là mô hình phù hợp quá mức với đặc điểm của tập dữ liệu đó Do đó, cần sử dụng tập dữ liệu kiểm tra độc lập Nếu độ chính xác chấp nhận được, mô hình có thể được áp dụng để phân lớp dữ liệu tương lai với giá trị thuộc tính chưa biết.
Hình 2.2 : Quá trình phân lớp dữ liệu - (b1) Ước lượng độ chính xác của mô hình
Hình 2.3: Quá trình phân lớp dữ liệu - (b2) Phân lớp dữ liệu mới
Trong mô hình phân lớp, thuật toán phân lớp đóng vai trò quyết định đến thành công của toàn bộ hệ thống Vì vậy, việc tìm kiếm một thuật toán phân lớp nhanh, hiệu quả, chính xác và có khả năng mở rộng là rất quan trọng Đặc biệt, khả năng mở rộng của thuật toán được chú trọng phát triển Nhiều kỹ thuật phân lớp đã được áp dụng trong những năm qua để cải thiện hiệu suất và độ chính xác của mô hình.
Phân lớp dữ liệu bằng cây quyết định
J Ros Quinlan là người phát triển giải thuật cây quyết định có tên là ID3 (viết tắt từ cụm từ “Iterative Dechotomiser”), sau đó cũng chính tác giả này đề xuất giải thuật phân lớp C4.5 (một hậu duệ của thuật toán ID3) Giải thuật C4.5 này đã được dùng làm chuẩn (benchmark) để các thuật toán mới so sánh Cũng trong khoảng thời gian này thì một nhóm các nhà thống kê gồm L Breiman, J Friedman,
R Olshen và C Stone đã xuất bản cuốn sách “Classfication and Regression Tree (CART)” mô tả phương pháp tạo cây quyết định nhị phân Giải thuật ID3 và CART đã trở thành các hòn đá tảng và nó mở đầu cho hàng loạt các giải thuật dựa trên học quy nạp cây quyết định (decision tree induction) Giải thuật học dựa trên cây quyết định hoạt động trên tập dữ liệu được biểu diễn bằng cách giá trị rời rạc, trong trường hợp dữ liệu được biểu diễn bằng các thuộc tính có giá trị liên tục thì cần thực hiện bước rời rạc hóa Các giải thuật ID3, CART và C4.5 đều áp dụng cách tiếp cận ăn tham (greedy) (một thuật toán không quay lui (non-backtracking)) để xây dựng cây theo hướng từ trên xuống Tập dữ liệu huấn luyện sẽ được chia thành các tập nhỏ hơn trong quá trình xây dựng cây theo cơ chế chia để trị (devide-and-conquer) Dười đây mô tả thuật toán xây dựng cây cơ bản chung của các giải thuật này
Hình 2.4:Phân lớp cho bài toán cho vay vốn của ngân hàng
Thuật toán xây dựng cây quyết định Đầu vào: Tập D chứa dữ liệu huấn luyện attribute_list chứa danh sách các thuộc tính ứng cử
Dữ liệu huấn luyện Giải thuật ID3 học Đữ liệu kiểm thử Đánh giá
Tập luật phân lớp Đánh giá
Nhãn lớp a) b) Đầu ra: Cây quyết định
Generate_decision_tree (D, attribute_list)
1 Tạo một nút gốc N cho cây quyết định
2 If toàn bộ dữ liệu trong D đều thuộc lớp C, return nút N là nút lá có nhãn C
3 If attribute_list là rỗng, return nút N với nhãn là lớp xuất hiện nhiều nhất trong D
4 splitting_attribute = attribute_selection_method (D, attribute_list) tìm thuộc tính phân chia tốt nhất
5 Gán cho nút N nhãn là splitting_attribute
6 attribute_list attribute_list \ {splitting_attribute}
(loại bỏ thuộc tính splitting_attribute khỏi attribute_list)
7 For each giá trị j của thuộc tính splitting_attribute
7.1 Gọi 𝐷 𝑗 là tập chứa các phần tử dữ liệu mà thuộc tính splitting_attribute có giá trị j
7.2 If 𝐷 𝑗 là rỗng thì thêm một nút lá 𝑁 𝑗 cho nút N có nhãn là nhãn phổ biến nhất xuất hiện trong D
7.3 Else gắn cây trả về bởi Generate_decision_tree
Hình 2.5:Thuật toán xây dựng cây quyết định
Trong bài viết này, attribute_list đại diện cho tập hợp các thuộc tính mô tả dữ liệu huấn luyện D Hàm attribute_selection_method được sử dụng để chọn thuộc tính tốt nhất cho việc phân chia dữ liệu, dựa trên các thuật toán heuristic Mục tiêu của phương pháp này là xác định thuộc tính có khả năng phân biệt các phần tử dữ liệu trong tập D thành các lớp khác nhau Để thực hiện điều này, phương pháp thường sử dụng các chỉ số như độ lợi thông tin (information gain) hoặc chỉ số Gini (Gini index) nhằm tìm ra thuộc tính tối ưu nhất.
Giải thuật bắt đầu bằng việc tạo ra nút N mô tả tập dữ liệu D Nếu tất cả dữ liệu trong D có chung nhãn lớp, N sẽ trở thành nút lá với nhãn chung, và thuật toán dừng lại Ngược lại, thuật toán sẽ gọi hàm attribute_selection_method() để xác định thuộc tính tốt nhất nhằm phân chia dữ liệu D thành các phần 𝐷𝑗, và gán nhãn cho nút N bằng thuộc tính đó Quá trình này tiếp tục theo đệ quy với các tập con dữ liệu 𝐷𝑗 Hình 2.4 minh họa cây quyết định được tạo ra từ thuật toán trên tập dữ liệu bán hàng, nhằm xác định loại khách hàng có khả năng mua máy tính (buys_computer) với kết quả yes (mua) và no (không mua) Độ phức tạp của thuật toán là O(n × D × log(D)), trong đó n là số thuộc tính mô tả tập dữ liệu và D là số lượng phần tử trong D.
Bảng 2.1: Bảng dữ liệu khách hàng
ID Tuổi Thu nhập Sinh viên Đánh giá tin dụng
1 youth high no fair no
2 youth high no excellent no
3 middleaged high no fair yes
4 senior medium no fair yes
5 senior low yes fair yes
6 senior low yes excellent no
7 middleaged low yes excellent yes
8 youth medium no fair no
9 youth low yes fair yes
10 senior midium yes fair yes
11 youth midium yes excellent yes
12 middleaged midium no excellent yes
13 middleaged high yes fair yes
14 senior midium no excellent no
Khi giá trị của một thuộc tính không phải là giá trị rời rạc, như thuộc tính tuổi, phương pháp rời rạc hóa được áp dụng để chia thành ba loại tuổi: trẻ (youth), trung niên (middle_age) và già (senior) Điểm quan trọng trong thuật toán xây dựng cây quyết định là hàm lựa chọn thuộc tính tốt nhất để phân chia dữ liệu Phần tiếp theo sẽ giới thiệu một số độ đo dùng để đánh giá “chất lượng” của các thuộc tính.
Hình 2.6: Minh họa cây quyết định
• Nút gốc: là node trên cùng của cây
• Node trong: biểu diễn một kiểm tra trên một thuộc tính đơn (hình chữ nhật)
• Nhánh: biểu diễn các kết quả của kiểm tra trên node trong (mũi tên)
Node lá trong cây quyết định biểu diễn lớp hoặc sự phân phối lớp, thường được hình dung dưới dạng hình tròn Để phân lớp dữ liệu chưa biết, các giá trị thuộc tính của mẫu sẽ được kiểm tra trên cây quyết định Mỗi mẫu sẽ có một đường đi từ gốc đến lá, và lá đó sẽ cho ra giá trị dự đoán cho phân lớp của mẫu.
2.2.1 Độ lợi thông tin Độ lợi thông tin (information gain) là độ đo đước sử dụng trong giải thuật ID3 Đầu tiên là công thức đo lượng thông tin kỳ vọng để phân lớp một phần tử trong tập dữ liệu D đước đo bằng công thức sau: age? student? credit_rating? no yes no youth senior
Middle_age yes excellent fair yes no yes
= − (2.1) Trong đó p i là xác suất một phần tử dữ liệu trong D thuộc vào lớp C i và nó được ước lượng bằng công thức i i p D
Tập D bao gồm các phần tử dữ liệu thuộc lớp C i, với m là số lượng lớp trong D Việc sử dụng hàm logarit cơ số 2 là cần thiết để đo lường thông tin theo đơn vị bit, theo lý thuyết thông tin.
C Shannon) Hàm info(D) còn được gọi là entropy của D
Khi phân chia dữ liệu D theo thuộc tính A với v giá trị khác nhau {a1, a2, , av}, dữ liệu sẽ được chia thành v tập con {D1, D2, , Dv}, trong đó Dj là tập hợp các phần tử có giá trị thuộc tính A là ai Mỗi tập con này tương ứng với một nhánh trong cây quyết định Mục tiêu lý tưởng là các tập con này phải đồng nhất, tức là các phần tử trong đó đều thuộc về một lớp Tuy nhiên, trong thực tế, các tập con thường không đồng nhất do chứa phần tử thuộc nhiều lớp khác nhau, vì vậy cần thêm thông tin để phân lớp chính xác Lượng thông tin cần thiết này được đo bằng một chỉ số nhất định.
D được sử dụng làm trọng số cho tập con D J Giá trị của info A (D) đại diện cho lượng thông tin kỳ vọng để phân lớp một phần tử dữ liệu trong D thông qua việc chia dữ liệu bằng thuộc tính A Giá trị này càng nhỏ thì độ đồng nhất của các tập con càng cao Cuối cùng, hàm đo độ lợi thông tin được tính bằng công thức.
Giá trị Gain(A) cho thấy mức độ lợi ích khi chia dữ liệu theo thuộc tính A; giá trị càng cao thì thuộc tính đó càng có giá trị trong việc phân nhánh cây quyết định Để minh họa, chúng ta tính toán giá trị Gain cho một thuộc tính trong tập dữ liệu ở bảng 2.1, trong đó trường cuối cùng là nhãn dữ liệu (Mua máy tính) với 2 giá trị: yes và no Cụ thể, có 9 phần tử dữ liệu có nhãn yes và 5 phần tử có nhãn no, từ đó áp dụng công thức (1.2) để tính toán giá trị Gain.
Tiếp đến theo công thức (2.2) ta tính giá trị của hàm cho thuộc tính tuổi (age):
Tiếp đến theo công thức (2.3) ta có độ lời thông tin theo thuộc tính tuổi sẽ là:
Gain age =info D −info D = − = bits
Chúng ta có thể tính giá trị độ lợi thông tin cho các thuộc tính như thu nhập (income), sinh viên (student) và đánh giá tín dụng (credit_rating), với các giá trị lần lượt là Gain(income) = 0.092 bits, Gain(student) = 0.151 bits và Gain(credit_rating) = 0.048 bits Kết quả cho thấy thuộc tính tuổi sẽ được chọn để phân chia dữ liệu Khi lặp lại quá trình xây dựng cây với các tập con dữ liệu đã loại bỏ thuộc tính tuổi, chúng ta sẽ thu được cây quyết định như hình (2.6).
Hình 2.7: Thuộc tính tuổi có thông tin thu được cao nhất
2.2.2 Tỉ số độ lợi Độ đo độ lợi thông tin hoạt động không tốt trong trường hợp một thuộc tính có nhiều giá trị Vì dụ, thuộc tính mã sản phẩm (product_ID), hay mã giao dịch sẽ có rất nhiều giá trị Đặc biệt nữa, khi chia dữ liệu theo thuộc tính này thì mỗi một tập con dữ liệu sẽ chỉ có tương ứng một bản ghi, do đó các tập con này là hoàn toàn đồng nhất Hay nói một cách khác, lượng thông tin cần để phân lớp tập dữ liệu D dưa trên cách phân chia dữ liệu trên thuộc tính này InfoProduct_ID(D)= 0 Và giá trị độ lợi thông tin sẽ đạt giá tri tối đa:
Gian (Product_ID) = Info(D)- Info Product_ID (D)=Info(D)
Nhưng rõ ràng việc phân lớp dựa trên thuộc tính này là vô nghĩa
Trong giải thuật C4.5, tác giả đã giới thiệu một độ đo mới gọi là tỉ số độ lợi (gain ratio) nhằm khắc phục nhược điểm của giải thuật ID3 Hàm tỉ số độ lợi này sử dụng phương pháp chuẩn hóa độ lợi thông tin thông qua giá trị phân chia thông tin (split information), được định nghĩa tương tự như hàm.
Giá trị này thể hiện thông tin tiềm năng được tạo ra khi chia tập dữ liệu huấn luyện D thành v tập con, tương ứng với các giá trị của thuộc tính A.
Phân lớp dữ liệu Bayesian
Bộ phân lớp Bayesian là một thuật toán phân lớp thống kê, dự đoán xác suất một phần tử dữ liệu thuộc về một lớp cụ thể Dựa trên định lý Bayes do Thomas Bayes phát triển, bộ phân lớp này, như Naive Bayes, cho thấy độ chính xác cao và tốc độ nhanh hơn so với các phương pháp như cây quyết định và mạng nơron, đặc biệt khi xử lý các cơ sở dữ liệu lớn.
Mục 2.3.1 nói lại các khái niệm xác suất cơ bản và định lý Bayes Sau đó ta sẽ xem phân lớp Nạve Bayes trong 2.3.2
Gọi X là một chứng cứ (evidience) (trong bài toán phân lớp thì X sẽ là một phần tử đữ liệu), Y là một giả thiết nào để cho X thuộc về một lớp một lớp C nào đó Trong bài toán phân lớp chúng ta muốn xác định giá trị P (Y |X) là xác suất để giả thiết Y là đúng với chứng cứ X thuộc vào lớp C với điều khiện ta biết các thông tin mô tả X P (Y |X) là một xác suất hậu nghiệm (posterior probability hay posteriori probability) của Y với điều kiện X
Trong một tập dữ liệu khách hàng, các thuộc tính quan trọng bao gồm tuổi và thu nhập Ví dụ, một khách hàng X có độ tuổi 35 và thu nhập 40.000 đô la.
Giả thiết rằng khách hàng sẽ mua máy tính, xác suất P(Y/X) thể hiện khả năng người dùng X sẽ thực hiện giao dịch này Trong khi đó, P(Y|X) phản ánh xác suất mua máy tính của người dùng X, dựa trên thông tin về tuổi tác và thu nhập của họ.
P(Y) là xác suất tiền nghiệm của Y, đại diện cho xác suất một khách hàng sẽ mua máy tính mà không cần thông tin về tuổi hay thu nhập của họ, tức là không phụ thuộc vào X P(X|Y) là xác suất của X với điều kiện Y, hay còn gọi là xác suất hậu nghiệm, ví dụ xác suất người dùng 35 tuổi với thu nhập $40.000 sẽ mua máy tính khi biết họ sẽ mua Cuối cùng, P(X) là xác suất tiền nghiệm của X, trong trường hợp này là xác suất một người trong tập dữ liệu có tuổi 34 và thu nhập $40.000 Các xác suất này được tính dựa trên định lý Bayes.
P X : Xác suất của sử kiện X xảy ra, Không quan tâm đến Y
P Y : Xác suất của sử kiện Y xảy ra, Không quan tâm đến X
P X Y : Xác suất (có điều kiện) của sự kiện X xảy ra, nếu biết rằng sự kiện
P Y X : Xác suất hậu nghiệm của Y nếu biết X
Thuật toán Bayes, dựa trên định lý Bayes, được áp dụng cho các bài toán giả định điều kiện độc lập, trong đó các đặc trưng của một lớp không ảnh hưởng hay phụ thuộc vào các đặc trưng của lớp khác.
Bộ phân lớp Nạve Bayes hay là bộ phân lớp Bayes đơn giản (simple Bayes classifier) hoạt động như sau:
1) Gọi D là tâp dữ liệu huấn luyện, trong đó mỗi phần tử dữ liệu X được biểu diễn bằng một vector chứa n giá trị thuộc tính A 1 , A 2 , , A n , X= {x 1 , x 2 , , x n }
2) Giả sử có m lớp C 1 , C 2 , , C m ; Cho một phần tử dữ liệu X, bộ phân lớp sẽ gán nhãn cho X là lớp có xác suất hậu nghiệm lớn nhất Cụ thể, bộ phân lớp Bayes sẽ dự đoán X thuộc vào lớp C i nếu và chỉ nếu:
Giá trị này sẽ được tình dựa vào định lý Bayes:
3) Để tìm giá trị xác suất lớn nhất, ta nhận thấy trong công thức (2.10) thì giá trị P(X) là giống nhau với mọi lớp nên ta không cần tìm Do đó ta chỉ cần tìm giá trị lớn nhất của P(X|C i ) x P(C i ) chú ý rằng P(C i ) được ước lượng bằng công thức
Trong bài toán phân loại, D là tập hợp các phần tử dữ liệu thuộc lớp C_i Nếu xác suất tiền nghiệm P(C_i) không xác định, ta giả định chúng bằng nhau: P(C_1) = P(C_2) = = P(C_m) Khi đó, mục tiêu là tìm giá trị P(X|C_i) lớn nhất.
4) Khi số lượng các thuộc tính mô tả dữ liệu là lớn thì chi phí tính toán P(X|Ci) là rất lớn, do đĩ để làm giảm độ phức tạp, giải thuật Nạve Bayes giả thiết các thuộc tính là độc lập nhau hay không có sự phụ thuộc nào giữa các thuộc tính Khi đó ta có thể tính:
Khi đó xác suất xảy ra của một điều kiện x mới là
P(Ci) được xác định dựa trên tần suất xuất hiện của tài liệu trong tập huấn luyện, trong khi P(x k |Ci) được tính từ các thuộc tính đã được phân tích trong quá trình huấn luyện.
Bước tính thuật toán Bayes:
Bước 1: Huấn luyện tập dữ liệu:
Bước 2: Lớp của giá trị mới được gắn cho lớp có xác suất lớn nhật theo công thức:
Phân lớp dữ liệu sử dụng máy hỗ trợ vector (SVM)
Support vector machine (SVM) là một phương pháp trong thống kê và khoa học máy tính, thuộc nhóm các kỹ thuật học có giám sát, được sử dụng để phân loại và phân tích hồi quy.
Nguyên lý cơ bản của SVM (Support Vector Machine) là xác định một siêu phẳng tối ưu để phân chia các điểm trong không gian nhiều chiều thành hai lớp khác nhau, nằm ở hai phía của siêu phẳng đó.
SVM dạng chuẩn nhận dữ liệu vào và phân loại chúng vào hai lớp khác nhau Do đó SVM là một thuật toán phân loại nhị phân
Hình 2.8 :Các điểm trong không gian D chiều
Giải thuật SVM nhằm mục tiêu tìm kiếm một siêu phẳng tối ưu trong không gian D chiều để phân chia n điểm, mỗi điểm thuộc vào một lớp ký hiệu là +1 hoặc -1 Siêu phẳng này cho phép các điểm cùng lớp nằm về một phía, đảm bảo sự phân hoạch hiệu quả giữa hai lớp.
= − = (2.14) Mỗi siêu phẳng đều có thể được viết dưới dạng một tập hợp các điểm x thỏa mãn: w x b• − =0 (2.15)
Công thức trên là tích vô hướng với vector pháp tuyến của siêu phẳng (w) và b đóng vai trò là tham số
Chúng ta cần xác định các giá trị của w và b nhằm tối đa hóa khoảng cách giữa hai siêu mặt song song, đồng thời vẫn đảm bảo khả năng phân chia dữ liệu một cách hiệu quả.
Các siêu mặt ấy được xác định bằng:
Hình 2.9: Siêu phẳng phân lớp các điểm trong không gian
Ví dụ: Giả sử ta có một tập được gán nhãn (+1): {(3,1), (3, -1), (6, 1), (6, -1)} Và tập các điểm được gán nhãn âm (-1): {(1, 0), (0, 1), (0, -1), (-1, 0)} trong mặt phẳng R+
Hình 2.10: Đồ thị biểu diễn các điểm trong mặt phẳng R+
Chúng tôi áp dụng SVM để phân loại hai lớp (+1 và -1) với dữ liệu được phân tách một cách tuyến tính Để thực hiện điều này, chúng tôi sử dụng một hàm tuyến tính nhằm phân chia hai lớp Qua quan sát, chúng tôi đã chọn ba vector hỗ trợ để tiến hành các phép toán, từ đó xác định mặt phẳng phân tách tối ưu nhất.
Hình 2.11: Các điểm lựa chọn cho siêu phẳng
Các vector hỗ trợ được cải tiến bằng cách thêm một phần tử, ví dụ, nếu s1 = (1,0), thì sẽ được chuyển đổi thành s = (1, 0, 1) Trong kiến trúc SVM, nhiệm vụ chính là xác định các giá trị α i.
Hình 2.12: Kiến trúc mô hình SVM
Khi sử dụng SVM tuyến tính, hàm chuyển đổi vector từ không gian dữ liệu đầu vào sang không gian đặc trưng được biểu diễn bằng Φ() = () I Biểu thức này có thể được viết lại dưới dạng khác.
Rút gọn biểu thức thông qua tính tích vô hướng của các vector:
Giải hệ phương trình trên có: α1 = -3.5, α2 = 0.75, α3 = 0.75 Tiếp đến tính trọng số ω thông qua công thức:
Siêu phẳng phân chia hai lớp đó là: y = wx + b với w = (1, 0) và b = -2
Hình 2.13: Đồ thị biểu diễn siêu phẳng tìm được
2.4.1 Phân lớp đa lớp với SVM
Thuật toán SVM truyền thống chỉ xử lý dữ liệu với 2 lớp, nhưng trong thực tế, dữ liệu có thể có nhiều lớp hơn May mắn thay, đã có các giải pháp để mở rộng SVM nhằm giải quyết các bài toán đa lớp hiệu quả.
Bài toán phân lớp câu hỏi đòi hỏi một bộ phân lớp đa lớp, do đó cần cải tiến SVM cơ bản (chỉ phân lớp nhị phân) thành một bộ phân lớp đa lớp hiệu quả hơn.
Một trong những phương pháp cải tiến trong phân lớp là sử dụng thuật toán 1-against-all, chuyển đổi bài toán phân lớp nhiều lớp thành nhiều bài toán phân lớp nhị phân.
• Giả sử tập dữ liệu mẫu (x 1 , y 1 ), , (x m , y m ) với x i là một vector n chiều và y i Y là nhãn lớp được gán cho vector x i (có m nhãn lớp khác nhau)
• Biến đổi tập Y ban đầu thành m tập có hai lớp con Z i = y Y i , −y i
Áp dụng SVM để phân lớp nhị phân cơ bản với m tập Z i nhằm xây dựng siêu phẳng cho phân lớp này, từ đó tạo ra m bộ phân lớp nhị phân.
Bộ phân lớp với sự kết hợp của m bộ phân lớp trên được gọi là bộ phân lớp đa lớp mở rộng với SVM
Phân lớp dữ liệu với Random Forest (rừng ngẫu nhiên)
Phương pháp Random Forest, được giới thiệu bởi Breiman (2001), là một trong những kỹ thuật tập hợp mô hình hiệu quả nhất, sử dụng một tập hợp các cây quyết định không cắt nhánh Mỗi cây được xây dựng từ mẫu bootstrap và tại mỗi nút, việc phân hoạch được thực hiện bằng cách chọn ngẫu nhiên một tập con các thuộc tính Độ chính xác tổng quát của rừng phụ thuộc vào độ chính xác của từng cây và sự phụ thuộc lẫn nhau giữa các cây Giải thuật này duy trì độ bias thấp và sử dụng tính ngẫu nhiên để giảm thiểu sự tương quan giữa các cây Random Forest cho độ chính xác cao so với các thuật toán học có giám sát hiện tại, có khả năng chịu đựng nhiễu tốt và không gặp tình trạng học vẹt Như Breiman (2001) đã chỉ ra, Random Forest học nhanh, hiệu quả trong việc phân loại và hồi quy, đáp ứng tốt các yêu cầu thực tiễn.
Rừng ngẫu nhiên là một phương pháp học máy sử dụng nhiều cây quyết định không cắt nhánh, được xây dựng từ các mẫu bootstrap (mẫu ngẫu nhiên có hoàn lại) Tại mỗi nút của cây, việc phân hoạch được thực hiện bằng cách chọn ngẫu nhiên một tập con các thuộc tính để đảm bảo tính ngẫu nhiên và giảm thiểu hiện tượng quá khớp.
Độ chính xác tổng quát của rừng phụ thuộc vào sự chính xác của từng cây thành viên và mối quan hệ tương tác giữa các cây Giải thuật rừng ngẫu nhiên đạt độ chính xác cao khi so sánh với các thuật toán học có giám sát hiện nay, cho thấy khả năng chống chịu tốt.
Với bài toán phân lớp: cho một tập dữ liệu huấn luyện D ( ) d i i N 1 ( x y i , i ) i N 1
= với x i là vector M chiều, y i Y , trong đó: Y gọi là lớp, giả sử có C nhãn lớp
Y C C Ý tưởng chính của mô hình RF là lựa chọn ngẫu nhiên 2 lần
(ngẫu nhiện mẫu và ngẫu nhiện thuộc tính) trong suốt quá trình xây dựng cây gồm có 3 pha như sau:
Pha 1: Từ dữ liệu ban đầu D, sử dụng kỹ thuật boostrap (lấy mẫu ngẫu nhiên có hoàn lại) để tạo ra t tập dữ liệu con S = {𝑆1, 𝑆2 , 𝑆t }
Pha 2: Trên mỗi tập dữ liệu Sj, xây dựng một cây quyết định ℎ𝑗 Mô hình Rừng ngẫu nhiên là mô hình h= h i t j = 1 Thay vì sử dụng tất cả các biến là biến ứng cử để lựa chọn điểm chia tốt nhất, tại mỗi nút RF chọn ngẫu nhiên một không gian tập con M’ thuộc tính từ M thuộc tính ban đầu (M’