i
LỜI CẢM ƠN
Để hoàn thành được luận văn này, trước hết tôi xin gửi lời cảm ơn sâu sắc nhất
tới GS.TS Vũ Đức Thi, Viện trưởng Viện công nghệ thông tin đã tận tình hướng
dẫn, chỉ bảo, định hướng, đóng góp những ý kiến quý báu trong suốt quá trình tôi
thực hiện luận văn.
Tôi xin chân thành cảm ơn các thầy, cô giáo trong Bộ môn Hệ thống thông tin,
Khoa Công nghệ thông tin, Phòng Đào tạo Sau đại học - Nghiên cứu Khoa học,
Trường Đại học Công nghệ - Đại học Quốc gia Hà Nội đã tạo mọi điều kiện tốt nhất
để tôi hoàn thành khóa học này. Đồng thời, tôi cũng xin cảm ơn gia đình, bạn bè,
những người luôn khuyến khích và giúp đỡ tôi trong mọi hoàn cảnh khó khăn. Tôi
xin cảm ơn cơ quan và các đồng nghiệp đã hết sức tạo điều kiện cho tôi trong suốt
quá trình học tập và làm luận văn này.

Hà Nội, ngày 10 tháng 04 năm 2011
Học viên
Nguyễn Thị Huế
ii
LỜI CAM ĐOAN
Tôi xin cam đoan những kiến thức trình bày trong luận văn này là do tôi tìm
hiểu, nghiên cứu và trình bày lại theo cách hiểu của tôi. Trong quá trình làm luận
văn tôi có tham khảo các tài liệu có liên quan và đã ghi rõ nguồn tài liệu tham khảo
đó. Phần lớn những kiến thức tôi trình bày trong luận văn này chưa được trình bày
hoàn chỉnh trong bất cứ tài liệu nào.
Hà Nội, ngày 10 tháng 04 năm 2011
Học viên
Nguyễn Thị Huế
iii
MỤC LỤC
MỞ ĐẦU 1
Chương 1 3

iv
DANH MỤC CÁC KÝ HIỆU, TỪ VIẾT TẮT
Từ hoặc cụm từ Từ viết tắt Từ tiếng Anh
Cơ sở dữ liệu CSDL DataBase
Khai phá tri thức trong cơ sở dữ liệu KDD Knowledge Discovery in
Databases
Khai phá dữ liệu KPDL Data Mining
Phân cụm dữ liệu PCDL Data Clustering
Khai phá tri thức KPTT Knowledge Discovery
v
DANH MỤC HÌNH VẼ
Hình 1.2: Quá trình khai phá tri thức 4
Hình 1.3: Qúa trình khai phá dữ liệu 7
Hình 2.1: Mô hình về phân cụm dựa trên tiêu chuẩn thu nhập và số nợ 15
Hình 2.2: Khoảng cách Euclidean 24
Hình 2.3: Bảng tham số 26
Hình 2.4: Ví dụ quá trình phân hoạch với k=3 29
Hình 2.6: Ví dụ về một số hình dạng cụm dữ liệu được khám phá bởi K-means 32
Hình 2.7: Các chiến lược phân cụm phân cấp 37
Hình 2.8: Ví dụ về kết quả phân cụm bằng thuật toán BIRCH 38
Hình 2.9. Khái quát thuật toán CURE 40
Hình 2.10. Các cụm dữ liệu được khám phá bởi CURE 41
Hình 2.11. Ví dụ thực hiện phân cụm bằng thuật toán CURE 43
Hình 2.12: Các bước thuật toán CHAMELEON 43
Hình 2.13: Hình dạng các cụm được khám phá bởi DBSCAN 45
Hình 2.14: Mật độ - đến được trực tiếp 46
Hình 2.15: Mật độ - đến được 46
Hình 2.16: Mật độ - liên thông 47
Hình 2.17: Cụm và nhiễu 47
Hình 2.18: Mô hình cấu trúc dữ liệu lưới 52

