Bài giảng Phân tích dữ liệu - Chương 5: Phân nhóm dữ liệu (Cluster)

TRƯỜNG ĐẠI HỌC BÁCH KHOA TP. HCM

PHÂN TÍCH DỮ LIỆU

Chương 5: Phâ n nhó m dữ liệu (Cluster)

Khoa KTXD - Bộ môn KTTNN

Chương 5: Phâ n nhó m dữ liệu (Cluster)

NỘI DUNG MÔN HỌC

Chương 1. Thống kê mô tả (ô n).

Chương 1bis. Xá c suất & phâ n phối thống kê (ô n)..

Chương 2. Khoảng tin cậy.

Chương 3. Kiểm định thống kê.

Chương 4. Phâ n khúc dữ liệu (Segmentation).

Chương 5. Phâ n nhó m dữ liệu (Cluster).

Chương 6. Phâ n tí ch thành phần chí nh (PCA).

Chương 7. Phâ n tí ch chuỗi thời gian.

Chương 8. Hồi quy tuyến tí nh.

Giảng viên: PGS. TS. NGUYỄN THỐNG

E-mail: [email protected] or nthong56@yahoo.fr

Chương 9. Xử lý số liệu thực nghiệm.

Web: http://www4.hcmut.edu.vn/~nguyenthong/

Chương 10. Giới thiệu phần mềm SPSS or R

1

PGS. TS. Nguyễn Thống

Té l. (08) 38 691 592- 098 99 66 719

PHÂN TÍCH DỮ LIỆU

Chương 5: Phâ n nhó m dữ liệu (Cluster)

GIỚI THIỆU VÀ ĐẶT VẤN ĐỀ

 Marketing và nghiên cứu thị trường

• Phâ n nhó m (cluster, groupe) là mô t kỹ

thuật được ứng dụng trong nhiều lĩnh

vực. Ví dụ :

• Phâ n loại khá ch hàng – nhận biết cá c thành

phần có cung cá ch tiêu thụ hàng hó a giống

nhau.

 Sinh học : phâ n nhó m cá c loại câ y, cá c

động vật theo một số đặc tí nh nào đó (định

lượng hoặc định tí nh).

 Y học : phâ n loại cá c loại bệnh nhâ n theo

một số chỉ tiêu y học.

• Phâ n loại sản phẩm – nghiên cứu nhiều nhã n

hiệu khá c nhau của 1 sản phẩm theo cá c

thuộc tí nh của chúng bởi người tiêu dùng. Cá c

nhã n hiệu xuất hiện trong cùng một nhó m sẽ

có cá c thuộc tí nh « gần guĩ » nhau nhất, trên

cơ sở cá c thuộc tí nh khảo sá t.

PGS. TS. Nguyễn Thống

PHÂN TÍCH DỮ LIỆU

Chương 5: Phâ n nhó m dữ liệu (Cluster)

LÝ THUYẾT PHÂN NHÓM

Chương 5: Phâ n nhó m dữ liệu (Cluster)

• Nghiên cứu một tập thể cá nhâ n theo cá c

yếu tố : hoạt động, thu nhập, quan điểm.

 Cá c cá nhâ n xuất hiện, trong cùng một

nhó m, thể hiện đó là cá c cá nhâ n có tổng

hợp cá c yếu tố là gần nhau nhất. Nó cho

phé p chúng ta hiểu được cá c cung cá ch

sá ch sống khá c nhau.

 Mục đích của phương phá p phâ n nhó m

là nhận ra cá c nhó m đồng nhất trong tập dữ

liệu cá c cá nhâ n đang xé t cùng với cá c biến

^Pl^Giê^S.n^TSq^{. N}u^ga^uyn^ễn(đ^Thị^ốnⁿh^gtí nh, định lượng).

Cũng như trong bất kỳ một phương pháp

phân tích thống kê nào, một số công tác

chuẩn bị phải được thực hiện trước. Các

vấn đề cơ bản đặt ra và phải quyết định như

