ĐẠI HỌC QUỐC GIA THÀNH PHỐ HỒ CHÍ MINH
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN
TIỂU LUẬN CHUYÊN ĐỀ
MÔN HỌC : KHAI PHÁ DỮ LIỆU VÀ KHO DỮ LIỆU
ĐỀ TÀI :
THUẬT TOÁN K-MEANS VỚI ỨNG DỤNG WEKA TRONG BÀI
TOÁN THỰC TẾ
GVHD : TS ĐỖ PHÚC
HỌC VIÊN : TRẦN ANH ĐỨC
MÃ HỌC VIÊN : 1102015
LỚP : CAO HỌC K6-HN
HÀ NỘI 2014
1
MỤC LỤC
Chương 1 : 3
1.1 Giới thiệu về khai phá dữ liệu: 3
1.2 Các nhiệm vụ của khai phá dữ liệu: 5
1.3 Các loại dữ liệu được khai phá: 5
1.4 Lịch sử phát triển của Khai phá dữ liệu: 6
1.5 Ứng dụng của Khai phá dữ liệu: 6
1.6 Phân loại: 8
1.7 Một số thách thức đặt ra cho việc khai phá dữ liệu : 8
Chương 2 : 8
2.1 Quy trình Tổng quát thực hiện Khai phá dữ liệu: 9
2.2 Tiến trình khám phá tri thức khi đi vào một bài toán cụ thể : 10
3. Ứng dụng WEKA trong bài toán thực tế : 18
1.1.Mô tả tập dữ liệu (Dataset) 18
1.1.1.Nguồn gốc (UCI ARFF Repository) 18
1.1.2.Thuộc tính và ý nghĩa các thuộc tính 19
1.2.Bài toán phân lớp (Classification Problem) trên tập dữ liệu đã cho 20
2.Xây dựng mô hình huấn luyện cho bộ phân lớp (classifier) 20

Chương 1 :
TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU
1.1 Giới thiệu về khai phá dữ liệu:
Khai phá dữ liệu được định nghĩa là quá trình trích xuất các thông tin có giá trị tiềm
ẩn bên trong lượng lớn dữ liệu được lưu trữ trong các cơ sở dữ liệu, kho dữ liệu. Cụ thể
3
hơn đó là tiến trình trích lọc, sản sinh những tri thức hoặc những mẫu tiềm ẩn, chưa biết
nhưng hữu ích từ các cơ sở dữ liệu lớn. Đồng thời là tiến trình khái quát các sự kiện rời
rạc trong dữ liệu thành các tri thức mang tính khái quát, tính qui luật hỗ trợ tích cực cho
các tiến trình ra quyết định. Hiện nay, ngoài thuật ngữ khai phá dữ liệu, người ta còn
dùng một số thuật ngữ khác có ý nghĩa tương tự như: Khai phá tri thức từ CSDL
(Knowlegde mining from database), trích lọc dữ liệu (Knowlegde extraction), phân tích
dữ liệu/mẫu (data/pattern analysis), khảo cổ dữ liệu (data archaeology), nạo vét dữ liệu
(data dredredging). Nhiều người coi khai phá dữ liệu và một số thuật ngữ thông dụng
khác là khám phá tri thức trong CSDL (Knowledge Discovery in Databases- KDD) là
như nhau. Tuy nhiên trên thực tế khai phá dữ liệu chỉ là một bước thiết yếu trong quá
trình Khám phá tri thức trong CSDL.
Để hình dung vấn đề này ta có thể sử dụng một ví dụ đơn giản như sau: Khai phá dữ
liệu được ví như tìm một cây kim trong đống cỏ khô. Trong ví dụ này, cây kim là một
mảnh nhỏ tri thức hoặc một thông tin có giá trị và đống cỏ khô là một kho cơ sở dữ liệu
rộng lớn. Như vậy, những thông tin có giá trị tiềm ẩn trong kho cơ sở dữ liệu sẽ được
chiết xuất ra và sử dụng một cách hữu ích nhờ khai phá dữ liệu. Chức năng khai phá dữ
liệu gồm có gộp nhóm phân loại, dự báo, dự đoán và phân tích các liên kết.
Nguồn dữ liệu phục vụ cho KTDL có thể là các CSDL lớn hay các kho dữ liệu
(Datawarehouse) có hay không có cấu trúc. Các tác vụ khai phá dữ liệu có thể được phân
thành hai loại: miêu tả và dự báohoặc các đặc tính chung của dữ liệu trong CSDL hiện
có. Các kỹ thuật này gồm có: phân cụm (clustering), tóm tắt (summerization), trực quan
hoá (visualiztion), phân tích sự phát triển và độ lệch (Evolution and deviation analyst),
phân tích luật kết hợp (association rules)…
- Các tác vụ khai phá miêu tả mô tả các đặc tính chung của dữ liệu trong cơ sở dữ