Phân cụm cơ sở dữ liệu là một trong những phương pháp quan trọng trong
quá trình tìm kiếm tri thức. Phân cụm là phương pháp học từ quan sát (learning
from obversation) hay còn gọi là học không thầy (unupervised learning or
automatic classfication) trong trí tuệ nhân tạo. Phân cụm đặc biệt hiệu quả khi ta
không biết về thông tin của các cụm, hoặc khi ta quan tâm tới những thuộc tính của
cụm mà chưa biết hoặc biết rất ít về những thông tin đó. Phân cụm được coi như
một công cụ độc lập để xem xét phân bố dữ liệu, làm bước tiền xử lý cho các thuật
toán khác. Việc phân cụm dữ liệu có rất nhiều ứng dụng như trong tiếp thị, sử dụng
đất, bảo hiểm, hoạch định thành phố … Hiện nay, phân cụm dữ liệu là một hướng
được nghiên cứu rất nhiều trong Tin học. Chính vì lý do đó mà em chọn đề tài
“Nghiên cứu các kỹ thuật phân cụm dữ liệu và Ứng dụng” là hướng nghiên cứu
chính cho luận văn của mình.
2
Nội dung chính của luận văn được trình bày trong 3 chương:
Chương 1: Tổng quan về khai phá tri thức và khai phá dữ liệu. Trong
chương này trình bày tổng quan về khai phá tri thức, khai phá dữ liệu; qui trình khai
phá tri thức, khai phá dữ liệu; …
Chương 2: Phân cụm và các kỹ thuật phân cụm. Trong chương này trình bày
tổng quan về phân cụm dữ liệu, một số phương pháp phân cụm dữ liệu dữ liệu phổ
biến như phân cụm phân hoạch, phân cụm phân cấp, phân cụm dựa trên mật độ,
phân cụm dựa trên lưới; trình bày một số giải thuật điển hình của mỗi phương pháp
phân cụm; …
Chương 3: Ứng dụng, triển khai bài toán với giải thuật DBSCAN
Phần kết luận trình bày tóm tắt về các nội dung thực hiện trong luận văn,
đồng thời đưa ra các vấn đề nghiên cứu tiếp cho tương lai. Phần phụ lục trình bày
một số modul chương trình cài đặt bằng thuật toán DBSCAN.
Do thời gian nghiên cứu và trình độ có hạn, luận văn không tránh khỏi những
hạn chế và thiếu sót. Em rất mong nhận được sự chỉ bảo, đóng góp ý kiến của các
thầy thầy/ cô giáo cũng như bạn bè và đồng nghiệp.
Em xin chân thành cảm ơn!

4
mô hình trong dữ liệu. Nói một cách khác, mục đích của phát hiện tri thức và khai
phá dữ liệu chính là tìm ra các mẫu và/hoặc các mô hình đang tồn tại trong các cơ
sở dữ liệu nhưng nhưng vẫn còn bị che khuất bởi hàng núi dữ liệu.
1.2.2. Quá trình khai phá tri thức
Việc khai phá tri thức thông thường có thể mô tả bằng sơ đồ các quy trình
sau [4]:
Hình 1.2: Quá trình khai phá tri thức
Trong đó, mỗi bước là một quy trình có vai trò riêng và nhiệm vụ khác nhau,
bao gồm:
Bước thứ nhất: tìm hiểu lĩnh vực ứng dụng và hình thành bài toán, bước này
sẽ quyết định cho việc rút ra được các tri thức hữu ích và cho phép chọn các phương
pháp khai phá dữ liệu thích hợp với mục đích ứng dụng và bản chất của dữ liệu.
Bước thứ hai: thu thập và xử lý dữ liệu thô, còn được gọi là tiền xử lý dữ liệu
nhằm loại bỏ nhiễu, xử lý việc thiếu dữ liệu, biến đổi dữ liệu và rút gọn dữ liệu nếu
cần thiết, bước này thường chiếm nhiều thời gian nhất trong toàn bộ quy trình khai
phá tri thức.
Bước thứ ba: khai phá dữ liệu, hay nói cách khác là trích ra các mẫu hoặc/và
các mô hình ẩn dưới các dữ liệu.
5
Bước thứ tư: hiểu tri thức đã tìm được, đặc biệt là làm sáng tỏ các mô tả và
dự đoán. Các bước trên có thể lặp đi lặp lại một số lần, kết quả thu được có thể
được lấy trung bình trên tất cả các lần thực hiện.
Bước thứ năm: sử dụng tri thức đã được khám phá vào thực tế, các tri thức
phát hiện được tích hợp chặt chẽ trong hệ thống. Tuy nhiên để sử dụng được các tri
thức đó đôi khi cần đến các chuyên gia trong các lĩnh vực quan tâm vì tri thức rút ra
có thể chỉ mang tính chất hỗ trợ quyết định hoặc cũng có thể được sử dụng cho một
quá trình khai phá tri thức khác.
Mặc dù được tóm tắt thành năm bước như trên, nhưng thực chất quá trình
xây dựng và thực hiện việc khám phá tri thức không chỉ phải tuân theo các bước cố