sau :

 Các biến (chỉ tiêu) nào sẽ được sử dụng

trong việc thành lập nhóm ?

 Định nghĩa về « khoảng cách » giữa các

biến được sử dụng.

PGS. TS. Nguyễn Thống

 ..

1

PHÂN TÍCH DỮ LIỆU

Chương 5: Phâ n nhó m dữ liệu (Cluster)

 Tiêu chuẩn gì sẽ được sử dụng để nhó m

cá c « phần tử» hoặc cá c nhó m lại với

nhau.

• Trong đó việc chọn cá c biến để thành lập

nhó m có một vai trò quan trọng nhất.

• Việc xá c định cá c chỉ tiêu để tiến hành

thành lập nhó m có một vai trò quyết định

đến kết quả phâ n nhó m.

PHÂN NHÓM DỰA TRÊN 1 BIẾN

(BÀI TOÁN 1 CHIỀU)

• Một loại thí nghiệm VLXD cho kết quả chỉ tiêu

khảo sá t X. Giả sử ta muốn phâ n loại X thành

2 nhó m dựa vào giá trị. Một cá ch định tí nh ta

có thể có được lời giải sau :

Nhó m 2

X

Nhó m 1

PGS. TS. Nguyễn Thống

PHÂN TÍCH DỮ LIỆU

Chương 5: Phâ n nhó m dữ liệu (Cluster)

Trường hợp muốn phâ n loại X thành 3

nhó m dựa vào giá trị. Một cá ch định tí nh ta

PHÂN NHÓM DỰA TRÊN 2 BIẾN

(BÀI TOÁN 2 CHIỀU)

có thể có được lời giải sau :

Ví dụ: Một Tổng Cô ng ty hoạt động có 14

Cô ng ty trực thuộc. Để thực hiện chủ

trương của Ban Giá m Đốc về việc thành lập

cá c Cô ng ty có quy mô « lớn » hơn so với

hiện tại để có thể cạnh tranh với cá c doanh

nghiệp cùng ngành Tổng Cô ng ty sẽ tiến

hành sá t nhập một số Cô ng ty trực thuộc.

Nhó m 3

X

Nhó m 2

Nhó m 1

PGS. TS. Nguyễn Thống

PHÂN TÍCH DỮ LIỆU

Chương 5: Phâ n nhó m dữ liệu (Cluster)

Tiêu chí sá t nhập đưa ra được dựa vào

doanh thu X₁và số lượng nhâ n sự X₂. Để

có thể tiến hành sắp xếp lại cá c Cô ng ty

trực thuộc, Tổng Cô ng ty cần phâ n nhó m

cá c Cô ng ty trực thuộc có doanh thu và

nhâ n sự « gần giống » nhau  Về mặt đồ

thị ta có thể biểu diễn 14 Cô ng ty dưới

dạng sau :

Nhâ n viên (100ng)

40

Trường hợp 4 nhó m

30

20

10

5 10

15

20 Doanh thu (100 tỷ)

PGS. TS. Nguyễn Thống

2

PHÂN TÍCH DỮ LIỆU

Chương 5: Phâ n nhó m dữ liệu (Cluster)

Nhâ n viên (100ng)

Trường hợp 3 nhó m

Nhâ n viên (100ng)

Trường hợp 2 nhó m

40

30

20

10

40

30

20

10

5

10

15

20 Doanh thu (100 tỷ)

5 10

15

20 Doanh thu (100 tỷ)

PGS. TS. Nguyễn Thống

PHÂN TÍCH DỮ LIỆU

Chương 5: Phâ n nhó m dữ liệu (Cluster)

Ghi chú : Ta có thể quan niệm đây là

trường hợp có 14 nhó m, trong đó

mỗi phần tử (Cô ng ty) hì nh thành 1

nhó m.

Bài toá n tương tự sẽ được tổng

quá t hoá trong trường hợp vấn đề

nhiều biến (n biến) Trong khô ng

gian n chiều.

PHÂN TÍCH DỮ LIỆU

