BỘ GIÁO DỤC VÀ ĐÀO TẠO
ĐẠI HỌC MỞ HÀ NỘI
LUẬN VĂN THẠC SĨ
Chuyên ngành: Công nghệ thông tin
Mã ngành: 84.8.02.01
Đề tài:
PHÂN LỚP Ý KIẾN KHÁCH HÀNG VÀ ỨNG DỤNG
TRONG HỆ TƢ VẤN BÁN HÀNG TRỰC TUYẾN
HỌC VIÊN THỰC HIỆN: TẠ VĂN KHOA
HƢỚNG DẪN KHOA HỌC: PGS. TS ĐOÀN VĂN BAN
HÀ NỘI, 2022
LỜI CẢM ƠN
Lời cảm ơn trân trọng đầu tiên, tôi muốn dành tới các thầy, cô giáo Trƣờng
Đại học Mở Hà Nội cùng các thầy, cô giáo Viện Hàn lâm Khoa học và Công nghệ
Việt Nam đã tận tình giảng dạy và truyền đạt kiến thức trong suốt khóa học cao học
vừa qua. Đặc biệt tôi xin bày tỏ lòng biết ơn chân thành và sâu sắc nhất của mình tới
thầy PGS.TS. Đoàn Văn Ban, đã tận tình dìu dắt và hƣớng dẫn tôi trong suốt quá
trình làm luận văn, sự chỉ bảo và định hƣớng của thầy giúp tôi tự tin nghiên cứu
những vấn đề mới và giải quyết bài toán một cách khoa học. Tôi xin chân thành cảm
ơn các thầy, cô giáo viên Công nghệ Thông Tin trƣờng Trƣờng Đại học Mở Hà Nội
đã tạo điều kiện thuận lợi cho tôi trong quá trình học tập, nghiên cứu. Cuối cùng, tôi
xin cảm ơn tập thể lớp Công nghệ thông tin khóa 18, các bạn đã cổ vũ, khích lệ và
chia sẻ kinh nghiệm bản thân giúp luận văn của tôi ngày một hoàn thiện. Mặc dù đã
cố gắng rất nhiều nhƣng chắc chắn trong quá trình học tập cũng nhƣ luận văn không
khỏi những thiếu sót. Tôi rất mong nhận đƣợc sự thông cảm và chỉ bảo tận tình của
các thầy cô và các bạn.
Tôi xin chân thành cảm ơn!
Hà Nội, ngày 21 tháng 04 năm 2021
Tạ Văn Khoa
i
LỜI CAM ĐOAN
Tên tôi là: Tạ Văn Khoa
Sinh ngày: 11/01/1988
Là học viên lớp cao học : 18M-CT52 Trƣờng Đại học Mở Hà Nội
Nơi công tác: Trƣờng Cao đẳng Cơ Khí Nông Nghiệp – Vĩnh Phúc
Tôi xin cam đoạn :
1. Tôi xin cam đoan “Phân lớp ý kiến khách hàng và ứng dụng trong hệ tƣ vấn
bán hàng trực tuyến” là công trình nghiên cứu khoa học của tôi dƣới sự hƣớng dẫn
khoa học trực tiếp của PGS.TS. Đoàn Văn Ban. Các nội dung nghiên cứu, kết quả
nghiên cứu đƣợc trình bày trong luận văn hoàn toàn là trung thực, không vi phạm
bất cứ điều gì trong luật sở hữu trí tuệ và pháp luật của Việt Nam .
2. Mọi tham khảo dùng trong khóa luận đều đƣợc trích dẫn rõ ràng tên tác giả, tên
công trình, thời gian, địa điểm công bố .
3. Mọi sao chép không hợp lệ, vi phạm quy chế đào tạo, hay gian trá, tôi xin chịu
hoàn toàn trách nhiệm .
Hà Nội , ngày 21 tháng 04 năm 2021
Học viên thực hiện
Tạ Văn Khoa
ii
MỤC LỤC
LỜI CẢM ƠN .................................................................................................... i
LỜI CAM ĐOAN ............................................................................................. ii
MỤC LỤC ........................................................................................................ iii
DANH MỤC BẢNG ....................................................................................... vii
DANH MỤC HÌNH ....................................................................................... viii
MỞ ĐẦU ........................................................................................................... 1
1. Tính cấp thiết của đề tài ............................................................................ 1
3. Đối tƣợng và phạm vi nghiên cứu ............................................................. 2
4. Phƣơng pháp nghiên cứu........................................................................... 2
5. Cấu trúc luận văn ...................................................................................... 3
CHƢƠNG 1: PHÂN LỚP DỮ LIỆU ................................................................ 4
1. 1. Giới thiệu phân lớp dữ liệu ................................................................... 4
1.2. Quy trình phân lớp dữ liệu ..................................................................... 6
1.3. Các vấn đề liên quan đến phân lớp dữ liệu ............................................ 9
CHƢƠNG 2: MỘT SỐ KỸ THUẬT TRONG PHÂN LOẠI VĂN BẢN ..... 16
2.1. Xử lý văn bản tiếng Việt ...................................................................... 16
2.1.1. So sánh giữa tiếng Anh và tiếng Việt ........................................... 16
2.1.2. Một số phƣơng pháp tách từ ......................................................... 17
2.2. Biểu diễn văn bản ................................................................................. 26
2.2.1. Mô hình boolean ........................................................................... 26
2.2.2. Mô hình không gian vector ........................................................... 27
2.2.3. Mô hình logic ............................................................................... 32
2.2.4. Mô hình phân tích cú pháp ........................................................... 33
2.2.5. Mô hình tần suất ........................................................................... 34
2.2.6. Các mô hình biểu diễn văn bản khác ............................................ 36
2.3. Độ tƣơng đồng...................................................................................... 37
2.3.1. Khái niệm ...................................................................................... 38
2.3.2. Độ tƣơng đồng văn bản trong Tiếng Việt ..................................... 38
2.3.3. Độ tƣơng đồng văn bản dựa trên tập từ chung.............................. 39
iii
2.3.4. Độ tƣơng đồng văn bản dựa trên vector biểu diễn ........................ 40
2.3.5. Tính độ tƣơng đồng cho toàn bộ văn bản ..................................... 41
2.4. Các phƣơng pháp phân loại văn bản .................................................... 42
2.4.1. Phƣơng pháp Naïve Bayes (NB) ................................................... 42
2.4.2. Phƣơng pháp K-Nearest Neighbor (K - NN) ................................ 43
2.4.3. Phƣơng pháp Linear Least Square Fit (LLSF).............................. 45
2.4.4. Phƣơng pháp Support Vector Machine (SVM) ............................ 46
2.4.5. Phƣơng pháp Centroid- based vector ............................................ 53
2.4.6. Đánh giá nhận xét.......................................................................... 53
2.5. Kết luận chƣơng 2 ................................................................................ 54
CHƢƠNG 3: PHÂN LỚP Ý KIẾN ĐÁNH GIÁ CỦA KHÁCH HÀNG TRÊN
HỆ THỐNG BÁN HÀNG TRỰC TUYẾN .................................................... 56
3.1. Website bán hàng trực tuyến ................................................................ 56
3.2. Xây dựng mô hình ứng dụng khai phá ý kiến phản hồi của khách hàng
trên website dựa trên SVM để hỗ trợ bán hàng trực tuyến ......................... 62
3.2.1. Phát biểu bài toán ......................................................................... 62
3.2.2. Mô hình ứng dụng khai phá ý kiến phản hồi của khách hàng
trên website dựa trên SVM...................................................................... 62
3.3. Yêu cầu phần cứng phần mềm ............................................................. 65
3.3.1. Cấu hình máy thực nghiệm ........................................................... 65
3.3.2. Công cụ và phần mềm sử dụng ..................................................... 65
3.4. Một số kết quả và đánh giá .................................................................. 66
3.4.1. Kết quả thử nghiệm ...................................................................... 66
3.4.2. Huấn luyện và phân lớp dữ liệu .................................................... 77
3.4.3. Đánh giá kết quả ............................................................................ 79
3.5. Kết luận chƣơng 3 ................................................................................ 79
KẾT LUẬN VÀ HƢỚNG PHÁT TRIỂN ...................................................... 80
TÀI LIỆU THAM KHẢO ............................................................................... 81
iv
DANH MỤC CÁC KÝ TỰ VIẾT TẮT
Từ viết tắt
Tiếng Anh
Tiếng Việt
1
SVM
Support Vector Machine
Máy vector hỗ trợ
2
Zalo OA
Zalo Official Account
Tài khoản Zalo chính
STT
thức
3
TP
Số lƣợng dự đoán chính
True Positive
xác
4
TN
Số lƣợng dự đoán chính
True Negative
xác một cách gián tiếp
5
FP
Số lƣợng các dự đoán
False Positive
sai lệch
6
FN
Số lƣợng các dự đoán
False Negative
sai lệch một cách gián
tiếp
7
TBL
Transformation-based Learning Phƣơng pháp học dựa
trên sự cải biến
8
9
10
WFST
IGATEC
TFxIDF
Weighted- Finite State
Chuyển đổi trạng thái
Transducer
trọng số hữu hạn
Internet and Genetics
Phƣơng pháp tách từ
Algorithm based Text
dựa trên thống kê từ trên
Categorization for Documents
Internet và giải thuật di
in Vietnamese
truyền
Term Frequency times Inverse
Phƣơng pháp tần suất từ
Document Frequency
khóa kết hợp phƣơng
pháp nghịch đảo tần số
văn bản
v
11
NB
Phƣơng pháp tiếp cận
Naïve Bayes
xác suất thống kê
12
K – NN
K-Nearest Neighbor
Thuật toán K láng giềng
gần
13
LLSF
Linear Least Square Fit
Thuật toán tuyến tính
bình phƣơng nhỏ nhất
14
NNet
Neural Network
Mạng Neural
15
CRF
Conditional Random Field
Thuật toán xác suất có
điều kiện
vi
DANH MỤC BẢNG
Bảng 2.1 So sánh những đặc điểm chính của Tiếng Việt và Tiếng Anh ................. 15
Bảng 2.2 Tách chuỗi từ “Tôi là công dân nƣớc Việt Nam” ..................................... 17
Bảng 2.3 Biểu diễn văn bản trong mô hình Logic ................................................... 31
Bảng 3.1 Kết quả huấn luyện và kiểm thử ............................................................... 76
vii
DANH MỤC HÌNH
Trang
Hình 1.1 Mô hình mô tả bài toán phân lớp dữ liệu .................................................. 6
Hình 1.2 Quá trình phân lớp dữ liệu - (a) Bƣớc xây dựng mô hình phân lớp ......... 7
Hình 1.3 Quá trình phân lớp dữ liệu - (b1) Ƣớc lƣợng độ chính xác của mô hình.. 8
Hình 1.4 Quá trình phân lớp dữ liệu - (b2) Phân lớp dữ liệu mới ........................... 9
Hình 1.5 Các chỉ số đánh giá mô hình phân lớp ...................................................... 13
Hình 2.1 Sơ đồ các bƣớc sử lý của WFST ............................................................... 20
Hình 2.2 Giải thuật di truyền IGATEC .................................................................... 21
Hình 2.3 Mô hình thuật toán K-NN ......................................................................... 42
Hình 2.4 Các điểm đƣợc khoanh tròn là các vector hỗ trợ ...................................... 45
Hình 2.5. Tập dữ liệu đƣợc phân chia tuyến tính ..................................................... 47
Hình 2.6. Tập dữ liệu phân chia tuyến tính nhƣng có nhiễu .................................... 48
Hình 2.7. Tập dữ liệu không phân chia tuyến tính ................................................... 49
Hình 3.1 Giao diện trang chủ ................................................................................... 54
Hình 3.2 Giao diện trang sản phẩm .......................................................................... 55
Hình 3.3 Giao diện trang đăng ký bảo dƣỡng .......................................................... 55
Hình 3.4 Giao diện trang tin tức – tƣ vấn ................................................................ 56
Hình 3.5 Giao diện trang liên hệ .............................................................................. 56
Hình 3.6 Nút đánh giá ngay ..................................................................................... 57
Hình 3.7 Form điền thông tin ý kiến ........................................................................ 57
Hình 3.8 Thống kê báo cáo ý kiến khách ................................................................. 58
Hình 3.9 xem ý kiến khách hàng .............................................................................. 58
viii
Hình 3.10 Các bƣớc trong quá trình phân lớp văn bản ............................................ 59
Hình 3.11 Giao diện phần mềm Weka ..................................................................... 63
Hình 3.12 Chuyển đổi dữ liệu sang .arff .................................................................. 67
Hình 3.13 Vector hóa dữ liệu ................................................................................... 68
Hình 3.14 Giao diện huấn luyện .............................................................................. 75
Hình 3.15 Kết quả huấn luyện.................................................................................. 75
ix
i
MỞ ĐẦU
1. Tính cấp thiết của đề tài
Hiện nay, chúng ta đang bƣớc vào cuộc cách mạng 4.0, cuộc cách mạng tập
trung chủ yếu vào sản xuất thông minh dựa trên các thành tựu đột phá trong công
nghệ thông tin, trí tuệ nhân tạo, công nghệ sinh học, công nghệ nano,… Dựa vào
công nghệ hiện nay, cá nhân, doanh nghiệp bán hàng trực tuyến rất muốn biết phản
hồi của khách hàng về sản phẩm, dịch vụ của họ nhƣ thế nào, cũng nhƣ họ muốn
phân lớp khách hàng để có thể tung ra những chiến dịch marketing, sản phẩm phù
hợp với từng loại đối tƣợng khách hàng. Việc nhiều ý kiến đánh giá của khách về
sản phẩm từ nhiều nguồn khác nhau (Website bán hàng, OA Zalo, Blog, Facebook,
Youtube, …). Để có thể tổng hợp ý kiến đánh giá, phản hồi của khách hàng về chất
lƣợng, thì phải tự động hóa đƣợc công việc thu thập và phân tích đánh giá ý kiến
của khách hàng.
Công nghệ phân lớp dữ liệu phục vụ cho việc phân lớp quan điểm khách
hàng đang rất phát triển, đây là một bài toán lớn trong việc hỗ trợ bán hàng trực
tuyến, và mọi doanh nghiệp muốn phát triển mảng bán hàng online thì việc phân
lớp khách hàng rất quan trọng. Trong vài năm gần đây, 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
(machine learning), hệ chuyên gia (expert system), thống kê (statistics), ... Công
nghệ này cũng nhƣ ứng dụng trong nhiều lĩnh vực thực tế nhƣ: tƣ vấn bán hàng trực
tuyến, thƣơng mại, nhà băng, maketing, ….
Phân lớp khách hàng chính là việc phân lớp văn bản là bài toán cơ bản trong
khai phá quan điểm. Các hệ thống phân lớp văn bản là các hệ thống phải có khả
năng xác định, khai phá ra nội dung thông tin.
Do đó tôi chọn đề tài “Phân lớp ý kiến khách hàng và ứng dụng trong hệ
tƣ vấn bán hàng trực tuyến” đề tài nghiên cứu một số kỹ thuật phân lớp văn bản
nhƣ Naïve Bayes (NB), Support Vector Machine (SVM) , K-Nearest Neighbor (KNN) , Linear Least Square Fit (LLSF) , Centroid – based vector để sử dụng trong
1
phƣơng pháp học máy phân lớp quan điểm khách hàng và ứng dụng thực tế vào bán
hàng trực tuyến.
2. Mục tiêu nghiên cứu
+ Nghiên cứu tổng quan về một số kỹ thuật phân lớp văn bản nhƣ: Naïve
Bayes (NB), Support Vector Machine (SVM) , K-Nearest Neighbor (K-NN) ,
Linear Least Square Fit (LLSF) , Centroid – based vector.
+ Nghiên cứu một số kỹ thuật sử dụng để phân lớp ý kiến khách hàng trên sản
phẩm bán hàng trực tuyến.
+ Đề xuất cải tiến hoàn thiện module thu thập dữ liệu và module xử lý dữ liệu
ngôn ngữ kết hợp với thuật toán SVM phân tích phân lớp ý kiến khách hàng và ứng
dụng trong hệ tƣ vấn bán hàng trực tuyến
3. Đối tƣợng và phạm vi nghiên cứu
+ Đối tƣợng: ý kiến khách hàng và ứng dụng trong hệ tƣ vấn bán hàng trực
tuyến.
+ Phạm vi:
Hệ thống xử lý văn bản đƣợc ứng dụng trong hệ tƣ vấn bán hàng trực
tuyến trên dòng xe ô tô VinFast Fadil bản tiêu chuẩn.
Nghiên cứu đƣợc tiến hành từ tháng 12/2020 đến 12/2021.
4. Phƣơng pháp nghiên cứu
- Phƣơng pháp nghiên cứu tài liệu, phân tích, tổng hợp là phƣơng pháp thu
thập thông tin thông qua nghiên cứu tài liệu nhằm mục đích tìm chọn những khái
niệm và tƣ tƣởng cơ bản là cơ sở cho lý luận của đề tài, hình thành giả thuyết khoa
học, dự đoán về những thuộc tính của đối tƣợng nghiên cứu, xây dựng những mô
hình lý thuyết hay thực nghiệm ban đầu.
Trong luận văn phƣơng pháp nghiên cứu lý thuyết đƣợc sử dụng để tìm
hiểu một số kỹ thuật phân lớp văn bản nhƣ Naïve Bayes (NB), Support Vector
Machine (SVM) , K-Nearest Neighbor (K-NN) , Linear Least Square Fit (LLSF) ,
Centroid – based vector.
2
- Phƣơng pháp thực nghiệm và đối chứng qua chƣơng trình thử nghiệm là
một trong những bƣớc quan trọng bậc nhất. Trong đó, nghiên cứu sẽ chủ động tác
động vào đối tƣợng cần đƣợc nghiên cứu và quá trình diễn biến bao gồm các sự
kiện hoặc hiện tƣợng mà đối tƣợng tham gia.
Trong luận văn pháp thực nghiệm và đối chứng qua chƣơng trình thử
nghiệm đã sử dụng thu thập dữ liệu về ý kiến khách hàng trên dòng xe VinFast
Fadil bản tiêu chuẩn tại web http://vinfastvinhphuc.net/san-pham/vinfast-fadil-tieuchuan/
- Phƣơng pháp trao đổi khoa học, lấy ý kiến chuyên gia là phƣơng pháp điều
tra qua đánh giá của các chuyên gia về vấn đề, một sự kiện khoa học nào đó.
Trong quá trình thực hiện luận văn, bản thân học viên đã tham vấn các thầy,
các chuyên gia trong việc phân lớp ý kiến khách hàng khi mua sản phẩm trực tuyến
.
5. Cấu trúc luận văn
Ngoài phần mở đầu, kết luận, luận văn đƣợc chia thành 3 chƣơng nhƣ sau:
Chƣơng 1: Phân tích lớp dữ liệu
Chƣơng 2: Một số kỹ thuật trong phân loại văn bản
Chƣơng 3: Phân lớp ý kiến đánh giá của khách hàng trên hệ thống bán hàng
trực tuyến
3
CHƢƠNG 1: PHÂN LỚP DỮ LIỆU
1. 1. Giới thiệu phân lớp dữ liệu
Ngày nay phân lớp dữ liệu (classification) là một trong những hƣớng nghiên
cứu chính của khai phá dữ liệu. Thực tế đặt ra nhu cầu là từ một cơ sở dữ liệu với
nhiều thông tin ẩn con ngƣời có thể trích rút ra các quyết định nghiệp vụ thông
minh. Phân lớp và dự đoán là hai dạng của phân tích dữ liệu nhằm trích rút ra một
mô hình mô tả các lớp dữ liệu quan trọng hay dự đoán xu hƣớng dữ liệu tƣơng lai.
Phân lớp dự đoán giá trị của những nhãn xác định (categorical label) hay những giá
trị rời rạc (discrete value), có nghĩa là phân lớp thao tác với những đối tƣợng dữ liệu
mà có bộ giá trị là biết trƣớc [5]. Trong khi đó, dự đoán lại xây dựng mô hình với
các hàm nhận giá trị liên tục. 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 đó. Hay nhờ các luật về xu
hƣớng, ý kiến mua hàng của khách hàng trên website thƣơng mại điện tử, các nhân
viên kinh doanh có thể ra những quyết sách đúng đắn về lƣợng mặt hàng cũng nhƣ
chủng loại bày bán, … Phần lớn các thuật toán ra đời trƣớc đều sử dụng cơ chế dữ
liệu cƣ trú trong bộ nhớ (memory resident), thƣờng thao tác với lƣợng dữ liệu nhỏ.
Một số thuật toán ra đời sau này đã sử dụng kỹ thuật cƣ trú trên đĩa cải thiện đáng
kể khả năng mở rộng của thuật toán với những 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 quan điểm: Là quá trình phân lớp một đối tƣợng dữ liệu
vào một hay nhiều lớp cho trƣớc nhờ một mô hình phân lớp mà mô hình này đƣợc
xây dựng dựa trên một tập hợp các đối tƣợng dữ liệu đã đƣợc gán nhãn từ trƣớc gọi
là tập dữ liệu học (tập huấn luyện). Quá trình phân lớp còn đƣợc gọi là quá trình gán
nhãn cho các đối tƣợng dữ liệu [1], [3].
Nhiệm vụ của bài toán phân lớp dữ liệu là cần xây dựng mô hình phân lớp để
khi có một dữ liệu mới vào thì mô hình phân lớp sẽ cho biết dữ liệu đó thuộc lớp
nào.
4
Có nhiều bài toán phân lớp dữ liệu, nhƣ phân lớp nhị phân, phân lớp đa lớp,
phân lớp đa trị, …. [5].
Phân lớp nhị phân là quá trình tiến hành việc phân lớp dữ liệu vào một trong
hai lớp khác nhau dựa vào việc dữ liệu đó có hay không một số đặc tính theo quy
định của bộ phân lớp [5], [7].
Phân lớp đa lớp là quá trình phân lớp với số lƣợng lớp lớn hơn hai. Nhƣ vậy,
tập hợp dữ liệu trong miền xem xét đƣợc phân chia thành nhiều lớp chứ không đơn
thuần chỉ là hai lớp nhƣ trong bài toán phân lớp nhị phân. Về bản chất, bài toán
phân lớp nhị phân là trƣờng hợp riêng của bài toán phân lớp đa lớp.
Trong phân lớp đa trị, mỗi đối tƣợng dữ liệu trong tập huấn luyện cũng nhƣ
các đối tƣợng mới sau khi đƣợc phân lớp có thể thuộc vào từ hai lớp trở lên. Ví dụ
nhƣ trang web về việc bùng phát bệnh cúm gia cầm, thủy cầm tại một số tính phía
Bắc vừa thuộc về lĩnh vực y tế liên quan đến lây bệnh sang ngƣời nhƣng cũng thuộc
về lĩnh vực kinh tế liên quan đến ngành chăn nuôi, …
Phân lớp dữ liệu:
Phân lớp dữ liệu (classification) là một trong những hƣớng nghiên cứu chính
của khai phá dữ liệu. Thực tế đặt ra nhu cầu là từ một cơ sơ dữ liệu với nhiều thông
tin ẩn con ngƣời có thể rút trích ra các quyết định nghiệp vụ thông minh. Phân lớp
là một dạng của phân tích dữ liệu nhằm rút trích ra một mô hình mô tả các lớp dữ
liệu quan trọng hay dự đoán xu hƣớng dữ liệu trong tƣơng lai.
Phân lớp dự đoán giá trị của những nhãn xác định hay những giá trị rời rạc,
có nghĩa là phân lớp thao tác với những đối tƣợng dữ liệu mà có bộ giá trị là biết
trƣớc. Tóm lại, phân lớp là quá trình nhóm các đối tƣợng giống nhau vào một lớp
dựa trên các đặc trƣng dữ liệu của chúng. 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 (machine learning), hệ chuyên gia (expert system), thống kê (statistics) 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, ngân
hàng, maketing, nghiên cứu thị trƣờng, bảo hiểm, y tế, giáo dục…
5
Bài toán phân lớp dữ liệu:
Là quá trình phân lớp một đối tƣợng dữ liệu vào một hay nhiều lớp đã cho
trƣớc nhờ một mô hình phân lớp (model). Mô hình này đƣợc xây dựng dựa trên một
tập dữ liệu đƣợc xây dựng trƣớc đó có gán nhãn (còn gọi là tập huấn luyện). Quá
trình phân lớp là quá trình gán nhãn cho đối tƣợng dữ liệu. Nhiệm vụ của bài toán
phân lớp là cần tìm một mô hình phân lớp để khi có dữ liệu mới thì có thể xác định
đƣợc dữ liệu đó thuộc vào phân lớp nào. Bài toán phân lớp dữ liệu có thể đƣợc mô
tả nhƣ hình 1.1 dƣới đây [5].
Hình 1.1 Mô hình mô tả bài toán phân lớp dữ liệu
Bài toán phân lớp dữ liệu có thể phát biểu tổng quát nhƣ sau:
Cho U = {A1, A2,…., Am} là tập có m thuộc tính, Y = {y1, y2, ….., yn} là tập các
nhãn của lớp: với D = A1 …
Am là tích Đề - các của các miền của m thuộc tính
tƣơng ứng có n số lớp và N là số mẫu dữ iệu. Mỗi dữ liệu di D thuộc một lớp yi Y
tƣơng ứng tạo thành từng cặp (di, yi)
.
1.2. Quy trình phân lớp dữ liệu
Giới thiệu mô hình và phân tích quy trình phân lớp dữ liệu, quá trình phân
lớp dữ liệu thƣờng gồm hai bƣớc: xây dựng mô hình (tạo bộ phân lớp) và sử dụng
mô hình đó để phân lớp dữ liệu, và đƣa ra chi tiết của hai bƣớc trên.
6
Quy trình thực hiện phân lớp dữ liệu thƣờng đƣợc thực hiện theo 2 bƣớc:
Bƣớc thứ nhất (learning) quá trình học để xây dựng mô hình phân lớp và bƣớc thứ
hai áp dụng mô hình phân lớp ở bƣớc thứ nhất để phân lớp dữ liệu mới.
Bước thứ nhất (learning)
Quá trình học nhằm xây dựng một mô hình mô tả một tập các lớp dữ liệu hay
các khái niệm định trƣớc. Đầu vào của quá trình này là một tập dữ liệu có cấu trúc
đƣợc mô tả bằng các thuộc tính và đƣợc tạo ra từ tập các bộ giá trị của các thuộc
tính đó. Mỗi bộ giá trị đƣợc gọi chung là một phần tử dữ liệu (data tuple), có thể là
các mẫu (sample), ví dụ (example), đối tƣợng (object), bản ghi (record) hay trƣờng
hợp (case). Trong tập dữ liệu này, mỗi phần tử dữ liệu đƣợc giả sử thuộc về một lớp
định trƣớc, lớp ở đây là giá trị của một thuộc tính đƣợc chọn làm thuộc tính gán
nhãn lớp hay thuộc tính phân lớp (class lable attribute). Đầu ra của bƣớc này thƣờng
là các quy tắc phân lớp dƣới dạng luật dạng if-then, cây quyết định, công thức logic,
hay mạng nơron. Quá trình này đƣợc mô tả nhƣ hình 1.2 [5], [8].
Hình 1.2 Quá trình phân lớp dữ liệu -(a) xây dựng mô hình phân lớp
Bước thứ hai (classification)
7
Bƣớc thứ hai dùng mô hình đã xây dựng ở bƣớc thứ nhất để phân lớp dữ liệu
mới. Trƣớc tiên độ chính xác mang tính chất dự đoán của mô hình phân lớp vừa tạo
ra đƣợc ƣớc lƣợng. Holdout là một kỹ thuật đơn giản để ƣớc lƣợng độ chính xác đó.
Kỹ thuật này sử dụng một 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 các mẫu trong tập dữ liệu đào
tạo. Độ chính xác của mô hình trên tập dữ liệu kiểm tra đã đƣa là tỉ lệ phần trăm các
mẫu trong tập dữ liệu kiểm tra đƣợc mô hình phân lớp đúng (so với thực tế). Nếu độ
chính xác của mô hình đƣợc ƣớc lƣợng dựa trên tập dữ liệu đào tạo thì kết quả thu
đƣợc là rất khả quan vì mô hình luôn có xu hƣớng “quá vừa” dữ liệu. Quá vừa dữ
liệu là hiện tƣợng kết quả phân lớp trùng khít với dữ liệu thực tế vì quá trình xây
dựng mô hình phân lớp từ tập dữ liệu đào tạo có thể đã kết hợp những đặc điểm
riêng biệt của tập dữ liệu đó. Do vậy cần sử dụng một tập dữ liệu mà giá trị của
thuộc tính phân lớp là chƣa biết.
Hình 1.3 Quá trình phân lớp dữ liệu - (b1) Ước lượng độ chính xác của
mô hình
8
Hình 1.4 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 giữ vai trò trung tâm, quyết
định tới sự thành công của mô hình phân lớp. Do vậy chìa khóa của vấn đề phân lớp
dữ liệu là tìm ra đƣợc một thuật toán phân lớp nhanh, hiệu quả, có độ chính xác cao
và có khả năng mở rộng đƣợc. Trong đó khả năng mở rộng của thuật toán đƣợc đặc
biệt chú trọng và phát triển.
1.3. Các vấn đề liên quan đến phân lớp dữ liệu
Vấn đề về chuẩn bị dữ liệu bao gồm: Làm sạch dữ liệu, phân tích sự cần thiết
của dữ liệu, chuyển đổi dữ liệu [5].
Làm sạch dữ liệu
Làm sạch dữ liệu liên quan đến việc xử lý với lỗi (noise) và giá trị thiếu
(missing value) trong tập dữ liệu ban đầu. Noise là các lỗi ngẫu nhiên hay các giá trị
không hợp lệ của các biến trong tập dữ liệu. Để xử lý với loại lỗi này có thể dùng kỹ
9
- Xem thêm -