khai phá dữ liệu là quá trình tìm kiếm thông tin hữu ích, tiềm ẩn và mang tính dự
báo trong các cơ sở dữ liệu lớn. Việc khai phá dữ liệu nhằm các mục đích chính như sau:
- Khai thác những thông tin tiềm ẩn mang tính dự đoán từ những cơ sở dữ liệu
lớn dựa trên các công cụ khai phá dữ liệu nhằm dự đoán những xu hướng
trong tương lai nhằm giúp các đối tượng cần tri thức khai phá như: các tổ
chức, doanh nghiệp, nhà nghiên cứu, …. để hỗ trợ việc đưa ra những quyết
định kịp thời, được định hướng trên những tri thức được khám phá mang lại;
- Thực hiện phân tích xử lý, tính toán dữ liệu một cách tự động cho mỗi quá
trình xử lý dữ liệu để tìm ra tri thức.
1.3.3. Quá trình khai phá dữ liệu
KPDL là một giai đoạn quan trọng trong quá trình KPTT. Về bản chất, nó là
giai đoạn duy nhất tìm ra được thông tin mới, thông tin tiềm ẩn có trong CSDL chủ
yếu phục vụ cho mô tả và dự đoán. Dự đoán là thực hiện việc suy luận trên dữ liệu
để đưa ra các dự báo nhằm phân tích tập dữ liệu huấn luyện và tạo ra một mô hình
cho phép dự đoán các mẫu, mô hình mới chưa biết. Mô tả dữ là tổng kết hoặc diễn
tả những đặc điểm chung của những thuộc tính dữ liệu trong kho dữ liệu mà con
người có thể hiểu được.
Quá trình KPDL bao gồm các bước như trong hình sau:
7
Hình 1.3: Qúa trình khai phá dữ liệu
 Xác định nhiệm vụ: Xác định chính xác các vấn đề cần giải quyết.
 Xác định các dữ liệu liên quan: Dùng để xây dựng giải pháp.
 Thu thập và tiền xử lý dữ liệu: Thu thập các dữ liệu liên quan và tiền
xử lý chúng sao cho thuật toán KPDL có thể hiểu được. Đây là một
quá trình rất khó khăn, có thể gặp phải rất nhiều các vướng mắc như:
dữ liệu phải được sao ra nhiều bản (nếu được chiết xuất vào các tệp),
quản lý tập các dữ liệu, phải lặp đi lặp lại nhiều lần toàn bộ quá trình
(nếu mô hình dữ liệu thay đổi), v.v
 Thuật toán khai phá dữ liệu: Lựa chọn thuật toán KPDL và thực hiện
việc PKDL để tìm được các mẫu có ý nghĩa, các mẫu này được biểu

