非监督分类PPT演示课件

.,1,非监督分类,电子科技大学师 君,.,2,相似性度量均值聚类向量量化最大流/最小割其它分类方法,.,3,分类基本的精神活动发现样本之间的联系，相似性，差异性,非监督分类,将物品按照用途分类,生物、化学分类,.,4,非监督聚类：根据相似性，对样本空间进行划分。硬聚类模糊聚类谱系聚类,非监督分类,.,5,分类分类的多样性。,非监督分类,.,6,距离测度定义在特征空间特征空间到实数的函数：,相似性测度,.,7,常用距离测度：范数距离：任意范数可以定义距离。其他距离测度：,相似性测度,.,8,常用距离测度：Hamming距离：。,相似性测度,.,9,编辑距离（Levenshtein/EDIT 距离）：将序列A变为序列B的所有可能方法中，代价最小的一个。,相似性测度,.,10,寻找最短编辑距离遍历法,相似性测度,.,11,寻找最短编辑距离图的最短路径问题动态规划法：阶段：步数状态：已处理节点集一步可达的新节点。代价：1,相似性测度,.,12,栅格图：横轴为目标字符串，纵轴为起始字符串。节点标注了所有可能状态状态为：节点横轴取值（包含）合并纵轴取值（不包含）（注意前后顺序）水平、垂直边权重为1；某节点水平与垂直对应符号相同其左下对角边权重为0，否则为1；对角边权重为0的两个状态相同；,相似性测度,.,13,.,14,编辑距离的性质：三角不等性： ED(x,y) ED(x,z) + ED(z,y)。分裂不等性：ED(x,y) ED(x1.i,y1.j)+ED(xi+1.n,yj+1.m)ED(x,y) m（目标与源字符串长度大的一个）ED(x,y) m-nED(x,y)=0 iff x=y如果两字符串等长， ED(x,y) HD(x,y)（海明距离）,相似性测度,.,15,DamerauLevenshtein距离除了替换、插入、删除外，允许交换相邻两个字符的位置。/wiki/Damerau%E2%80%93Levenshtein_distance,相似性测度,.,16,相似性测度,相似性测度,.,17,常用相似测度：内积：Tanimoto测度：,相似性测度,.,18,点到集合的距离：最大距离：最小距离：平均距离：,相似性测度,.,19,点到平面的距离（支持向量机）点到二次曲面的距离：二次曲面：代数距离：,相似性测度,.,20,垂直距离：求解z得到：,相似性测度,.,21,径向距离（椭圆集特有）：,相似性测度,.,22,归一化径向距离（椭圆集特有）：通过线性变换，将椭圆变成正圆，计算正圆距离为：归一化径向距离：归一化距离与径向距离关系。,相似性测度,.,23,集合到集合的距离：最大距离：最小距离：平均距离：重心距离：,相似性测度,.,24,相似性度量均值聚类向量量化最大流/最小割其它分类方法,.,25,回顾KNN分类器：已知类中心聚类（监督分类），x属于到各类重心最近的类。,均值聚类,clear allclose allclcN = 300;% 产生样本for iii = 1 : N if iii 200) data(:, iii) = randn(2, 1) + -3; 4; else data(:, iii) = randn(2, 1) + -3; -4; endendfigure; plot(data(1, :), data(2, :), ro)% Nc = 3; c1 = 3; 4;c2 = -3; 4;c3 = -3; -4;cnt1 = 1;cnt2 = 1;cnt3 = 1;for iii = 1 : N dist(1) = norm(data(:, iii) - c1, 2); dist(2) = norm(data(:, iii) - c2, 2); dist(3) = norm(data(:, iii) - c3, 2); a, b = min(dist); switch b case 1 Class1(cnt1) = iii; cnt1 = cnt1 + 1; case 2 Class2(cnt2) = iii; cnt2 = cnt2 + 1; case 3 Class3(cnt3) = iii; cnt3 = cnt3 + 1; endendfigure; hold on;plot(data(1, Class1), data(2, Class1), ro)plot(data(1, Class2), data(2, Class2), bo)plot(data(1, Class3), data(2, Class3), ko),.,26,问题：非监督聚类还需要得到类中心。K/c均值聚类：目标：取定c类，选取c个初始聚类中心，即代表点。按最小距离原则将各样本分配到离代表点最近的一类中，不断重新计算类中心，调整各样本类别，最终使聚类准则函数Je最小。,均值聚类,.,27,C/K均值聚类：C（K）均值：对类中心进行动态调整。1. 选择任意数据作为初始类中心，2. 最小距离分类3. 更新类中心为各类中心4. 迭代，直到类中心不发生变化。,动态聚类,clear allclose allclcN = 300;% 产生样本K = 2;for iii = 1 : N if iii 200) data(:, iii) = K * randn(2, 1) + -3; 4; else data(:, iii) = K * randn(2, 1) + -3; -4; endendfigure; plot(data(1, :), data(2, :), ro)% Nc = 3; Ni = 30;P = randperm(N);c1 = data(:, P(1);c2 = data(:, P(2);c3 = data(:, P(3);epss = 0.00001;figure;for kkk = 1 : Ni cnt1 = 1; cnt2 = 1; cnt3 = 1; clear Class1 Class2 Class3 for iii = 1 : N dist(1) = norm(data(:, iii) - c1, 2); dist(2) = norm(data(:, iii) - c2, 2); dist(3) = norm(data(:, iii) - c3, 2); a, b = min(dist); switch b case 1 Class1(cnt1) = iii; cnt1 = cnt1 + 1; case 2 Class2(cnt2) = iii; cnt2 = cnt2 + 1; case 3 Class3(cnt3) = iii; cnt3 = cnt3 + 1; end end c11 = sum(data(:, Class1).). / cnt1; c22 = sum(data(:, Class2).). / cnt2; c33 = sum(data(:, Class3).). / cnt3; if (norm(c11 - c1) 分类-更新参数-分类，过程与EM算法类似，属于一类迭代算法。,均值聚类,.,29,特征空间变换：如果数据分布不具有各项同性，分类前需要对数据进行变换。等价于变换距离测度：马氏距离：,均值聚类,.,30,逐个样本进入聚类器，每个类竞争该样本，得到该样本的类更新参数。参数更新公式：竞争胜出者：竞争失败者：竞争学习是一种更新策略，相对于K均值分类的“批量模式”，竞争学习为“在线模式”，可用于各种具体方法。,竞争学习,.,31,K均值聚类的竞争学习：参数c为类中心，如果希望在竞争到新样本后类中心为包含该样本的类中心，则迭代公式为：竞争胜出者：竞争失败者：,竞争学习,.,32,一般地，应满足：,竞争学习,.,33,竞争学习,clear allclose allclcN = 300;% 产生样本K = 1;for iii = 1 : N if iii 200) data(:, iii) = K * randn(2, 1) + -3; 4; else data(:, iii) = K * randn(2, 1) + -3; -4; endendfigure; plot(data(1, :), data(2, :), ro)% Nc = 3; Ni = 30;P = randperm(N);data1 = data;for iii = 1 : 300 data(:, iii) = data1(:, P(iii);endc1 = data(:, P(1);c2 = data(:, P(2);c3 = data(:, P(3);epss = 0.00001;cnt1 = 1;cnt2 = 1;cnt3 = 1;figure;h2 = 0.0000;for iii = 1 : N dist(1) = norm(data(:, iii) - c1, 2); dist(2) = norm(data(:, iii) - c2, 2); dist(3) = norm(data(:, iii) - c3, 2); a, b = min(dist); switch b case 1 Class1(cnt1) = iii; cnt1 = cnt1 + 1; c1 = (cnt1 - 1) * c1 + data(:, iii) / cnt1; c2 = c2 + h2 * (data(:, iii) - c2); c3 = c3 + h2 * (data(:, iii) - c3); case 2 Class2(cnt2) = iii; cnt2 = cnt2 + 1; c1 = c1 + h2 * (data(:, iii) - c1); c2 = (cnt2 - 1) * c2 + data(:, iii) / cnt2; c3 = c3 + h2 * (data(:, iii) - c3); case 3 Class3(cnt3) = iii; cnt3 = cnt3 + 1; c1 = c1 + h2 * (data(:, iii) - c1); c2 = c2 + h2 * (data(:, iii) - c2); c3 = (cnt3 - 1) * c3 + data(:, iii) / cnt3; end hold off; plot(c1(1), c1(2), r+, markersize, 10, linewidth, 2) hold on; plot(c2(1), c2(2), b+, markersize, 10, linewidth, 2) plot(c3(1), c3(2), k+, markersize, 10, linewidth, 2) try plot(data(1, Class1), data(2, Class1), ro) end try plot(data(1, Class2), data(2, Class2), bo) end try plot(data(1, Class3), data(2, Class3), ko) end pause(0.1);end,.,34,相似性度量均值聚类向量量化最大流/最小割其它分类方法,.,35,向量量化,连续-离散映射将连续样本空间映射为离散空间，使得失真最小。映射函数：失真误差：样本在连续空间中均匀分布，则均匀划分。样本集中处，应该划分的更密集，样本稀疏处，应该划分更粗略。,.,3