ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ Nguyễn Thị Thu Hiền Các kỹ thuật phân cụm trong khai phá dữ liệu
LUẬN VĂN THẠC SĨ

Các kỹ thuật phân cụm trong khai phá dữ liệu
Ngành: Công Nghệ Thông tin
Mã số: 60.48.05 LUẬN VĂN THẠC SĨ NGƯỜI HƯỚNG DẪN KHOA HỌC:

PGS.TS. Vũ Đức Thi
Hà Nội - 2009
- 1 -

LỜI CAM ĐOAN

Tôi xin cam đoan luận văn “Các kỹ thuật phân cụm trong khai phá dữ liệu”
là công trình nghiên cứu của riêng tôi. Các số liệu, kết quả nêu trong luận văn được


- 3 -
MỤC LỤC
LỜI CAM ĐOAN 1
LỜI CẢM ƠN 2
MỤC LỤC 3
DANH MỤC CÁC KÝ HIỆU, CÁC CHỮ VIẾT TẮT 5
DANH MỤC BẢNG BIỂU 6
DANH MỤC HÌNH VẼ, ĐỒ THỊ 7
LỜI MỞ ĐẦU 9
CHƢƠNG 1 - TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU 11
1.1. Quá trình khám phá tri thức trong cơ sở dữ liệu 11
1.2. Tính liên ngành của khai phá dữ liệu 13
1.3. Các bài toán khai phá dữ liệu điển hình 14
1.4. Các dạng dữ liệu có thể khai phá dữ liệu 16
1.5. Hướng tiếp cận và kỹ thuật chính trong khai phá dữ liệu 16
1.6. Ứng dụng của khai phá dữ liệu 18
1.7. Các thách thức trong KPTT và KPDL 18
CHƢƠNG 2 - PHÂN CỤM DỮ LIỆU 19
2.1. Bài toán phân cụm dữ liệu 19
2.2. Các giai đoạn của quá trình phân cụm dữ liệu 20
2.3. Ứng dụng của phân cụm dữ liệu 21
2.4. Các kiểu dữ liệu và độ đo tương tự 21
2.5. Các kỹ thuật tiếp cận phân cụm dữ liệu 25
2.6. Yêu cầu đối với các thuật toán phân cụm dữ liệu 29
CHƢƠNG 3 - CÁC THUẬT TOÁN PHÂN CỤM DỮ LIỆU ĐIỂN HÌNH 30
3.1. Các thuật toán phân cụm phân hoạch 30
3.1.1. Thuật toán k-means 30
3.1.2. Thuật toán PAM 33
3.1.3. Thuật toán CLARA 35

4.3. Thuật toán FCM 80
4.3.1. Hàm mục tiêu 80
4.3.2. Thuật toán FCM 85
4.4. Một số kết quả thử nghiệm 85
4.4.1. Thí nghiệm dữ liệu có ngoại lai 85
4.4.2. Phân cụm dữ liệu các nhóm có ngoại lai và xếp chồng dữ liệu 88
KẾT LUẬN 91
TÀI LIỆU THAM KHẢO 92
PHỤ LỤC 94
CÀI ĐẶT THỬ NGHIỆM THUẬT TOÁN K-MEANS 94 - 5 -
DANH MỤC CÁC KÝ HIỆU, CÁC CHỮ 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
Công nghệ thông tin
CNTT
Information Technology
Khám phá tri thức
KPTT
Knowledge Discovery

KDD

Bảng 4.1. Số lỗi tâm cụm lớn nhất của FCM và FCM theo số phần tử ngoại lai 87
Bảng 4.2. Chuẩn Frobenius của các lỗi tâm các cụm 88
Bảng 4.3. Cực đại các lỗi tâm cụm với dữ liệu có ngoại lai 89
Bảng 4.4. Frobenius của các lỗi tâm cụm cho dữ liệu có ngoại lai 89 - 7 -
DANH MỤC HÌNH VẼ, ĐỒ THỊ

