第十八讲 距离和相似系数2dSij=expd:距离，s:相似系数
第十八讲 距离和相似系数 1 𝑠𝑖𝑗 = exp − 1 2 𝑑𝑖𝑗 2 𝑑: 距离，𝑠: 相似系数
内积：相似度向量内积向量内积(x,y) = xTy = Zxiyi衡量两个向量x,y的相似性，当yαx时相似度最大。假设矩阵Xnxp，Ynxg的行代表样本，列代表变量，则XTYX = (x(1)., X(p), Y = (y(1),..,y(g), XTY = (x()y()描述了X,Y列向量/变量之间相似性，其(i,j)元x)yG)代表X(),y)之间的相似性。如果X,Y是列中心化的，则碧=Sxy 是样本协方差矩阵。所以协方差或相关系数都是某种相似度量。Y = X时, X = (x(1),., X(p)) = (X1, ., Xn)T→XTX=(x)×G)描述X各列(变量)之间的相似性;*XXT=(x,x)描述了样本(X的行)之间的相似性。2
2 内积：相似度 向量内积 𝐱, 𝐲 = 𝐱 ⊤𝐲 = σ 𝑥𝑖𝑦𝑖 衡量两个向量 𝐱, 𝐲 的相似性，当𝐲 ∝ 𝐱时相似度最大。 假设矩阵 𝑋𝑛×𝑝, 𝑌𝑛×𝑞 的行代表样本，列代表变量，则 𝑋 = 𝐱 1 , . , 𝐱 𝑝 ，𝑌 = (𝐲 1 , . , 𝐲 𝑞 )，𝑋 ⊤𝑌 = 𝐱(𝑖) ⊤ 𝐲(𝑗) 描述了𝑋, 𝑌列向量/变量之间相似性，其 (𝑖,𝑗) 元 𝐱(𝑖) ⊤ 𝐲(𝑗) 代表 𝐱 𝑖 , 𝐲(𝑗)之间的相似性。 如果𝑋, 𝑌是列中心化的，则 𝑋 ⊤𝑌 𝑛−1 = 𝑆𝐱𝐲 是 样本协方差矩阵。所以协方差或相关系数都是某种相似度量。 向量 内积 𝑋 ⊤𝑌 𝑌 = 𝑋时，𝑋 = 𝐱 1 , . , 𝐱 𝑝 = (𝐱1, . , 𝐱𝑛) ⊤ 𝑋 ⊤𝑋 = 𝐱(𝑖) ⊤ 𝐱(𝑗) 描述𝑋各列(变量)之间的相似性； 𝑋𝑋 ⊤ = 𝐱𝑖 ⊤ 𝐱𝑗 描述了样本 (𝑋的行)之间的相似性
这里的“因子”与例1.(1)n个p-水平属性变量(因子变量)的one-hotembedding因子分析中的“因子”含义不同。X1,,XnERP，其中xi分量中仅有一个1，其余全是0。记X = (X1,.,Xn)T = (xij), X1p = 1pxij=1，若样本取第j个水平记X第i列的总和rj==1xii=水平j的样本个数，水平之间互，X不同列内积为0（不相似）：0rXTX =.0例如因子变量size 取值大、中、小，n=5 次观测为大、小、小、中、大，以示性变量表示，样本矩阵X如下大中小001000201X=00XTX-001XXT02000100
3 例1. 1 𝑛个𝑝-水平属性变量(因子变量)的 one-hot embedding 𝐱1, . , 𝐱𝑛 ∈ 𝑅 𝑝 , 其中𝐱𝑖分量中仅有一个1，其余全是0。记 𝑋 = (𝐱1, . , 𝐱𝑛) ⊤ = (𝑥𝑖𝑗), 𝑋𝟙𝑝 = 𝟙𝑝 记𝑋第𝑗列的总和 𝑟𝑗 = σ𝑖=1 𝑛 𝑥𝑖𝑗 = 水平 𝑗 的样本个数， 水平之间互斥，𝑋不同列内积为0（不相似）： 𝑋 ⊤𝑋 = 𝑟1 ⋯ 0 ⋮ ⋱ ⋮ 0 ⋯ 𝑟𝑝 ， , 0 0 2 0 1 0 2 0 0 1 0 0 0 1 0 0 0 1 0 0 1 1 0 0 X X X ， T 1 0 0 0 1 0 0 0 1 0 0 1 1 0 0 0 1 1 0 0 1 0 0 0 1 T XX 大 中 小 例如因子变量 size 取值大、中、小， 𝑛 = 5 次观测为大、小、小、中、大， 以示性变量表示，样本矩阵𝑋如下 𝑥𝑖𝑗 = 1，若样本 𝑖取第 𝑗 个水平 这里的“因子”与 因子分析中的“因 子”含义不同
(2）假设n个样本，每个样本有两个因子变量x,y，各有p,q个水平x1..x和y1,Yg，则数据one-hot表示为n×（p+q)矩阵X1p = 1pZ = (X,Y),Y1g = 1q其中X=(xi),Y=(yi)分别是第一、二个因子的one-hot表示。记r=XT1,c=T1分别为X，Y的列边际总和，则同(1)XTX = diag(r) ≤ Dr, YTY = diag(c) 二 Dc而W =XTY= (wWik),其G,k)元Wjk=n=1xiiyik=#[x,y水平各为,k的样本个数)则W=XTY是两个因子x,y交叉分类得到的列联表：yi,.yqx1r = XTIn = XTYIg = W1g:W=XTYrC= YTIn = YTX1p = WT1,XpC74
4 (2) 假设𝑛个样本 ，每个样本有两个因子变量𝑥, 𝑦，各有 𝑝, 𝑞个水平𝑥1,., 𝑥𝑝和𝑦1,., 𝑦𝑞，则数据one-hot表示为𝑛 × (𝑝 + 𝑞)矩阵 𝑍 = (𝑋, 𝑌), 其中𝑋 = (𝑥𝑖𝑗), 𝑌 = 𝑦𝑖𝑗 分别是第一、二个因子的one-hot表示 。 记 𝐫 = 𝑋 ⊤𝟙, 𝐜 = 𝑌 ⊤𝟙分别为𝑋， 𝑌的列边际总和，则同(1), 𝑋 ⊤𝑋 = 𝑑𝑖𝑎𝑔(𝐫) ≜ 𝐷𝐫 , 𝑌 ⊤𝑌 = 𝑑𝑖𝑎𝑔(𝐜) ≜ 𝐷𝐜 而𝑊 = 𝑋 ⊤𝑌 = (𝑤𝑗𝑘), 其 (𝑗, 𝑘) 元 𝑤𝑗𝑘 = σ𝑖=1 𝑛 𝑥𝑖𝑗𝑦𝑖𝑘 = #{𝑥, 𝑦 水平各为𝑗, 𝑘 的样本个数} 则𝑊 = 𝑋 ⊤𝑌是两个因子𝑥, 𝑦交叉分类得到的列联表： 𝐫 𝐜 ⊤ 𝑊 = 𝑋 ⊤𝑌 𝐫 = 𝑋 ⊤ 𝟙𝑛 = 𝑋 ⊤𝑌𝟙𝑞 = 𝑊𝟙𝑞 𝐜 = 𝑌 ⊤ 𝟙𝑛 = 𝑌 ⊤𝑋𝟙𝑝 = 𝑊⊤ 𝟙𝑝 𝑋𝟙𝑝 = 𝟙𝑝 𝑌𝟙𝑞 = 𝟙𝑞 𝑦1, ., 𝑦𝑞 𝑥1 ⋮ 𝑥𝑝
综上，WD.XTXXTYZTZ :WTW=XTYyTXD.YTY1zTz ER(p+a)×(p+Q)是所有x.,xp;y.,yg的内积相似度矩阵，其中我们主要关心W。C例如，n=5，每个个体有两个因子变量：x（size：大中小），y（weight：轻、重）sizeweight重轻大中小大中小重轻010I0大(20020列联表0001中0OXTYxix0Z=(X,Y)=010=小7100YxY'Y00011重02210010轻300
5 ， 1 0 0 1 1 0 0 1 1 0 1 0 0 0 1 0 0 0 1 0 0 1 1 0 0 Z (X ,Y) 大 中 小 重 轻 size weight 例如，𝑛 = 5, 每个个体有两个因子变量: 𝑥 (size:大中小), 𝑦 (weight:轻、重) 0 1 1 0 3 2 0 1 2 0 0 0 2 1 1 0 1 0 0 1 2 0 0 2 0 轻 重 小 中 大 大 中 小 重 轻 Y X Y Y X X X Y Z Z T T T T T 列联表 综上， 𝑍 ⊤𝑍 = 𝑋 ⊤𝑋 𝑋 ⊤𝑌 𝑌 ⊤𝑋 𝑌 ⊤𝑌 = 𝐷𝐫 𝑊 𝑊⊤ 𝐷𝐜 𝑍 ⊤𝑍 ∈ 𝑅 𝑝+𝑞 × 𝑝+𝑞 是所有 𝑥1,., 𝑥𝑝；𝑦1,., 𝑦𝑞的内积相 似度矩阵，其中我们主要关心𝑊。 𝐫 𝐜 ⊤ 𝑊 = 𝑋 ⊤𝑌
记Zc=(Xc,Y）=(X-IrT/n,Y-1cT/n)为Z的列中心化，则(SxxSxy)(xTXeXTY)-(Dr-rrT/nW-rcT/n(n - 1) (YT X。YTYe)=(WT-crT/n D-ccT/nSyxSyy))其中W-rcT/nW.是W的双向中心化，而W的中心标准化为W, = D=1/2W.D-1/2*Pearons独立性/齐一性检验的卡方统计量X2 = nllW,ll12[W,I, amax(W,)?*对应分析：W,奇异值分解：W,=D-1/2WeD=1/2=UDVTF = D-1/2UD, G = D-1/2VD,biplot：取F[,1:2],G[,1:2]分别作为因子x,y的二维表示，plot(FL,1:2)points(G[,1:2])6
6 记𝑍𝑐 = 𝑋𝑐 , 𝑌𝑐 = 𝑋 − 𝟙𝐫 ⊤/𝑛, 𝑌 − 𝟙𝐜 ⊤/𝑛 为 𝑍 的列中心化，则 其中 𝑊 − 𝐫𝐜 ⊤/𝑛 ≜ 𝑊𝑐是𝑊的双向中心化，而𝑊的中心标准化为 𝑊𝑠 = 𝐷𝐫 −1/2𝑊𝑐𝐷𝐜 −1/2 |𝑊𝑠 |, 𝜆𝑚𝑎𝑥 𝑊𝑠 ? (𝑛 − 1) 𝑆𝐱𝐱 𝑆𝐱𝐲 𝑆𝐲𝐱 𝑆𝐲𝐲) = 𝑋𝑐 ⊤ 𝑋𝑐 𝑋𝑐 ⊤ 𝑌𝑐 𝑌𝑐 ⊤ 𝑋𝑐 𝑌𝑐 ⊤ 𝑌𝑐 = 𝐷𝐫 − 𝐫𝐫 ⊤/𝑛 𝑊 − 𝐫𝐜 ⊤/𝑛 𝑊⊤ − 𝐜𝐫 ⊤/𝑛 𝐷𝐜 − 𝐜𝐜⊤/𝑛 Pearons独立性/齐一性检验的卡方统计量 𝑋 2 = 𝑛 𝑊𝑠 2 对应分析： 𝑊𝑠奇异值分解：𝑊𝑠 = 𝐷𝐫 −1/2𝑊𝑐𝐷𝐜 −1/2 = 𝑈𝐷𝑉 ⊤ 𝐹 = 𝐷𝐫 −1/2 𝑈𝐷, 𝐺 = 𝐷𝐜 −1/2 𝑉𝐷, biplot: 取 𝐹[, 1: 2], 𝐺[, 1: 2] 分别作为因子 𝑥, 𝑦 的二维表示， plot(F[,1:2]) points(G[,1:2])
通过例1的分析，我们可以这样理解对应分析口列联表的欧氏表示：通过one-hotembedding把列联表W中的所有入体用欧氏向量表示出来。口对欧氏表示的方差-协方差矩阵应用主成分分析对于一般的相似度矩阵或丰度矩阵可以类似地处理
7 通过例1的分析，我们可以这样理解对应分析： 列联表的欧氏表示：通过 one-hot embedding 把 列联表 𝑊 中的所有个体用欧氏向量表示出来。 对欧氏表示的方差-协方差矩阵应用主成分分析 对于一般的相似度矩阵或丰度矩阵可以类似地处理
相似度和距离相似度或邻近程度：proximity，similarity，closeness距离或相异度：distance，dissimilarity有些问题相似度容易定义，另一些问题距离可能更容易确定两者是相反的概念。距离表示两个物体的相异程度。满足数学定义的距离比较容易相似度定义，最常用的是欧氏距离。但在某些问题中，“距离”代表和距离主观感知的远近程度，未必满足距离的数学定义。相似度或相似系数代表两个物体的相似程度，在数学上没有严格定义。在实际应用中通常以欧氏内积或相关系数作为相似度，有时以距离的减函数定义。凭主观感知打分的相似度也很常见，尤其是研究对象不可测量的时候。无论哪种方式定义，距离或相似度一般都是对称的。基于相似/相异系数的方法：聚类分析、多维标度法、配列等。8
8 相似度和距离 距离表示两个物体的相异程度。满足数学定义的距离比较容易 定义，最常用的是欧氏距离。但在某些问题中，“距离”代表 主观感知的远近程度，未必满足距离的数学定义。 相似度或相似系数代表两个物体的相似程度，在数学上没有严 格定义。在实际应用中通常以欧氏内积或相关系数作为相似度， 有时以距离的减函数定义。凭主观感知打分的相似度也很常见， 尤其是研究对象不可测量的时候。 相似度 和距离 无论哪种方式定义，距离或相似度一般都是对称的。基于相 似/相异系数的方法：聚类分析、多维标度法、配列等。 相似度或邻近程度：proximity， similarity，closeness 距离或相异度：distance，dissimilarity 有些问题相似度容易定义，另一些问题距离可能更容易确定， 两者是相反的概念
相似对于可测量的情形，通常以内积或者相关概念定义相似度。对于没系数有具体测量的情形，两个研究对象的相似系数通常根据具体问题给出或主观印象打分评定。假设两个对象的测量为向量xy，根据具体问题背景，相似系数s(x,y)可以定义为与内积或距离有关的函数：内积: s(x,y) = cxTy, s(x,y) = cxTy/ lxllyll·距离的减函数，比如高斯核函数将距离转化为相似系数：s(x,y) = exp(-Ix -yll2例2.假设x,y都是长度为p的0-1序列，x = 110100y=010010下述相似系数都与。s(x,y)=xTy/p=1匹配的比例=1/6.· s(x,y)=[xTy+(1-x)T(1-y)]/p=1或0匹配的比例=3/6.·s(x,y)= xTy/Z1(xi+yi>0)= 1/4(都是o的位置不统计在内)
9 对于可测量的情形，通常以内积或者相关概念定义相似度。对于没 有具体测量的情形，两个研究对象的相似系数通常根据具体问题给 出或主观印象打分评定。 相似 系数 例2. 假设 𝐱, 𝐲都是长度为𝑝的0-1序列， 𝐱 = 110100 𝐲 = 010010 下述相似系数都与 • 𝑠 𝐱, 𝐲 = 𝐱 ⊤𝐲/𝑝 = 1匹配的比例=1/6. • 𝑠 𝐱, 𝐲 = [𝐱 ⊤𝐲 + 𝟏 − 𝐱 ⊤ 𝟏 − 𝐲 ]/𝑝 = 1或0匹配的比例=3/6. • 𝑠 𝐱, 𝐲 = 𝐱 ⊤𝐲/σ 1(𝑥𝑖+𝑦𝑖> 0) = 1/4 (都是0的位置不统计在内). 假设两个对象的测量为向量𝐱, 𝐲, 根据具体问题背景，相似系 数𝑠(𝐱, 𝐲)可以定义为与内积或距离有关的函数： • 内积： 𝑠 𝐱, 𝐲 = 𝑐𝐱 ⊤𝐲, 𝑠 𝐱, 𝐲 = 𝑐𝐱 ⊤𝐲/ 𝐱 𝐲 • 距离的减函数，比如高斯核函数将距离转化为相似系数： 𝑠 𝐱, 𝐲 = exp − 1 2 𝐱 − 𝐲 2
例3.（不同“相似性”的定义）下面图（a)中的16张扑克牌。(b）根据花式区分，相同的花式是相似的：(c)根据颜色区分，同色的相似；(d)主牌相似、副牌相似。inusis(bridge例4，各种语言在历史上不断演变或相互影响，研究语言之间的关系有助于了解历史上文化发展融合过程。语言的相似性可以体现在多方面，主要体现在发音，其中数字1,2....9，10的读音颇具代表性。汉字在日本分音读和训读（本地）两种读法，在越南分汉语词和纯越词两种读法。下表是粤语（南越、唐话）、越南（汉越）、日语（音读）的数字读音：数字13468910572粤语baseilaocha相似度7/10yisayasanggaotupthatbat越南(汉越)nhatnhingulucciruthaptamchaba粤语seilaosayayinggaosa相似度4/10ichini日语（音读）shi,yonroku shichi,nana hachikujuusango10
10 例3.（不同“相似性”的定义） 下面图(a)中的 16张扑克牌。 (b) 根据花式区分，相同的花式是相似的； (c) 根据颜色区分，同色的相似； (d) 主牌相似、副牌相似。 ♦♥ 例4. 各种语言在历史上不断演变或相互影响，研究语言之间的关系有助 于了解历史上文化发展融合过程。语言的相似性可以体现在多方面，主 要体现在发音，其中数字1,2,.,9, 10的读音颇具代表性。汉字在日本分音 读和训读（本地）两种读法，在越南分汉语词和纯越词两种读法。下表 是粤语（南越、唐话）、越南（汉越）、日语（音读）的数字读音： 数字 1 2 3 4 5 6 7 8 9 10 粤语 ya yi sa sei ng lao cha ba gao sa 越南(汉越) nhất nhì tam tư ngũ lục thất bát cửu thập 粤语 ya yi sa sei ng lao cha ba gao sa 日语(音读) ichi ni san shi,yon go roku shichi,nana hachi ku juu 相似度7/10 相似度4/10