Thuật toán K-Means và ứng dụng trong thực tế
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 (385.44 KB, 23 trang )
Bạn đang đọc: Thuật toán K-Means và ứng dụng trong thực tế
Đại học Quốc gia Thành phố Hồ Chí Minh
Trường Đại học Công nghệ thông tin
Khoa Mạng máy tính và truyền thông
o0o
Bài báo cáo môn:
KHAI PHÁ DỮ LIỆU VÀ
KHO DỮ LIỆU
Đề tài:
Thuật toán K-Means và ứng
dụng trong thực tế
GVHD : PGS.TS. Đỗ Phúc
Học viên : Bùi Anh Kiệt
MSHV : CH1101018
Tp. Hồ Chí Minh – Ngày 24 tháng 11 năm 2012
Khai phá dữ liệu & kho dữ liệu Thuật toán K-Means & ứng dụng thực tế
Lời mở đầu
Dữ liệu trong tự nhiên là một tài nguyên vô tận, nó tồn tại ở rất nhiều dạng, vật
chất, thông tin kể cả con người. Và trong thời đại của công nghệ thông tin, dữ liệu
của tự nhiên dần dần chuyển thành dạng thông tin và lưu trữ khắp nơi trên thế
giới số.
Khai thác dữ liệu là một ngành khoa học có nhiều ứng dụng trong thực tế, đặc
biệt là trong các ngành kinh tế học. Việc khai thác dữ liệu có hiệu quả hay không
phụ thuộc vào nhiều yếu tố. Hai trong số đó là thuật toán dùng để khai phá dữ
liệu và loại dữ liệu muốn khai phá. Trong điều kiện công nghệ thông tin phát triển
mạnh, dữ liệu tự nhiên đã hầu như chuyển thành dạng dữ liệu số và đó chính là
điều kiện để các thuật toán khai phá dữ liệu có cơ hội phát triển bùng nổ.
Trong các thuật toán về khai phá dữ liệu, thuật toán gom cụm dữ liệu được biết
đến nhiều vì khả năng áp dụng của nó trong việc phân tích và chọn lọc dữ liệu
cần thiết từ nguồn dữ liệu số. Và trong các thuật toán gom cụm, thuật toán K-
Means được xem như một thuật toán cơ bản, khởi đầu cho phương pháp khai phá
dữ liệu bằng cách gom cụm.
Tuy còn hạn chế nhưng thuật toán K-Means là nền tảng, chỉ ra một hướng đi về
khai phá dữ liệu bằng cách gom cụm và đạt được hiệu quả cao. Không những vậy,
K-Means còn là khởi đầu cho nhiều thuật toán gom cụm ra đời tiếp theo với mục
đích đạt được hiệu quả tối ưu nhất.
Và trong tài liệu này, tôi xin được trình bày về K-Means, về những ưu nhược điểm
và đề xuất ra những hướng khắc phục cho thuật toán này.
Và để hoàn thành tài liệu này, ngoài nổ lực bản thân còn có sự giúp đỡ rất lớn từ
PGS.TS Đỗ Phúc, người đã truyền đạt ý tưởng và những vấn đề quan trọng về
thuật toán K-Means, về những nhận định hướng phát triển mới của thuật toán.
Học viên: Bùi Anh Kiệt – CH1101018 2
Khai phá dữ liệu & kho dữ liệu Thuật toán K-Means & ứng dụng thực tế
Mục lục
Lời mở đầu 2
Mục lục 3
1 Thuật toán K-Means 4
1.1 Tổng quan 4
1.2 Nội dung thuật toán 5
1.3 Đặc điểm của thuật toán 7
1.4 Các biến thể của thuật toán K-Means 8
2 Ứng dụng thuật toán K-Means trong thực tế 9
2.1 Phân đoạn ảnh 9
2.2 Nhận dạng 10
2.3 Khai phá dữ liệu 11
3 Cài đặt thuật toán K-Means 13
3.1 Ý tưởng thuật toán K-Means 13
3.2 Cài đặt thuật toán 13
3.3 Hướng phát triển của thuật toán 14
4 Kết luận 16
Phụ lục 17
Tài liệu tham khảo 23
Học viên: Bùi Anh Kiệt – CH1101018 3
Khai phá dữ liệu & kho dữ liệu Thuật toán K-Means & ứng dụng thực tế
1 Thuật toán K-Means
1.1 Tổng quan
K-Means là thuật toán phân cụm dữ liệu, dùng để tiếp cận phân hoạch. Số
lượng cụm trong phân hoạch là một số cố định cho trước. Các cụm được hình
thành dựa vào khoảng cách các điểm trung tâm. Một điểm sẽ thuộc vào một cụm
nếu như khoảng cách từ điểm đó đến điểm trung tâm của cụm là nhỏ nhất trong số
các khoảng cách từ điểm đó đến các điểm trung tâm.
Vì vậy, cần khởi tạo một tập các điểm trung tâm ban đầu để làm nền tảng
.cho việc tính toán và phân lại cụm cho các điểm trong đồ thị. Quá trình xác định
cụm cho một điểm được thực lặp đi lặp lại nhiều lần, sau mỗi lần tính toán, các
điểm trung tâm sẽ thay đổi vị trí và các cụm của đồ thị cũng thay đổi theo. Quá
trình tính toán và xác định cụm cho các điểm dừng lại khi thành phần các cụm
tương đối ổn định (các điểm thuộc vào các cụm không thay đổi).
Trong phương pháp K-means, chọn một giá trị k và sau đó chọn ngẫu nhiên
k trung tâm của các đối tượng dữ liệu. Tính toán khoảng cách giữa đối tượng dữ
liệu trung bình mỗi cùm để tìm kiếm phần tử nào là tương tự và thêm vào cụm đó.
Từ khoảng cách này có thể tính toán trung bình mới của cụm và lặp lại quá trình
cho đến khi mỗi các đối tượng dữ liệu là một bộ phận của các cụm k.
Mục đích của thuật toán K-means là sinh k cụm dữ liệu {C1, C2,…, Ck} từ
một tập dữ liệu chứa n đối tượng trong không gian d chiều Xi = {xi1, xi2,…xid},
i = 1÷ n, sao cho hàm tiêu chuẩn :
đạt giá trị tối tiểu.
Trong đó: m
i
là trọng tâm của cụm Ci, D là khoảng cách giữa hai đối tượng.
Trọng tâm của cụm là một vector, trong đó giá trị của mỗi phần tử của nó là trung
cộng của các thành phần tương ứng của các đối tượng vector dữ liệu trong cụm
Học viên: Bùi Anh Kiệt – CH1101018 4
Khai phá dữ liệu & kho dữ liệu Thuật toán K-Means & ứng dụng thực tế
đang xét. Tham số đầu vào của thuật toán là số cụm k, và tham số đầu ra của thuật
toán là các trọng tâm của các cụm dữ liệu. Độ đo khoảng cách D giữa các đối
tượng dữ liệu thường được sử dụng là khoảng cách Euclide vì đây là mô hình
khoảng cách nên dễ lấy đạo hàm và xác định các cực trị tối thiểu. Hàm tiêu chuẩn
và độ đo khoảng cách có thể được xác định cụ thể hơn tùy ý vào ứng dụng hoặc
quan điểm của người dùng.
1.2 Nội dung thuật toán
Cho k là số cụm sau khi phân hoạch. (1 <= k <= n, với n là số điểm đối
tượng trong không gian dữ liệu.
Thuật toán K-Means gồm 4 bước:
1. Chọn k điểm làm trọng tâm ban đầu của k cụm.
2. Gán (hoặc gán lại) từng điểm vào cụm có trọng tâm gần điểm đang xét
nhất.
Nếu không có phép gán lại nào thì dừng, vì không có phép gán lại nào có
nghĩa là các cụm đã ổn định và thuật toán không thể cải thiện làm giảm độ
phân biệt được nữa.
3. Tính lại trọng tâm cho từng cụm.
4. Quay lại bước 2.
Một số khái niệm được dùng trong thuật toán K-Means:
(1) Ma trận phân hoạch: Ma trận phân hoạch là ma trận biểu hiện cho sự phụ
thuộc của một điểm vào một cụm nào đó.
Table 1.1 – Ví dụ về ma trận phân hoạch
x
1
x
2
x
3
x
4
x
5
c
1
1 1 0 0 0
c
2
0 0 1 0 1
c
3
0 0 0 1 0
Học viên: Bùi Anh Kiệt – CH1101018 5
Khai phá dữ liệu & kho dữ liệu Thuật toán K-Means & ứng dụng thực tế
Trong ma trận phân hoạch trên, ta thấy ứng với mỗi cột chỉ có một dòng có
giá trị 1 điều đó thể hiện mỗi đối tượng trong một thời điểm chỉ thuộc về
một cụm.
Sau mỗi lượt gán cụm cho các đối tượng, ma trận phân hoạch lại được cập
nhật. Trong suốt quá trình cập nhật, một đối tượng vẫn chỉ thuộc một cụm
duy nhất.
(2) Vector trọng tâm
Vector trọng tâm chính là vị trí của điểm trung tâm của mỗi cụm. Vector
trọng tâm trong từng thời điểm là không giống nhau và nó phụ thuộc vào số
lượng các điểm nằm trong cụm đó.
Các tính vector trọng tâm được thể hiện như sau:
với:
và
Trong đó, m
ij
là giá trị tương ứng của hang i, cột j trong ma trận phân hoạch
(m
ij
= 0/1). x
ix
là giá trị hoành độ của đối tượng thứ i, x
iy
là giá trị tung độ
của đối tượng thứ i.
(3) Khoảng cách Euclid
Là khoảng cách từ một đối tượng bất kì đến một vector trọng tâm nào đó.
Việc xác định khoảng cách Euclid có ý nghĩa trong việc xác định đối tượng
đang xét thuộc cụm nào. Một đối tượng thuộc một cụm khi khoảng cách
Euclid từ điểm đó đến vector trọng tâm của cụm đó là nhỏ nhất. Khoảng
cách Euclid từ một điểm đến một vector trọng tâm được xác định như sau:
Học viên: Bùi Anh Kiệt – CH1101018 6
Khai phá dữ liệu & kho dữ liệu Thuật toán K-Means & ứng dụng thực tế
1.3 Đặc điểm của thuật toán
Chất lượng của thuật toán K–Means phụ thuộc nhiều vào các tham số đầu vào
như: số cụm k, và k vector trọng tâm khởi tạo ban đầu. Trong trường hợp các
vector trọng tâm khởi tạo ban đầu mà quá lệch so với các trọng tâm cụm tự nhiên
thì kết quả phân cụm của K–Means là rất thấp, nghĩa là các cụm dữ liệu được
khám phá rất lệch so với các cụm trong thực tế. Trên thực tế, chưa có một giải
pháp nào để chọn tham số đầu vào, giải pháp thường được sử dụng nhất là thử
nghiệm với các giá trị đầu vào, giải pháp thường được sử dụng nhất là thử nghiệm
với giá trị đầu vào k khác nhau rồi sau đó chọn giải pháp tốt nhất.
1. Ưu điểm:
– Tương đối nhanh, độ phức tạp của thuật toán là O(tkn) trong đó:
n: là số điểm trong không gian dữ liệu
t: số lần lặp (thường thì t rất nhỏ so với n)
k: số cụm cần phân hoạch
– K-Means phù hợp với các cụm có dạng hình cầu.
– Có khả năng mở rộng và dể dàng sửa đổi với những dữ liệu mới.
– Bảo đảm hội tụ sau một số bước lặp hữu hạn.
– Số cụm luôn ổn định (k cụm cho trước).
– Luôn có ít nhất một điểm trong cụm.
– Các cụm được tách biệt rỏ rang không có hiện tượng một đối tượng xuất
hiện trong nhiều cụm dữ liệu.
2. Nhược điểm:
– Không đảm bảo đạt được tối ưu toàn cục và kết quả đầu ra phụ thuộc
vào nhiều vào việc chọn k điểm khởi đầu.
– Cần xác định trước số cụm.
Học viên: Bùi Anh Kiệt – CH1101018 7
Khai phá dữ liệu & kho dữ liệu Thuật toán K-Means & ứng dụng thực tế
– Khó xác định được thực sự số cụm có trong không gian dữ liệu. Do đó
có thể phải thử với các số k khác nhau.
– Khó phát hiện các loại cụm có hình dạng phức tạp và nhất là các dạng
cụm không lồi.
– Không thể xử lí nhiều mẫu cá biệt (nhiễu).
– Chỉ có thể áp dụng khi tính được trọng tâm.
1.4 Các biến thể của thuật toán K-Means
1.4.1 Thuật toán K-Medoid
Thuật toán K-Medoid tương tự thuật toán K-Means, mỗi cụm được đại diện bởi
một trong số các đối tượng của cụm. Thông thường thì điểm gần vector trọng tâm
sẽ được chọn làm điểm đại diện của cụm.
Thuật toán K-Medoid khắc phục được yếu điểm là loại được nhiễu trong thuật
toán K-Means. Nhưng bù lại, độ phức tạp của thuật toán lại rất lớn.
1.4.2 Thuật toán Fuzzy C-Means
Thuật toán Fuzzy C-Means có chiến lược phân cụm giống như K-Means. Nhưng
có một điểm khác biệt là K-Means phân cụm dữ liệu cứng (một đối tượng chỉ
thuộc vào một cụm) còn Fuzzy C-Means là phân cụm dữ liệu mềm (một đối tượng
có thể thuộc nhiều cụm khác nhau).
Fuzzy C-Means có khả năng phân cụm trong không gian đa chiều và có khả năng
phân cụm tối ưu toàn cục. Tuy nhiên thuật toán này khá phức tạp và tốc độ hội tụ
phụ thuộc vào trạng thái ban đầu của ma trận thành viên.
Học viên: Bùi Anh Kiệt – CH1101018 8
Khai phá dữ liệu & kho dữ liệu Thuật toán K-Means & ứng dụng thực tế
2 Ứng dụng thuật toán K-Means trong thực tế
2.1 Phân đoạn ảnh
Phân đoạn ảnh được xem như là ứng dụng cơ bản của các thuật toán phân cụm.
Định nghĩa:
– Phân đoạn ảnh được hiểu là từ một ảnh đầu vào, thong qua các thuật toán
phân cụm mà tách thành các vùng miền khác nhau và các đối tượng được
tách ra đó được gọi là ảnh con.
– Phân đoạn ảnh là một thao tác ở mức thấp trong toàn bộ quá trình xử lý ảnh.
Quá trình này thực hiện việc phân vùng ảnh thành các vùng rời rạc và đồng
nhất với nhau hay nói cách khác là xác định các biên của các vùng ảnh đó.
Các vùng ảnh đồng nhất này thông thường sẽ tương ứng với toàn bộ hay
từng phần của các đối tượng thật sự bên trong ảnh. Vì thế, trong hầu hết các
ứng dụng của lĩnh vực xử lý ảnh phân đoạn ảnh luôn đóng một vai trò cơ
bản và thường là bước tiền xử lý đầu tiên trong toàn bộ quá trình trước khi
thực hiện các thao tác khác ở mức cao hơn như nhận dạng đối tượng, biểu
diễn đối tượng, nén ảnh dựa trên đối tượng, hay truy vấn ảnh dựa vào nội
dung.
Ứng dụng của phân cụm dữ liệu:
– Ứng dụng đặc điểm của thuật toán phân cụm để chia ảnh thành các vùng
không trùng lắp. Mỗi vùng gồm một nhóm pixel liên thông và đồng nhất
theo một tiêu chí nào đó. Tiêu chí này phụ thuộc vào mục tiêu của quá trình
phân đoạn. Ví dụ như đồng nhất về màu sắc, mức xám, kết cấu, độ sâu của
các layer…
– Mục tiêu của phân cụm là có được một chuỗi các cụm hyperellipsoidal bắt
đầu với các trung tâm cụm vị trí tại các vị trí mật độ tối đa trong không gian
mẫu, và các cụm phát triển về các trung tâm cho đến khi một thử nghiệm tốt
đẹp của x
2
cho phù hợp đã bị vi phạm. Một loạt các tính năng được thảo luận
và áp dụng cho cả hai màu xám và màu sắc hình ảnh.
Học viên: Bùi Anh Kiệt – CH1101018 9
Khai phá dữ liệu & kho dữ liệu Thuật toán K-Means & ứng dụng thực tế
– Kỹ thuật Clustering cũng đã được sử dụng thành công được cho nhiều phân
đoạn của hình ảnh. Trong các báo cáo khoa học về phân vùng ảnh mức xám,
có khá nhiều kỹ thuật cố thực hiện việc thoả mãn cùng lúc cả hai tiêu chí về
tính đồng nhất trong không gian đặc trưng của ảnh và tính cô đọng về nội
dung ảnh. Tuỳ theo các kỹ thuật mà các thuật giải này áp dụng, chúng được
phân thành các nhóm sau:
(1) Các thuật giải áp dụng kỹ thuật chia và trộn vùng.
(2) Các thuật giải áp dụng kỹ thuật tăng trưởng vùng.
(3) Các thuật giải áp dụng lý thuyết đồ thị.
(4) Các giải thuật áp dụng mạng neural.
(5) Các giải thuật dựa trên cạnh.
2.2 Nhận dạng
Có hai kỹ thuật nhận dạng chính trong thuật toán nhận dạng là nhận dạng đối
tượng và nhận dạng kí tự:
– Nhận dạng đối tượng là rút trích hình ảnh đối tượng trong trong một tập đối
tượng xuất hiện trong hình ảnh. Nhận dạng đối tượng được áp dụng nhiều
trong các ngành khoa học tiên tiến như y khoa, sinh hóa hay khoa học hình
sự… Trong y khoa, thuật toán nhận dạng đối tượng giúp ích cho việc xác
định các đối tượng lạ (vật thể lạ, khối u bứu…) trong hình ảnh chụp từ bên
trong cơ thể. Việc xác định các đối tượng lạ này thông qua việc so sánh đối
tượng của hai bức ảnh tương đương, dựa vào đó mà các chuyên viên y khoa
sẽ biết được những vấn đề về sức khoẻ của bệnh nhân. Trong kỹ thuật sinh
hoá, thuật toán nhận diện đối tượng giúp cho việc phát hiện các biến thể mới
hình thành… Trong khoa học hình sự, việc nhận dạng đối tượng là nguồn hổ
trợ chính trong phân tích và nhận dạng các đối tượng hình sự.
– Nhận dạng kí tự là phương pháp rút trích các chuổi kí tự (có thể là một kí tự)
trong một chuổi kí tự đưa vào với mục đích nhận dạng (phỏng đoán) nội
Học viên: Bùi Anh Kiệt – CH1101018 10
Khai phá dữ liệu & kho dữ liệu Thuật toán K-Means & ứng dụng thực tế
dung của văn bản. Nhận dạng kí tự được áp dụng trong các thuật toán như
lọc email, phân loại văn bản hay tóm lược nội dung các văn bản đầu vào.
Hiện nay thuật toán này cũng được áp dụng nhiều trong các phần mềm dùng
để ngăn chặn việc truy xuất đến một số trang có nội dung không lành mạnh
hay một số trang có làm mất thong tin người dùng (các trang được cài đặt
vi-rút để trích dữ liệu người dùng).
Ứng dụng của thuật toán gom cụm trong nhận dạng đối tượng:
– Các điểm ảnh được gom thành những đối tượng khác nhau thông qua màu
sắc, ngữ cảnh.
– Gom các hình ảnh giống nhau qua một chuổi ảnh (các ảnh tĩnh) và các hình
ảnh thay đổi qua một chuổi ảnh (ảnh động) để xác định hành vị của đối
tượng.
Ứng dụng thuật toán gom cụm trong nhận dạng kí tự:
– Gom các kí tự giống nhau thành từng cụm.
– Gom các cụm thành các phần khác nhau và dựa vào đặc điểm của từng cụm
mà xét độ ưu tiên để đánh giá nội dụng văn bản.
– Việc nhận dạng kí tự còn được phát triển và áp dụng trong nhận dạng chữ
viết. Các thông tin nhận dạng trong văn bản chữ viết bao gồm điểm đặt bút,
nét các kí tự, độ dài rộng các kí tự, các nét lên, xuống của từng kí tự.
2.3 Khai phá dữ liệu
Thuật toán gom cụm được ứng dụng khá hiệu quả và phổ biến trong việc khai phá
dữ liệu.
Hiện nay, bên cạnh nguồn dữ liệu có được từ việc thu thập thực tế thông qua khảo
sát thị trường thì nguồn dữ liệu từ internet đã và đang đóng vai trò cốt yếu trong
việc khai thác thị trường. Nguồn dữ liệu từ internet được xem là một trong những
nguồn dữ liệu chính và là nguồn dữ liệu vô tận mà rất nhiều tổ chức (có thể là cá
nhân) quan tâm và muốn khai thác. Ví dụ như: thông tin khách hàng, ý kiến khách
Học viên: Bùi Anh Kiệt – CH1101018 11
Khai phá dữ liệu & kho dữ liệu Thuật toán K-Means & ứng dụng thực tế
hàng về sản phẩm hay quan điểm khách hàng về những mặc hàng xuất hiện trong
tương lai.
Với sự phát triển mạnh mẽ của công nghệ thông tin hiện nay, internet đã và đang
trở thành cở sở dữ liệu vô tận. Nguồn dữ liệu này có ý nghĩa với rất nhiều tổ chức
và cá nhân đặc biệt là các tổ chức và cá nhân trong lĩnh vực kinh doanh. Do đó,
việc khai thác nguồn dữ liệu vô tận được lưu trữ trên internet đã và đang trở thành
một hướng đi mới trong việc khai thác thị trường. Một khi thành công trong việc
khai thác dữ liệu khách hàng từ internet, vấn đề tìm hiểu và khai thác thị trường sẽ
trở nên đơn giản và hiệu quả cao. Hiệu quả về chi phí là điểm nổi bật có thể nhìn
thấy được, bên cạnh đó hiệu quả về thời gian cũng là một điểm đáng ghi nhận.
Mọi thông tin khách hàng đã có sẵn, tuy nhiên làm thế nào để phân loại và đánh
giá nó chính xác đòi hỏi người làm công việc khai thác thị trường phải bỏ công
sức đầu tư để có một thuật toán phân tích và tổng hợp thật hiệu quả. Và với công
việc này, thuật toán gom cụm được sử dụng như phương pháp chính để khai hoàn
thành mục đích đặt ra.
Học viên: Bùi Anh Kiệt – CH1101018 12
Khai phá dữ liệu & kho dữ liệu Thuật toán K-Means & ứng dụng thực tế
3 Cài đặt thuật toán K-Means
3.1 Ý tưởng thuật toán K-Means
Thuật toán K-Means được hình thành bởi MacQueen từ 1967, là một trong những
thuật toán đơn giản nhất dùng để giải quyết vấn đề gom cụm. Quá trình xử lí dựa
trên số cụm của đối tượng được cho trước. Ý tưởng chính của thuật toán là dựa
vào số cụm cho trước, hình thành tương ứng số vector trọng tâm cho mỗi cụm. và
từ vector trọng tâm đó, các cụm được hình thành bằng cách gom các điểm xung
quanh gần nó nhất. Một đối tượng được xác định là thuộc một cụm nào đó khi và
chỉ khi khoảng cách Euclid từ đối tượng đó đến vector trọng tâm là nhỏ nhất so
với các vector trọng tâm còn lại. Việc xác định vector trọng tâm được thực hiện
nhiều lần để tìm ra những cụm tốt nhất. Vậy nên giá trị của vector trọng tâm trong
mỗi lần tính có thể khác nhau. Khi giá trị của vector trọng tâm là không đổi, lúc đó
các cụm của đồ thị đã ổn định và ta có thể dừng thuật toán.
3.2 Cài đặt thuật toán
3.2.1 Tiên đề
Thuật toán K-Means được hình thành dựa trên số cụm và một ma trận phân hoạch
cho trước để làm cơ sở cho quá trình tính toán.
Nếu số lượng cụm quyết có vai trò quyết định trong việc xây dựng thuật toán thì
ma trận phân hoạch có ý nghĩa trong việc xác định độ phức tạp của thuật toán. Với
một ma trận phân hoạch tốt, quá trình tính toán sẽ giảm đi rất nhiều.
3.2.2 Nội dung thuật toán
Dữ liệu đầu vào:
Số cụm k và các ma trận phân hoạch khởi đầu.
Dữ liệu đầu ra:
Các cụm dữ liệu thể hiện thông qua ma trận phân hoạch cuối cùng.
Học viên: Bùi Anh Kiệt – CH1101018 13
Khai phá dữ liệu & kho dữ liệu Thuật toán K-Means & ứng dụng thực tế
Bước 1:
(1) Chọn số cụm (số điểm trọng tâm trên đồ thị) ban đầu.
(2) Khởi tạo ma trận phân hoạch ngẫu nhiên đầu tiên
Bước 2:
(1) Tìm các điểm trọng tâm của đồ thị thông qua ma trận phân hoạch.
(2) Tính khoảng cách từ các điểm đến các điểm trọng tâm.
(3) Gán điểm đang xét vào cụm mà khoảng cách từ điểm đang xét đến điểm
trọng tâm của cụm là nhỏ nhất.
(4)
Bước 3:
(1) Gán điểm đang xét vào cụm mà khoảng cách từ điểm đang xét đó đến
vector trọng tâm của cụm là nhỏ nhất (cập nhật ma trận phân hoạch ở vị
trí cột là điểm đang xét).
(2) Thực hiện bước trên cho đối tượng tiếp theo.
Bước 4:
(1) Xét xem ma giá trị của ma trận phân hoạch có ổn định hay không. Nếu đã
ổn định (đạt điều kiện dừng) thì ngừng chương trình.
(2) Quay lại bước 2.
3.3 Hướng phát triển của thuật toán
Thuật toán K-Means là khởi nguồn của hệ thống các thuật toán gom cụm, vậy nên
song song với những điểm mạnh vẫn còn tồn tại nhiều hạn chế. Cũng vì lẽ đó nên
đã có rất nhiều thuật toán kế thừa K-Means và cải thiện những yếu điểm mà K-
Means mắc phải. Kết quả của quá trình cải thiện K-Means là đáng ghi nhận khi có
rất nhiều thuật toán ra đời như K-Medoid, Fuzzy C-Means hay PAM, CLARAR…
Tuy nhiên, đến thời điểm hiện tại vẫn chưa có thuật toán nào có thể đạt được hiệu
quả tuyệt đối.
Học viên: Bùi Anh Kiệt – CH1101018 14
Khai phá dữ liệu & kho dữ liệu Thuật toán K-Means & ứng dụng thực tế
Vì lẽ đó nên để hệ thống thuật toán gom cụm đạt hiệu quả cao chúng ta cần phải
hạn chế yếu điểm của thuật toán càng nhiều càng tốt (vì không thể loại bỏ những
yếu điểm tồn tại trong thuật toán).
Phương pháp dễ nhận thấy nhất trong thuật toán K-Means chính là việc hình thành
ma trận phân hoạch đầu tiên như thế nào để các cụm hình thành sau quá trình này
là tương đối ổn định. Vậy nên trong quá trình cải tiến K-Means, có rất nhiều học
giả đã chọn phương pháp này. Tuy nhiên, làm cách nào để có thể đạt được hiệu
quả tối ưu của quá trình hình thành ma trận phân hoạch ban đầu là việc làm vô
cùng phức tạp.
Bên cạnh vai trò quyết định của ma trận phân hoạch khởi đầu, một điểm cần chú ý
trong việc cải thiện tốc độ thuật toán là tinh lọc quá trình tính toán để xác định
vector trọng tâm và khoảng cách Euclid từ các đối tượng đến vector trọng tâm.
Các cách tính hiện nay có thể thay thế bằng những phương pháp tính mới đơn giản
hơn, hiệu quả hơn nhưng vẫn giữ được độ chính xác cần được đầu tư nghiên cứu.
Mặc dù nó đóng vai trò không quyết định nhưng tác động của nó sẽ không nhỏ
nếu được cải thiện hiệu quả.
Ngoài ra chúng ta còn có thể cải thiện thuật toán gom cụm K-Means đối với
những đồ thị có số đối tượng và số cụm lớn bằng cách gom các đối tượng thành
những cụm lớn hơn. Ví dụ như thay vì thuật toán phải cài đặt để tính toán cho k
cụm với n đối tượng (k và n rất lớn), chúng ta có thể gom cụm cho k/2, k/4 cụm và
n đối tượng. Vì số cụm nhỏ hơn nên số lần lặp sẽ giảm đáng kể. Và khi đã xác
định các cụm lớn, chúng ta có thể phân chia các cụm lớn thành các cụm nhỏ hơn.
Với cách tính này, chúng ta có thể tăng tốc được rất nhiều cho quá trình tính toán.
Học viên: Bùi Anh Kiệt – CH1101018 15
Khai phá dữ liệu & kho dữ liệu Thuật toán K-Means & ứng dụng thực tế
4 Kết luận
K-Means là thuật toán gom cụm đầu tiên được phát hiện và phát triển. Dù vẫn còn
nhiều hạn chế về khả năng tìm ra kết quả cuối cùng chính xác nhất nhưng K-
Means vẫn là thuật toán gom cụm cơ bản nhất. Có rất nhiều thuật toán gom cụm
mới đã được tìm hiểu và thực sự đã khắc phục được rất nhiều nhược điểm của K-
Means nhưng vẫn không thể thay thế được vì độ phức tạp và cách tiếp cận đơn
giản mà K-Means đa sở hữu. Vậy nên có thể khẳng định, K-Means là một trong
nhưng cơ sở của các thuật toán gom cụm đang có hiện nay. Vì thế trong xu hướng
phát triển mới của các thuật toán gom cụm, thay vì tìm một thuật toán mới hiệu
quả, tập trung cải thiện những yếu điểm mà K-Means gặp phải để đạt được những
cải thiện về tốc độ và khả năng tìm ra lời giải tối ưu nhất đã và đang là ưu tiên. Và
trên thực tế, đã có rất nhiều thuật toán đã ra đời với mục đích cải thiện về tốc độ
và tìm ra lời giải tối ưu nhất. Tuy vẫn chưa đạt được mục đích cuối cùng nhưng có
thể khẳng định đó là hướng phát triển đúng của việc phát triển các thuật toán gom
cụm.
Với những ưu điểm về tốc độ xử lí, hiện nay K-Means đang được ứng dụng trong
rất nhiều lĩnh vực cuộc sống. Và hai mảng chính mà K-Means đóng vai trò chủ
đạo là phân đoạn ảnh và khai phá dữ liệu.
Tuy nhiên với những đặc điểm nổi trội trong việc gom cụm, K-Means sẽ còn được
ứng dụng nhiều hơn và đóng vai trò cốt yếu trong nhiều lĩnh vực khác của cuộc
sống.
Học viên: Bùi Anh Kiệt – CH1101018 16
Khai phá dữ liệu & kho dữ liệu Thuật toán K-Means & ứng dụng thực tế
Phụ lục
Giới thiệu về chương trình cài đặt cho thuật toán K-Means.
Hình 1. Giao diện chương trình cài đặt thuật toán K-Means
Chương trình demo cung cấp cho người sử dụng hai tuỳ chọn về hình thức đưa dữ
liệu ban đầu vào. Có thể lựa chọn thao tác bằng tay và chọn mở file đã có sẵn
(mặc định chương trình cung cấp là mở file có sẵn).
Nội dung của file có sẵn là số lượng cụm của đồ thị và vị trí của các đối tượng
trong đồ thị.
Học viên: Bùi Anh Kiệt – CH1101018 17
Khai phá dữ liệu & kho dữ liệu Thuật toán K-Means & ứng dụng thực tế
Hình 2. Nội dung file dữ liệu đầu vào
Học viên: Bùi Anh Kiệt – CH1101018 18
Khai phá dữ liệu & kho dữ liệu Thuật toán K-Means & ứng dụng thực tế
Hình 3. Giao diện người dùng cho việc chọn dữ liệu đầu vào có sẵn
Học viên: Bùi Anh Kiệt – CH1101018 19
Khai phá dữ liệu & kho dữ liệu Thuật toán K-Means & ứng dụng thực tế
Hình 3. Giao diện người dùng cho việc chọn thao tác dữ liệu đầu vào
Chương trình hổ trợ tại một thời điểm chỉ có một cách thức nhập liệu được cho
phép (hoặc chọn dữ liệu từ file sẵn có hoặc nhập giá trị mới).
Button “submit” dùng để đưa dữ liệu nhập vào khung “Object information”.
Học viên: Bùi Anh Kiệt – CH1101018 20
Khai phá dữ liệu & kho dữ liệu Thuật toán K-Means & ứng dụng thực tế
Hình 4. Submit dữ liệu hiển thị
Button “calculate” dùng để thực thi việc tính toán để tìm ra các cụm đối tượng trên
đồ thị.
Quá trình tính toán sẽ được ghi lại trong khung “Partition matrix” và kết quả cuối
cùng được thể hiện trên khung “Result (final partition matrix)”.
Học viên: Bùi Anh Kiệt – CH1101018 21
Khai phá dữ liệu & kho dữ liệu Thuật toán K-Means & ứng dụng thực tế
Hình 5. Quá trình tính toán và kết quả cuối cùng
Ngoài ra, người dùng có thể chọn lưu dữ liệu vừa thao tác bằng tay thông qua
button “save info” hay xoá tất cả nội dung vừa thao tác bằng button “clear all”.
Học viên: Bùi Anh Kiệt – CH1101018 22
Khai phá dữ liệu & kho dữ liệu Thuật toán K-Means & ứng dụng thực tế
Tài liệu tham khảo
1. Định nghĩa thuật toán K-Means từ wikipedia:
http://en.wikipedia.org/wiki/K-means_clustering
2. Giáo trình Khai thác dữ liệu – Trường ĐH Công nghệ thông tin – TS Đỗ Phúc.
3. Bài giảng về Khai phá dữ liệu và ứng dụng – PGS.TS Đỗ Phúc
Học viên: Bùi Anh Kiệt – CH1101018 23
Tuy còn hạn chế nhưng thuật toán K-Means là nền tảng, chỉ ra một hướng đi vềkhai phá tài liệu bằng cách gom cụm và đạt được hiệu suất cao cao. Không những vậy, K-Means còn là khởi đầu cho nhiều thuật toán gom cụm sinh ra tiếp theo với mụcđích đạt được hiệu suất cao tối ưu nhất. Và trong tài liệu này, tôi xin được trình diễn về K-Means, về những ưu nhược điểmvà đề xuất kiến nghị ra những hướng khắc phục cho thuật toán này. Và để hoàn thành xong tài liệu này, ngoài nổ lực bản thân còn có sự trợ giúp rất lớn từPGS. tiến sỹ Đỗ Phúc, người đã truyền đạt ý tưởng sáng tạo và những yếu tố quan trọng vềthuật toán K-Means, về những nhận định hướng tăng trưởng mới của thuật toán. Học viên : Bùi Anh Kiệt – CH1101018 2K hai phá tài liệu và kho tài liệu Thuật toán K-Means và ứng dụng thực tếMục lụcLời mở màn 2M ục lục 31 Thuật toán K-Means 41.1 Tổng quan 41.2 Nội dung thuật toán 51.3 Đặc điểm của thuật toán 71.4 Các biến thể của thuật toán K-Means 82 Ứng dụng thuật toán K-Means trong thực tiễn 92.1 Phân đoạn ảnh 92.2 Nhận dạng 102.3 Khai phá tài liệu 113 Cài đặt thuật toán K-Means 133.1 Ý tưởng thuật toán K-Means 133.2 Cài đặt thuật toán 133.3 Hướng tăng trưởng của thuật toán 144 Kết luận 16P hụ lục 17T ài liệu tìm hiểu thêm 23H ọc viên : Bùi Anh Kiệt – CH1101018 3K hai phá tài liệu và kho tài liệu Thuật toán K-Means và ứng dụng thực tế1 Thuật toán K-Means1. 1 Tổng quanK-Means là thuật toán phân cụm tài liệu, dùng để tiếp cận phân hoạch. Sốlượng cụm trong phân hoạch là một số cố định và thắt chặt cho trước. Các cụm được hìnhthành dựa vào khoảng cách những điểm TT. Một điểm sẽ thuộc vào một cụmnếu như khoảng cách từ điểm đó đến điểm TT của cụm là nhỏ nhất trong sốcác khoảng cách từ điểm đó đến những điểm TT. Vì vậy, cần khởi tạo một tập những điểm TT khởi đầu để làm nền tảng. cho việc giám sát và phân lại cụm cho những điểm trong đồ thị. Quá trình xác địnhcụm cho một điểm được thực lặp đi lặp lại nhiều lần, sau mỗi lần giám sát, cácđiểm TT sẽ đổi khác vị trí và những cụm của đồ thị cũng đổi khác theo. Quátrình giám sát và xác lập cụm cho những điểm dừng lại khi thành phần những cụmtương đối không thay đổi ( những điểm thuộc vào những cụm không đổi khác ). Trong chiêu thức K-means, chọn một giá trị k và sau đó chọn ngẫu nhiênk TT của những đối tượng người dùng tài liệu. Tính toán khoảng cách giữa đối tượng người dùng dữliệu trung bình mỗi cùm để tìm kiếm thành phần nào là tựa như và thêm vào cụm đó. Từ khoảng cách này hoàn toàn có thể thống kê giám sát trung bình mới của cụm và lặp lại quá trìnhcho đến khi mỗi những đối tượng người dùng tài liệu là một bộ phận của những cụm k. Mục đích của thuật toán K-means là sinh k cụm tài liệu { C1, C2, …, Ck } từmột tập dữ liệu chứa n đối tượng người dùng trong khoảng trống d chiều Xi = { xi1, xi2, … xid }, i = 1 ÷ n, sao cho hàm tiêu chuẩn : đạt giá trị tối tiểu. Trong đó : mlà trọng tâm của cụm Ci, D là khoảng cách giữa hai đối tượng người dùng. Trọng tâm của cụm là một vector, trong đó giá trị của mỗi thành phần của nó là trungcộng của những thành phần tương ứng của những đối tượng người tiêu dùng vector tài liệu trong cụmHọc viên : Bùi Anh Kiệt – CH1101018 4K hai phá tài liệu và kho tài liệu Thuật toán K-Means và ứng dụng thực tếđang xét. Tham số nguồn vào của thuật toán là số cụm k, và tham số đầu ra của thuậttoán là những trọng tâm của những cụm tài liệu. Độ đo khoảng cách D giữa những đốitượng dữ liệu thường được sử dụng là khoảng cách Euclide vì đây là mô hìnhkhoảng cách nên dễ lấy đạo hàm và xác lập những cực trị tối thiểu. Hàm tiêu chuẩnvà độ đo khoảng cách hoàn toàn có thể được xác lập đơn cử hơn tùy ý vào ứng dụng hoặcquan điểm của người dùng. 1.2 Nội dung thuật toánCho k là số cụm sau khi phân hoạch. ( 1 < = k < = n, với n là số điểm đốitượng trong khoảng trống tài liệu. Thuật toán K-Means gồm 4 bước : 1. Chọn k điểm làm trọng tâm khởi đầu của k cụm. 2. Gán ( hoặc gán lại ) từng điểm vào cụm có trọng tâm gần điểm đang xétnhất. Nếu không có phép gán lại nào thì dừng, vì không có phép gán lại nào cónghĩa là những cụm đã không thay đổi và thuật toán không hề cải tổ làm giảm độphân biệt được nữa. 3. Tính lại trọng tâm cho từng cụm. 4. Quay lại bước 2. Một số khái niệm được dùng trong thuật toán K-Means : ( 1 ) Ma trận phân hoạch : Ma trận phân hoạch là ma trận bộc lộ cho sự phụthuộc của một điểm vào một cụm nào đó. Table 1.1 – Ví dụ về ma trận phân hoạch1 1 0 0 00 0 1 0 10 0 0 1 0H ọc viên : Bùi Anh Kiệt – CH1101018 5K hai phá tài liệu và kho tài liệu Thuật toán K-Means và ứng dụng thực tếTrong ma trận phân hoạch trên, ta thấy ứng với mỗi cột chỉ có một dòng cógiá trị 1 điều đó biểu lộ mỗi đối tượng người tiêu dùng trong một thời gian chỉ thuộc vềmột cụm. Sau mỗi lượt gán cụm cho những đối tượng người dùng, ma trận phân hoạch lại được cậpnhật. Trong suốt quy trình update, một đối tượng người dùng vẫn chỉ thuộc một cụmduy nhất. ( 2 ) Vector trọng tâmVector trọng tâm chính là vị trí của điểm TT của mỗi cụm. Vectortrọng tâm trong từng thời gian là không giống nhau và nó phụ thuộc vào vào sốlượng những điểm nằm trong cụm đó. Các tính vector trọng tâm được bộc lộ như sau : với : vàTrong đó, mijlà giá trị tương ứng của hang i, cột j trong ma trận phân hoạch ( mij = 0/1 ). xixlà giá trị hoành độ của đối tượng người dùng thứ i, xiylà giá trị tung độcủa đối tượng người tiêu dùng thứ i. ( 3 ) Khoảng cách EuclidLà khoảng cách từ một đối tượng người tiêu dùng bất kể đến một vector trọng tâm nào đó. Việc xác lập khoảng cách Euclid có ý nghĩa trong việc xác lập đối tượngđang xét thuộc cụm nào. Một đối tượng người tiêu dùng thuộc một cụm khi khoảng chừng cáchEuclid từ điểm đó đến vector trọng tâm của cụm đó là nhỏ nhất. Khoảngcách Euclid từ một điểm đến một vector trọng tâm được xác lập như sau : Học viên : Bùi Anh Kiệt – CH1101018 6K hai phá tài liệu và kho tài liệu Thuật toán K-Means và ứng dụng thực tế1. 3 Đặc điểm của thuật toánChất lượng của thuật toán K – Means nhờ vào nhiều vào những tham số đầu vàonhư : số cụm k, và k vector trọng tâm khởi tạo bắt đầu. Trong trường hợp cácvector trọng tâm khởi tạo bắt đầu mà quá lệch so với những trọng tâm cụm tự nhiênthì tác dụng phân cụm của K – Means là rất thấp, nghĩa là những cụm tài liệu đượckhám phá rất lệch so với những cụm trong trong thực tiễn. Trên thực tiễn, chưa có một giảipháp nào để chọn tham số nguồn vào, giải pháp thường được sử dụng nhất là thửnghiệm với những giá trị nguồn vào, giải pháp thường được sử dụng nhất là thử nghiệmvới giá trị đầu vào k khác nhau rồi sau đó chọn giải pháp tốt nhất. 1. Ưu điểm : - Tương đối nhanh, độ phức tạp của thuật toán là O ( tkn ) trong đó : n : là số điểm trong khoảng trống dữ liệut : số lần lặp ( thường thì t rất nhỏ so với n ) k : số cụm cần phân hoạch - K-Means tương thích với những cụm có dạng hình cầu. - Có năng lực lan rộng ra và dể dàng sửa đổi với những tài liệu mới. - Bảo đảm quy tụ sau một số ít bước lặp hữu hạn. - Số cụm luôn không thay đổi ( k cụm cho trước ). - Luôn có tối thiểu một điểm trong cụm. - Các cụm được tách biệt rỏ rang không có hiện tượng kỳ lạ một đối tượng người tiêu dùng xuấthiện trong nhiều cụm tài liệu. 2. Nhược điểm : - Không bảo vệ đạt được tối ưu toàn cục và tác dụng đầu ra phụ thuộcvào nhiều vào việc chọn k điểm khởi đầu. - Cần xác lập trước số cụm. Học viên : Bùi Anh Kiệt – CH1101018 7K hai phá tài liệu và kho tài liệu Thuật toán K-Means và ứng dụng trong thực tiễn - Khó xác lập được thực sự số cụm có trong khoảng trống tài liệu. Do đócó thể phải thử với những số k khác nhau. - Khó phát hiện những loại cụm có hình dạng phức tạp và nhất là những dạngcụm không lồi. - Không thể xử lí nhiều mẫu riêng biệt ( nhiễu ). - Chỉ hoàn toàn có thể vận dụng khi tính được trọng tâm. 1.4 Các biến thể của thuật toán K-Means1. 4.1 Thuật toán K-MedoidThuật toán K-Medoid tương tự thuật toán K-Means, mỗi cụm được đại diện thay mặt bởimột trong số những đối tượng người dùng của cụm. Thông thường thì điểm gần vector trọng tâmsẽ được chọn làm điểm đại diện thay mặt của cụm. Thuật toán K-Medoid khắc phục được yếu điểm là loại được nhiễu trong thuậttoán K-Means. Nhưng bù lại, độ phức tạp của thuật toán lại rất lớn. 1.4.2 Thuật toán Fuzzy C-MeansThuật toán Fuzzy C-Means có kế hoạch phân cụm giống như K-Means. Nhưngcó một điểm độc lạ là K-Means phân cụm tài liệu cứng ( một đối tượng người dùng chỉthuộc vào một cụm ) còn Fuzzy C-Means là phân cụm tài liệu mềm ( một đối tượngcó thể thuộc nhiều cụm khác nhau ). Fuzzy C-Means có năng lực phân cụm trong khoảng trống đa chiều và có khả năngphân cụm tối ưu toàn cục. Tuy nhiên thuật toán này khá phức tạp và vận tốc hội tụphụ thuộc vào trạng thái bắt đầu của ma trận thành viên. Học viên : Bùi Anh Kiệt – CH1101018 8K hai phá tài liệu và kho tài liệu Thuật toán K-Means và ứng dụng thực tế2 Ứng dụng thuật toán K-Means trong thực tế2. 1 Phân đoạn ảnhPhân đoạn ảnh được xem như thể ứng dụng cơ bản của những thuật toán phân cụm. Định nghĩa : - Phân đoạn ảnh được hiểu là từ một ảnh nguồn vào, thong qua những thuật toánphân cụm mà tách thành những vùng miền khác nhau và những đối tượng người tiêu dùng đượctách ra đó được gọi là ảnh con. - Phân đoạn ảnh là một thao tác ở mức thấp trong hàng loạt quy trình giải quyết và xử lý ảnh. Quá trình này triển khai việc phân vùng ảnh thành những vùng rời rạc và đồngnhất với nhau hay nói cách khác là xác lập những biên của những vùng ảnh đó. Các vùng ảnh như nhau này thường thì sẽ tương ứng với hàng loạt haytừng phần của những đối tượng người tiêu dùng thật sự bên trong ảnh. Vì thế, trong hầu hết cácứng dụng của nghành giải quyết và xử lý ảnh phân đoạn ảnh luôn đóng một vai trò cơbản và thường là bước tiền giải quyết và xử lý tiên phong trong hàng loạt quy trình trước khithực hiện những thao tác khác ở mức cao hơn như nhận dạng đối tượng người tiêu dùng, biểudiễn đối tượng người tiêu dùng, nén ảnh dựa trên đối tượng người tiêu dùng, hay truy vấn ảnh dựa vào nộidung. Ứng dụng của phân cụm tài liệu : - Ứng dụng đặc thù của thuật toán phân cụm để chia ảnh thành những vùngkhông trùng lắp. Mỗi vùng gồm một nhóm px liên thông và đồng nhấttheo một tiêu chuẩn nào đó. Tiêu chí này nhờ vào vào tiềm năng của quá trìnhphân đoạn. Ví dụ như giống hệt về sắc tố, mức xám, cấu trúc, độ sâu củacác layer … - Mục tiêu của phân cụm là có được một chuỗi những cụm hyperellipsoidal bắtđầu với những TT cụm vị trí tại những vị trí tỷ lệ tối đa trong không gianmẫu, và những cụm tăng trưởng về những TT cho đến khi một thử nghiệm tốtđẹp của xcho tương thích đã bị vi phạm. Một loạt những tính năng được thảo luậnvà vận dụng cho cả hai màu xám và sắc tố hình ảnh. Học viên : Bùi Anh Kiệt – CH1101018 9K hai phá tài liệu và kho tài liệu Thuật toán K-Means và ứng dụng thực tiễn - Kỹ thuật Clustering cũng đã được sử dụng thành công xuất sắc được cho nhiều phânđoạn của hình ảnh. Trong những báo cáo giải trình khoa học về phân vùng ảnh mức xám, có khá nhiều kỹ thuật cố triển khai việc thoả mãn cùng lúc cả hai tiêu chuẩn vềtính giống hệt trong khoảng trống đặc trưng của ảnh và tính cô đọng về nộidung ảnh. Tuỳ theo những kỹ thuật mà những thuật giải này vận dụng, chúng đượcphân thành những nhóm sau : ( 1 ) Các thuật giải vận dụng kỹ thuật chia và trộn vùng. ( 2 ) Các thuật giải vận dụng kỹ thuật tăng trưởng vùng. ( 3 ) Các thuật giải vận dụng triết lý đồ thị. ( 4 ) Các giải thuật vận dụng mạng neural. ( 5 ) Các giải thuật dựa trên cạnh. 2.2 Nhận dạngCó hai kỹ thuật nhận dạng chính trong thuật toán nhận dạng là nhận dạng đốitượng và nhận dạng kí tự : - Nhận dạng đối tượng người dùng là rút trích hình ảnh đối tượng người dùng trong trong một tập đốitượng Open trong hình ảnh. Nhận dạng đối tượng người tiêu dùng được vận dụng nhiềutrong những ngành khoa học tiên tiến và phát triển như y khoa, sinh hóa hay khoa học hìnhsự … Trong y khoa, thuật toán nhận dạng đối tượng người tiêu dùng giúp ích cho việc xácđịnh những đối tượng người dùng lạ ( vật thể lạ, khối u bứu … ) trong hình ảnh chụp từ bêntrong khung hình. Việc xác lập những đối tượng người tiêu dùng lạ này trải qua việc so sánh đốitượng của hai bức ảnh tương tự, dựa vào đó mà những nhân viên y khoasẽ biết được những yếu tố về sức khoẻ của bệnh nhân. Trong kỹ thuật sinhhoá, thuật toán nhận diện đối tượng người tiêu dùng giúp cho việc phát hiện những biến thể mớihình thành … Trong khoa học hình sự, việc nhận dạng đối tượng người dùng là nguồn hổtrợ chính trong nghiên cứu và phân tích và nhận dạng những đối tượng hình sự. - Nhận dạng kí tự là chiêu thức rút trích những chuổi kí tự ( hoàn toàn có thể là một kí tự ) trong một chuổi kí tự đưa vào với mục tiêu nhận dạng ( phỏng đoán ) nộiHọc viên : Bùi Anh Kiệt – CH1101018 10K hai phá tài liệu và kho tài liệu Thuật toán K-Means và ứng dụng thực tếdung của văn bản. Nhận dạng kí tự được vận dụng trong những thuật toán nhưlọc email, phân loại văn bản hay tóm lược nội dung những văn bản nguồn vào. Hiện nay thuật toán này cũng được vận dụng nhiều trong những ứng dụng dùngđể ngăn ngừa việc truy xuất đến 1 số ít trang có nội dung không lành mạnhhay 1 số ít trang có làm mất thong tin người dùng ( những trang được cài đặtvi-rút để trích tài liệu người dùng ). Ứng dụng của thuật toán gom cụm trong nhận dạng đối tượng người tiêu dùng : - Các điểm ảnh được gom thành những đối tượng người dùng khác nhau trải qua màusắc, ngữ cảnh. - Gom những hình ảnh giống nhau qua một chuổi ảnh ( những ảnh tĩnh ) và những hìnhảnh biến hóa qua một chuổi ảnh ( ảnh động ) để xác lập hành vị của đốitượng. Ứng dụng thuật toán gom cụm trong nhận dạng kí tự : - Gom những kí tự giống nhau thành từng cụm. - Gom những cụm thành những phần khác nhau và dựa vào đặc thù của từng cụmmà xét độ ưu tiên để nhìn nhận nội dụng văn bản. - Việc nhận dạng kí tự còn được tăng trưởng và vận dụng trong nhận dạng chữviết. Các thông tin nhận dạng trong văn bản chữ viết gồm có điểm đặt bút, nét những kí tự, độ dài rộng những kí tự, những nét lên, xuống của từng kí tự. 2.3 Khai phá dữ liệuThuật toán gom cụm được ứng dụng khá hiệu suất cao và phổ cập trong việc khai phádữ liệu. Hiện nay, bên cạnh nguồn tài liệu có được từ việc tích lũy thực tiễn trải qua khảosát thị trường thì nguồn tài liệu từ internet đã và đang đóng vai trò cốt yếu trongviệc khai thác thị trường. Nguồn tài liệu từ internet được xem là một trong nhữngnguồn dữ liệu chính và là nguồn tài liệu vô tận mà rất nhiều tổ chức triển khai ( hoàn toàn có thể là cánhân ) chăm sóc và muốn khai thác. Ví dụ như : thông tin người mua, quan điểm kháchHọc viên : Bùi Anh Kiệt – CH1101018 11K hai phá tài liệu và kho tài liệu Thuật toán K-Means và ứng dụng thực tếhàng về mẫu sản phẩm hay quan điểm người mua về những mặc hàng Open trongtương lai. Với sự tăng trưởng can đảm và mạnh mẽ của công nghệ thông tin lúc bấy giờ, internet đã và đangtrở thành cở sở dữ liệu vô tận. Nguồn tài liệu này có ý nghĩa với rất nhiều tổ chứcvà cá thể đặc biệt quan trọng là những tổ chức triển khai và cá thể trong nghành kinh doanh thương mại. Do đó, việc khai thác nguồn tài liệu vô tận được tàng trữ trên internet đã và đang trở thànhmột hướng đi mới trong việc khai thác thị trường. Một khi thành công xuất sắc trong việckhai thác dữ liệu người mua từ internet, yếu tố khám phá và khai thác thị trường sẽtrở nên đơn thuần và hiệu suất cao cao. Hiệu quả về ngân sách là điểm điển hình nổi bật hoàn toàn có thể nhìnthấy được, cạnh bên đó hiệu suất cao về thời hạn cũng là một điểm đáng ghi nhận. Mọi thông tin người mua đã có sẵn, tuy nhiên làm thế nào để phân loại và đánhgiá nó đúng chuẩn yên cầu người làm việc làm khai thác thị trường phải bỏ côngsức góp vốn đầu tư để có một thuật toán nghiên cứu và phân tích và tổng hợp thật hiệu suất cao. Và với côngviệc này, thuật toán gom cụm được sử dụng như phương pháp chính để khai hoànthành mục tiêu đặt ra. Học viên : Bùi Anh Kiệt – CH1101018 12K hai phá tài liệu và kho tài liệu Thuật toán K-Means và ứng dụng thực tế3 Cài đặt thuật toán K-Means3. 1 Ý tưởng thuật toán K-MeansThuật toán K-Means được hình thành bởi MacQueen từ 1967, là một trong nhữngthuật toán đơn thuần nhất dùng để xử lý yếu tố gom cụm. Quá trình xử lí dựatrên số cụm của đối tượng người dùng được cho trước. Ý tưởng chính của thuật toán là dựavào số cụm cho trước, hình thành tương ứng số vector trọng tâm cho mỗi cụm. vàtừ vector trọng tâm đó, những cụm được hình thành bằng cách gom những điểm xungquanh gần nó nhất. Một đối tượng người dùng được xác lập là thuộc một cụm nào đó khi vàchỉ khi khoảng cách Euclid từ đối tượng người dùng đó đến vector trọng tâm là nhỏ nhất sovới những vector trọng tâm còn lại. Việc xác lập vector trọng tâm được thực hiệnnhiều lần để tìm ra những cụm tốt nhất. Vậy nên giá trị của vector trọng tâm trongmỗi lần tính hoàn toàn có thể khác nhau. Khi giá trị của vector trọng tâm là không đổi, lúc đócác cụm của đồ thị đã không thay đổi và ta hoàn toàn có thể dừng thuật toán. 3.2 Cài đặt thuật toán3. 2.1 Tiên đềThuật toán K-Means được hình thành dựa trên số cụm và một ma trận phân hoạchcho trước để làm cơ sở cho quy trình đo lường và thống kê. Nếu số lượng cụm quyết có vai trò quyết định hành động trong việc kiến thiết xây dựng thuật toán thìma trận phân hoạch có ý nghĩa trong việc xác lập độ phức tạp của thuật toán. Vớimột ma trận phân hoạch tốt, quy trình giám sát sẽ giảm đi rất nhiều. 3.2.2 Nội dung thuật toánDữ liệu nguồn vào : Số cụm k và những ma trận phân hoạch khởi đầu. Dữ liệu đầu ra : Các cụm tài liệu bộc lộ trải qua ma trận phân hoạch ở đầu cuối. Học viên : Bùi Anh Kiệt – CH1101018 13K hai phá tài liệu và kho tài liệu Thuật toán K-Means và ứng dụng thực tếBước 1 : ( 1 ) Chọn số cụm ( số điểm trọng tâm trên đồ thị ) bắt đầu. ( 2 ) Khởi tạo ma trận phân hoạch ngẫu nhiên đầu tiênBước 2 : ( 1 ) Tìm những điểm trọng tâm của đồ thị trải qua ma trận phân hoạch. ( 2 ) Tính khoảng cách từ những điểm đến những điểm trọng tâm. ( 3 ) Gán điểm đang xét vào cụm mà khoảng cách từ điểm đang xét đến điểmtrọng tâm của cụm là nhỏ nhất. ( 4 ) Bước 3 : ( 1 ) Gán điểm đang xét vào cụm mà khoảng cách từ điểm đang xét đó đếnvector trọng tâm của cụm là nhỏ nhất ( update ma trận phân hoạch ở vịtrí cột là điểm đang xét ). ( 2 ) Thực hiện bước trên cho đối tượng người dùng tiếp theo. Bước 4 : ( 1 ) Xét xem ma giá trị của ma trận phân hoạch có không thay đổi hay không. Nếu đãổn định ( đạt điều kiện kèm theo dừng ) thì ngừng chương trình. ( 2 ) Quay lại bước 2.3.3 Hướng tăng trưởng của thuật toánThuật toán K-Means là khởi nguồn của mạng lưới hệ thống những thuật toán gom cụm, vậy nênsong tuy nhiên với những điểm mạnh vẫn còn sống sót nhiều hạn chế. Cũng vì lẽ đó nênđã có rất nhiều thuật toán thừa kế K-Means và cải tổ những yếu điểm mà K-Means mắc phải. Kết quả của quy trình cải tổ K-Means là đáng ghi nhận khi córất nhiều thuật toán sinh ra như K-Medoid, Fuzzy C-Means hay PAM, CLARAR … Tuy nhiên, đến thời gian hiện tại vẫn chưa có thuật toán nào hoàn toàn có thể đạt được hiệuquả tuyệt đối. Học viên : Bùi Anh Kiệt – CH1101018 14K hai phá tài liệu và kho tài liệu Thuật toán K-Means và ứng dụng thực tếVì lẽ đó nên để mạng lưới hệ thống thuật toán gom cụm đạt hiệu suất cao cao tất cả chúng ta cần phảihạn chế yếu điểm của thuật toán càng nhiều càng tốt ( vì không hề vô hiệu nhữngyếu điểm sống sót trong thuật toán ). Phương pháp dễ nhận thấy nhất trong thuật toán K-Means chính là việc hình thànhma trận phân hoạch tiên phong như thế nào để những cụm hình thành sau quy trình nàylà tương đối không thay đổi. Vậy nên trong quy trình nâng cấp cải tiến K-Means, có rất nhiều họcgiả đã chọn giải pháp này. Tuy nhiên, làm cách nào để hoàn toàn có thể đạt được hiệuquả tối ưu của quy trình hình thành ma trận phân hoạch bắt đầu là việc làm vôcùng phức tạp. Bên cạnh vai trò quyết định hành động của ma trận phân hoạch khởi đầu, một điểm cần chú ýtrong việc cải tổ vận tốc thuật toán là tinh lọc quy trình giám sát để xác địnhvector trọng tâm và khoảng cách Euclid từ những đối tượng người dùng đến vector trọng tâm. Các cách tính lúc bấy giờ hoàn toàn có thể sửa chữa thay thế bằng những giải pháp tính mới đơn giảnhơn, hiệu suất cao hơn nhưng vẫn giữ được độ đúng chuẩn cần được góp vốn đầu tư nghiên cứu và điều tra. Mặc dù nó đóng vai trò không quyết định hành động nhưng tác động ảnh hưởng của nó sẽ không nhỏnếu được cải tổ hiệu suất cao. Ngoài ra tất cả chúng ta còn hoàn toàn có thể cải thiện thuật toán gom cụm K-Means đối vớinhững đồ thị có số đối tượng người tiêu dùng và số cụm lớn bằng cách gom những đối tượng người tiêu dùng thànhnhững cụm lớn hơn. Ví dụ như thay vì thuật toán phải setup để thống kê giám sát cho kcụm với n đối tượng người dùng ( k và n rất lớn ), tất cả chúng ta hoàn toàn có thể gom cụm cho k / 2, k / 4 cụm vàn đối tượng người dùng. Vì số cụm nhỏ hơn nên số lần lặp sẽ giảm đáng kể. Và khi đã xácđịnh những cụm lớn, tất cả chúng ta hoàn toàn có thể phân loại những cụm lớn thành những cụm nhỏ hơn. Với cách tính này, tất cả chúng ta hoàn toàn có thể tăng cường được rất nhiều cho quy trình thống kê giám sát. Học viên : Bùi Anh Kiệt – CH1101018 15K hai phá tài liệu và kho tài liệu Thuật toán K-Means và ứng dụng thực tế4 Kết luậnK-Means là thuật toán gom cụm tiên phong được phát hiện và tăng trưởng. Dù vẫn cònnhiều hạn chế về năng lực tìm ra hiệu quả sau cuối đúng mực nhất nhưng K-Means vẫn là thuật toán gom cụm cơ bản nhất. Có rất nhiều thuật toán gom cụmmới đã được tìm hiểu và khám phá và thực sự đã khắc phục được rất nhiều điểm yếu kém của K-Means nhưng vẫn không hề thay thế sửa chữa được vì độ phức tạp và cách tiếp cận đơngiản mà K-Means đa chiếm hữu. Vậy nên hoàn toàn có thể chứng minh và khẳng định, K-Means là một trongnhưng cơ sở của những thuật toán gom cụm đang có lúc bấy giờ. Vì thế trong xu hướngphát triển mới của những thuật toán gom cụm, thay vì tìm một thuật toán mới hiệuquả, tập trung chuyên sâu cải tổ những yếu điểm mà K-Means gặp phải để đạt được nhữngcải thiện về vận tốc và năng lực tìm ra giải thuật tối ưu nhất đã và đang là ưu tiên. Vàtrên thực tiễn, đã có rất nhiều thuật toán đã sinh ra với mục tiêu cải tổ về tốc độvà tìm ra giải thuật tối ưu nhất. Tuy vẫn chưa đạt được mục tiêu sau cuối nhưng cóthể khẳng định chắc chắn đó là hướng tăng trưởng đúng của việc tăng trưởng những thuật toán gomcụm. Với những ưu điểm về vận tốc xử lí, lúc bấy giờ K-Means đang được ứng dụng trongrất nhiều nghành nghề dịch vụ đời sống. Và hai mảng chính mà K-Means đóng vai trò chủđạo là phân đoạn ảnh và tìm hiểu và khám phá tài liệu. Tuy nhiên với những đặc thù nổi trội trong việc gom cụm, K-Means sẽ còn đượcứng dụng nhiều hơn và đóng vai trò cốt yếu trong nhiều nghành khác của cuộcsống. Học viên : Bùi Anh Kiệt – CH1101018 16K hai phá tài liệu và kho tài liệu Thuật toán K-Means và ứng dụng thực tếPhụ lụcGiới thiệu về chương trình thiết lập cho thuật toán K-Means. Hình 1. Giao diện chương trình thiết lập thuật toán K-MeansChương trình demo cung ứng cho người sử dụng hai tuỳ chọn về hình thức đưa dữliệu khởi đầu vào. Có thể lựa chọn thao tác bằng tay và chọn mở file đã có sẵn ( mặc định chương trình cung ứng là mở file có sẵn ). Nội dung của file có sẵn là số lượng cụm của đồ thị và vị trí của những đối tượngtrong đồ thị. Học viên : Bùi Anh Kiệt – CH1101018 17K hai phá tài liệu và kho tài liệu Thuật toán K-Means và ứng dụng thực tếHình 2. Nội dung file tài liệu đầu vàoHọc viên : Bùi Anh Kiệt – CH1101018 18K hai phá tài liệu và kho tài liệu Thuật toán K-Means và ứng dụng thực tếHình 3. Giao diện người dùng cho việc chọn tài liệu nguồn vào có sẵnHọc viên : Bùi Anh Kiệt – CH1101018 19K hai phá tài liệu và kho tài liệu Thuật toán K-Means và ứng dụng thực tếHình 3. Giao diện người dùng cho việc chọn thao tác dữ liệu đầu vàoChương trình hổ trợ tại một thời gian chỉ có một phương pháp nhập liệu được chophép ( hoặc chọn tài liệu từ file sẵn có hoặc nhập giá trị mới ). Button “ submit ” dùng để đưa tài liệu nhập vào khung “ Object information ”. Học viên : Bùi Anh Kiệt – CH1101018 20K hai phá tài liệu và kho tài liệu Thuật toán K-Means và ứng dụng thực tếHình 4. Submit dữ liệu hiển thịButton “ calculate ” dùng để thực thi việc giám sát để tìm ra những cụm đối tượng người tiêu dùng trênđồ thị. Quá trình thống kê giám sát sẽ được ghi lại trong khung “ Partition matrix ” và hiệu quả cuốicùng được biểu lộ trên khung “ Result ( final partition matrix ) ”. Học viên : Bùi Anh Kiệt – CH1101018 21K hai phá tài liệu và kho tài liệu Thuật toán K-Means và ứng dụng thực tếHình 5. Quá trình đo lường và thống kê và hiệu quả cuối cùngNgoài ra, người dùng hoàn toàn có thể chọn lưu dữ liệu vừa thao tác bằng tay thông quabutton “ save info ” hay xoá toàn bộ nội dung vừa thao tác bằng button “ clear all ”. Học viên : Bùi Anh Kiệt – CH1101018 22K hai phá tài liệu và kho tài liệu Thuật toán K-Means và ứng dụng thực tếTài liệu tham khảo1. Định nghĩa thuật toán K-Means từ wikipedia : http://en.wikipedia.org/wiki/K-means_clustering2. Giáo trình Khai thác tài liệu – Trường ĐH Công nghệ thông tin – tiến sỹ Đỗ Phúc. 3. Bài giảng về Khai phá tài liệu và ứng dụng – PGS.TS Đỗ PhúcHọc viên : Bùi Anh Kiệt – CH1101018 23