Hình 1.1. Quá trình khám phá tri thức trong CSDL 12
Hình 1.2. Tính đa/liên ngành của khai phá dữ liệu 13
Hình 1.3. Sơ đồ biểu diễn mô hình học máy: cần học đường nét rời 17
Hình 2.1. Quá trình phân cụm dữ liệu 20
Hình 2.2. Các khoảng cách Euclidean và Manhattan giữa hai đối tượng 23
Hình 2.3. Phương pháp xây dựng cây phân cụm phân cấp 26
Hình 2.4. Mô tả phân cụm phân hoạch và phân cụm phân cấp 27
Hình 3.1. Ý tưởng thuật toán k-means 30
Hình 3.2. Các bước cơ bản của thuật toán k-means 31
Hình 3.3. Chi tiết thuật toán k-means 32
Hình 3.4. Các bước thực hiện thuật toán PAM 35
Hình 3.5. Các bước thực hiện thuật toán CLARA 36
Hình 3.6. Thuật toán CLARANS 38
Hình 3.7. Thuật toán BIRCH sử dụng cây CF 40
Hình 3.8. Các bước cơ bản của thuật toán BIRCH 42

Hình 4.5. Thực nghiệm phương pháp FCM với  = 2 86
Hình 4.6. Thực nghiệm FCM,  = 2 với các cụm có dữ liệu xếp chồng và ngoại lai 90
Hình 4.7. Thực nghiệm FCM với các cụm có dữ liệu xếp chồng và ngoại lai 90 - 9 -

LỜI MỞ ĐẦU

Trong những năm gần đây, sự phát triển mạnh mẽ của công nghệ thông tin và
ngành công nghiệp phần cứng đã làm cho khả năng thu thập và lưu trữ thông tin của
các hệ thống thông tin tăng nhanh một cách chóng mặt. Bên cạnh đó, việc tin học
hóa một cách ồ ạt và nhanh chóng của các hoạt động sản xuất, kinh doanh cũng như
nhiều lĩnh vực hoạt động khác đã tạo ra một lượng dữ liệu lưu trữ khổng lồ. Hàng
triệu CSDL đã được sử dụng trong các hoạt động sản xuất, kinh doanh, quản lí ,
trong đó có nhiều CSDL cực lớn. Sự bùng nổ này đã dẫn tới một yêu cầu cấp thiết
là cần có những kĩ thuật và công cụ mới để tự động chuyển đổi lượng dữ liệu khổng
lồ kia thành các tri thức có ích. Từ đó, các kĩ thuật khám phá hay còn gọi là phát
hiện tri thức trong CSDL (Knowledge Discovery in Databases) đã trở thành một
lĩnh vực thời sự của ngành công nghệ thông tin trên thế giới hiện nay.
Khai phá dữ liệu (Data Mining) là một bước trong quá trình khám phá tri thức
và đượ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 CSDL, kho dữ liệu… 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ự

Chương 2: Giới thiệu về phân cụm dữ liệu, trong đó đi sâu phân tích chi tiết
các vấn đề cơ bản trong PCDL và ý nghĩa của PCDL. Đồng thời, trình bày tóm tắt
về các đặc trưng của các phương pháp PCDL 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 độ,… và nêu các kỹ thuật đánh giá kết quả PCDL.
Chương 3: Trình bày các phân tích, đánh giá đối với các thuật toán PCDL điển
hình và chỉ ra ưu, nhược điểm của chúng.
Chương 4: Trình bày về kỹ thuật phân cụm mờ trong PCDL, cụ thể là trình
bày hai thuật toán FCM (Fuzzy C-means) và FCM. Nêu lên một số kết quả thực
nghiệm cho các thuật toán phân cụm mờ.
Phụ lục: Cài đặt chương trình thử nghiệm cho thuật toán k-means.

- 11 -
CHƢƠNG 1.
TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU

1.1. Quá trình khám phá tri thức trong cơ sở dữ liệu
Cuộc cách mạng của khoa học kỹ thuật đã cho phép số hóa thông tin dễ dàng,
nhanh chóng với chi phí lưu trữ thấp. Đồng thời, cùng với sự phát triển, trang bị
hiện đại của hệ thống phần mềm, phần cứng máy tính, một số lượng dữ liệu khổng
lồ đã được tích lũy, lưu trữ. Mục đích của việc thu thập và lưu trữ các kho dữ liệu
khổng lồ như vậy không ngoài mục tiêu khai phá dữ liệu nhằm phát hiện các tri thức
mới có ích cho hoạt động của con người. Chính vì vậy, kỹ thuật thống kê và các
công cụ quản trị dữ liệu cũ không thể đáp ứng được nhu cầu phân tích đầy đủ dữ
liệu rộng lớn được nữa và một khuynh hướng mới đã được ra đời, phát triển, đó là
lĩnh vực khám phá tri thức và khai phá dữ liệu.
Theo Fayyad, Piatetsky-Shapiro, Smyth, việc nghiên cứu phát triển lĩnh vực
khám phá tri thức trong CSDL (Knowledge Discovery in Databases: KDD) nhằm
giải quyết tình trạng “ngập tràn thông tin mà vẫn thiếu thốn tri thức”. [22]
Khám phá tri thức trong cơ sở dữ liệu là lĩnh vực đã, đang và sẽ được quan
tâm triển khai nghiên cứu, phát triển một cách nhanh chóng và rộng rãi. Đã có rất

- Biến đổi dữ liệu (Data transformation)
Là bước chuẩn hóa và làm mịn dữ liệu để đưa dữ liệu về dạng thuận lợi nhất
nhằm phục vụ cho mục đích khai thác ở bước sau.
- Khai phá dữ liệu (Data mining)
Đây là bước quan trọng và tốn nhiều thời gian nhất của quá trình khám phá tri
thức, áp dụng các kỹ thuật phân tích (phần lớn là các kỹ thuật của học máy) nhằm
khai thác, trích chọn được các mẫu thông tin, các mối liên hệ đặc biệt trong dữ liệu.

Dữ liệu
Dữ liệu đích
Dữ liệu đã
tiền xử lý
Dữ liệu
chuyển dạng
Mẫu
Tri thức
Đánh giá và biểu
diễn tri thức
Trích
chọn dữ
liệu
Tiền xử lý
dữ liệu
Biến đổi
dữ liệu
Khai phá
dữ liệu

- 13 -
- Đánh giá và biểu diễn tri thức (Knowledge representation & evaluation)

hữu dụng hoặc hấp dẫn) trong các tập hợp dữ liệu lớn của thế giới thực.
Phát hiện máy với mục tiêu là phát hiện các luật kinh nghiệm từ quan sát và
thử nghiệm và mô hình nhân quả phát hiện các kết luận của mô hình nhân quả từ dữ
liệu là những lĩnh vực nghiên cứu có mối liên hệ với nhau.
Một lĩnh vực nghiên cứu và triển khai có liên quan (trong nhiều trường hợp
được coi là một bộ phận của lĩnh vực khai phá dữ liệu và phát hiện tri thức trong
CSDL) là lĩnh vực kho dữ liệu (data warehouse) chỉ dẫn tới các khuynh hướng hệ
thống thông tin quản lý (MIS: Managment Information Systems) phổ biến hiện tại
đối với việc thu thập và làm sạch dữ liệu giao dịch và tạo cho chúng sự biến động
khi tìm kiếm trực tuyến. Một tiệm cận phổ biến đối với việc phân tích kho dữ liệu
gọi là OLAP (On-Line Analytical Processing), qua một tập các nguyên lý được
Codd đề xuất vào năm 1993 [19].
1.3. Các bài toán khai phá dữ liệu điển hình
Bước khai phá dữ liệu trong quá trình KDD thường áp dụng một phương pháp
khai phá dữ liệu cụ thể, liên quan đến các khái niệm mẫu và mô hình. Mẫu là một
biểu thức trong một ngôn ngữ mô tả L được chọn. Mô hình được coi là một biểu
thức tổng quát trong ngôn ngữ mô tả L nói trên mà tính tổng quát được thể hiện
thông qua các tham số (được gọi là tham số mô hình), trong trường hợp đó, mẫu là
một thể hiện của mô hình.
Nhiệm vụ của bài toán khai phá dữ liệu là từ dữ liệu (tập các sự kiện) quan sát
đã có thì hoặc cần phải xác định mô hình phù hợp với dữ liệu quan sát, hoặc cần tìm
ra các mẫu từ dữ liệu đó.
Ở mức cao - tổng quát, hai mục tiêu chủ yếu của khai phá dữ liệu là dự đoán
và mô tả. Dự đoán dùng một số biến hoặc trường trong CSDL để dự đoán hoặc về
giá trị chưa biết hoặc về giá trị sẽ có trong tương lai của các biến. Mô tả hướng tới
việc tìm ra các mẫu mô tả dữ liệu. Dự đoán và mô tả có tầm quan trọng khác nhau
đối với các thuật toán khai phá dữ liệu riêng.
Ở mức chi tiết - cụ thể, dự đoán và mô tả được thể hiện thông qua các bài toán
cụ thể như mô tả khái niệm, quan hệ kết hợp, phân cụm, phân lớp, hồi quy, mô hình
phụ thuộc, phát hiện biến đổi và độ lệch và một số bài toán cụ thể khác.

