Luận văn Khai thác và phân tích dữ liệu nhằm quản lý rủi ro trong giao dịch tín dụng

gì cần dạy và cách dạy. Mô hình học tập của các sinh viên có thể được nắm bắt và sử dụng để phát triển các kỹ thuật để dạy họ. Kỹ thuật sản xuất Kiến thức là tài sản tốt nhất mà một doanh nghiệp sản xuất sẽ sở hữu. Các công cụ Khai phá dữ liệu có thể rất hữu ích để khám phá các mẫu trong quy trình sản xuất phức tạp. Khai phá dữ liệu có thể được sử dụng trong thiết kế cấp hệ thống để trích xuất các mối quan hệ giữa kiến trúc sản phẩm, danh mục sản phẩm và dữ liệu nhu cầu của khách hàng. Nó cũng có thể được sử dụng để dự đoán thời gian phát triển sản phẩm, chi phí và sự phụ thuộc giữa các nhiệm vụ khác. Quản lý quan hệ khách hàng Quản lý quan hệ khách hàng là tất cả về việc có được và giữ chân khách hàng, cũng cải thiện lòng trung thành của khách hàng và thực hiện các chiến lược tập trung vào khách hàng. Để duy trì mối quan hệ đúng đắn với khách hàng, một doanh nghiệp cần thu thập dữ liệu và phân tích thông tin. Đây là nơi Khai phá dữ liệu đóng vai trò của nó. Với công nghệ Khai phá dữ liệu, dữ liệu thu thập được có thể được sử dụng để phân tích. Thay vì bối rối nơi tập trung để giữ chân khách hàng, những người tìm kiếm giải pháp có được kết quả được lọc. Phát hiện gian lận Hàng tỷ đô la đã bị mất cho các hành động gian lận. Các phương pháp phát hiện gian lận truyền thống rất tốn thời gian và phức tạp. Hỗ trợ Khai phá dữ liệu trong việc cung cấp các mẫu có ý nghĩa và biến dữ liệu thành thông tin. Bất kỳ thông tin nào là hợp lệ và hữu ích là kiến thức. Một hệ thống phát hiện gian lận 11 hoàn hảo sẽ bảo vệ thông tin của tất cả người dùng. Một phương pháp được giám sát bao gồm thu thập các hồ sơ mẫu. Những hồ sơ này được phân loại gian lận hoặc không gian lận. Một mô hình được xây dựng bằng cách sử dụng dữ liệu này và thuật toán được thực hiện để xác định xem bản ghi có lừa đảo hay không. Phát hiện xâm nhập Bất kỳ hành động nào sẽ làm tổn hại đến tính toàn vẹn và bảo mật của tài nguyên là một sự xâm nhập. Các biện pháp phòng thủ để tránh sự xâm nhập bao gồm xác thực người dùng, tránh lỗi lập trình và bảo vệ thông tin. Khai phá dữ liệu có thể giúp cải thiện phát hiện xâm nhập bằng cách thêm một mức độ tập trung vào phát hiện bất thường. Nó giúp một nhà phân tích phân biệt một hoạt động với hoạt động mạng hàng ngày phổ biến. Khai phá dữ liệu cũng giúp trích xuất dữ liệu phù hợp hơn với vấn đề. Phát hiện nói dối Bắt một tên tội phạm là dễ dàng trong khi đưa ra sự thật từ anh ta là khó khăn. Thực thi pháp luật có thể sử dụng các kỹ thuật khai thác để điều tra tội phạm, giám sát liên lạc của những kẻ khủng bố bị nghi ngờ. Điều này bao gồm khai thác văn bản cũng. Quá trình này tìm kiếm các mẫu có ý nghĩa trong dữ liệu thường là văn bản phi cấu trúc. Mẫu dữ liệu được thu thập từ các cuộc điều tra trước được so sánh và một mô hình để phát hiện nói dối được tạo ra. Với mô hình này, các quy trình có thể được tạo ra theo sự cần thiết. Phân khúc khách hàng Nghiên cứu thị trường truyền thống có thể giúp chúng tôi phân khúc khách hàng nhưng Khai phá dữ liệu đi sâu và tăng hiệu quả thị trường. Hỗ trợ Khai phá dữ liệu trong việc sắp xếp các khách hàng thành một phân khúc riêng biệt và có thể điều chỉnh các nhu cầu theo khách hàng. Thị trường luôn luôn là giữ chân khách hàng. Khai phá dữ liệu cho phép tìm một phân khúc khách hàng dựa trên lỗ hổng và doanh nghiệp có thể cung cấp cho họ các ưu đãi đặc biệt và nâng cao sự hài lòng. Ngân hàng tài chính Với ngân hàng máy tính ở khắp mọi nơi, lượng dữ liệu khổng lồ được cho là sẽ được tạo ra với các giao dịch mới. Khai phá dữ liệu có thể góp phần giải quyết các vấn đề kinh doanh trong tài chính ngân hàng bằng cách tìm ra mô hình, nguyên nhân và mối tương quan trong thông tin kinh doanh và giá cả thị trường không rõ ràng đối với các nhà quản lý vì dữ liệu khối lượng quá lớn hoặc được các chuyên gia tạo ra quá nhanh. Các nhà quản lý có thể tìm thấy những thông 12 tin này để phân khúc, nhắm mục tiêu, thu nhận, giữ chân và duy trì một khách hàng có lợi nhuận tốt hơn. Giám sát doanh nghiệp Giám sát doanh nghiệp là giám sát hành vi của một người hoặc nhóm của một công ty. Dữ liệu được thu thập thường được sử dụng cho mục đích tiếp thị hoặc bán cho các tập đoàn khác, nhưng cũng thường xuyên được chia sẻ với các cơ quan chính phủ. Nó có thể được sử dụng bởi các doanh nghiệp để điều chỉnh các sản phẩm của họ mong muốn của khách hàng của họ. Dữ liệu có thể được sử dụng cho các mục đích tiếp thị trực tiếp, chẳng hạn như quảng cáo được nhắm mục tiêu trên Google và Yahoo, nơi quảng cáo được nhắm mục tiêu đến người dùng công cụ tìm kiếm bằng cách phân tích lịch sử tìm kiếm và email của họ. Phân tích nghiên cứu Lịch sử cho thấy chúng ta đã chứng kiến những thay đổi mang tính cách mạng trong nghiên cứu. Khai phá dữ liệu rất hữu ích trong việc làm sạch dữ liệu, xử lý trước dữ liệu và tích hợp cơ sở dữ liệu. Các nhà nghiên cứu có thể tìm thấy bất kỳ dữ liệu tương tự từ cơ sở dữ liệu có thể mang lại bất kỳ thay đổi trong nghiên cứu. Xác định bất kỳ chuỗi đồng xảy ra và mối tương quan giữa bất kỳ hoạt động có thể được biết. Trực quan hóa dữ liệu và Khai phá dữ liệu trực quan cung cấp cho chúng ta một cái nhìn rõ ràng về dữ liệu. Điều tra tội phạm Tội phạm học là một quá trình nhằm xác định các đặc điểm tội phạm. Thực tế phân tích tội phạm bao gồm khám phá và phát hiện tội phạm và mối quan hệ của họ với tội phạm. Khối lượng lớn các bộ dữ liệu tội phạm và sự phức tạp của các mối quan hệ giữa các loại dữ liệu này đã khiến tội phạm học trở thành một lĩnh vực thích hợp để áp dụng các kỹ thuật Khai phá dữ liệu. Báo cáo tội phạm dựa trên văn bản có thể được chuyển đổi thành tập tin xử lý văn bản. Những thông tin này có thể được sử dụng để thực hiện quá trình khớp tội phạm. Tin học sinh học Phương pháp Khai phá dữ liệu có vẻ phù hợp lý tưởng với Tin sinh học, vì nó giàu dữ liệu. Khai phá dữ liệu sinh học giúp trích xuất kiến thức hữu ích từ các bộ dữ liệu khổng lồ được thu thập trong sinh học và trong các lĩnh vực khoa học đời sống liên quan khác như y học và khoa học thần kinh. Các ứng dụng Khai phá dữ liệu cho tin sinh học bao gồm tìm gen, suy luận chức năng protein, chẩn đoán bệnh, tiên lượng bệnh, tối ưu hóa điều trị bệnh, tái tạo mạng lưới tương tác protein và gen, làm sạch dữ liệu và dự đoán vị trí tế bào phụ protein. 13 1.7. Đề tài khai phá dữ liệu phân lớp rủi ro tín dụng Trong phạm vi luận văn, tác giả đề cập đến ứng dụng khai phá dữ liệu để phân lớp rủi ro tín dụng. Đánh giá rủi ro tín dụng là môt bước quan trọng trong hoạt động cho vay trong ngành tài chính ngân hàng. Thiếu bước này, ngân hàng sẽ không thể đưa ra quyết định khách quan về việc có nên giải ngân cho vay khách hàng hay không. Đánh giá rủi ro thường là sự cố gắng định lượng độ rủi ro mất mát của ngân hàng khi thực hiện một quyết định cho vay. Ở đây, rủi ro tín dụng có thể được định lượng bằng giá trị của tài sản thế chấp hoặc, các yếu tố thông tin về người vay, của yếu tố khả năng mất vốn, và tỷ lệ thu hồi của công cụ trong trường hợp người vay không có khả năng trả nợ Do đó ta có thể sử dụng các phương pháp phân lớp - classifications áp dụng trên thông tin dữ liệu của khách vay để phân loại nhóm khách hàng. 14 CHƯƠNG 2: BÀI TOÁN PHÂN LỚP DỰ BÁO RỦI RO TÍN DỤNG 2.1. Lý thuyết rủi ro tín dụng Khái niệm rủi ro tín dụng Tín dụng ngân hàng (cho vay) là quan hệ tín dụng giữa ngân hàng, các tổ chức tín dụng và các tổ chức kinh tế, cá nhân theo nguyên tắc hoàn trả. Việc hoàn trả được nợ gốc trong tín dụng có nghĩa là việc thực hiện được giá trị hàng hoá trên thị trường, còn việc hoàn trả được lãi vay trong tín dụng là việc thực hiện được giá trị thặng dư trên thị trường. Trong quan hệ tín dụng có hai đối tượng tham gia là ngân hàng cho vay và người đi vay [6]. Rủi ro tín dụng là:  Khoản lỗ có nguy cơ xảy ra khi ngân hàng cấp tín dụng.  Những thiệt hại mà ngân hàng gánh chịu do người vay vốn không trả đúng hạn, không thực hiện đúng nghĩa vụ cam kết trong hợp đồng cho vay vì bất kể lý do gì. Những nguyên nhân phát sinh rủi ro tín dụng Rủi ro tín dụng thường xảy ra bởi những nguyên nhân sau:  Khách hàng vay vốn gặp những nguy cơ và tai nạn bất ngờ hoặc thua lỗ trong kinh doanh nên không có tiền trả nợ dẫn đến nợ quá hạn.  Do tác động của tình hình kinh tế trong nước và thế giới.  Các vấn đề vì ham lợi nhuận, vi phạm nguyên tắc cho vay, phân tích đánh giá khách hàng sai, quyết định cho vay thiếu thông tin xác thực. Phân loại nhóm nợ Ngân hàng thực hiện phân loại nợ như sau: Nhóm 1 (nợ được đánh giá là đủ tiêu chuẩn):  Nợ còn trong hạn, chưa đến thời hạn thanh toán và được hệ thống ngân hàng đánh giá là có đủ khả năng thu hồi đầy đủ cả gốc và lãi đúng hạn.  Các món nợ khác của Khách hàng cũng đều không bị quá hạn. Nhóm 2 (nợ được đánh giá là cần chú ý):  Nợ đã quá hạn chưa quá 3 tháng.  Nợ đã được cơ cấu lại thời hạn trả nợ trong hạn. 15  Những khoản tín dụng được đánh giá là có khả năng thu hồi đầy đủ cả gốc và lãi, nhưng có dấu hiệu khách hàng bị suy giảm khả năng trả nợ. Nhóm 3 (nợ được đánh giá là dưới tiêu chuẩn):  Các khoản nợ quá hạn từ 3 tháng => đến 6 tháng.  Các khoản nợ đã được cơ cấu lại thời hạn trả nợ nhưng bị quá hạn trên 90 ngày.  Nợ được đánh giá là rủi ro có khả năng không thu hồi được đầy đủ cả gốc và lãi khi đến hạn, và có khả năng tổn thất một phần nợ gốc và lãi. Nhóm 4 (nợ nghi ngờ):  Các khoản nợ quá hạn từ 6 tháng => đến 1 năm.  Các khoản nợ được được cơ cấu lại thời hạn trả nợ nhưng bị quá hạn từ 90 đến 180 ngày.  Các khoản nợ bị đánh giá là có khả năng tổn thất cao. Nhóm 5 (nợ có khả năng bị mất vốn):  Nợ quá hạn trên 1 năm.  Các khoản nợ khoanh phải chờ Chính Phủ xử lý.  Các khoản nợ được cơ cấu lại thời hạn trả nợ nhưng bị quá hạn trên 180 ngày. Trên quan điểm phân hạng nợ Tốt/Xấu thì:  Nợ Tốt: là những khoản vay nằm trong Nhóm 1, 2  Nợ Xấu: là những khoản vay nằm trong Nhóm 3, 4, 5 Điều kiện vay vốn Các khách hàng muốn được vay vốn phải có các điều kiện sau đây:  Có năng lực pháp luật dân sự, năng lực hành vi dân sự và chịu trách nhiệm dân sự theo quy định của pháp luật  Có mục đích sử dụng vay vốn hợp pháp  Có khả năng tài chính đảm bảo trả nợ trong thời hạn cam kết  Có phương án sản xuất kinh doanh, dự án đầu tư, dịch vụ khả thi và có hiệu quả. 16 Căn cứ xác định định mức cho vay  Nhu cầu vay vốn của khách hàng.  Mức vốn của khách hàng tham gia vào dự án, phương án kinh doanh, sản xuất, dịch vụ, đời sống.  Tỷ lệ cho vay tối đa so với giá trị tài sản bảo đảm tiền vay theo quy định về bảo đảm tiền vay của ngân hàng.  Khả năng hoàn trả nợ của khách hàng.  Khả năng nguồn vốn của mỗi ngân hàng và không được vượt quá định mức cho vay được ủy quyền bởi tổng giám đốc Ngân hàng cho vay. Đối tượng áp dụng Ngân hàng cho vay các đối tượng sau:  Giá trị vật tư, máy móc, hàng hoá, thiết bị và các khoản chi phí để khách hàng thực hiện các dự án sản xuất, kinh doanh dịch vụ... Ngân hàng không cho vay các đối tượng sau:  Số tiền thuế phải nộp.  Số tiền để trả nợ gốc và lãi vay cho các tổ chức tín dụng khác.  Số tiền vay trả cho chính tổ chức tín dụng cho vay vốn. Mô hình lượng hóa rủi ro tín dụng cho khách hàng cá nhân Dưới đây là bảng tiêu chí cho mô hình chấm điểm tín dụng khách hàng cá nhân của VietinBank. Bảng 2: Chấm điểm tín dụng khách hàng cá nhân tại VietinBank STT Các hạng mục xác định chất lượng tín dụng Điểm số 1 Nghề nghiệp của người vay Chuyên gia hay phụ trách kinh doanh Công nhân có kinh nghiệm (tay nghề cao) Nhân viên văn phòng Sinh viên Công nhân không có kinh nghiệm Công nhân bán thất nghiệp 10 8 7 5 4 2 2 Trạng thái nhà ở 17 STT Các hạng mục xác định chất lượng tín dụng Điểm số Nhà riêng Nhà thuê hay căn hộ Sống cùng bạn hay người thân 6 4 2 3 Xếp hạng tín dụng Tốt Trung bình Không có hồ sơ Tồi 10 5 2 0 4 Kinh nghiệm nghề nghiệp Nhiều hơn 1 năm 5 Từ 1 năm trở xuống 5 2 5 Thời gian cư trú tại điểm hiện tại Nhiều hơn 1 năm Từ 1 năm trở xuống 2 1 6 Điện thoại cố định Có Không 2 0 7 Số người sống phụ thuộc Không Một Hai Ba Nhiều hơn ba 3 3 4 4 2 8 Các tài khoản tại ngân hàng Tiết kiệm thẻ & Tài khoản tiết kiệm Tài khoản tiết kiệm Tiết kiệm thẻ Không có 4 3 2 0 Khi cấp tín dụng cho khách hàng, ngân hàng thường căn cứ vào 3 chỉ tiêu là:  Nguồn trả nợ của khách 18  Tài sản thế chấp  Mục đích sử dụng vốn vay Ba tiêu chí trên tác động chủ yếu đến điểm tín dụng của khách hàng. Căn cứ vào kết quả điểm tín dụng, ngân hàng sẽ phân loại và cấp tín dụng cho khách Tuy nhiên, ngay cả khi khách hàng trong trường hợp được đánh giá là loại tốt, 3 tiêu chí trên đều tốt, thì với việc ngân hàng cấp vốn vay, nguy cơ rủi ro là vẫn có thể xảy ra. Vì RRTD ảnh hưởng rất lớn đến sự phát triển của ngân hàng cũng như của nền kinh tế nói chung nên việc dự đoán để phòng ngừa rủi ro đóng vai trò hết sức quan trọng. Do đó, việc áp dụng các Kỹ thuật Khai phá dữ liệu cho bài toán RRTD để tìm ra những nguồn tri thức mới, giúp cho các chuyên gia ngân hàng đánh giá, phòng ngừa rủi ro là rất cần thiết. 2.2. Phát biểu bài toán Hình 2.3.1: Phát biểu bài toán Đầu vào:  Tập thông tin khách hàng và lịch sử trả nợ của các khách hàng bao gồm o Tập huấn luyện (Training Set) nhằm mục đích xây dựng mô hình o Tập kiểm thử (Testing Set) nhằm mục đích kiểm chứng mô hình  Tập thông tin khách hàng mới cần dự báo Áp dụng mô hình Dữ liệu trên corebank Dữ liệu Huấn luyện Dữ liệu Kiểm thử Kiểm thử mô hình Mô hình phân lớp Xây dựng mô hình Khách hàng mới Nợ Tốt Nợ Xấu Dự đoán Phân loại nợ 19 Đầu ra:  Đưa ra mô hình phân lớp dự báo, các chỉ số đánh giá mô hình, các luật rút ra từ mô hình giúp phân loại các khách hàng mới. Ví dụ:  Đầu vào: o Thông tin khách hàng về khách hàng vay vốn: Mục đích vay mua nhà, có thu nhập trên 11 triệu, đang thuê nhà, làm tại công ty phần mềm, chức vụ chuyên viên, thời gian đã công tác trong lĩnh vực chuyên môn dưới 3 năm  Đầu ra: o Dự báo khách hàng có khả năng rơi vào nhóm nợ cần chú ý (nhóm 2) Mục tiêu của bài toán là xây dựng mô hình chứa các tập luật ràng buộc về dữ liệu. Mô hình này sẽ là cơ sở tri thức, mà dựa vào đó có thể phân loại được khách hàng mới dựa vao thông tin đầu vào của khách vay. Việc dự báo chính xác sẽ giúp ngân hàng giảm thiểu các rủi ro có thể có từ các khách hàng có khả năng không trả được nợ 2.3. Quy trình phân lớp xây dựng mô hình Để có thể xây dựng được mô hình như yêu cầu bài toán ở mục 2.3 ta phải thực hiện thứ tự theo các bước như sau [14]: 20 a. Xây dựng mô hình từ tập huấn luyện – Training data Hình 2.4.1: Quy trình huấn luyện - training Quá trình phân lớp thực hiện nhiệm vụ xây dựng mô hình các công cụ phân lớp giúp cho việc gán nhãn phân loại cho các dữ liệu. Example:  Nhãn “An toàn” hoặc “Rủi ro” cho các yêu cầu vay vốn; “Có” hoặc “Không” cho các thông tin thị trường.  Các Nhãn dùng phân loại được biểu diễn bằng các giá trị rời rạc trong đó việc sắp xếp trùng là không có ý nghĩa. Phân lớp dữ liệu gồm hai quá trình.  Công cụ phân lớp sẽ được xây dựng để xem xét nguồn data. Đây là quá trình học, qua đó một thuật toán phân lớp được xây dựng bằng cách phân tích từ tập dữ liệu huấn luyện được xây dựng sẵn bao gồm nhiều bộ dữ liệu.  Một bộ dữ liệu X biểu diễn bằng một vector n chiều, X = (x1, x2, , xn), đây là các giá trị cụ thể của một tập n thuộc tính của nguồn dữ liệu {A1, A2, , An}. Mỗi bộ được giả sử rằng nó thuộc về một lớp được định nghĩa trước với các nhãn xác định. Classification algorithm IF age=young THEN loan_decicion=risky IF income=high THEN loan_decicion=safe IF age=middle AND income=low THEN loan_decicion=risky Chạy thuật toán Xây dựng rules Mô hình hóa 21 b. Đánh giá mô hình bằng tập kiểm kiểm thử - Data test Hình 2.4.2: Quy trình test dữ liệu c. Áp dụng mô hình để dự đoán dữ liệu mới Hình 2.4.3: Quy trình áp dụng mô hình 2.4. Mô hình phân lớp dự báo rủi ro Dựa trên quy trình phân lớp dữ liệu, ta có thể áp dụng mô hình sau vào bài toán phân lớp rủi ro tín dụng Tập huấn luyên (Training Set) Tập kiểm thử (Testing Set) Khách hàng mới Đánh giá Kết quả dự báo Mô hìnhThuật toán phân lớp Áp dụng Mô hình Các thuật toán áp dụng:  Cây quyết định C45, J48  Naïve Bayes Classifier  Thuật toán Apriori khai phá luật kết hợp Hình 2.5.1: Mô hình phân lớp dự báo rủi ro Để xây dựng được mô hình phân lớp dữ liệu ta cần 2 yếu tố  Bộ dữ liệu đầu vào (Tập huấn luyện & Tập kiểm thử) IF age=young THEN loan_decicion=risky IF income=high THEN loan_decicion=safe IF age=middle AND income=low THEN loan_decicion=risky New data risky (Jonh henry, middle, low) Loan_decicion? Model tree 22  Thuật toán phân lớp 2.5. Lựa chọn nghiên cứu thuật toán Dựa vào Ưu nhược điểm của các thuật toán đã được trình bày sơ lược ở chương I (Mục 1.6 – Các thuật toán phân lớp) Dựa vào tính chất dữ liệu của bài toán rủi ro tín dụng: các thuộc tính dữ liệu có dải giá trị không nhiều, và theo nghiệp vụ Ngân hàng thì giải giá trị rời rạc này thường được gom nhóm thành một tập hữu hạn. Ví dụ:  Tuổi của khách vay thì từ 28 – 65, nhưng thực tế thì sẽ được chia thành 5 nhóm tuổi Tín dụng để quản lý  Nơi cư trú: khách vay thì ở rất nhiều địa chỉ khác nhau, nhưng thực tế sẽ được gom nhóm thành 1 tập hữu hạn các khu vực như: Khu vực Hà Nội 1, Khu vực Hà Nội 2, Khu vực nông thôn v.v.  Tiền vay thì cũng nhận rất đa dạng các giá trị khác nhau từ 18 triệu – đến trên 18 tỷ. Nhưng cũng lại được gom thành các nhóm giá trị vay: dưới 200 triệu, từ 200-700, từ 700-1 tỷ. Tác giả nhận thấy có thuật toán (Phân lớp sử dụng cây quyết định, và Phân lớp sử dụng thuật toán Navie Bayes) phù hợp với dữ liệu của bài toán quản lý Rủi ro tín dụng. Vậy nên, trong khuôn khổ luận văn tác giả chọn đi sâu nghiên cứu 2 thuật toán này. Phân lớp Cây quyết định 2.5.1.1. Thuật toán cây quyết định Cây quyết định là một cấu trúc cây giống như sơ đồ trong đó một nút bên trong đại diện cho tính năng (hoặc thuộc tính), nhánh đại diện cho một quy tắc quyết định và mỗi nút lá đại diện cho kết quả. Nút trên cùng trong cây quyết định được gọi là nút gốc. Nó học cách phân vùng trên cơ sở giá trị thuộc tính. Nó phân vùng cây theo cách đệ quy gọi phân vùng đệ quy. Cấu trúc giống như sơ đồ này giúp bạn trong việc ra quyết định. Nó trực quan giống như một sơ đồ sơ đồ dễ dàng bắt chước tư duy cấp độ của con người. Đó là lý do tại sao cây quyết định dễ hiểu và giải thích [10]. 23 Hình 2.6.1: Cây quyết định Cây quyết định là một loại hộp trắng của thuật toán Machine Learning (ML). Nó chia sẻ logic ra quyết định nội bộ, vốn không có sẵn trong loại thuật toán hộp đen như Mạng thần kinh. Thời gian đào tạo của nó nhanh hơn so với thuật toán mạng thần kinh. Độ phức tạp thời gian của cây quyết định là một hàm của số lượng bản ghi và số lượng thuộc tính trong dữ liệu đã cho. Cây quyết định là một phương pháp không phân phối hoặc không tham số, không phụ thuộc vào các giả định phân phối xác suất. Cây quyết định có thể xử lý dữ liệu chiều cao với độ chính xác tốt. 2.5.1.2. Hoạt động của thuật toán Cây quyết định Ý tưởng cơ bản về hoạt động của thuật toán cây quyết định như sau: 1. Chọn thuộc tính tốt nhất bằng cách sử dụng các biện pháp lựa chọn thuộc tính (ASM – attribute selection measure) để phân chia các bản ghi. 2. Biến thuộc tính đó thành nút quyết định và chia tập dữ liệu thành các tập con nhỏ hơn. 3. Bắt đầu xây dựng cây bằng cách lặp lại quy trình này một cách đệ quy cho mỗi Node con cho đến khi một trong những điều kiện sẽ khớp:  Tất cả các bộ dữ liệu thuộc về cùng một giá trị thuộc tính.  Không còn thuộc tính nào nữa.  Không có nhiều trường hợp nữa. 24 Data Data Training Data Test Lựa chọn thuộc tính tốt nhất dựa vào chỉ số Gain, Gini Tách dữ liệu thành các tập nhỏ hơn theo thuộc tính cha Model tri thức Biểu diễn mô hình 1. accuracy – độ chính xác 2. precision - dự đoán 3. recall – độ hồi tưởng Lặp lại xử lý với node con Hình 2.6.2: luồng hoạt động của cây quyết định 2.5.1.3. Các biện pháp lựa chọn thuộc tính Biện pháp lựa chọn thuộc tính là một heuristic để chọn tiêu chí phân tách dữ liệu phân vùng thành cách tốt nhất có thể. Nó còn được gọi là quy tắc chia tách vì nó giúp chúng ta xác định các điểm dừng cho các bộ dữ liệu trên một nút nhất định. ASM (attribute selection measure) cung cấp thứ hạng cho từng tính năng (hoặc thuộc tính) bằng cách giải thích tập dữ liệu đã cho. Thuộc tính điểm tốt nhất sẽ được chọn làm thuộc tính chia ( Nguồn ). Trong trường hợp thuộc tính có giá trị liên tục, các điểm phân chia cho các nhánh cũng cần xác định. Các biện pháp lựa chọn phổ biến nhất là Thông tin đạt được, Tỷ lệ tăng và Chỉ số Gini. 2.5.1.4. Thông tin đạt được Shannon đã phát minh ra khái niệm entropy, đo lường sự không tinh khiết của bộ đầu vào. Trong vật lý và toán học, entropy được gọi là tính ngẫu nhiên hoặc tạp chất trong hệ thống. Trong lý thuyết thông tin, nó đề cập đến tạp chất trong một nhóm các ví dụ. Thông tin đạt được là sự giảm entropy. Độ lợi thông tin tính toán sự khác biệt giữa entropy trước khi tách và entropy trung bình sau khi tách bộ dữ liệu dựa trên các giá trị thuộc tính đã cho. Thuật toán cây quyết định ID3 (Iterative Dichotomiser) sử dụng thông tin thu được. 𝐼𝑛𝑓𝑜(𝐷) = − ∑ 𝑃𝑖 log2 𝑃𝑖 𝑚 𝑖=1 Trong đó, Pi là xác suất mà một tuple tùy ý trong D thuộc về lớp Ci. 𝐼𝑛𝑓𝑜𝐴(𝐷) = ∑ |𝐷𝑗| |𝐷| 𝑋 𝐼𝑛𝑓𝑜(𝐷𝑗) 𝑉 𝑗=1 𝐺𝑎𝑖𝑛(𝐴) = 𝐼𝑛𝑓𝑜(𝐷) − 𝐼𝑛𝑓𝑜𝐴(𝐷) 25 Ở đây:  Thông tin (D) là lượng thông tin trung bình cần thiết để xác định nhãn lớp của một tuple trong D.  | Dj | / | D | đóng vai trò là trọng lượng của phân vùng thứ j.  InfoA (D) là thông tin dự kiến cần có để phân lớp một tuple từ D dựa trên phân vùng của A.  Thuộc tính A có mức tăng thông tin cao nhất, Gain (A), được chọn làm thuộc tính tách tại nút N (). 2.5.1.5. Tỷ lệ tăng Thông tin đạt được là thiên vị cho thuộc tính với nhiều kết quả. Nó có nghĩa là nó thích thuộc tính với một số lượng lớn các giá trị riêng biệt. Chẳng hạn, hãy xem xét một thuộc tính có số nhận dạng duy nhất, chẳng hạn như customer_ID không có thông tin (D) vì phân vùng thuần túy. Điều này tối đa hóa việc đạt được thông tin và tạo phân vùng vô dụng. C4.5, một cải tiến của ID3, sử dụng một phần mở rộng để đạt được thông tin được gọi là tỷ lệ khuếch đại. Tỷ lệ khuếch đại xử lý vấn đề sai lệch bằng cách bình thường hóa mức tăng thông tin bằng cách sử dụng Thông tin phân tách. Việc triển khai Java của thuật toán C4.5 được gọi là J48, có sẵn trong công cụ Khai phá dữ liệu WEKA. 𝑆𝑝𝑙𝑖𝑡𝐼𝑛𝑓𝑜𝐴(𝐷) = − ∑ |𝐷𝑗| |𝐷| 𝑣 𝑗=1 𝑋 log2 ( |𝐷𝑗| |𝐷| ) Ở đây,  | Dj | / | D | đóng vai trò là trọng lượng của phân vùng thứ j.  v là số lượng giá trị rời rạc trong thuộc tính A. Tỷ lệ khuếch đại có thể được định nghĩa là 𝐺𝑎𝑖𝑛𝑅𝑎𝑡𝑖𝑜(𝐴) = 𝐺𝑎𝑖𝑛(𝐴) 𝑆𝑝𝑙𝑖𝑡𝐼𝑛𝑓𝑜𝐴(𝐷) Thuộc tính có tỷ lệ khuếch đại cao nhất được chọn làm nút gốc. 2.5.1.6. chỉ số Gini Một thuật toán cây quyết định khác sử dụng phương thức Gini để tạo các điểm phân chia. 26 𝐺𝑖𝑛𝑖(𝐷) = 1 − ∑ 𝑃𝑖2 𝑚 𝑖=1 Trong đó, pi là xác suất mà một tuple trong D thuộc về lớp Ci. Chỉ số Gini xem xét phân chia nhị phân cho từng thuộc tính. Bạn có thể tính tổng trọng số của tạp chất của từng phân vùng. Nếu phân chia nhị phân trên thuộc tính A phân vùng dữ liệu D thành D1 và D2, chỉ số Gini của D là: 𝐺𝑖𝑛𝑖𝐴(𝐷) = |𝐷1| |𝐷| 𝐺𝑖𝑛𝑖(𝐷1) + |𝐷2| |𝐷| 𝐺𝑖𝑛𝑖(𝐷2) Trong trường hợp thuộc tính có giá trị rời rạc, tập hợp con cung cấp chỉ số gini tối thiểu cho lựa chọn đó được chọn làm thuộc tính tách. Trong trường hợp thuộc tính có giá trị liên tục, chiến lược là chọn từng cặp giá trị liền kề làm điểm phân tách và điểm có thể có chỉ số gini nhỏ hơn được chọn làm điểm phân tách. 𝐺𝑖𝑛𝑖(𝐴) = 𝐺𝑖𝑛𝑖(𝐷) − 𝐺𝑖𝑛𝑖𝐴(𝐷) Thuộc tính có chỉ số Gini tối thiểu được chọn làm thuộc tính tách. Phân lớp Naive Bayes 2.5.2.1. Quy trình phân lớp Bất cứ khi nào bạn thực hiện phân lớp, bước đầu tiên là hiểu vấn đề và xác định các tính năng và nhãn tiềm năng. Các tính năng là những đặc điểm hoặc thuộc tính ảnh hưởng đến kết quả của nhãn. Ví dụ: trong trường hợp phân phối cho vay, quản lý ngân hàng xác định nghề nghiệp, thu nhập, tuổi tác, địa điểm, lịch sử cho vay trước đây, lịch sử giao dịch và điểm tín dụng. Những đặc điểm này được gọi là các tính năng giúp mô hình phân loại khách hàng. Việc phân lớp có hai giai đoạn, giai đoạn học tập và giai đoạn