tiền xử lí cho các thuật toán khai phá dữ liệu khác.
1.3.4.3. Phân lớp dữ liệu và hồi qui
Mục tiêu của phương pháp phân lớp dữ liệu là dự đoán nhãn lớp cho các mẫu
dữ liệu. Quá trình phân lớp dữ liệu thường gồm 2 bước: xây dựng mô hình và sử
dụng mô hình:
- Bước 1: một mô hình sẽ được xây dựng dựa trên việc phân tích các mẫu dữ
liệu sẵn có. Mỗi mẫu tương ứng với một lớp, được quyết định bởi một thuộc
tính gọi là thuộc tính lớp. Các mẫu dữ liệu này còn được gọi là tập dữ liệu
huấn luyện (training data set). Các nhãn lớp của tập dữ liệu huấn luyện đều
phải được xác định trước khi xây dựng mô hình, vì vậy phương pháp này còn
9
được gọi là học có thầy (supervised learning) khác với phân cụm dữ liệu là
học không có thầy (unsupervised learning).
- Bước 2: sử dụng mô hình để phân lớp dữ liệu. Trước hết phải tính độ chính
xác của mô hình. Nếu độ chính xác là chấp nhận được, mô hình sẽ được sử
dụng để dự đoán nhãn lớp cho các mẫu dữ liệu khác trong tương lai. Phương
pháp hồi qui khác với phân lớp dữ liệu ở chỗ, hồi qui dùng để dự đoán về các
giá trị liên tục còn phân lớp dữ liệu thì chỉ dùng để dự đoán về các giá trị rời
rạc.
1.3.4.4. Luật kết hợp
Có rất nhiều kiểu luật có thể được phát hiện từ cơ sở dữ liệu nói chung. Ví dụ
như luật đặc trưng, luật biệt số, luật kết hợp, luật về sự lệch hướng và sự phát triển.
Phương pháp phát hiện luật kết hợp không gian cũng là một phương pháp
quan trọng trong khám phá tri thức. Phương pháp phát hiện luật kết hợp đưa ra
những luật về sự kết hợp giữa một hoặc nhiều thuộc tính đối với một hoặc nhiều
thuộc tính khác. Hướng tiếp cận này được ứng dụng nhiều trong lĩnh vực kinh
doanh, y học, tin sinh học, giáo dục, viễn thông, tài chính và thị trường chứng
khoán,
Khái niệm về luật kết hợp được phát biểu diễn như sau: một luật có dạng X
→Y (c%) với X và Y là tập các thuộc tính với độ tin cậy là c% được coi là luật kết

ánh sự xuất hiện của biến cố X sẽ dẫn đến việc xuất hiện biến cố Y. Hướng tiếp cận
này được ứng dụng nhiều trong lĩnh vực tài chính và thị trường chứng khoán bởi
chúng có tính dự báo cao.
1.3.4.6. Khai phá dữ liệu sử dụng mạng Neural
Mạng Neural là một phương pháp khai phá dữ liệu phát triển dựa trên cấu
trúc toán học với khả năng học trên mô hình hệ thần kinh con người.
Mạng Neural có thể đưa ra ý nghĩa các dữ liệu phức tạp hoặc không chính
xác và có thể được sử dụng để chiết suất các mẫu và phát hiện xu hướng quá phức
tạp mà con người cũng như các kỹ thuật máy tính khác không thể phát hiện được.
Một trong những ưu điểm của mạng Neural là khả năng tạo ra các mô hình
dự đoán do độ chính xác cao, có thể áp dụng cho nhiều các bài toán khác nhau, đáp
ứng được các nhiệm vụ đặt ra của khai phá dữ liệu như: phân lớp, phân nhóm, mô
hình hoá, dự báo…
11
Mẫu chiết suất bằng mạng Neural được thể hiện bằng một trong những nút
đầu của mạng. Mạng Neural sử dụng các hàm số chứ không sử dụng các hàm biểu
tượng để tính mức tích cực của các nút đầu ra và cập nhật các trọng số của nó.
Đặc điểm của mạng Neural là không cần gia công dữ liệu nhiều, trước khi
bắt đầu quá trình học như các kỹ thuật khác. Tuy nhiên, để có thể sử dụng mạng
Neural có hiệu quả cần phải xác định các yếu tố khi thiết kế mạng như:
- Mô hình mạng là gì?
- Mạng cần bao nhiêu nút?
- Số lớp ẩn sử dụng cho mạng là như thế nào?
- Khi nào thì việc học dừng?
Ngoài ra còn có nhiều bước quan trọng cần phải làm để tiền xử lý dữ liệu
trước khi đưa vào mạng Neural để mạng có thể hiểu được.
Mạng Neural được đóng gói với những thông tin trợ giúp của các chuyên gia
đáng tin cậy và được họ đảm bảo các mô hình này làm việt tốt. Sau khi học, mạng
có thể được coi là một chuyên gia trong lĩnh vực thông tin mà nó vừa được học.
1.3.4.7. Khai phá dữ liệu sử dụng thuật giải di truyền