Chương 5: Phâ n nhó m dữ liệu (Cluster)

 Mỗi cá nhâ n nghiên cứu sẽ được

« định vị » trong khô ng gian n chiều

nhờ vào n tọa độ là giá trị cá c biến

tương ứng (sẽ nó i rõ hơn trong chủ

đề: Phâ n tí ch nhâ n tố cá c thành

phần chí nh).



PGS. TS. Nguyễn Thống

PHÂN TÍCH DỮ LIỆU

Chương 5: Phâ n nhó m dữ liệu (Cluster)

TIÊU CHUẨN « KẾT HỢP » THÀNH NHÓ M

Hai cá thể (hì nh thành một tiểu

nhó m) sẽ được nhó m lại khi nó có

cá c thuộc tí nh « gần gũi» nhất, so với

cá c cá thể (nhó m) cò n lại.

 Để đánh giá sự gần gũi của 2 cá thể,

ta dựa vào cá c tiêu chuẩn phổ biến

sau đây :

Cá c ví dụ trên chỉ cho chúng ta một

cá ch nhì n có tí nh cá ch trực giá c trong

việc thành lập nhó m. Về mặt lý thuyết,

để tiến hành kết hợp 2 hay nhiều « cá

thể» vào trong một nhó m ta sẽ dựa vào

cá c khá i niệm cơ bản trì nh bày sau.

PGS. TS. Nguyễn Thống

3

PHÂN TÍCH DỮ LIỆU

Chương 5: Phâ n nhó m dữ liệu (Cluster)

Khoảng cá ch Euclic : Xé t trong khô ng

gian n chiều, hai cá thể A và B sẽ được

xá c định « vị trí » trong khô ng gian này

nhờ vào cá c giá trị (tọa độ) tương ứng :

• Khoảng cách Chebychev : Được

định nghĩa như giá trị tuyệt đối

lớn nhất của các sai biệt của A và

B :

A

B

A(x₁, x₂,…, x_n) và B(x₁, x₂,…, x_n).

D(A,B)  Max _ix_i^A x_i^B

Khoảng cá ch Euclic giữa A & B định nghĩa

bởi:

2

D



A,B







x^A x^B





i

PGS. TS. Nguyễn Thống

PHÂN TÍCH DỮ LIỆU

Chương 5: Phâ n nhó m dữ liệu (Cluster)

• Trong trường hợp số liệu ở dạng tần số

« frequency), « khoảng cá ch » được đo

SỰ TƯƠNG TỰ

Để có thể « nhó m » cá c cá thể,

ngoài khaí niệm dựa vào sự « gần »

nhau theo thô ng số khoảng cá ch

Euclic (hoặc định nghĩa khoảng

cá ch khá c) như trên.

thô ng qua sự đánh giá « độc lập » giữa 2

2

biến, dựa vào định nghĩa

nghĩa như sau :

và được định



2

x_i^A E



x_i^A







i

x_i^B E



x_i^B





^



D(A,B) 



E



x_i^A



E



x_i^B



i



PGS. TS. Nguyễn Thống

PHÂN TÍCH DỮ LIỆU

Chương 5: Phâ n nhó m dữ liệu (Cluster)

• Tiêu chuẩn tương quan theo Pearson :

SỰ TƯƠNG TỰ

N

Đô i khi người ta cò n dựa vào tiêu

chuẩn sự tương tự bởi tiêu chuẩn

sau đây :

X_iY



i

i1

S(A,B) 

N 1

• Với X_i, Y_ilà biến x_i& y_iđược trung tâm

Tiêu chuẩn cosin:

hóa & chuẩn hóa

x_i^Ax_i^B



i

S(A,B) 

2



x_i^A



.



x_i^B





i

PGS. TS. Nguyễn Thống

4

PHÂN TÍCH DỮ LIỆU

Chương 5: Phâ n nhó m dữ liệu (Cluster)

Chú ý : Tí nh khoảng cá ch trong trường

