Ứng dụng kỹ thuật phân lớp dữ liệu cho phân loại thuê bao di động Vinaphone (Luận văn thạc sĩ)
Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (1.7 MB, 71 trang )
HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG
-------------------------------------------
VI QUYẾT THẮNG
Vi Quyết Thắng
ỨNG DỤNG KỸ THUẬT PHÂN LỚP DỮ LIỆU
CHO PHÂN LOẠI THUÊ BAO DI ĐỘNG
HỆ THỐNG THÔNG TIN
VINAPHONE
LUẬN VĂN THẠC SĨ KỸ THUẬT
(Theo định hướng ứng dụng)
2016 - 2018
HÀ
NỘI
2018
HÀ NỘI, NĂM 2018
HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG
---------------------------------------
Vi Quyết Thắng
ỨNG DỤNG KỸ THUẬT PHÂN LỚP DỮ LIỆU
CHO PHÂN LOẠI THUÊ BAO DI ĐỘNG
VINAPHONE
Chuyên ngành: Hệ thống thông tin
Mã số: 8480101
LUẬN VĂN THẠC SĨ KỸ THUẬT
(Theo định hướng ứng dụng)
NGƯỜI HƯỚNG DẪN KHOA HỌC: PGS.TS. TRẦN ĐÌNH QUẾ
HÀ NỘI, NĂM 2018
i
LỜI CAM ĐOAN
Tôi xin cam đoan đây là đề tài nghiên cứu của riêng tôi, thực hiện dưới sự
hướng dẫn của PGS.TS. Trần Đình Quế.
Các kết quả nêu trong luận văn là trung thực, dựa trên số liệu thực tế do tôi
khảo sát và thu thập tại Trung tâm viễn thông 5 Móng Cái – VNPT Quảng Ninh. Kết
quả luận văn chưa từng được công bố trong bất cứ công trình nào khác.
Hà Nội, ngày 10 tháng 11 năm 2017
Họ và tên
Vi Quyết Thắng
ii
LỜI CẢM ƠN
Lời đầu tiên tôi xin gửi lời cảm ơn sâu sắc tới PGS.TS. Trần Đình Quế, Học
viện Công nghệ Bưu chính Viễn thông. Người Thầy đã dành nhiều thời gian tận tình
chỉ bảo, hướng dẫn tôi trong suốt quá trình tìm hiểu, nghiên cứu. Thầy đã đưa ra nhiều
góp ý quý báu trong suốt quá trình thực hiện để tôi có thể hoàn thành luận văn này.
Tôi xin chân thành cảm ơn các thầy, các cô thuộc khoa Công nghệ thông tin,
khoa Điện tử viễn thông tại Học viện Công nghệ Bưu chính Viễn thông đã trang bị
cho tôi những kiến thức cần thiết trong thời gian học tập tại trường.
Tôi cũng bày tỏ lòng biết ơn về sư giúp đỡ nhiệt tình của lãnh đạo cơ quan,
các đồng nghiệp tại Trung tâm viễn thông 5 Móng Cái – VNPT Quảng Ninh đã cung
cấp thông tin, dữ liệu, tài liệu cần thiết và cho tôi những lời khuyên quý báu khi thực
hiện khảo sát tại đây.
Tôi xin cảm ơn gia đình, người thân và bạn bè luôn quan tâm, động viên và
tạo mọi điều kiện tốt nhất cho tôi trong suốt quá trình thực hiện luận văn.
Tôi xin chân thành cảm ơn!
Hà Nội, ngày 10 tháng 11 năm 2017
Họ và tên
Vi Quyết Thắng
iii
MỤC LỤC
LỜI CAM ĐOAN ....................................................................................................... i
LỜI CẢM ƠN ............................................................................................................ ii
MỤC LỤC ................................................................................................................. iii
DANH MỤC CÁC THUẬT NGỮ, CHỮ VIẾT TẮT .............................................. vi
DANH MỤC CÁC BẢNG....................................................................................... vii
DANH MỤC CÁC HÌNH VẼ.................................................................................. vii
MỞ ĐẦU .....................................................................................................................1
CHƯƠNG 1: TỔNG QUAN VỀ PHÂN LỚP DỮ LIỆU ...........................................3
1.1 Giới thiệu...............................................................................................................3
1.2 Phân lớp dữ liệu ....................................................................................................3
1.2.1 Khái niệm và quy trình của phân lớp dữ liệu .................................................3
1.2.2 Các vấn đề trong phân lớp dữ liệu .................................................................5
1.2.2.1 Tiền xử lý dữ liệu ....................................................................................5
1.2.2.2 So sánh các mô hình phân lớp.................................................................6
1.3 Một số kỹ thuật phân lớp dữ liệu ..........................................................................7
1.3.1 Phân lớp dữ liệu bằng Neural Network ..........................................................7
1.3.2 Phân lớp dữ liệu bằng mạng Naïve Bayes ...................................................10
1.3.3 Phân lớp dữ liệu bằng giải thuật học ILA ....................................................13
1.3.4 Phân lớp dữ liệu bằng cây quyết định ..........................................................14
1.4 Kết luận ...............................................................................................................17
CHƯƠNG 2: CÂY QUYẾT ĐỊNH TRONG VẤN ĐỀ PHÂN LOẠI THUÊ BAO DI
ĐỘNG .......................................................................................................................18
iv
2.1 Giới thiệu.............................................................................................................18
2.2 Vấn đề phân loại thuê bao di động Vinaphone ...................................................18
2.2.1 Thực trạng tại TTVT5 Móng Cái – VNPT Quảng Ninh..............................18
2.2.2 Các vấn đề tồn tại .........................................................................................20
2.3 Ứng dụng cây quyết định trong phân loại thuê bao di động ...............................24
2.3.1 Xác định giá trị khách hàng .........................................................................24
2.3.2 Khả năng dự đoán thuê bao rời mạng ..........................................................25
2.3.2.1 Khái niệm rời mạng và tỷ lệ rời mạng ..................................................25
2.3.2.2 Kỹ thuật dự đoán rời mạng trong Viễn thông .......................................27
2.3.2.3 So sánh một số kỹ thuật dự đoán rời mạng ...........................................33
2.4 Thiết kế và xây dựng cây quyết định ..................................................................36
2.4.1 Tư tưởng thuật toán xây dựng cây quyết định .............................................36
2.4.2 Xây dựng cây quyết định .............................................................................37
2.4.2.1 Thuật toán CLS .....................................................................................38
2.4.2.2 Thuật toán ID3 ......................................................................................39
2.4.2.3 Thuật toán C4.5 .....................................................................................40
2.4.2.4 Thuật toán SLIQ ....................................................................................42
2.4.3 Cắt tỉa cây quyết định ...................................................................................42
2.5 Kết luận ...............................................................................................................43
CHƯƠNG 3: THỬ NGHIỆM VÀ ĐÁNH GIÁ .......................................................44
3.1 Giới thiệu.............................................................................................................44
3.2 Thu thập và xử lý dữ liệu ....................................................................................44
3.3 Tình hình phát hiện rời mạng được ứng dụng trong nước hiện nay ...................46
3.4 Phân loại khách hàng và dự đoán rời mạng dựa trên số tiền thanh toán ............47
v
3.5 Cài đặt .................................................................................................................51
3.6 Thử nghiệm và đánh giá ......................................................................................54
3.6.1 Thử nghiệm ..................................................................................................54
3.6.2 Đánh giá .......................................................................................................57
3.7 Kết luận ...............................................................................................................58
KẾT LUẬN ...............................................................................................................59
DANH MỤC CÁC TÀI LIỆU THAM KHẢO .........................................................61
vi
DANH MỤC CÁC THUẬT NGỮ, CHỮ VIẾT TẮT
Viết tắt
ANN
NN
ILA
TTVT5
Tiếng Anh
Artificial Neural Network
Neural Network
Inductive Learning Algorithm
Tiếng Việt
Mạng Nơ – rôn nhân tạo
Mạng Nơ – rôn
Giải thuật học quy nạp
Trung tâm viễn thông 5
vii
DANH MỤC CÁC BẢNG
Bảng 1.1: Giả thuyết cho mạng Bayes ......................................................................11
DANH MỤC CÁC HÌNH VẼ
Hình 1.1: Bước học (phân tích/ học tập huấn luyện) ..................................................4
Hình 1.2: Bước phân lớp trong quá trình phân lớp dữ liệu .........................................5
Hình 1.3: Minh họa mạng nơ-rôn nhân tạo .................................................................7
Hình 1.4: Cấu trúc một nơ-rôn ....................................................................................8
Hình 1.5: Tiến trình học của mạng nơ-rôn ..................................................................9
Hình 1.6: Ví dụ về cây quyết định ............................................................................15
Hình 2.1: Thông tin những thuê bao đã ngừng sử dụng dịch vụ ..............................22
Hình 2.2: Số lượng thuê bao rời mạng và phát triển tại TTVT5 Móng Cái - 2017 ..23
Hình 2.3: Tạo dựng mô hình khai phá dữ liệu trong viễn thông...............................32
Hình 2.4: Khả năng dự đoán của cây quyết định ......................................................33
Hình 3.1: Dữ liệu mẫu mô tả thông tin khách hàng ..................................................45
Hình 3.2: Cây quyết định phân loại thuê bao di động dựa trên số tiền thanh toán ...52
Hình 3.3: File đầu vào sau khi đã được chọn lọc thuộc tính .....................................52
Hình 3.4: Giao diện chương trình phân loại khách hàng ..........................................54
Hình 3.5: Chức năng “Dự đoán rời mạng” ...............................................................55
Hình 3.6: Biểu đồ thể hiện tỷ lệ các thuê bao di động ..............................................56
1
MỞ ĐẦU
Đầu tiên, mục đích của luận văn này là nghiên cứu thói quen, hành vi của
khách hàng viễn thông bằng các phương pháp khai phá dữ liệu để tìm ra quy luật và
xu hướng của họ nhằm hỗ trợ phát triển hoạt động kinh doanh. Trong bất cứ hoạt
động kinh doanh của bất cứ ngành nghề hay lĩnh vực nào thì vấn đề quản lý khách
hàng dựa trên khảo sát, đánh giá và phân loại khách hàng là rất quan trọng. Điều đó
nhằm mục đích hiểu họ là ai, thuộc đối tượng phục vụ như thế nào, có xu hướng thế
nào trong tương lai. Điều đó sẽ giúp ích rất nhiều cho chiến lược phát triển kinh doanh
của doanh nghiệp. Chúng ta thường nghe “Biết người biết ta, trăm trận trăm thắng”
hay là “Chia để trị”, những câu nói này đúng không chỉ trên chiến trường mà còn
chính xác trong kinh doanh bởi thương trường là chiến trường, cạnh tranh rất khốc
liệt, chúng ta sẽ nắm rõ thất bại nếu không hiểu rõ đối thủ hoặc khách hàng của mình.
Chẳng hạn, chúng ta không nên tư vấn cho một khách hàng có kinh tế eo hẹp cho một
dịch vụ đắt đỏ được – mặc dù sẽ có ngoại lệ. Hoặc chúng ta cũng phải có phương án
phục vụ khách hàng trung thành khác với khách hàng đang có nguy cơ rời bỏ mình.
Những điều trên cho thấy việc phân loại khách hàng ảnh hưởng đến chiến lược
kinh doanh của các cơ quan, tổ chức như thế nào. Trong lĩnh vực viễn thông, khách
hàng (các thuê bao di động) chính là những người mang lại doanh thu và duy trì hoạt
động cho nhà cung cấp dịch vụ, vì vậy việc nghiên cứu, phân loại và đánh giá họ để
đưa ra những quyết sách phù hợp là cần thiết. Ngoài ra, một lý do quan trọng nữa là
việc phân loại sẽ giúp nhà cung cấp tiết kiệm chi phí trong công cuộc “giữ chân”
những thuê bao đang hoạt động, tác động kịp thời để duy trì những thuê bao có ý định
rời mạng và phát triển các thuê bao mới.
Nhận thấy tầm quan trọng của việc đánh giá và phân loại khách hàng, tôi xin
trình bày luận văn với đề tài “Ứng dụng kỹ thuật phân lớp dữ liệu cho phân loại
thuê bao di động Vinaphone”. Luận văn đi sâu vào áp dụng phương pháp phân lớp
dữ liệu dựa trên cây quyết định, từ đó sẽ đánh giá, phân loại và dự đoán hành vi của
các thuê bao di động đang hoạt động.
2
Luận văn này có tất cả ba chương:
Chương 1: Tổng quan về phân lớp dữ liệu
Chương này trình bày về cơ sở lý thuyết như khái niệm, trình bày một số
phương pháp phân lớp dữ liệu phổ biến. Tìm hiểu các điểm mạnh điểm yếu của từng
phương pháp, qua đó cho thấy ưu điểm của phương pháp phân lớp dữ liệu dựa trên
cây quyết định phù hợp để giải quyết vấn đề phân loại các thuê bao di động.
Chương 2: Cây quyết định trong vấn đề phân loại thuê bao di động
Chương này tập trung vào khảo sát tình hình thực tế tại TTVT5 Móng Cái,
trình bày về sự cần thiết của việc phân loại các thuê bao di động. Chương này cũng
trình bày các ứng dụng của cây quyết định trong viễn thông và phương pháp thiết kế
xây dựng cây quyết định để giải quyết vấn đề phân loại.
Chương 3: Thử nghiệm và đánh giá
Với cơ sở lý luận và thực trạng đã trình bày ở các chương 1 và 2, với mẫu thử
là dữ liệu của các thuê bao di động được thu thập từ TTVT5 Móng Cái – VNPT
Quảng Ninh, tôi đã áp dụng thử nghiệm trên chương trình, xuất ra kết quả phân loại
và dự đoán. Từ kết quả đó sẽ đưa ra nhận xét, đánh giá và phương hướng phát triển
chương trình trong tương lai.
3
CHƯƠNG 1: TỔNG QUAN VỀ PHÂN LỚP DỮ LIỆU
1.1 Giới thiệu
Khoa học công nghệ ngày càng phát triển đồng nghĩa với lượng thông tin, dữ
liệu ngày càng nhiều. Để có thể phát hiện và trích xuất những tri thức, những thông
tin đáng giá từ kho dữ liệu khổng đó để đưa vào phục vụ con người thì chúng ta đã
biết tới khái niệm “Khai phá dữ liệu”, được biết đến như là một giải pháp có khả năng
giải quyết tình trạng thông tin thừa, tri thức thiếu. Muốn tìm tri thức, chúng ta phải
“đào” trong các “mỏ” thông tin. Về mặt kỹ thuật, phân lớp dữ liệu là một trong các
phương pháp khai phá dữ liệu đã được ứng dụng rộng rãi trong nhiều lĩnh vực khác
nhau. Trong chương 1 này sẽ trình bày tổng quan về phân lớp dữ liệu và một số kỹ
thuật phân lớp phổ biến.
1.2 Phân lớp dữ liệu
1.2.1 Khái niệm và quy trình của phân lớp dữ liệu
Phân lớp dữ liệu là một hướng nghiên cứu quan trọng trong khai phá dữ liệu.
Nó là một dạng của phân tích dữ liệu nhằm chọn lọc, trích xuất, mô tả và phân loại
một cách có hệ thống các thông tin hữu ích để phục vụ một mục đích cụ thể nào đó
như khảo sát, phân tích, đánh giá, dự đoán [1], [2].
Ví dụ mô hình phân lớp dự báo thời tiết có thể cho biết thời tiết ngày mai là
mưa, hay nắng dựa vào những thông số về độ ẩm, sức gió, nhiệt độ,… của ngày hôm
nay và các ngày trước đó [2]. Trong những năm qua, phân lớp dữ liệu đã thu hút sự
quan tâm các nhà nghiên cứu trong nhiều lĩnh vực khác nhau như học máy, thống
kê... Công nghệ này cũng ứng dụng trong nhiều lĩnh vực khác nhau như: thương mại,
nghiên cứu thị trường, bảo hiểm, y tế, giáo dục...
Về mặt kỹ thuật, phân lớp dữ liệu là một quá trình gồm hai bước [6]:
- Bước học (giai đoạn huấn luyện): Xây dựng nên mô hình phân lớp hoặc
nói cách khác là bộ phân loại bằng việc phân tích/ học tập huấn luyện.
4
- Bước phân lớp: Từ mô hình vừa xây dựng ở bước học sẽ được sử dụng để
dự đoán các nhãn lớp cho những dữ liệu nào đó. Nếu độ chính xác của bộ phân loại
được đánh giá là chấp nhận được thì tại bước này sẽ tiến hành phân loại dữ liệu hoặc
đối tượng.
Để hiểu rõ hơn về hai bước đã đề cập ở trên, chúng ta xét ví dụ sau: Hình 1.1
và hình 1.2 minh họa cho quá trình phân loại dữ liệu với mục đích khảo sát và đánh
giá khách hàng sử dụng dịch vụ viễn thông. Để dễ hiểu, chúng ta chỉ giữ lại những
thuộc tính cơ bản nhất như “Tên”, “Độ_tuổi”, “Thu_nhập”, “Dịch_vụ”.
THUẬT TOÁN
PHÂN LỚP
Hình 1.1: Bước học (phân tích/ học tập huấn luyện)
5
LUẬT
PHÂN LỚP
Trả_sau
Hình 1.2: Bước phân lớp trong quá trình phân lớp dữ liệu
Độ chính xác 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 ứng với bản ghi đó.
Trong ví dụ xác định khách hàng sử dụng dịch vụ viễn thông bên trên, các luật
phân lớp học được trong hình 1.1 từ việc phân tích dữ liệu của những khách hàng đã
đăng ký sử dụng dịch vụ trước đó, nếu có độ chính xác cao khi phân lớp tập kiểm tra
thì có thể được sử dụng để dự đoán các khách hàng mới hoặc sẽ xuất hiện trong tương
lai, như đã được minh họa trong hình 1.2.
1.2.2 Các vấn đề trong phân lớp dữ liệu
1.2.2.1 Tiền xử lý dữ liệu
Vấn đề tiền xử lý dữ liệu cho quá trình phân lớp là một việc làm không thể
thiếu và có vai trò quan trọng quyết định tới việc có thể áp dụng được hay không mô
hình phân lớp. Quá trình tiền xử lý dữ liệu sẽ giúp cải thiện độ chính xác, tính hiệu
quả và khả năng mở rộng được của mô hình phân lớp.
Quá trình tiền xử lý dữ liệu gồm có các công việc sau:
6
Làm sạch dữ liệu:
Làm sạch dữ liệu liên quan đến việc xử lý dữ liệu lỗi và giá trị thiếu trong tập
dữ liệu ban đầu. Kỹ thuật xử lý có thể bằng cách thay giá trị thiếu bằng giá trị phổ
biến nhất của thuộc tính đó hoặc bằng giá trị có thể xảy ra nhất dựa trên thống kê [3],
[9]. Mặc dù phần lớn thuật toán phân lớp đều có cơ chế xử lý với những giá trị thiếu
và lỗi trong tập dữ liệu, nhưng bước tiền xử lý này có thể làm giảm sự hỗn độn trong
suốt quá trình.
Phân tích sự cần thiết của dữ liệu:
Phân tích sự cần thiết của dữ liệu nhằm mục đích loại bỏ những thuộc tính dư
thừa khỏi quá trình học vì những thuộc tính đó sẽ làm chậm, phức tạp và có thể gây
ra sự hiểu sai trong quá trình học dẫn tới một mô hình phân lớp không dùng được [2],
[6]. Ví dụ, dữ liệu về “Nhãn hiệu điện thoại” là không cần thiết khi nghiên cứu ứng
dụng phân loại các thuê bao di động.
Chuyển đổi dữ liệu:
Việc khái quát hóa dữ liệu lên mức khái niệm cao hơn đôi khi là cần thiết trong
quá trình tiền xử lý. Việc này đặc biệt hữu ích với những thuộc tính liên tục. Ví dụ
các giá trị số của thuộc tính “thu nhập” của khách hàng có thể được khái quát hóa
thành các dãy giá trị rời rạc: thấp, trung bình, cao. Tương tự với những thuộc tính rời
rạc như “địa chỉ phố” có thể được khái quát hóa lên thành thành phố. Việc khái quát
hóa làm cô đọng dữ liệu học nguyên thủy, vì vậy các thao tác vào/ra liên quan đến
quá trình học sẽ giảm [2].
1.2.2.2 So sánh các mô hình phân lớp
Trong từng ứng dụng cụ thể cần lựa chọn mô hình phân lớp phù hợp. Việc lựa
chọn đó căn cứ vào sự so sánh giữa các mô hình phân lớp với nhau, dựa trên các tiêu
chuẩn sau [11]:
Độ chính xác dự đoán:
7
Khả năng của mô hình có thể dự đoán chính xác nhãn lớp của dữ liệu mới hay
dữ liệu chưa biết. Ước lượng độ chính xác của mô hình phân lớp rất quan trọng bởi
vì nó cho phép đoán được độ chính xác của kết quả phân lớp những dữ liệu tương lai.
Tốc độ:
Là những chi phí tính toán liên quan đến quá trình tạo ra và sử dụng mô hình.
Sức mạnh:
Là khả năng của mô hình tạo ra những dự đoán đúng từ dữ liệu lỗi hay dữ liệu
với những giá trị thiếu.
Khả năng mở rộng:
Là khả năng thực thi hiệu quả trên lượng lớn dữ liệu của mô hình đã học.
Tính hiểu được:
Là mức độ hiểu và hiểu rõ những kết quả sinh ra bởi mô hình đã học.
Tính đơn giản:
Tính đơn giản liên quan đến độ cô đọng của các luật.
1.3 Một số kỹ thuật phân lớp dữ liệu
1.3.1 Phân lớp dữ liệu bằng Neural Network
Hình 1.3: Minh họa mạng nơ-rôn nhân tạo
8
Học bằng mạng nơ-rôn nhân tạo (ANN) được giới thiệu năm 1943 bởi nhà
thần kinh học Warren McCulloch và nhà logic học Walter Pits. Nhưng với những kỹ
thuật trong thời gian này chưa cho phép họ nghiên cứu được nhiều. Những năm gần
đây việc mô phỏng ANN mới xuất hiện và phát triển. Một mạng nơ-rôn nhân tạo, hay
gọi tắt là mạng nơ-rôn là một tập hợp các nút xuất/ nhập nối kết với nhau, trong đó
mỗi đường nối kết có một trọng số liên kết với nó [3].
Mỗi nơ-rôn (nút) là một đơn vị xử lý thông tin của mạng nơ-rôn, là yếu tố cơ
bản để cấu tạo nên mạng nơ-rôn.
wk1
∑
wk2
f(.)
Output
yk
wk3
b
Hình 1.4: Cấu trúc một nơ-rôn
Trong đó:
xi: các tín hiệu input y
wkp: trọng số của từng input
f(.): hàm hoạt động
yk: kết xuất của nơ-rôn
b: thông số ảnh hưởng đến ngưỡng ra của output
Nơ-rôn đầu vào: Nơ-rôn đầu vào cung cấp các giá trị thuộc tính đầu vào cho
các mô hình khai thác dữ liệu. Đối với thuộc tính đầu vào rời rạc, một nơ-rôn đầu vào
thường đại diện cho một trạng thái đơn nhất từ các thuộc tính đầu vào. Một thuộc tính
đầu vào liên tục tạo ra hai nơ-rôn đầu vào: Một nơ-rôn cho một trạng thái bị thiếu,
một nơ-rôn cho giá trị của chính thuộc tính liên tục đó. Nơ-rôn đầu vào cung cấp đầu
vào cho một hoặc nhiều nơ-rôn ẩn.
9
Nơ-rôn ẩn: nơ-rôn ẩn nhận đầu vào từ các nơ-rôn đầu vào và cung cấp đầu ra
cho các nơ-rôn đầu ra.
Nơ-rôn đầu ra: Nơ-rôn đầu ra đại diện cho các giá trị của thuộc tính dự đoán.
Đối với các thuộc tính đầu ra là rời rạc, một nơ-rôn đầu ra đại diện duy nhất cho một
trạng thái dự đoán của thuộc tính dự đoán, bao gồm cả giá trị thiếu. Nếu các thuộc
tính dự đoán liên tục tạo ra hai nơ-rôn đầu ra: một nơ-rôn cho một trạng thái bị thiếu,
một nơ-rôn cho chính các giá trị của thuộc tính liên tục đó. Mỗi đầu vào có một giá
trị được gán cho nó có trọng số là w, mô tả sư liên quan giữa đầu vào đến các nơ-rôn
ẩn hoặc các nơ-rôn đầu ra.
Tiến trình học:
Tương tự như bộ não con người, một phiên bản giản lược của bộ não là mạng
nơ-rôn nhân tạo cũng cần phải thông qua tiến trình học để có thể nhận biết được dữ
liệu với tình huống là các thông số tự do của mạng có thể thay đổi dựa theo thay đổi
của môi trường xung quanh, và mạng nơ-rôn phải ghi nhớ được điều đó.
Hình 1.5: Tiến trình học của mạng nơ-rôn
Trong quá trình học, giá trị đầu vào được đưa vào mạng và theo dòng chảy
trong mạng tạo thành giá trị ở đầu ra. Tiếp đến là quá trình so sánh giá trị tạo ra bởi
mạng nơ-rôn với giá trị ra mong muốn. Nếu hai giá trị này giống nhau thì không thay
đổi gì cả. Tuy nhiên, nếu có một sai lệch giữa hai giá trị này vượt quá giá trị sai số
mong muốn thì đi ngược mạng từ Output về Input để thay đổi một số kết nối.
10
Đây là một quá trình lặp liên tục và có thể không dừng khi không tìm được
các giá trị w sao cho Output tạo bởi mạng nơ-rôn bằng đúng Output mong muốn. Do
đó trong thực tế người ta phải thiết lập tiêu chuẩn dựa trên một giá trị sai số nào đó
của hai giá trị này hoặc dựa trên một số lần lặp xác định.
Chi tiết kỹ thuật phân lớp dữ liệu bằng NN có thể tham khảo tại [7], [11].
Ưu điểm:
- Các mô hình học được từ NN có khả năng chịu đựng dữ liệu nhiễu cao; có khả
năng phân lớp được những mẫu hình mà chúng chưa từng được huấn luyện.
- Rất thích hợp đối với dữ liệu nhập và xuất có giá trị liên tục.
- Các thuật toán mạng nơ-rôn vốn có sẵn tính song song; có thể dùng các kỹ thuật
song song hóa để tăng tốc quá trình tính toán.
- Ngoài ra đã có nhiều kỹ thuật được xây dựng để rút ra các luật phân lớp dễ hiểu
từ các mạng nơ-rôn học được.
Nhược điểm:
- Học bằng NN đòi hỏi thời gian huấn luyện phải dài, vì thế thích hợp hơn với
các ứng dụng nào chấp nhận được điều này.
- Thuật toán xây dựng NN cần một số tham số mà thường thì chỉ được xác định
tốt nhất thông qua thí nghiệm, như cấu trúc.
- Các mô hình học bằng NN đã bị chỉ trích vì tính khó hiểu của chúng; con người
khó diễn đạt được ý nghĩa biểu tượng đằng sau các trọng số và ý nghĩa của các
“đơn vị ẩn” trong mạng.
1.3.2 Phân lớp dữ liệu bằng mạng Naïve Bayes
Các mô hình phân lớp dựa theo Bayes là loại mô hình phân lớp theo lý thuyết
thống kê. Chúng có thể dự đoán xác suất của các thành viên lớp, chẳng hạn xác suất
để một bản ghi nhất định thuộc về một lớp cụ thể nào đó. Phân lớp dựa theo Bayes
căn cứ vào nền tảng lý thuyết là Định lý Bayes (đặt tên theo Thomas Bayes, nhà toán
học người Anh sống ở thế kỷ 18).
11
Thuật toán phân lớp Naïve Bayes giả định rằng ảnh hưởng của một giá trị
thuộc tính nào đó trên một lớp nhất định là độc lập với các giá trị của các thuộc tính
khác. Giả định này được gọi là sự độc lập theo điều kiện lớp. Người ta giả định như
vậy để đơn giản hóa khối lượng tính toán cần thiết, và vì lý do này, nó được gọi là
“ngây thơ” (naïve).
Xét bảng dưới đây:
Bảng 1.1: Giả thuyết cho mạng Bayes
Class:
Age
Income
Student
Credit_rating
buys_computer
1
Youth
High
No
Fair
No
2
Youth
High
No
Excellent
No
3
Middle_aged
High
No
Fair
Yes
4
Senior
Medium
No
Fair
Yes
5
Senior
Low
Yes
Fair
Yes
6
Senior
Low
Yes
Excellent
No
7
Middle_aged
Low
Yes
Excellent
Yes
8
Youth
Medium
No
Fair
No
9
Youth
Low
Yes
Fair
Yes
10
Senior
Medium
Yes
Fair
Yes
11
Youth
Medium
Yes
Excellent
Yes
12
Middle_aged
Medium
No
Excellent
Yes
13
Middle_aged
High
Yes
Fair
Yes
14
Senior
Medium
No
Excellent
No
X: Một đối tượng.
H: Giả thuyết.
12
P(H|X):
Xác
suất
có
điều
kiện
của
H
đối
với
X.
Ví
dụ:
P(buys_computer=yes|age=youth, income=high) là xác suất mua máy tính của khách
hàng có tuổi là “youth” và thu nhập “high”.
P(X|H): Xác suất có điều kiện của X đối với H. Ví dụ: P(age=youth,
income=high|buys_computer=yes) là xác suất khách hàng mua máy tính có tuổi là
“youth” và thu nhập “high”.
P(H): Xác suất của H, ví dụ: P(buys_computer=yes) là xác suất mua máy tính
của khách hàng nói chung.
P (X): Xác suất của X, ví dụ: P(age=youth, income=high) là xác suất mua máy
tính của khách hàng có tuổi “youth” và thu nhập “high”.
P(X|H), P(X), P(H) có thể được tính từ tập dữ liệu cho trước.
P(X|H) được tính từ định lý Bayes:
𝑃 (𝐻 | 𝑋 ) =
𝑃(𝑋|𝐻 ). 𝑃(𝐻)
𝑃(𝑋)
(1.1)
P(buys_computer=no|age=youth, income=high) = P(age=youth, income =
high|buys_computer=no).P(buys_computer=no)/P(age=youth, income=high) = 0,4 x
0,375 : 0,143 = 0,9986.
Chi tiết của kỹ thuật phân lớp dữ liệu bằng mạng Naïve Bayes có thể tham
khảo tại [7].
Ưu điểm:
- Thời gian học ít hơn so với một số phương pháp chẳng hạn như quy nạp cây
quyết định, ít hơn nhiều so với mạng nơ-rôn, đặc biệt là đối với dữ liệu rời rạc.
- Hiệu năng (độ chính xác và tốc độ xử lý) cao khi áp dụng với cơ sở dữ liệu lớn.
- Thuật toán dễ hiểu và dễ thực hiện.
Nhược điểm:
13
- Do Naïve Bayes giả định là các thuộc tính độc lập với nhau, nên khi các thuộc
tính có sự phục thuộc lẫn nhau (ví dụ trong giáo dục có một số môn học có ý
nghĩa tiên quyết đối với một số môn học khác) thì phương pháp Naïve Bayes
trở nên thiếu chính xác.
- Naïve Bayes không sinh ra được những mô hình phân lớp dễ hiểu đối với người
dùng không chuyên về khai phá dữ liệu.
1.3.3 Phân lớp dữ liệu bằng giải thuật học ILA
Thuật giải học quy nạp ILA (Inductive Learning Algorithm) được dùng để xác
định các luật phân loại cho tập hợp các mẫu học. Giải thuật này thực hiện theo cơ chế
lặp, để tìm luật riêng đại diện cho tập mẫu của từng lớp. Sau khi xác định được luật,
thuật giải sẽ loại bỏ các mẫu mà luật này bao hàm, đồng thời thêm luật mới này vào
tập luật. Kết quả có được là một danh sách có thứ tự các luật.
Quá trình học của ILA xuất phát từ các thuộc tính quyết định. ILA chia tập dữ
liệu huấn luyện thành các tập con rời nhau, mỗi tập con là một phân lớp dựa trên
thuộc tính quyết định. Tiếp đến ILA sẽ xem xét trong từng phân lớp xem có thuộc
tính nào (hoặc tổ hợp thuộc tính nào) có giá trị chỉ xuất hiện trong lớp đó mà không
xuất hiện trong lớp khác hay không. Nếu có những (tổ hợp) thuộc tính và giá trị đó
sẽ được chọn làm đặc trưng cho phân lớp đó.
Mô tả giải thuật ILA:
- Bước 1: Chia bảng con chứa m mẫu thành n bảng con. Mỗi bảng con ứng với
một giá trị của thuộc tính phân lớp hay “thuộc tính quyết định” của tập mẫu
(Lặp lại từ bước 2 đến bước 8 cho mỗi bảng con).
- Bước 2: Khởi tạo biến đếm kết hợp thuộc tính j với j = 1 cho biết số thuộc tính
đang xét.
- Bước 3: Với mỗi bảng con đang xét, phân chia các thuộc tính của nó thành một
danh sách các tổ hợp phân biệt, mỗi tổ hợp của danh sách ứng với j thuộc tính
phân biệt.
14
- Bước 4: Với mỗi tổ hợp các thuộc tính trong danh sách trên, đếm số lần xuất
hiện các giá trị của các thuộc tính trong cùng tổ hợp ở các dòng chưa bị đánh
dấu của bảng đang xét, nhưng nó không được xuất hiện cùng giá trị ở những
bảng con khác. Chọn ra một tổ hợp trong danh sách sao choó có giá trị tương
ứng xuất hiện nhiều nhất và được gọi là Max_combination (tổ hợp lớn nhất).
- Bước 5: Nếu Max_combination = 0 thì tăng j lên, j = j+1 và quay lại bước 3.
- Bước 6: Đánh dấu các dòng ở bảng con đang xét có giá trị bằng với giá trị tạo
ra Max_combination.
- Bước 7: Thêm luật mới vào tập luật R với vế trái là tập các giá trị của thuộc tính
ứng với tổ hợp lớn nhất (kết hợp các thuộc tính bằng toán tử AND) và vế phải
là giá trị thuộc tính quyết định tương ứng.
- Bước 8: Nếu tất cả các dòng đều đã được đánh dấu phân lớp:
o Nếu còn bảng con thì qua bảng con tiếp theo và quay lại bước 2
o Nếu các bảng con đã được xét thì kết thúc thuật toán.
Ngược lại nếu chưa đánh dấu hết các dòng thì quay lại bước 4.
Chi tiết của kỹ thuật phân lớp dữ liệu bằng mạng Naïve Bayes có thể tham
khảo tại [7].
Ưu điểm:
- Các luật thích hợp cho việc thăm dò dữ liệu, cụ thể là có thể mô tả các lớp theo
cách đơn giản nhất cho phép phân biệt lớp đó với các lớp khác.
- Các luật được xếp theo kiểu mô-đun, cho phép tập trung vào một luật tại một
thời điểm.
- Được đánh giá là mạnh mẽ, đặc biệt là với trường hợp có số lượng lớn các nút.
Nhược điểm:
- Chi phí đào tạo cao.
1.3.4 Phân lớp dữ liệu bằng cây quyết định
Cây quyết định là một cấu trúc biểu diễn dưới dạng cây. Mỗi cây quyết định
là một cấu trúc cây kiểu lưu đồ, trong đó mỗi nút trong biểu thị một sự kiểm tra trên
15
một thuộc tính nào đó, mỗi nhánh biểu diễn một kết quả của sự kiểm tra đó, còn mỗi
nút lá chứa một nhãn lớp. Một số thuật toán cây quyết định chỉ sinh ra các cây nhị
phân (trong đó mỗi nút trong sẽ rẽ nhánh đến hai nút khác), trong khi một số thuật
toán cây quyết định khác lại có thể sinh ra những cây không phải nhị phân. Quy nạp
cây quyết định là việc tìm kiếm các cây quyết định từ những bản ghi huấn luyện đã
có nhãn lớp.
Hình 1.6 minh họa cho một cây quyết định tiêu biểu, mô tả mức độ nguy hiểm
cao hay thấp khi tham gia giao thông. Trong đó:
- Nút (node) gốc: Nằm ở vị trí trên cùng của cây, chứa tên của thuộc tính cần
kiểm tra.
- Các nút trong: Biểu diễn một kiểm tra trên một thuộc tính đơn, được thể hiện
bằng các hình chữ nhật.
- Các nút lá: Biểu diễn lớp hay sự phân phối lớp, được thể hiện bằng các hình
tròn.
- Các nhánh: Biểu diễn các kết quả của kiểm tra trên nút trong, được thể hiện
bằng các mũi tên.
Hình 1.6: Ví dụ về cây quyết định
16
Các cây quyết định được dùng cho phân lớp như thế nào? Cho một bản ghi X
nào đó mà ta chưa biết nhãn lớp liên kết với nó, các giá trị thuộc tính của bản ghi đó
được kiểm tra so với cây quyết định. Dựa theo những cuộc kiểm tra đó, ta lần ra một
đường đi từ nút gốc đến một nút lá chưa kết quả dự đoán lớp dành cho bản ghi ấy.
Các cây quyết định có thể dễ dàng được chuyển đổi thành các luật phân lớp, tức là
hình thức phân loại đơn giản và dễ hiểu nhất đối với người sử dụng [11].
Trong lĩnh vực học máy, cây quyết định là một kiểu mô hình dự báo, nghĩa là
một ánh xạ từ các quan sát về một sư vật/hiện tượng tới các kết luận về giá trị mục
tiêu của sự vật/hiện tượng. Mỗi nút trong tương ứng với một biến, đường nối giữa nó
với nút con của nó thể hiện giá trị cụ thể cho biến đó. Mỗi nút lá đại diện cho giá trị
dự đoán của biến mục tiêu, cho trước các giá trị dự đoán của các biến được biểu diễn
bởi đường đi từ nút gốc tới nút lá đó.
Ưu điểm:
- Khả năng sinh ra các quy tắc hiểu được: Nó có thể sinh ra các quy tắc chuyển
đổi được sang dạng if…then…else, hoặc các câu lệnh SQL. Đây là ưu điểm nổi
bật của kỹ thuật này. Thậm chí với cả những tập dữ liệu lớn khiến cho hình dáng
cây quyết định lớn và phức tạp, việc đi theo bất cứ đường nào trên cây là dễ
dàng theo ý nghĩa phổ biến và rõ ràng. Do vậy sự giải thích cho bất cứ một sự
phân lớp hay dự đoán nào đều tương đối rõ ràng.
- Khả năng xử lý với cả thuộc tính liên tục và thuộc tính rời rạc: Cây quyết định
có thể xử lý thuộc tính liên tục và thuộc tính rời rạc với độ “tốt” như nhau. Tuy
rằng với thuộc tính liên tục cần nhiều tài nguyên tính toán hơn [5].
- Thể hiện rõ ràng những thuộc tính tốt nhất: Các thuật toán xây dựng cây quyết
định đưa ra thuộc tính mà phân chia tốt nhất tập dữ liệu đào tạo bắt đầu từ nút
gốc của cây. Từ đó có thể thấy những thuộc tính nào là quan trọng nhất cho việc
dự đoán hay phân lớp.
- Dễ dàng tính toán khi phân lớp: Mặc dù cây quyết định có thể chứa nhiều định
dạng, nhưng trong thực tế, các thuật toán sử dụng để tạo ra cây quyết định
