HỌC VIỆN CÔNG NGHỆ BƢU CHÍNH VIỄN THÔNG

NGUYỄN LÂM TÚ
NGHIÊN CỨU PHƢƠNG PHÁP CHO BÀI TOÁN PHÂN
CỤM VÀ XÂY DỰNG HỆ THỐNG THỬ NGHIỆM
Chuyên ngành: Khoa học máy tính
Mã số: 60.48.01
TÓM TẮT LUẬN VĂN THẠC SĨ
HÀ NỘI – 2013

Thông tin là một nguồn tri thức rồi rào và quan trọng đối với nhân loại,
lƣợng dữ liệu con ngƣời ta thu thập đƣợc ngày càng lớn. Với sự phát triển của công
nghệ điện toán và hệ thống lƣu trữ dữ liệu thì khối lƣợng tài nguyên số ngày càng
trở nên đồ sộ và phức tạp. Trong một xã hội hiện đại, thông tin đóng một vai trò
then chốt. Thông tin không những chỉ là một tri thức mà nó còn đóng những vai trò
khác nhƣ điều hƣớng quá trình sản xuất. Ảnh hƣởng đến hoạt động xã hội hay thị
trƣờng. Tác động đến thói quen ngƣời tiêu dùng.
Việc phân cụm dữ liệu, để phân loại và quản lý nguồn dữ liệu một cách có
hiệu quả là một trong những trọng tâm nghiên cứu trong khai phá dữ liệu và Khoa
học máy tính. Mà ứng dụng của nó đã đƣợc hiện thực hóa nhiều trong thực tế, kinh
doanh thông minh (BI-Bussiness Intellegent) là một ví dụ rõ nét nhất. Các công ty
và doanh nghiệp luôn muốn phát triển khả năng kinh doanh của họ, muốn phục vụ
khách hàng tốt, có thêm khách hàng và lợi nhuận nhiều hơn. Việc hoạch định chiến
lƣợc kinh doanh dựa trên những thông tin hiện tại của công ty là một nhu cầu tất
yếu. Từ đó xây dựng và phát triển các hệ thống BI trở nên rất cần thiết và dần gắn
liền với các hoạt động của công ty.
Phân cụm dữ liệu có khá nhiều phƣơng pháp. Mỗi phƣơng pháp đều có ƣu
điểm, nhƣợc điểm và khả năng ứng dụng riêng của mình. Trong nội dung luận văn
này, tác giả sẽ trình bày phƣơng pháp phân cụm phân cấp kết hợp với mạng nơ-ron
để giải quyết một vấn đề cụ thể trong hệ thống BI.
Luận văn đƣợc trình bày gồm 3 chƣơng với nội dung các chƣơng nhƣ sau:
Chƣơng 1: Giới thiệu về khai phá dữ liệu, các khái niệm cơ bản trong khai
phá dữ liệu. Đồng thời trong chƣơng này tác giả cũng đi sâu vào phân cụm dữ liệu
và một số phƣơng pháp trong lĩnh vực này.
Chƣơng 2: Trong chƣơng này luận văn tập trung vào việc tìm hiều kết hợp
thuật toán trong phân cụm, áp dụng chúng vào một vấn đề cụ thể trong BI. Hai thuật
toán đƣợc tìm hiểu sau trong chƣơng này là phân cụm phân cấp và thuật toán SOM.
2

Bài toán đƣợc đƣa ra để giải quyết là bài toán về phân loại khách hàng triển vọng và

4