- Khám phá quy luật biến đổi: tìm những tập luật phản ánh những hành vi tiến hóa, biến
đổi chung của một tập dữ liệu. Ví dụ như luật khám phá những yếu tố chính tác động lên
sự thay đổi của những giá cổ phiếu nào đó.
1.3 Các loại dữ liệu được khai phá:
Khai phá dữ liệu thường làm việc với nhiều kiểu dữ liệu khác nhau. Hầu hết các
kiểu dữ liệu được khai phá là những kiểu sau:
- Cơ sở dữ liệu quan hệ: những cơ sở dữ liệu được tổ chức theo mô hình quan hệ. Hầu
hết những hệ quản trị cơ sở dữ liệu hiện nay đều hỗ trợ mô hình
này như: Oracle, IBM DB2, MS SQL Server, MS Access…
- Cơ sở dữ liệu đa chiều: cơ sở dữ liệu này được gọi là nhà kho dữ liệu,trong đó dữ liệu
được chọn từ nhiều ngồn khác nhau và chứa những đặc tính lịch sử thông qua thuộc tính
thời gian tường minh hay ngầm định.
5
- Cơ sở dữ liệu giao tác: đây là loại cơ sở dữ liệu được sử dụng nhiều trong siêu thị,
thương mại, tài chính, ngân hàng…
- Cơ sở dữ liệu quan hệ - hướng đố tượng: mô hình cơ sở dữ liệu này lai giữa mô hình
hướng đối tượng và mô hình cơ sở dữ liệu quan hệ.
- Cơ sở dữ liệu thời gian, không gian: chứa những thông tin về không gian địa lý hoặc
thông tin theo thời gian.
- Cơ sở dữ liệu đa phương tiện: loại dữ liệu này bao gồm: âm thanh, ảnh,video, văn bản
và nhiều kiểu dữ liệu định dạng khác. Ngày nay loại dữ liệu này được sử dụng nhiều trên
mạng Internet.
1.4 Lịch sử phát triển của Khai phá dữ liệu:
- Những năm 1960: Xuất hiện CSDL theo mô hình mạng và mô hình phân cấp.
- Những năm 1970: Thiết lập nền tẩng lý thuyết cho CSDL quan hệ, các hệ quản
trị CSDL quan hệ.
- Những năm 1980: Hoàn thiện lý thuyết về CSDL quan hệ và các hệ quản trị
CSDL quan hệ, xuất hiện các hệ quản trị CSDL cao cấp (hướng đối tượng, suy diễn, )
và hệ quản trị hướng ứng dụng trong lĩnh vực không gian, khoa học, công nghiệp, nông
nghiệp, địa lý .