biến. Tình huống ứng dụng hồi quy rất đa dạng, chẳng hạn như dự báo nhu cầu
người tiêu dùng đối với một sản phẩm mới, dự đoán số lượng sinh vật phát quang
trong khu rừng nhờ đo vi sóng các sensor từ xa, hoặc ước lượng xác suất người
bệnh có thể chết theo kết quả test triệu chứng,…
 Mô hình phụ thuộc
Bài toán xây dựng mô hình phụ thuộc hướng tới việc tìm ra một mô hình mô
tả sự phụ thuộc có ý nghĩa giữa các biến. Mô hình phụ thuộc gồm hai mức: mức cấu
trúc của mô hình mô tả (thường dưới dạng đồ thị) và mức định lượng. Trong đó, ở
mức cấu trúc của mô hình các biến là phụ thuộc bộ phận vào các biến khác, còn ở
mức định lượng của mô hình mô tả sức mạnh của tính phụ thuộc khi sử dụng đo
theo số.

- 16 -
 Phát hiện biến đổi và độ lệch
Tập trung vào việc phát hiện hầu hết sự thay đổi có ý nghĩa dưới dạng độ đo
đã biết trước hoặc giá trị chuẩn.
 Ngoài ra có thể kể tới phân tích định hướng mẫu và thống kế khác.
1.4. Các dạng dữ liệu có thể khai phá dữ liệu
Nguồn dữ liệu được sử dụng để tiến hành khai phá dữ liệu nhằm phát hiện tri
thức rất phong phú.
 Cơ sở dữ liệu quan hệ (relational databases) : là các dữ liệu được tổ chức theo
mô hình dữ liệu quan hệ.
 Cơ sở dữ liệu đa chiều (multidimention structures, data warehouses, data
mart): là các kho dữ liệu được tập hợp và chọn lọc từ nhiều nguồn dữ liệu
khác nhau. Dạng dữ liệu này chủ yếu phục vụ cho quá trình phân tích cũng
như khai phá tri thức và hỗ trợ quá trình ra quyết định.
 Cơ sở dữ liệu giao tác (transactonal databases)
 Cơ sở dữ liệu quan hệ - hướng đối tượng (object relational databases): là dạng
lai giữa hai mô hình quan hệ và hướng đối tượng.
 Dữ liệu không gian và thời gian (spatial, temporal, and time-series data)

hiện kế tiếp biến cố Y. Hướng tiếp cận này có tính dự báo.
 Phân cụm (clustering/segmentation): Sắp xếp các đối tượng theo từng cụm
(số lượng và tên của cụm chưa được biết trước). Các đối tượng được gom cụm sao
cho mức độ tương tự giữa các đối tượng trong cùng một cụm là lớn nhất và mức độ
tương tự giữa các đối tượng nằm trong các cụm khác nhau là nhỏ nhất. Phân cụm
còn được gọi là học không có giám sát (unsupervised learning).
Mô hình học máy (có giám sát và không giám sát) được trình bày như hình 1.4
dưới đây: Hình 1.3. Sơ đồ biểu diễn mô hình học máy: cần học đƣờng nét rời