- Bƣớc tích hợp (Integration): dữ liệu có thể đƣợc lấy từ nhiều nguồn khác
nhau, tại bƣớc này tất cả dứ liệu sẽ đƣợc kết hợp lại với nhau.
- Bƣớc lựa chọn dữ liệu (Data Selection): trong bƣớc này những dữ liệu đƣợc
coi là tốt nhất sẽ đƣợc lấy ra, chúng sẽ là dữ liệu đầu vào cho việc phân tích
dữ liệu.
- Bƣớc cuối cùng là bƣớc chuyển đổi (Transformation): trong bƣớc này dữ liệu
sẽ đƣợc chuyển đổi hoặc hợp nhất vào một định dạng phù hợp với việc khai
phá sau này. Một số kỹ thuật thƣờng đƣợc sử dụng ở bƣớc này là tổng quát
hóa (summary) hay kết hợp (aggregation) .
Giai đoạn khai phá dữ liệu là giai đoạn cơ bản và quan trọng nhất trong toàn bộ
quá trình. Sau giai đoạn tiền xử lý, lƣợng dữ liệu sẽ đƣợc đƣa vào cho giai đoạn
khai phá. Một số kỹ thuật đƣợc sử dụng trong giai đoạn này: khai phá luật kết hợp
(association rule mining), khai phá mẫu tuần tự (sequential pattern mining), học
giám sát (hay phân loại –classification) và học không giám sát (hay phân cụm -
clustering ). Tuy vào đặc trƣng của từng bài toán mà kỹ thuật thích hợp nhất sẽ
đƣợc sử dụng. Kết quả của giai đoạn này là đƣa ra, rút trích đƣợc các mẫu hay các
tri thức.
Giai đoạn cuối cùng là giai đoạn sau khi đã xử lý xong. Trong nhiều ứng dụng
không phải tất cả các mẫu có đƣợc từ giai đoạn khai phá đều hữu dụng. Bạn hay
tƣởng tƣợng rằng với một hệ thống lớn có sử dụng khai phá dữ liệu thì nó có thể có
tới hàng nghìn hay hàng triệu các luật hay các mẫu. Các luật hay các mẫu này có
đƣợc từ một giai đoạn xử lý phức tạp với lƣợng dữ liệu lớn. Chính vì thế không phải
các luật, mẫu đƣợc sinh ra nào cũng thật sự tốt. Hơn thế, một mẫu đƣợc coi là tốt
khi nó cần đảm bảo một số tính chất nhƣ: dễ hiểu và con ngƣời dễ tiếp cận, hoạt
động tốt với những dữ liệu mới, mang tính cách tân và hữu dụng,nó cũng cần phù
hợp với cá lý thuyết đƣợc đề ra. Đây chính là nhiệm vụ của bƣớc đánh giá
(Evaluation) trong giai đoạn hậu xử lý dữ liệu. Ngoai ra trong giai đoạn này còn có
bƣớc là trình bày lại tri thức (Knowledge Presentation). Bƣớc này sử dụng các kỹ


1.2.3. Phƣơng pháp dựa trên mật độ (Density-Based Methods)
Để tìm ra các cụm có hình dạng phức tạp và ở nhiều kiểu khác nhau, ngƣời ta
sử dụng phƣơng pháp phân cụm dựa trên mật độ [4, 20]. Phƣơng pháp nhằm phân
định các vùng có mật độ đối tƣợng dầy đặc thành các nhóm và tách biệt khỏi những
vùng có mật độ đối tƣợng ít.
1.2.4. Phƣơng pháp dựa trên lƣới (Grid-Based Methods)
Cách tiếp cận phân cụm dựa trên lƣới sử dụng một cấu trúc lƣới đa phân giải.
Lƣới cấu trúc này sẽ định lƣợng đối tƣợng trong không gian vào một lƣợng giới hạn
các ô của lƣới. Tiếp đó nó thực hiện tất cả các thao tác phân cụm trên cấu trúc.
Thuận lợi chính của tiếp cận này là thời gian xử lý nhanh chóng của nó độc lập với
số các đối tƣợng dữ liệu và chỉ tuỳ thuộc vào số lƣợng các ô trong mỗi chiều của
không gian [6, 7, 20].
1.3. Kết luận chƣơng
7

CHƢƠNG 2: PHƢƠNG PHÁP PHÂN CỤM PHÂN CẤP VÀ
PHƢƠNG PHÁP SOM
2.1. Phương pháp phân cụm phân cấp
Phương pháp phân cụm phân cấp là một phương pháp phân cụm, trong đó các
đối tượng dữ liệu được gom vào các cụm có cấu trúc dạng cây.
Trong phƣơng pháp này các đối tƣợng sẽ đƣợc phân rã theo dạng cấu trúc phân cấp
(có thứ bậc). Tuy theo cách thức phân rã mà ngƣời ta có thể sử dụng một trong hai
kỹ thuật của phƣơng pháp này đó là: Phân rã theo hƣớng từ trên xuống (tiếp cận
theo hƣớng phân chia) hoặc phân rã theo hƣớng từ dƣới lên (tiếp cận theo hƣớng
tích tụ) [12].
2.1.1. Những khái niệm chung trong phƣơng pháp Phân cụm phân cấp
Cách tiếp cận dƣới lên: Ban đầu, chúng ta xem mỗi đối tƣợng là 1 nhóm
(cụm) và nhóm 2 đối tƣợng gần nhất thành 1 cụm. Quá trình này lặp lại cho đến khi
tất cả các đối tƣợng đƣợc nhóm vào 1 cụm cuối cùng.

