数学建模————统计问题之分类/聚类(二) 1 p1 u4 f) I% @. @ Q- R: V 首先要弄明白分类和聚类的区别: 5 Y F0 h& o- E( z5 o$ Q/ Y 分类(判别):数据包含数据特征部分和样本标签部分,分类的目的就是判别新的数据特征到其应有的样本标签(类别)中。 4 k6 L! n0 p6 m. o: G# G$ ^' c4 M, a
比方说,现在告诉大家一个教室里面其中一半人每个人的性别(男女),现在需要大家将另一半人中每个人的性别判断出来,因此大家首先要做的的找到区分性别的特征,然后应用到另一半人身上,将其归类。, C, ~* t$ a8 B4 e
# Q9 i8 k. }* I; o
聚类:数据中只有数据特征,需要根据某一标准将其划分到不同的类中。 7 A$ B; U. t C( z" G: `4 {, k# f2 M
同样的,现在一个教室里面所有人都没什么标签,现在需要你将整个教室的人分为两类,那么你可以从性别、体型、兴趣爱好、位置等等角度去分析。3 P8 `% v( Y4 K4 d: u* B
4 d* Q, H4 }' S3 E 3 p$ y% X. D" Z$ Y. h! a" |, n. z- w, f
可以看到,分类其实跟预测差不多,只不过输出是一维的,并且还是整数,所以可以用预测中的机器学习方法来解决分类问题。而聚类则不同,一般来说,聚类需要定义一种相似度或者距离,从而将相似或者距离近的样本归为一类,常见的有:kmeans算法、分层聚类、谱聚类等。3 u& r8 c+ |/ V# I
* R c& Z- \% F. v" k3 ~ 对于聚类来说,除了相似性的度量之外,还有一个比较重要的是终止条件,即需要聚成多少类,一般来说,基本都是在聚类之前就设定好需要聚成多少类,其中kmeans就是先设定几个类中心,然后将与类中心相近的数据归到那一类,然后不断更新类中心,直至所有数据聚类完毕,而分层聚类则是相反,先将所有数据各自为一类,然后将相似的类合并,直至达到k类为止...3 e" q0 C2 C: |! N! [- t f
当然,也可以将终止条件改为当最小的距离大于某一阈值时,不再合并类(适用于分层聚类),除了这些算法,还有机器学习方法,如:自组织竞争网络(SOM),可以自行了解。5 x* a: e l& ?, b* f5 K
3 i' o) z+ r u/ v: a& C 接下来我们以分层聚类为例进行讲解,这一部分例子来自于《数学建模算法与应用》,用以辅助说明。通常来说,分层聚类有两类,一类是从上到下的分裂(即现将所有个体看做一个类,然后利用规则一步步的分裂成多个类),另一类是从下到上的合并(即先将每个个体看作一个类,然后依据规则一步步合并为一个类)。因此分层聚类最终可以得到一个金字塔结构,每一层都有不同的类别数量,我们可以选取需要的类别数量。 6 q" t( y) W, S& i3 Y- Z--------------------- 0 f# ]% u, Y$ b5 {0 }# g* K
例子:设有5个销售员w1,w2,w3,w4,w5,他们的销售业绩由二维变量(v1,v2)描述: - S" F( @, W g: S" @; j, v$ L- r
8 k" ]4 \& ^: t# A0 W& q) S' b" C
将5个人的两种数据看作他们的指标,首先,我们简单定义任意两组数据的距离为:. T5 `5 D, j( g
3 P+ _( J6 y$ A( s
; O# q, ? E G, r4 [$ h: x
7 \" e& v1 s! |7 e/ h; h9 M2 ~' g. x 1 [+ Q3 C& M2 ]# w+ \9 i8 M ) z2 k$ ]/ f+ a% i ( z' W, d' I& R7 [- y6 Z- v 0 j {6 e, X5 D; D/ X- C2 Q 与此相对应的,当有样本归为一类后,我们要计算类间距离就又得需要一个计算方式,我们定义任意两类间的距离为两类中每组数据距离的最小值: - f5 s: X7 |0 A% ^4 e7 P " Z5 u( i( N1 N2 y0 b7 @: c4 [6 T1 p$ D, U& Z1 G5 i4 X
: C" ~) } D! U: c) D- }4 D5 w; U# A. H: t
A- ~9 n3 s7 J; g
9 W2 W, {8 Y- v; Z& O2 `$ l' l$ B# m! g 7 s7 B1 [7 l$ b4 I 因此,可以得到任意两个销售员的数据距离矩阵: + q4 p" ]5 H/ I6 i1 T2 [& O% E0 J5 D7 n" w+ Y! ]
s% D! d- t2 d7 c. M% g
0 e d$ N) q# U' {" C
Step1 首先,最相近的两组样本是w1和w2,他们的距离为1,所以先将其聚为一类; + b: k! c( W# F & O+ v# w+ c' [2 S5 u, TStep2 然后,剩下的样本为{w1,w2},w3,w4,w5,我们发现除了距离1之外,最相似的是 w3,w4,他们的距离为2,所以将其聚为一类; 2 X4 I+ y7 e7 AStep3 然后,剩下的样本为{w1,w2},{w3,w4},w5,我们发现除了距离1,2之外,最相似的 是{w1,w2}和{w3,w4},他们的距离以 w2和w3的距离为准,距离为3,所以将这两类聚为一类; 3 L4 U4 y- o" N' f6 X' b/ o- e
Step4 最后,剩下的样本为{w1,w2,w3,w4},w5,只剩最后两类了,所以最后一类为 {w1,w2,w3,w4,w5},类间距以w3/w4与w5的距离4为准。 , a0 y0 X' J# J) d - s" V" [; h. z8 p0 l5 x 代码如下:%% 编程实现clc;clear;close all8 g, B/ Z" E% D+ I% p! `
data = [1,0;1,1;3,2;4,3;2,5];%原始数据0 z5 s9 T3 |* i' I7 q* b6 I- c& ?
[m, ~] = size(data);5 m8 O3 H$ h+ z& z4 c9 m6 z
d = mandist(data');%求任意两组数据的距离 2 E f1 p! W! l0 A4 ~; ld = tril(d);%取下三角区域数据 ) X5 p% k8 R/ l% _! And = nonzeros(d);%去除0元素 ) p2 r2 _4 {5 d) N1 vnd = unique(nd);%去除重复元素 4 ]- Z& g" N) B+ V for i = 1 : m-1 3 @' }8 ]5 i( e6 y& o k nd_min = min(nd);0 {" [5 j4 W# E7 f c/ k: }
[row, col] = find(d == nd_min); z+ }. W& P8 y0 n
label = union(row,col);%提取相似的类别 ( F2 j4 K9 Y7 p# h% A9 O) x6 }& e label = reshape(label, 1, length(label));%将类别标签转化成行向量 0 Z. {9 t7 a+ [+ v2 S$ O/ G disp(['第',num2str(i),'次找到的相似样本为:',num2str(label)]); ' J. v9 s' o5 E \* w" Q nd(nd == nd_min) = [];%删除已归类的距离 6 ?2 ~* @9 W/ e/ G if isempty(nd)%如果没有可分的类就停止 # o7 H0 I( T) ]- S* E break 2 M9 d* S9 I( r6 H4 J9 D+ v end G+ d' _. G5 D/ m5 q6 D' T& W( k
end* h2 i O* C% \4 ?& j Y" Q2 ^
%% 工具箱实现. O+ l; C3 y! a
clc;clear;close all $ h: ~" H; H7 ldata = [1,0;1,1;3,2;4,3;2,5];%原始数据 8 q$ ?1 c5 A+ A) Ay = pdist(data,'cityblock');%计算任意两样本的绝对值距离 : ~$ \9 L. D: \: A% i4 zyc = squareform(y);%将距离转化成对称方阵1 K6 v$ C; i2 C- |0 A
z = linkage(y);%生成聚类树* z \9 c% s1 ?9 v) k, J% {$ w! X H3 s
[h, t] = dendrogram(z);%画出聚类树) S" X) E1 ^; C8 e$ V
n = 3;%最终需要聚成多少类 7 G2 z$ C% i" C3 kT = cluster(z, 'maxclust', n);%分析当分n类时,个样本的标签 . [0 `& D9 x2 o: _for i = 1 : n * L T8 a, Q6 e2 U9 V label = find(T == i);- h Q1 h/ z! \: v$ o `
label = reshape(label, 1, length(label)); : [0 {, g& X3 `9 ]- E p disp(['第',num2str(i),'类有:',num2str(label)]); 5 e- R' n" k+ D8 u- zend + [0 {$ c- g8 W 结果如下: . K5 o* i( w- M7 n% a8 G# Q5 Y2 Z: ]# n* n2 _& i
--------------------- 9 w" D0 A+ C F8 S; ` J# G ! h7 _. t/ S8 Y7 A5 S: D3 W; ?' [: O- W4 z Y. _
" e" Q# a( y# \* ~/ A
6 L R( f$ [8 u* B' K