Cây quyết định là một mô tả tri thức dạng đơn giản nhằm phân các đối tượng
dữ liệu thành một số lớp nhất định. Các nút của cây được gán nhãn là tên của các
thuộc tính, các cạnh được gán các giá trị có thể của các thuộc tính, các lá mô tả các
lớp khác nhau. Các đối tượng được phân lớp theo các đường đi trên cây, qua các
cạnh tương ứng với giá trị của thuộc tính của đối tượng tới lá.
Quá trình xây dựng cây quyết định là quá trình phát hiện ra các luật phân
chia dữ liệu đã cho thành các lớp đã được định nghĩa. Trong thực tế, tập các cây
quyết định có thể có đối với bài toán này rất lớn và rất khó có thể duyệt hết một
cách tường tận.
Có nhiều phương pháp xây dựng cây quyết định khi khai phá dữ liệu, đó là
các phương pháp sử dụng các thuật toán CLS, ID3, C4.5,… và một phương pháp
tương đối tiên tiến hiện nay và đang là tâm điểm được nghiên cứu là phương pháp
xây dựng cây quyết định dựa trên phụ thuộc hàm.
13
1.3.5. Thách thức – khó khăn trong khai phá tri thức và khai phá dữ liệu
KPTT và KPDL liên quan đến nhiều ngành, nhiều lĩnh vực trong thực tế, vì
vậy các thách thức và khó khăn ngày càng nhiều, càng lớn. Một số các thách thức
và khó khăn cần được quan tâm:
Các cơ sở dữ liệu lớn, các tập dữ liệu cần xử lý có kích thước rất lớn, trong
thực tế, kích thước của các tập dữ liệu thường ở mức tera-byte (hàng ngàn giga-
byte).
- Mức độ nhiễu cao hoặc dữ liệu bị thiếu
- Số chiều lớn
- Thay đổi dữ liệu và tri thức có thể làm cho các mẫu đã phát hiện không
còn phù hợp
- Quan hệ giữa các trường phức tạp
1.3.6. Ứng dụng của khai phá dữ liệu
Các kỹ thuật KDD có thể được áp dụng vào trong nhiều lĩnh vực, điển hình:
• Thông tin thương mại:
o Phân tích dữ liệu tiếp thị và bán hàng và thị trường;