hợp cho 2 nhó m, mà mỗi nhó m có chứa

hơn 1 phần tử. Lúc đó ta sẽ có 3 định

nghĩa khá c nhau về khoảng cá ch giữa 2

nhó m :

• Khoảng cá ch được định nghĩa là khoảng

cá ch min cuả 2 phần tử thuộc 2 nhó m.

• Khoảng cá ch được định nghĩa là khoảng

cá ch max cuả 2 phần tử thuộc 2 nhó m.

 Tùy theo sự lựa chọn 1 trong 3 cá ch

tí nh khoảng cá ch nêu trên, có thể sự sá t

nhập nhó m dựa vào khoảng cá ch sẽ cho

kết quả khô ng giống nhau.

• Khoảng cá ch được định nghĩa là giá trị

khoảng cá ch trung bì nh cò n gọi là

khoảng cá ch có tí nh trọng số (khoảng

cá ch giữa 2 tâ m trọng trường của 2

PGS. TS. Nguyễn Thống

nhó m).

PGS. TS. Nguyễn Thống

PHÂN TÍCH DỮ LIỆU

Chương 5: Phâ n nhó m dữ liệu (Cluster)

Ví dụ: Phâ n nhó m theo tiêu chí min

Chương 5: Phâ n nhó m dữ liệu (Cluster)

Ví dụ: Phâ n nhó m theo tiêu chí max

PGS. TS. Nguyễn Thống

PHÂN TÍCH DỮ LIỆU

Chương 5: Phâ n nhó m dữ liệu (Cluster)

Và nhó m mới thành lập này sẽ thay thế 2

cá thể vừa được nhó m lại, được hiểu là

một « cá thể».

PHƯƠNG PHÁP « KẾT HỢP » THÀNH NHÓ M

• Phương phá p 1: Từ dưới lên (Ascendant).

Đây là phương phá p phổ biến :

 Cô ng việc tiếp tục và ta sẽ lần lượt có số

số nhó m giảm dần sau mỗi lần nhó m lại.

Note: Dĩ nhiên lần kết hợp thứ (N-1) sẽ

cho ta cò n 1 nhó m duy nhất gồm N phần

tử.

Tập hợp gồm N cá thể cần nhó m lại với

nhau để thành M nhó m (<N).

Ta tiến hành thực hiện phé p nhó m đầu tiên

cho 2 cá thể « gần » nhau nhất (ví dụ theo

tiêu chuẩn khoảng cá ch Euclic nhỏ nhất) và

như vậy ta cò n có N-1 nhó m.

PGS. TS. Nguyễn Thống

5

PHÂN TÍCH DỮ LIỆU

Chương 5: Phâ n nhó m dữ liệu (Cluster)

• Phương phá p 2: Từ trên xuống

(Descendant)

CHÚ Ý

Giả thiết số liệu 1D, khi gộp

cò n 2 nhó m  Khoảng cá ch 2

nhó m là « xa nhất » (tá ch biệt

rõ nhất).

 Đây là một quy trì nh ngược lại. Ban đầu ta

xem N cá thể chỉ trong duy nhất 1 nhó m, sau

đó ta tiến hành tá ch ra để thành lập 2 nhó m,

ví dụ dựa theo tiêu chuẩn khoảng cá ch

Euclic « lớn nhất ».

 ….

 Quy trì nh tiếp tục trong logic như vậy cho

đến khi ta có được N nhó m với mỗi nhó m là

một phần tử của số liệu ban đầu.

PGS. TS. Nguyễn Thống

PHÂN TÍCH DỮ LIỆU

Chương 5: Phâ n nhó m dữ liệu (Cluster)

Bài tập 0: Cho số liệu sau:

Ma trận khoảng cá ch Euclic:

Cá nhâ n

Biến

x1

a

b

c

d

e

Proximity Matrix

Euclidean Distance

8

10

2

8

6

3

5

2

6

9

Case

a

b

c

d

e

a

b

c

d

e

x2

0.000 6.325 7.280 8.544 2.236

