Chương 1: Giới thiệu 8 Chương 2.1 Bài toán Phân lớp trong KPDL Phân lớp là một hình thức phân tích dữ liệu nhằm rút ra những mô hình mô tả những lớp dữ liệu quan trọng. Những mô hình này, gọi là mô hình phân lớp (classifier hoặc classification model), được dùng để dự đoán những nhãn lớp có tính phân loại (categorical), rời rạc và không có thứ tự cho những đối tượng dữ liệu mới. Ví dụ, ta có thể xây dựng một mô hình phân lớp để phân loại những đơn xin vay tiền của ngân hàng là an toàn hay rủi ro. Việc phân tích như thế giúp ta hiểu rõ hơn về hầu hết dữ liệu.
Các nhà nghiên cứu đã đề xuất nhiều phương pháp phân lớp trong học máy (machine learning), nhận dạng mẫu (pattern recognition), và thống kê học (statistics). Phân lớp có nhiều ứng dụng, bao gồm cả phát hiện lừa đảo, tiếp thị theo khách hàng mục tiêu (target marketing), dự đoán hiệu năng làm việc (performance prediction), sản xuất, và chẩn đoán bệnh trong y khoa, … 2.1 Các khái niệm cơ bản Chúng tôi giới thiệu khái niệm về phân lớp trong tiểu mục 2.2 mô tả cách tiếp cận chung để phân lớp như một quy trình gồm hai bước: ở bước 1, ta xây dựng một mô hình phân lớp dựa trên những dữ liệu đã có từ trước; ở bước 2, ta xác định xem độ chính xác của mô hình có chấp nhận được hay không, và nếu chấp nhận được thì ta sẽ dùng mô hình ấy để phân lớp dữ liệu mới.1 Phân lớp là gì? Một viên chức ngân hàng phụ trách cho vay cần phân tích dữ liệu của khách hàng để tìm hiểu xem những người xin vay nào là “an toàn” (safe) hoặc “rủi ro” (risk) cho Chương 2: Cơ sở lý thuyết 9 ngân hàng. Một giám đốc tiếp thị tại công ty AllElectronics cần xử lý dữ liệu để dự đoán một khách hàng với tiểu sử sơ lược cho trước sẽ mua máy tính mới hay không. Một nhà nghiên cứu y học muốn phân tích dữ liệu bệnh ung thư vú để dự đoán là nên áp dụng cách nào trong số ba cách điều trị cụ thể cho một bệnh nhân.
Trong mỗi ví dụ này, công việc phân tích dữ liệu là phân lớp, trong đó một mô hình phân lớp được xây dựng để dự đoán các nhãn lớp (có tính phân loại), như “safe” hoặc “risk” đối với dữ liệu xin vay tiền; “yes” hoặc “no” đối với dữ liệu tiếp thị; hoặc “treatment A”, “treatment B”, hay “treatment C” đối với dữ liệu y học. Các nhãn lớp này có thể được biểu diễn bằng những giá trị rời rạc, trong đó thứ tự giữa các giá trị không có ý nghĩa. Ví dụ, các giá trị 1, 2, và 3 có thể được dùng để biểu diễn các cách điều trị A, B, và C, ở đó không có hàm ý gì về thứ tự trong nhóm các cách điều trị này. Giả sử người giám đốc tiếp thị ở trên muốn dự đoán rằng một khách hàng cho trước sẽ tiêu bao nhiêu tiền trong một lần mua hàng tại công ty AllElectronics.
Công việc phân tích dữ liệu này là một ví dụ về dự đoán số (numeric prediction), ở đó mô hình xây dựng được dùng để dự đoán một hàm có trị liên tục hay giá trị có thứ tự, trái ngược với các nhãn lớp. Mô hình này là một mô hình dự đoán (predictor). Phân tích hồi quy (regression analysis) là một phương pháp thống kê, thường được dùng cho dự đoán số; vì thế hai thuật ngữ này thường được xem là đồng nghĩa với nhau, mặc dù vẫn có những phương pháp dự đoán số khác. Phân lớp và dự đoán số là hai loại chính trong số các bài toán dự đoán.
Ở đây ta chỉ tập trung vào bài toán phân lớp.2 Cách tiếp cận chung đối với bài toán phân lớp Phân lớp dữ liệu là một quá trình gồm hai bước: một bước học (trong đó xây dựng nên một mô hình phân lớp) và một bước phân lớp (trong đó mô hình vừa xây dựng được sử dụng để dự đoán các nhãn lớp cho những dữ liệu nào đó).1 minh họa quá trình này cho trường hợp dữ liệu xin vay tiền. Dữ liệu ấy đã được đơn giản hóa để dễ minh họa. Trong thực tế, có thể ta cần xem xét nhiều thuộc tính hơn. Chương 2: Cơ sở lý thuyết 10 Hình 2.1a: Bước học/huấn luyện trong quá trình phân lớp hai bước [5].1b: Bước phân lớp trong quá trình phân lớp hai bước [5].
Ở bước thứ nhất, ta xây dựng một mô hình phân lớp mô tả một bộ xác định trước các lớp dữ liệu hay khái niệm. Đây là bước học (hay giai đoạn huấn luyện), ở đó một giải thuật phân lớp xây dựng nên mô hình phân lớp bằng cách phân tích hoặc “học hỏi Chương 2: Cơ sở lý thuyết 11 từ” một tập huấn luyện (training set) hình thành từ các bản ghi trong cơ sở dữ liệu và các nhãn lớp liên kết với chúng. Mỗi bản ghi X được biểu diễn bởi một vector thuộc tính (attribute vector) gồm n-chiều, X = (x1, x2, …, xn), mô tả n giá trị đo đã thực hiện trên bản ghi đó từ n thuộc tính tương ứng của cơ sở dữ liệu A1, A2, …, An2. Mỗi bản ghi X được giả định là thuộc về một lớp được quy định trước, như được xác định bởi một thuộc tính khác của cơ sở dữ liệu gọi là thuộc tính nhãn lớp (class label attribute).
Thuộc tính nhãn lớp này có trị rời rạc và không có thứ tự. Nó có tính phân loại (categorical hay nominal) ở chỗ mỗi giá trị của nó đóng vai trò một loại (category) hoặc lớp (class). Các bản ghi riêng rẽ tạo thành tập huấn luyện được gọi là các bản ghi huấn luyện (training tuple) và được lấy mẫu ngẫu nhiên từ cơ sở dữ liệu đang phân tích. Trong ngữ cảnh phân lớp, các bản ghi của cơ sở dữ liệu có thể được các tài liệu khác nhau gọi là mẫu (sample), ví dụ (example), thể hiện (instance), điểm dữ liệu (data point), hoặc đối tượng (object)3.
Do nhãn lớp của mỗi bản ghi huấn luyện đều được cung cấp sẵn, nên bước này còn được gọi là học có giám sát (supervised learning, tức là việc học của mô hình phân lớp là “có giám sát” ở chỗ nó được cho biết là mỗi bản ghi huấn luyện thuộc về lớp nào). Nó trái với học không giám sát (unsupervised learning, hay còn gọi là gom cụm – clustering), trong đó ta không biết nhãn lớp của mỗi bản ghi huấn luyện và có thể cả số lượng hoặc tập hợp các lớp cần học nữa. Ví dụ, nếu như ta không có dữ liệu loan_decision (tức quyết định cho vay) cho tập huấn luyện, ta có thể dùng kỹ thuật gom cụm để cố gắng xác định các “nhóm các bản ghi giống nhau”, các nhóm này có thể tương ứng với các nhóm nguy cơ bên trong dữ liệu xin vay tiền. 2 Mỗi thuộc tính đại diện cho một “đặc điểm” (feature) của X.
Do đó các tài liệu về nhận dạng mẫu dùng thuật ngữ vector đặc điểm thay cho vector thuộc tính. Trong luận văn này, chúng tôi dùng thuật ngữ vector thuộc tính, và trong cách ký hiệu của chúng tôi, bất kỳ biến nào đại diện cho một vector đều được trình bày bằng kiểu chữ đậm và nghiêng, các giá trị đo mô tả vector đó được trình bày bằng kiểu chữ nghiêng (ví dụ: X = (x1, x2, x3)). 3 Trong các tài liệu về học máy, các bản ghi huấn luyện thường được gọi là mẫu huấn luyện (training sample) hoặc ví dụ huấn luyện (training example). Chương 2: Cơ sở lý thuyết 12 Bước thứ nhất của quá trình phân lớp còn có thể được xem như là việc học (hay tìm kiếm) một ánh xạ hay hàm y = f(X) mà có thể dự đoán được nhãn lớp y liên kết với một bản ghi X cho trước.
Theo cách quan sát này, chúng ta muốn tìm ra một ánh xạ hay hàm mà chia tách các lớp dữ liệu. Thông thường, ánh xạ này được biểu diễn dưới dạng các luật phân lớp, các cây quyết định, hoặc các công thức toán học. Trong ví dụ dữ liệu xin vay ngân hàng bên trên, ánh xạ này được biểu diễn dưới dạng các luật phân lớp giúp nhận diện những đơn xin vay tiền nào là an toàn hoặc rủi ro (Hình 2. Các luật này có thể được dùng để phân loại các bản ghi dữ liệu trong tương lai cũng như giúp ta hiểu biết sâu hơn về những gì hàm súc trong dữ liệu.
Chúng cũng cung cấp một cách biểu diễn dữ liệu ngắn gọn, cô đọng. Ở bước thứ hai (Hình 2.1b), mô hình tìm được ở bước thứ nhất sẽ được dùng cho việc phân loại những dữ liệu mới. Trước hết, ta đánh giá độ chính xác dự đoán (predictive accuracy) của mô hình phân loại ấy. Nếu như ta dùng tập huấn luyện để đánh giá độ chính xác của mô hình phân lớp thì việc đánh giá này nhiều khả năng là quá lạc quan, bởi vì mô hình ấy có khuynh hướng quá khớp (overfit) dữ liệu (tức là trong quá trình học, nó có thể sáp nhập luôn một số trường hợp bất thường của dữ liệu huấn luyện, vốn không hiện diện trong tổng thể tập dữ liệu nói chung).
Vì thế, ta dùng một tập kiểm tra (test set), bao gồm các bản ghi kiểm tra (test tuple) và các nhãn lớp liên kết với chúng, để thực hiện việc đánh giá này. Các bản ghi kiểm tra này độc lập với các bản ghi huấn luyện, nghĩa là chúng không được dùng để xây dựng mô hình phân lớp. Độ chính xác (accuracy) của một mô hình phân lớp trên một tập kiểm tra xác định là tỷ lệ các bản ghi của tập kiểm tra được phân loại đúng đắn bởi mô hình phân lớp ấy. Nhãn lớp liên kết của mỗi bản ghi kiểm tra được so sánh với sự dự đoán lớp của mô hình phân lớp học ứng với bản ghi đó.1 bên dưới mô tả vài phương pháp để đánh giá độ chính xác của mô hình phân lớp.
Nếu độ chính xác của mô hình phân lớp được xem là chấp nhận được, thì mô hình phân lớp có thể được dùng để phân loại Chương 2: Cơ sở lý thuyết 13 những bản ghi dữ liệu trong tương lai mà nhãn lớp chưa biết. Ví dụ, các luật phân lớp học được trong Hình 2.1a từ việc phân tích dữ liệu của những đơn xin vay tiền lúc trước, nếu có độ chính xác cao khi phân lớp tập kiểm tra, thì có thể được dùng để chuẩn thuận hoặc bác những đơn xin vay tiền mới hoặc sẽ có trong tương lai, như được minh họa trong Hình 2. Sau đây là vài phương pháp thông dụng nhất để xây dựng mô hình phân lớp: quy nạp cây quyết định, mạng Naïve Bayes, và mạng nơ-rôn (Neural Network).