Trong đó, học máy không giám sát (phân cụm) không có giá trị mục tiêu cho
ví dụ học (không có hai đường liền nét hướng tới giá trị mục tiêu) - 18 -
1.6. Ứng dụng của khai phá dữ liệu
KPDL được vận dụng trong nhiều lĩnh vực khác nhau nhằm khai thác nguồn
dữ liệu phong phú được lưu trữ trong các hệ thống thông tin. Tuỳ theo bản chất của
từng lĩnh vực, việc vận dụng KPDL có những cách tiếp cận khác nhau.
Ứng dụng của KPDL có thể được chia thành hai lớp chính bao gồm ứng dụng
phân tích dữ liệu - hỗ trợ quyết định và một số lĩnh vực ứng dụng khác.
Các ứng dụng trong phân tích dữ liệu và hỗ trợ quyết định bao gồm các ứng
dụng trong phân tích và quản lý thị trường, phân tích và quản lý rủi ro, khám phá
ngoại lai và các mẫu không hữu ích. Dữ liệu trong các ứng dụng này là khá phong
phú từ các giao dịch thẻ tín dụng, nghiên cứu đời sống công đồng Các kỹ thuật
KPDL đã được áp dụng thành công trong việc dự đoán lưu lượng viễn thông cho
các công ty điện thoại, mức độ tiêu thụ sản phẩm cho các nhà sản xuất, giá trị của
sản phẩm trên thị trường cho các công ty tài chính hay phân nhóm các khách hàng

Phân cụm dữ liệu là quá trình phân chia một tập dữ liệu ban đầu thành các
cụm dữ liệu sao cho các phần tử trong một cụm thì “tương tự” nhau và các phần tử
trong các cụm khác nhau thì “phi tương tự” với nhau. Số các cụm dữ liệu được
phân ở đây có thể được xác định trước theo kinh nghiệm hoặc có thể được tự động
xác định.
Sau khi xác định các đặc tính của dữ liệu, người ta đi tìm cách thích hợp để
xác định "khoảng cách" giữa các đối tượng, hay là phép đo tương tự dữ liệu. Đây
chính là các hàm để đo sự giống nhau giữa các cặp đối tượng dữ liệu, thông thường
các hàm này hoặc là để tính độ tương tự (Similar) hoặc là tính độ phi tương tự
(Dissimilar) giữa các đối tượng dữ liệu. Giá trị của hàm tính độ đo tương tự càng
lớn thì sự giống nhau giữa đối tượng càng lớn và ngược lại; còn hàm tính độ phi
tương tự tỉ lệ nghịch với hàm tính độ tương tự.
Trong học máy, phân cụm dữ liệu được xem là vấn đề học không có giám sát
(unsupervised learning), vì nó giải quyết vấn đề tìm một cấu trúc trong tập hợp các
dữ liệu chưa biết trước các thông tin về lớp hay các thông tin về tập ví dụ huấn
luyện. Trong nhiều trường hợp, khi phân lớp được xem là vấn đề học có giám sát thì
phân cụm dữ liệu là một bước trong phân lớp dữ liệu, trong đó phân cụm dữ liệu sẽ
khởi tạo các lớp cho phân lớp bằng cách xác định các nhãn cho các nhóm dữ liệu.
Một vấn đề thường gặp trong PCDL đó là hầu hết các dữ liệu cần cho phân
cụm đều có chứa dữ liệu “nhiễu” (noise) do quá trình thu thập thiếu chính xác hoặc
không đầy đủ. Vì vậy, cần phải xây dựng chiến lược cho bước tiền xử lý dữ liệu
nhằm khắc phục hoặc loại bỏ “nhiễu” trước khi bước vào giai đoạn phân tích phân
cụm dữ liệu.
Ngoài ra, dò tìm phần tử ngoại lai (outlier) cũng là một trong những hướng
nghiên cứu quan trọng trong KPDL, chức năng của nó là xác định một nhóm nhỏ

- 20 -
các đối tượng dữ liệu “khác thường”, dị biệt so với các dữ liệu khác - tức là các đối
tượng dữ liệu không tuân theo các hành vi hoặc mô hình dữ liệu - nhằm tránh ảnh
hưởng của chúng tới quá trình và kết quả PCDL. Khám phá các phần tử ngoại lai đã

Cluster

Dữ liệu
Clusters
Tri thức