Lấy khoảng cách
2 đối tƣợng xa
nhau nhất
2
( log )NN

Ảnh hƣởng đến các dữ liệu
ngoại biên
Liên kết trung
bình nhóm
Lấy khoảng cách
trung bình giữa
các đối tƣợng
2
( log )NN

Là lựa chọn tốt cho nhiều
ứng dụng
Liên kết tâm
Lấy khoảng cách
2 tâm của cụm
2
( log )NN

Sự đảo ngƣợc có thể xảy ra
2.1.3. Ứng dụng của phƣơng pháp Phân cụm phân cấp
Phƣơng pháp phân cụm theo thứ bậc đƣợc sử dụng khá nhiều trong thực tế. Một
số kỹ thuật thƣờng thấy trong phƣơng pháp này đó là: [2. 20]
- BIRCH
- CURE

lớp kia. Điều đó có nghĩa là sẽ không xảy ra trƣờng hợp output của lớp này trở
ngƣợc lại làm input của lớp trƣớc đó.
Đối với mạng hồi quy, nó có chứa các liên kết hồi quy. Nghĩa là trong một số
trƣờng hợp dòng dữ liệu sẽ đảo ngƣợc, quay trở lại với lớp trƣớc đó. Điều này sẽ
làm tăng khả năng linh hoạt của mạng trong việc điều chỉnh chỉ số và các liên kết để
hàm chuyển đổi có thể đạt đến giá trị mong muốn.
Khi một mạng ANN đƣợc xây dựng và định dạng đƣợc cấu trúc cũng nhƣ
hình trạng, đó là lúc nó sẵn sàng cho quá trình học. Giá trị trọng số của các đơn vị
xử lý ban đầu sẽ đƣợc lựa trọn một cách ngẫu nhiên. Nhƣ thế quá trình học của
ANN bắt đầu. ANN có hai phƣơng pháp học đó là: học có giám sát (Supervised
10

Learning) và học không giám sát (Un-Supervised Learning). Học giám sát nghĩa là
các giá trị đầu vào và kết quả mong muốn đƣợc đƣa ra trƣớc. Điển hình cho kỹ
thuật này là mạng Nơ-ron lan truyền ngƣợc (Backpropagation). Học không giám sát
thì ta chỉ biết đƣợc giá trị đầu vào, còn giá trị mong muốn sẽ đƣợc thiết lập dần
trong quá trình học. Mạng Nơ-ron điển hình đƣợc huấn luyện theo kiểu học không
giám sát là mạng tự tổ chức SOM ( Self Organization Map). Không có kiểu học
giám sát theo mô hình mạng tự tổ chức.
Mạng Nơ-ron có 3 cách huấn luyện chính đó là huấn luyện theo khối, huấn luyện
ngẫu nhiên và huấn luyện trực tuyến
2.2.2. Nội dung và đặc điểm của phƣơng pháp SOM
SOM ( Seft Organization Map) là một mạng Nơ-ron nhân tạo, được huấn
luyện bởi kỹ thuật không giám sát,trong đó số lượng Nơ-ron của SOM chính bằng
số lượng cụm của dữ liệu huấn luyện. Các Nơ-ron trong SOM được biểu diễn bởi
dãy, có thể là dãy một chiều hay dãy hai chiều. Cách biều diễn thường được sử
dụng đó là biểu diễn theo hai chiều, khi đó SOM được coi như một mạng tự tổ chức
hai chiều của các cụm. Dữ liệu đầu vào sẽ thuộc một cụm nhất định-tương ứng với
một Nơ-ron, cụm có số chiều chính bằng số chiều của Nơ-ron này. Như vậy SOM
có khả năng biểu diễn các dữ liệu đầu vào nhiều chiều trở thành ít chiều [19, 21].

h i j x

  

Bước 6: giảm chỉ số học

và và bán kính láng riềng