◊ Phát hiện dùng thẻ tín dụng giả trên mạng và là công cụ hữu ích cho dịch vụ quản lý
rủi ro cho thương mại điện tử
- Thương mại điện tử:
◊ Công cụ tìm hiểu, định hướng thúc đẩy, giao tiếp với khách hàng.
◊ Phân tích hành vi mua sắm trên mạng và cho biết thông tin tiếp thị phù hợp với loại
khách hàng trong một phân khu thị trường nhất định
- Nhân sự:
◊ Giúp nhà tuyển dụng chọn ứng viên thích hợp nhất cho nhu cầu của công ty
- Y học:
◊ Hỗ trợ bác sĩ phát hiện ra bệnh của bệnh nhân dựa trên các xét nghiệm đầu vào
- An ninh, an toàn mạng
◊ Ứng dụng trong hệ thống phát hiện xâm nhập trái phép IDS/IPS để phát hiện ra các
cuộc tấn công xâm nhập mạng trái phép.
- Một số ứng dụng của khai phá dữ liệu trong lĩnh vực kinh doanh:
BRANDAID: mô hình marketing linh hoạt tập chung vào hàng tiêu dùng đóng gói.
7
CALLPLAN: giúp nhân viên bán hàng xác định số lần viếng thăm của khách hàng
triển vọng và khách hàng hiện có.
DETAILER: xác định khách hàng nào nên viếng thăm và sản phẩm nào nên giới
thiệu trong từng chuyến viếng thăm,
GEOLINE: mô hình thiết kế địa bàn tiêu thụ và dịch vụ.
MEDIAC: Giúp người quảng cáo mua phương tiện trong một năm, lập kế hoạch
sử dụng phương tiện bao gồm phác hoạ khúc thị trường, ước tính tiềm năng .
1.6 Phân loại:
Chúng ta có thể phân lớp hệ thống khai phá dữ liệu theo các tiêu chuẩn sau:
Phân lớp dựa trên loại dữ liệu được khai phá: những hệ thống khai phá dữ liệu làm
việc với cơ sở dữ liệu quan hệ, nhà kho dữ liệu, cơ sở dữ liệu giao tác, cơ sở dữ liệu
hướng đối tượng, đa phương tiện và Web…
Phân lớp dựa trên kiểu tri thức khai phá: hệ thống khai phá dữ liệu xuất kết quả kiểu tóm
tắt, mô tả, luật kết hợp, phân lớp, phân nhóm và dự báo…

quan hoá dữ liệu để biểu diễn tri thức khai phá được cho người sử dụng. Ordinal
Hình 2.1: Data mining – một bước trong quá trình khám phá tri thức
9
2.2 Tiến trình khám phá tri thức khi đi vào một bài toán cụ thể :
Chính vì mục tiêu khám phá trí thức ngầm định trong cơ sở dữ liệu nên quá trình
khai phá thường phải qua một số các giai đoạn cần thiết. Bao gồm những giai đoạn chuẩn
bị dữ liệu khai phá, giai đoạn khai phá dữ liệu và cuối cùng là giai đoạn chuyển kêt quả
khai phá sang những tri thức cho con người hiểu được. Chi tiết các bước thực hiện được
mô tả trong bảng tóm tắt như sau:
- Giai đoạn 1: đầu tiên là phát triển một sự hiểu biết về lĩnh vực ứng dụng và những tri
thức tương ứng. Xác định mục đích của tiến trình khai phá dữ liệu từ qua điểm của người
dùng.
- Giai đoạn 2: chuẩn bị dữ liệu để khai phá, thu thập dữ liệu và dữ liệu mẫu
- Giai đoạn 3: tiền xử lý dữ liệu, xóa các thông tin bị nhiễu trong dữ liệu,loại bỏ sự trùng
lặp dữ liệu và xác định chiến lược để xử lý dữ liệu bị mất.
- Giai đoạn 4: chiếu dữ liệu, thu nhỏ dữ liệu và tìm những đặc trưng để khai phá
Hình 2.2: Tổng quan tiến trình khai phá dữ liệu
- Giai đoạn 5: chọn một phương pháp khai phá dữ liệu thích hợp nhất trong số các
phương pháp phổ biến như: tóm tắt, phân lớp, hồi quy, phân nhóm, kết hợp…
10
- Giai đoạn 6: từ thuật toán đã chọn, mô hình hóa thuật toán để giải quyết trong trường
hợp cụ thể đang xét. Lựa chọn những phương pháp tìm kiếm mẫu dữ liệu, quyết định các
tham số.
- Giai đoạn 7: đây là giai đoạn khai phá dữ liệu, sử dụng thuật toán để tìm kiếm những
mẫu thú vị trong một hình thức thể hiện đắc thù hoặc một tập những thể hiện bao gồm
những luật phân lớp, cây, sự hồi quy và phân nhóm.
- Giai đoạn 8: thông dịch lại những mẫu đã được khai phá dưới các hình thức thể hiện tri
thức của dữ liệu như ngôn ngữ, biểu đồ, hình cây, bảng…
Quá trình khai phá này có sự tương tác và lặp lại giữa hại bước bất kỳ, những bước cơ
bản của tiến trình được minh họa trong hình trên. Hầu hết những công việc trước đây đều