Phân cụm là quá trình nhóm các điểm dữ liệu trong cơ sở dữ liệu thành các
cụm sao cho những điểm dữ liệu trong cùng một cụm có độ tương đồng lớn và
những điểm không cùng một cụm có sự tương đồng là rất nhỏ. Một cụm các đối
tượng dữ liệu có thể xem như là một nhóm trong nhiều ứng dụng, ví dụ: mô hình về
phân cụm các trường dựa trên tiêu chuẩn về thu nhập và số nợ. Cụm 1 là cụm
những người thu nhập cao, số nợ nhiều. Cụm 2 gồm những người thu nhập cao
nhưng nợ ít. Cụm 3 gồm những đối tượng thu nhập ít nhưng nợ nhiều.
Hình 2.1: Mô hình về phân cụm dựa trên tiêu chuẩn thu nhập và số nợ
Quá trình phân cụm là quá trình tìm ra các đối tượng trong cơ sở dữ liệu một
cách tự động. Không giống như phân lớp (clasification), phân cụm không cần
những thông tin được xác định trước. Nói cách khác, phân cụm là phương pháp học
từ quan sát (learning from obversation) hay còn gọi là học không thầy
(unsupervised learning or automatic classfication) trong trí tuệ nhân tạo. Phân cụm
đặc biệt hiệu quả khi không biết về thông tin các cụm, hoặc khi ta quan tâm tới các
thuộc tính của cụm mà chưa biết hoặc biết rất ít về các thông tin đó.
Đã có rất nhiều thuật toán cũng như hệ thống được phát triển cho bài toán
phân cụm trong cơ sở dữ liệu lớn. Sự phát triển của lĩnh vực này đã được áp dụng
16
vào nhiều lĩnh vực ứng dụng như xử lý ảnh, nhận dạng, đánh giá kinh doanh…Sự
đa dạng của thuật toán phân cụm là do sự khác nhau của những ứng dụng thực tế
cũng dẫn tới những yêu cầu về dữ liệu khác nhau và đòi hỏi những thuật toán phân
cụm khác nhau.
Một trong những câu hỏi lớn đặt ra trong bài toán phân cụm là đo độ tương
đồng không gian giữa các đối tượng dữ liệu (spatial similarity). Trong dữ liệu
không gian thì độ đo tương đồng được xem như sự quan hệ về vị trí không gian
giữa các đối tượng dữ liệu. Nói cách khác thì hai đối tượng dữ liệu được gọi là
tương đồng nếu “khoảng cách không gian” giữa chúng là nhỏ.
Một trong những phương pháp đo độ tương đồng giữa hai đối tượng là bằng
nghịch đảo của hàm không tương đồng (dissimilarity function). Hàm không tương
đồng, hàm dựa trên những thuộc tính không gian của các đối tượng dữ liệu như: toạ