Bước 7: kiểm tra giá trị điều kiện dừng. kết thúc thuật toán nếu điều kiện
dừng là đúng.
2.2.3. Ứng dụng của SOM trong thực tế
Một số ứng dụng trong thực tế của SOM có thể kể ra:
- Kohonen (1984) hệ thống nhận biết âm
- Hệ thông nhận biết về ký tự
12

- Ứng dụng trong việc giải quyết bài toán ngƣời bán hàng.
- Tổ chức và lƣu trữ tài liệu (Document Organization and Retrieval
- SOM đƣợc sử dụng trong các ứng dụng về Gen và di truyền học.
2.3. Giới thiệu về BI và bài toán hỗ trợ kinh doanh
2.3.1. BI và chiến lƣợc khách hàng
BI ( Business Intelligence) là tập hợp lý thuyết, phương pháp, quy trình, kiến
trúc, và công nghệ với mục tiêu là chuyển hóa những dữ liệu thô thành những thông
tin có nghĩa và hữu ích cho việc kinh doanh [27].
Các thành phần của BI:

Hình 2.8. Các thành phần của hệ thống BI

Thông thƣờng khi một doanh nghiệp chọn BI là khi mà họ nghĩ đến một hệ

vụ nào phù hợp với nhóm khách hàng ấy.
Kết quả bài toán sẽ giúp cho doanh nghiệp biết đƣợc tính chất của từng nhóm khách
hàng, khoanh vùng đƣợc khách hàng. Đồng thời cũng thấy đƣợc cần phải chú trọng
vào mạng kinh doanh sản phẩm hay dịch vụ nào.
14

2.4. Kết hợp giữa phân cụm phân cấp và SOM để giải quyết bài toán hỗ trợ
kinh doanh.
2.4.1. Sự kết hợp của phân cụm phân cấp với SOM, thuật toán HSOM
SOM là một phƣơng pháp phân cụm đƣợc đánh giá là mạnh mẽ và linh hoạt.
Trong đó trọng tâm của thuật toán rơi vào việc xây dựng mạng lƣới các Nơ-ron
cùng với vector trọng số của mỗi Nơ-ron đó. Tính linh hoạt của phƣơng pháp gắn
liền với quá trình cập nhật các lân cận của mỗi Nơ-ron chiến thắng. Mỗi Nơ-ron có
thể đƣợc coi là một cụm. Nhƣ vậy, ta có thể thấy rằng việc xây dựng một mạng lƣới
các Nơ-ron ban đầu cùng với các đặc tính của mỗi Nơ-ron là một bƣớc quan trọng
của SOM. Việc sử dụng phƣơng pháp phân cụm phân cấp mà cụ thể là kỹ thuật tích
tụ (tích tụ algorithm) là một hƣớng để tích hợp giữa hai phƣơng pháp.
Quá trình xử lý của phƣơng pháp SOM có thể đƣợc minh họa bởi sơ đồ sau:

Hình 2.9. Kết hợp phân cụm phân cấp và SOM

Trong phạm vi luận văn này, việc kết hợp giữa hai phƣơng pháp SOM và
Hierachical Clustering để tạo ra các bƣớc trong việc phân cụm dữ liệu đƣợc gọi là
tắt là thuật toán HSOM.
Nội dung của thuật toán HSOM nhƣ sau:
Input: cho tập các vector đầu vào X ={x
1
, x
2
, …, x

- Đối với vector trọng số của mỗi Nơ-ron: Vector trọng số của mỗi Nơ-ron
đƣợc tính toán lại theo công thức trung bình sau:

12
w w w
w (2.13)
k
k
  


- Thực hiện việc ánh xạ đến mạng tự tổ chức SOM nhƣ sau:
+ Tìm 2 vị trí còn trống có khoảng cách đến đến nhau là nhỏ nhất
+ Tìm min(a
ij
), xác định đƣợc hai đối tƣợng e
i
, e
j,
đặt vào hai vị trí vừa
tìm đƣợc.

Gom nhóm hai đối tƣợng thành một nhóm
+Cập nhật lại ma trận khoảng cách M với số lƣợng đối tƣợng giảm đi một.
+ Kết thúc quá trình ánh xạ nếu nhƣ lƣới SOM đƣợc lấp đầy
- Xác định đƣợc bán kính láng giềng ban đầu của mạng tự tổ chức:
0

=
max(a

2
( , ) exp (2.16)
2
j inner
d
h i j






10
/ log( ) (2.17)T epoch



Bước 6: giảm chỉ số học

và bán kính
 
0
( ) exp (2.18)
count
n
epochs



0

những quyết định cho phù hợp với công ty.
2.4.3. Quá trình tìm kiếm BMU và cập nhật BMU vào HSOM Map
Nơ-ron có vector trọng số gần giống với giá trị huấn luyện đầu vào nhất đƣợc
gọi là BMU (Best matching unit). Hay có thể hiểu theo một cách khác, đây chính
là Nơ-ron có khoảng cách nhỏ nhất tới giá trị huấn luyện.
BMU đƣợc xác định ở bƣớc số 3 và 4 của thuật toán HSOM. Để có thể biết
đƣợc đâu là Nơ-ron giống với giá trị huấn luyện nhất, chúng ta sử dụng cách tính
khoảng cách bằng công thức Euclid:
2
1
( ) ( -w )
n
i ji
i
D j x


Sau đó ta xác định khoảng cách nhỏ nhất tƣơng ứng với Nơ-ron là BMU. BMU
đƣợc xác định sau mỗi vòng lặp chứ không phải là cố định trong suốt quá trình chạy
của thuật toán. BMU chỉ ra rằng, đâu là điểm trên mạng tự tổ chức giữ vai trò trung
tâm trong vòng lặp đó. Đồng thời, nó cũng chỉ ra đƣợc những điểm láng giềng nhờ
vào giá trị bán kính láng giềng.
Tiếp sau đó, BMU sẽ đƣợc dịch chuyển và cập nhật giá trị sao cho càng tiến
sát vector đâu vào hơn. Những giá trị láng giềng cũng theo đó mà đƣợc cập nhật và
gom lại gần nhau hơn. Việc cập nhật này thông qua việc thay đổi giá trị trọng số của
Nơ-ron cùng với vị trí của chúng trên mạng tự tổ chức. Việc cập nhật trọng số đƣợc
tính theo công thức sau:


3.2. Xây dựng kiến trúc ứng dụng
Hệ thống đƣợc xây dựng bao gồm 8 gói (package) nhƣ sơ đồ sau:

Hình 3.1. Các gói (package) trong hệ thống
3.3. Thực hiện ứng dụng
3.3.1. Biểu đồ lớp và biểu đồ tuần tự
Có 5 lớp chính đƣợc sử dụng trong ứng dụng, chúng sẽ đƣợc miêu tả theo sơ
đồ lớp nhƣ sau:

20

Hình 3.2. Sơ đồ các lớp cơ bản trong ứng dụng
Quá trình xử lý của ứng dụng có thể đƣợc mô hình hóa dƣới dạng sơ đồ tuần tự sau:

Hình 3.3. Biểu đồ tuần tự quá trình xử lý của ứng dụng

Quá trình tích hợp và xuất báo cáo đƣợc mô tả trong sơ đồ tuần tự sau: Hình

Hình 3.4. Biểu đồ tuần tự quá trình truy xuất báo cáo

21

Dữ liệu đầu vào cho ứng dụng
Dữ liệu đầu vào của ứng dụng có thể là dƣới dạng file hay trích xuất từ một
cơ sở dữ liệu. Ứng dụng có thể chấp nhận các dữ liệu dạng vector đƣợc lƣu xuống
file. File có phần đuôi mở rộng .som là file mặc định mà ứng dụng có thể đọc đƣợc.
Trong phần cài đặt của luận văn, tác giả sử dụng hệ quản trị DB2 để quản lý dữ liệu.
Cấu trúc của các bảng đƣợc sử dụng miêu tả bởi sơ đồ thực thể sau:
Hình 3.5. Mô hình thực thể kết hợp

trợ cho việc ra quyết định và hoạch định chiến lƣợc.
Giá trị
thực
Bộ biến đổi
Giá trị
trọng số

23 Hình 3.9. Hình ảnh về ứng dụng

Hình 3.20. Báo cáo về nhóm khách hàng và sản phẩm
Dƣới đây là một báo cáo khác nữa, nó cho thấy những mặt hàng(inventory Code)
nào đƣợc mua nhiều nhất, có tiềm năng để kinh doanh.
3.6. Kết luận chƣơng