(clustering weblog);…
Các kỹ thuật phân cụm được phân loại như sau (xem hình)
12
2. Thuật Toán K-Means
K-Means là thuật toán rất quan trọng và được sử dụng phổ biến trong kỹ thuật phân cụm.
Tư tưởng chính của thuật toán K-Means là tìm cách phân nhóm các đối tượng (objects)
đã cho vào K cụm (K là số các cụm được xác đinh trước, K nguyên dương) sao cho tổng
bình phương khoảng cách giữa các đối tượng đến tâm nhóm (centroid ) là nhỏ nhất.
Thuật toán K-Means được mô tả như sauThuật toán K-Means thực hiện qua các bước chính sau:
13
1. Chọn ngẫu nhiên K tâm (centroid) cho K cụm (cluster). Mỗi cụm được đại diện
bằng các tâm của cụm.
2. Tính khoảng cách giữa các đối tượng (objects) đến K tâm (thường dùng khoảng
cách Euclidean)
3. Nhóm các đối tượng vào nhóm gần nhất
4. Xác định lại tâm mới cho các nhóm
5. Thực hiện lại bước 2 cho đến khi không có sự thay đổi nhóm nào của các đối
tượng

Ví dụ minh họa thuật toán K-Mean:
Giả sử ta có 4 loại thuốc A,B,C,D, mỗi loại thuộc được biểu diễn bởi 2 đặc trưng X và Y
như sau. Mục đích của ta là nhóm các thuốc đã cho vào 2 nhóm (K=2) dựa vào các đặc
trưng của chúng.
Bước 1. Khởi tạo tâm (centroid) cho 2 nhóm. Giả sử ta chọn A là tâm của nhóm thứ nhất
(tọa độ tâm nhóm thứ nhất c1(1,1)) và B là tâm của nhóm thứ 2 (tạo độ tâm nhóm thứ hai
c2 (2,1)).
Bước 2. Tính khoảng cách từ các đối tượng đến tâm của các nhóm (Khoảng cách

17
Thuật toán K-Means có ưu điểm là đơn giản, dễ hiểu và cài đặt. Tuy nhiên, một số hạn
chế của K-Means là hiệu quả của thuật toán phụ thuộc vào việc chọn số nhóm K (phải
xác định trước) và chi phí cho thực hiện vòng lặp tính toán khoảng cách lớn khi số cụm K
và dữ liệu phân cụm lớn.
• Điểm mạnh của phương pháp gom cụm k- means
- Hiệu suất tương đối: O(nkt) với n là số đối tượng, k là số cụm, t là số lần lặp.
Thông thường k, t << n.
- Thuật toán này có ưu điểm là rõ ràng, dễ dàng cài đặt.
• Điểm yếu của phương pháp k- means
- Có thể áp dụng chỉ khi xác định được trị trung bình
- Cần chỉ định trước số các cụm- k.
- Không thể xử lý nhiễu và outliers
3. Ứng dụng WEKA trong bài toán thực tế :
1.Bài toán thực tế :
1.1. Mô tả tập dữ liệu (Dataset)
1.1.1. Nguồn gốc (UCI ARFF Repository)
Link download từ Intrenet:
Gordon Peterson và Harold Barney đã tiến hành một điều tra chi tiết về các
nguyên âm Anh - Mỹ trong bài báo [1]. Công trình này đưa ra một độ đo âm thanh
của tần số gốc (Fundalmental frequency – F0) và 9 tần số đặc trưng tiếp theo (formant
frequencies – là những tần số trong âm thanh có được do cộng hưởng của các tần số
bậc thấp hơn) đối với một tập các từ chứa các nguyên âm khác nhau. Cụ thể, đối với
mỗi nguyên âm, các tác giả đặt trong những từ khác nhau, bắt đầu bằng âm h và kết
thúc bằng âm d (Ví dụ: heed /hi:d/, hid/hId/…) và ghi nhận lại các tần số âm thanh
phát ra theo 10 đặc trưng nêu trên. Bảng 1 cho thấy dữ liệu trong thực nghiệm này:
18

Raymond Watrous [2] đã tiến hành sắp xếp lại dữ liệu tổ chức trong [1] sử dụng
tại trường đại học University of Pennsylvania. Sau một thời gian được chỉnh sửa và

khác nhau (Từ F1 đến F9). Mỗi tần số được mô hình hóa kiểu real (miền dữ liệu liên
tục).
Tập nguyên âm mẫu:
Trong tập dữ liệu vowel, mỗi nguyên âm /X/ được coi là một thành phần của một từ
nào đó có dạng /hXd/. Các từ này được trình bày trong bảng 1. Tập các nguyên âm
được đưa vào thuộc tính Class (thuộc tính được chỉ định dùng để phân lớp). Thuộc
tính Class được cấu trúc thành dạng tập hợp 11 thành phần (tương ứng với 11 nguyên
âm tiếng Anh) như sau:
@attribute 'Class' { hid, hId, hEd, hAd, hYd, had, hOd, hod, hUd, hud, hed}
1.2. Bài toán phân lớp (Classification Problem) trên tập dữ liệu đã cho
- Dùng tập dữ liệu đã cho huấn luyện một bộ phân lớp có khả năng phân biệt các
nguyên âm tiếng Anh.
- Ngoài ra, dựa trên tập dữ liệu huấn luyện, kiểm nghiệm những nguyên lý vật lý cơ
bản về giọng nói như: Sự phụ thuộc của tần số âm hòa âm vào tần số gốc, các
nguyên âm được phát ra có được phân biệt bởi các thuộc tính hòa âm hay không.
2. Xây dựng mô hình huấn luyện cho bộ phân lớp (classifier)
Trong lĩnh vực máy học (machine Learning) và nhận dạng mẫu (pattern
recognition), bài toán phân lớp (classification) đề cập đến các thuật toán (algorithms)
nhằm xác định lớp (class) của đối tượng đã cho sẽ thuộc về lớp nào trong các lớp đã
cho trước (given categories). Khác với bài toán phân cụm (clustering), dữ liệu dùng
để xây dựng mô hình (Training Data) trong bài toán phân lớp phải được xác định lớp
trước (pre-Labeled). Ví dụ, xác định một email thuộc “spam” hoặc “non-spam”, hay
xác định loại bệnh của bệnh nhân dựa vào các triệu chứng của họ.
Điều kiện tiên quyết để xây dựng một bộ phân lớp hiệu quả là việc xử lý dữ liệu
huấn luyện. Điều này được thể hiện rõ trên hai khía cạnh. Thứ nhất, việc xử lý dữ liệu
làm dữ liệu huấn luyện ổn định, hạn chế sai sót (xử lý oulier), hạn chế tình trạng mất
mát dữ liệu. Từ đó mà bộ phân lớp trở nên ổn định hơn. Thứ hai, việc xử lý dữ liệu
bao gồm cả việc lựa chọn các thuộc tính có liên quan, loại bỏ các thuộc tính ít liên
quan trong quá trình phân lớp. Điều này làm giảm các trường dữ liệu gây nhiễu cho
quá trình huấn luyện bộ phân lớp.

21
2.1.1. Vấn đề loại bỏ các thuộc tính không có liên quan đến thuộc tính phân lớp
a. Dựa vào nhận xét chủ quan đối với bộ dữ liệu đang xét
Dựa trên kiến thức vật lý (chủ quan của sinh viên) về âm thanh và giọng nói, mỗi
nguyên âm (vowel) được phát ra sẽ có một tập các phổ tần số khác nhau, là kết quả
của tần số cơ bản F0 và các tần số hòa âm F1…F9. Tuy nhiên – cũng theo nhận thức
của sinh viên – thì âm của nguyên âm có năng lượng tập trung ở các dải âm tần tương
thấp (tức là tập trung chủ yếu vào các tần số F0, F1, F2, F3). Thực tế thì trong mẫu dữ
liệu gốc của vowel.arff là pbvowel.arff cũng chỉ quan tâm đến các tần số F0, F1, F2,
F3. Vậy, khi tách lớp, ta có thể loại bỏ các thuộc tính âm tần bậc cao (F7, F8, F9).
Weka cung cấp cho người sử dụng một phương thức rất đơn giản để loại bỏ các
thuộc tính không cần thiết bằng tay (chọn các thuộc tính muốn xóa rồi nhấn Remove).
b. Dựa vào đánh giá khách quan theo các thuật toán đo độ tương quan
Các luồng ý kiến khác cho rằng việc nhận xét về một tập dữ liệu nào đó sử dụng
tri thức đã có để tiến hành chọn các thuộc tính liên quan là không thỏa đáng. Những
người ủng hộ luồng ý kiến này cho rằng số liệu thống kê và số đo độ tương quan giữa
các thuộc tính là yếu tố quyết định xem một thuộc tính là quan trọng hay không quan
trọng đối với thuộc tính khác (ở đây là thuộc tính phân lớp). Xem xét này có thể đúng
với một số trường hợp, tuy nhiên với những dữ liệu thực tế thì lại thường không hiệu
quả, nhất là những mẫu dữ liệu “chưa đủ lớn – chưa đầy đủ, chưa đủ chuẩn hóa và
22
chưa đủ ổn định”. Lấy ví dụ, việc sử dụng các thuật toán đo độ tương quan giữa
thuộc tính “số con cái” và thuộc tính “kế hoạch sinh con” trong điều tra về việc thụ
thai (UCI Contraceptive Method Choice -
có thể sai nếu
số liệu về số con cái chưa được khảo sát đầy đủ (dữ liệu khuyết thiếu).
*) Những nhận định và phương pháp loại bỏ thuộc tính trên sẽ được thực nghiệm
trên tập dữ liệu vowel.arff, sử dụng weka. Tuy nhiên, do những hạn chế ở mỗi
phương pháp tiếp cận trên, việc phối hợp linh hoạt giữa tri thức người và đo lường
của máy là điều kiện cần để có một bộ dữ liệu huấn luyện tốt.

Initialize the weights in the network (often randomly)
Do
For each example e in the training set
O = neural-net-output(network, e) ; forward pass
T = teacher output for e
Calculate error (T - O) at the output units
Compute delta_wh for all weights from hidden layer to output layer ;
backward pass
Compute delta_wi for all weights from input layer to hidden layer ; backward
pass continued
Update the weights in the network
Until all examples classified correctly or stopping criterion satisfied
Return the network
Mã giả phân loại dữ liệu với mạng neural
25