tổng quát nào có thể giải quyết trọn vẹn cho tất cả các dạng cấu trúc CSDL. Hơn
nữa, các phương pháp phân cụm cần có cách thức biểu diễn cấu trúc của các CSDL,
với mỗi cách thức biểu diễn khác nhau sẽ có tương ứng thuật toán phân cụm phù
hợp. Vì vậy, phân cụm dữ liệu vẫn đang là một vấn đề khó và mở vì phải giải quyết
nhiều vấn đề cơ bản một cách trọn vẹn và phù hợp với nhiều dạng dữ liệu khác
nhau, đặc biệt là với kho dữ liệu hỗn hợp đang ngày càng tăng và đây cũng là một
trong những thách thức lớn trong lĩnh vực KPDL.
Vậy phân cụm dữ liệu là một thách thức trong lĩnh vực nghiên cứu vì những
ứng dụng tiềm năng của chúng được đưa ra ngay chính trong những yêu cầu đặc
biệt của chúng. Do đặc thù của của cơ sở dữ liệu là lớn, phức tạp, và có dữ liệu
nhiễu nên những thuật toán phân cụm được áp dụng phải thoả mãn những yêu cầu
sau:[4][14]:
• Thuật toán phải hiệu quả và thời gian chạy phải là tăng tuyến tính theo kích thước
của dữ liệu
18
• Thuật toán phải xử lý và áp dụng được với cơ sở dữ liệu nhiều nhiễu, phức
tạp gồm cả dữ liệu không gian, phi không gian, dữ liệu số, phi số, kiểu nhị
phân, dữ liệu định danh, hạng mục, thích nghi với kiểu dữ liệu hỗn hợp.
• Thuật toán phải có khả năng xác định được những cụm với hình dáng bất kỳ
bao gồm cả những cụm có hình dạng lồng nhau, cụm có hình dạng lõm, hình
cầu, hình que…
• Tối thiểu lượng tri thức cần cho xác định các tham số đầu vào. Do các giá trị
đầu vào thường ảnh hưởng rất lớn đến thuật toán phân cụm và rất phức tạp
để xác định các giá trị vào thích hợp đối với các CSDL lớn.
• Thuật toán phải thực hiện với mọi thứ tự đầu vào dữ liệu. Nói cách khác kết
quả của thuật toán nên độc lập với dữ liệu đầu vào (Cùng một tập dữ liệu, khi
đưa vào xử lý cho thuật toán PCDL với các thứ tự vào của các đối tượng dữ
liệu ở các lần thực hiện khác nhau thì không ảnh hưởng lớn đến kết quả phân
cụm )
• Thuật toán không đòi hỏi những tri thức về cơ sở dữ liệu từ người dùng
f p
i if ip
n nf np
x x x
x x x
x x x
 
 
 
 
 
 
 
 
Ma trận phi tương tự (Dissimilarity matrix, object-by-object structure): là
mảng n hàng, n cột. Phần tử d(i,j) chứa khoảng cách hay độ khác biệt giữa các đối
tượng i và đối tượng j, d(i,j) là một số không âm, trong đó nếu d(i,j) xấp xỉ 0 thì hai
đối tượng i và j là khá "gần" nhau, nếu d(i,j) càng lớn thì hai đối tượng i, j khá khác
nhau. Do d(i,j) = d(j,i) = 0 nên ta có thể biểu diễn ma trận phi tương tự như sau:
0
(2,1) 0
(3,1) (3,2) 0

( ,1) ( ,2) 0
d
d d
d n d n
 

• Thuộc tính rời rạc: Nếu miền giá trị của nó là tập hữu hạn, đếm được (ví
dụ: các thuộc tính số,…) trường hợp đặc biệt của thuộc tính rời rạc là thuộc
tính nhị phân mà miền giá trị chỉ có hai phân tử (ví dụ: Yes/No, True/False,
On/Off )
2. Kiểu dữ liệu dựa trên hệ đo
• Thuộc tính định danh: Là dạng thuộc tính khái quát hoá của thuộc tính nhị
phân, trong đó có miền giá trị là rời rạc không phân biệt thứ tự và có nhiều
hơn hai phần tử. Nếu x và y là hai đối tượng thuộc tính thì chỉ có thể xác
định là x ≠ y hoặc x =y.
• Thuộc tính có thứ tự: Là thuộc tính định danh nhưng có thêm tính thứ tự
nhưng chúng không được định lượng. Nếu x và y là hai thuộc tính thứ tự thì
có thể xác định là x ≠ y hoặc x = y hoặc x > y hoặc x< y.
• Thuộc tính khoảng: để đo các giá trị theo xấp xỉ tuyến tính, với thuộc tính
khoảng có thể xác định một thuộc tính là đứng trược hoặc đứng sau thuộc
tính khác với một khoảng là bao nhiêu. Nếu x
i
> y
i
thì có thể nói x cách y
một khoảng x
i
- y
i
tương ứng với thuộc tính thứ i.
Việc lựa chọn đơn vị đo cho các thuộc tính cũng ảnh hưởng đến chất lượng
phân cụm. Nếu đơn vị độ đo của một thuộc tính càng được chia nhỏ, thì khoảng
cách xác định của thuộc tính đó càng lớn và ảnh hưởng nhiều hơn đến kết quả phân
cụm. Để tránh phụ thuộc vào việc lựa chọn đơn vị đo, dữ liệu cần được chuẩn hóa.
Việc chuẩn hóa sẽ gán cho tất cả các thuộc tính một trọng số bằng nhau. Tuy nhiên,