6.325 0.000 6.403 6.708 4.123

7.280 6.403 0.000 1.414 6.000

8.544 6.708 1.414 0.000 7.071

2.236 4.123 6.000 7.071 0.000

Dùng tiêu chí để nhó m là khoảng

cá ch Euclic.

a. Tí nh ma trận khoảng cá ch

b. Thực hiện tạo nhó m

PGS. TS. Nguyễn Thống

PHÂN TÍCH DỮ LIỆU

Chương 5: Phâ n nhó m dữ liệu (Cluster)

(c+d)  ma trận distance mới

 (a+e)  ma trận distance mới

 (ae+b)  ma trận distance mới

Cá nhâ n

2 nhó m !

Cá nhâ n (aeb)

(cd)

6

0

(aeb)

(cd)

0

PGS. TS. Nguyễn Thống

6

PHÂN TÍCH DỮ LIỆU

Chương 5: Phâ n nhó m dữ liệu (Cluster)

Bài tập 1: Một thí nghiệm né n R(kg/cm²) cho

10 mẫu bêtô ng cho kết quả như sau. Hã y

phâ n dữ liệu trên thành 2 nhó m theo

phương phá p min khoảng cá ch Euclic

của trọng tâ m nhó m.

Hướng dẫn: SPSS\Analyse\Classify\

1

2

3

4

5

6

7

8

9

10

Mẫu

80 85 100 76 82 95 90 98 86 102

R

Số liệu: SPSS ../PTDuLieu/Cluster_1D.sav

Giải Excel:  ../PTDuLieu/Cluster_1D.xls

PGS. TS. Nguyễn Thống

PHÂN TÍCH DỮ LIỆU

Chương 5: Phâ n nhó m dữ liệu (Cluster)

PGS. TS. Nguyễn Thống

PHÂN TÍCH DỮ LIỆU

Chương 5: Phâ n nhó m dữ liệu (Cluster)

PGS. TS. Nguyễn Thống

7

PHÂN TÍCH DỮ LIỆU

Chương 5: Phâ n nhó m dữ liệu (Cluster)

Bài tập 2: Thí nghiệm 6 mẫu vật liệu về lực

ké o (R) & cắt (T) cho kết quả như sau.

Người ta muốn chia 6 mẫu này thành 2

nhó m theo phương phá p tí nh khoảng cá ch

Euclic (giả thiết khô ng kể đến đơn vị).

Mẫu

R

1

2

3

4

5

6

2.9 3.0 3.2 3.3 3.7 3.8

1.8 1.9 2.4 2.5 2.6 2.7

T

PGS. TS. Nguyễn Thống

PHÂN TÍCH DỮ LIỆU

Chương 5: Phâ n nhó m dữ liệu (Cluster)

Hướng dẫn:

Bài tập 3: Thí nghiệm 6 mẫu vật liệu về lực

ké o (R) & cắt (T) cho kết quả như sau.

Người ta muốn chia 5 mẫu này thành 2

nhó m theo phương phá p tí nh khoảng cá ch

Euclic (giả thiết khô ng kể đến đơn vị).

Mẫu

R

1

2

3

4

5

4.0

1.8

2.9 3.0

1.8 2.6

3.2 3.8

1.2 2.5

T

PGS. TS. Nguyễn Thống

PHÂN TÍCH DỮ LIỆU

Chương 5: Phâ n nhó m dữ liệu (Cluster)

Hướng dẫn:

PGS. TS. Nguyễn Thống

8

THOÁNG KEÂ ÖÙNG DUÏNG TRONG QUAÛN LYÙ & KYÕ THUAÄT

PHÂN TÍCH DỮ LIỆU

Chương 1: Phân phối thống kê & xác suất

Chương 5: Phâ n nhó m dữ liệu (Cluster)



HẾT

PGS. TS. Nguyễn Thống

9

Bài giảng Phân tích dữ liệu - Chương 5: Phân nhóm dữ liệu (Cluster) - Nguyễn Thống