- 21 -
2.3. Ứng dụng của phân cụm dữ liệu
Phân cụm dữ liệu thực hiện phân chia dữ liệu thành các cụm dữ liệu. Quá trình
phân cụm dữ liệu có nhiều ý nghĩa trong các hoạt động của con người và đã được áp
dụng rất rộng rãi trong nhiều ứng dụng, bao gồm nhận dạng mẫu, phân tích dữ liệu,
xử l‎ý ảnh, lập kế hoạch marketing Cụ thể:
Trong thương mại phân cụm dữ liệu có thể giúp các công ty khám phá ra các
nhóm khách hàng quan trọng có các đặc trưng tương đồng nhau và đặc tả khách
hàng từ các mẫu mua bán trong cơ sở dữ liệu khách hàng để từ đó đưa ra các chiến
lược kinh doanh hợp lý.
Trong sinh học phân cụm dữ liệu được sử dụng để xác định các loại sinh vật,
phân loại các gen với chức năng tương đồng và thu được các cấu trúc trong các mẫu.
Phân tích dữ liệu không gian tạo ra các cụm từ cơ sở dữ liệu đồ sộ của dữ liệu
không gian như dữ liệu thu được từ các hình ảnh chụp từ vệ tinh các thiết bị y học
hoặc hệ thống thông tin địa lý (GIS), …trợ giúp con người tự động phân tích và xử
lý các dữ liêu không gian như nhận dạng và chiết xuất các đặc tính hoặc các mẫu dữ
liệu quan tâm có thể tồn tại trong cơ sở dữ liệu không gian.
Trong lĩnh vực Web Mining, phân cụm dữ liệu có thể khám phá các nhóm tài
liệu quan trọng, có nhiều ý nghĩa trong môi trường Web. Các lớp tài liệu này trợ
giúp cho việc khám phá tri thức từ dữ liệu, …
2.4. Các kiểu dữ liệu và độ đo tƣơng tự
Trong phân cụm dữ liệu, các đối tượng dữ liệu cần phân tích được cho dưới rất
nhiều dạng thức. Mỗi đối tượng được mô tả thông qua các thuộc tính của nó. Cho
một tập dữ liệu X chứa n đối tượng trong không gian k chiều; x

). Trong đó t
i
,
u
i
, v
i
(
1,ik
) là các đặc trưng của thuộc tính tương ứng với các đối tượng x
1
, x
2
, x
3
.
Khi đó, khái niệm “các kiểu dữ liệu” và “các kiểu thuộc tính dữ liệu” được xem là
tương đương nhau.
Khi các giá trị của thuộc tính đã được xác định người ta tìm cách thích hợp để
xác định “khoảng cách” giữa các đối tượng, hay chính là phép đo tương tự dữ liệu.
Đây là các hàm đo sự giống nhau giữa các cặp đối tượng dữ liệu. Thông thường,
chúng ta tính độ tương tự (Similarity) hoặc độ phi tương tự (Dissimilarity). Giá trị
của hàm tính độ tương tự càng lớn thì sự giống nhau giữa các đối tượng càng lớn và
ngược lại. Hàm tính độ phi tương tự và hàm tính độ tương tự là tỉ lệ nghịch với nhau.

- 22 -
Tất cả độ đo sau đây được xác định trong không gian metric. Bất kỳ một
metric nào cũng là một độ đo nhưng điều ngược lại không đúng. Độ đo ở đây có thể
là độ tương tự hoặc phi tương tự. Một tập dữ liệu X là một không gian metric nếu:
 Với mỗi cặp đối tượng x, y thuộc X đều xác định một số thực d(x, y) theo một



,
ở đây x và y có vai trò như nhau, tức là chúng đối xứng và cùng trọng số.

y : 1
y : 0

x : 1


 + 
x : 0


 + 

 + 
 +  - 23 -
Hệ số Jacard (Jaccard Coefficient):
( , )d x y

  


, công thức này được
áp dụng trong trường hợp mà trọng số của các thuộc tính có giá trị 1 lớn hơn rất

1/ 2
1
( , ) ( )
n
ii
i
d x y x y



, nó là trường hợp của
khoảng cách Minkowski với q = 2.
 Khoảng cách Mahattan:
1
( , ) ( )
n
ii
i
d x y x y



, nó là trường hợp của khoảng
cách Minkowski với q = 1.
 Khoảng cách cực đại:
( , )
n
i=1 i i
d x y max x y
, chú ý rằng đây là trường hợp