快捷搜索:  as  test  1111  test aNd 8=8  test++aNd+8=8  as++aNd+8=8  as aNd 8=8

和记娱乐App_集报网



1.测度定义

“数学上,测度(Measure)是一个函数,它对一个给定聚拢的某些子集指定一个数,这个数可以比作大年夜小、体积、概率等等。传统的积分是在区间长进行的,后来人们盼望把积分推广到随意率性的聚拢上,就成长出测度的观点,它在数学阐发和概率论有紧张的职位地方”——wikipedia

聚类之前必然要定义好向量之间的相似程度——即隔邻测度。在聚类历程中我们应用的测度,范围要更广泛,首先定义向量之间的测度,接着便是聚拢与向量,聚拢之间的测度。

对付X上的不相似测度(Dissimilarity Measure, DM) d 是一个函数: 此中R是实数聚拢,假如d有以下的属性:

(1.1)

(1.2)

(1.3)

假如又满意

(1.4)

(1.5)

那么d被称为度量DM。此中的公式(1.5)也叫三角不等式。稍稍解释一下(着实太好理解了),不相似性测度着实就像我们说的间隔一样,两个向量代表两个工具好了。公式1.2定义(向量)工具自己和自己的间隔是d0;公式1.1阐清楚明了随意率性两个工具之间的间隔要小于正无穷却大年夜于自己和自己的间隔(你和别人的间隔大年夜于你和自己的间隔,这不废话吗^_^);公式1.3阐明间隔的交互性;公式1.4不说清楚明了,公式1.5便是三角不等式(初中水平)。

同理相似性测度(Similarity Measure, SM)和记娱乐App定义为满意:

(1.6)

(1.7)

(1.8)

假如又满意

(1.9)

(1.10)

就把s叫做度量SM。详细同DM,各公式的表达一清二楚哦~~~

从定义和字面上我们都可以看出二者的不合,在表达相似性时两者都可以,只不过度量的角度不合,对付判别相似,DM越大年夜阐明越不相似,越小则越相似,而SM却恰恰相反,是以我们也可以遐想,DM与SM可以使用这种对立关系来定义。举例来说,假如d是一个DM,那么s=1/d便是一个SM。

2. 向量之间的隔邻测度

上面的定义只是一个宏不雅的概括,那么详细的向量之间的测度若何谋略呢?下面将具体的先容。

首先对付实向量的不相似测度,实际利用中最通用的便是加权lp度量了:

(2.1)

此中的xi和yi分手是向量x和y中的第i个值,wi是第i个权重系数,l是向量的维数(以下公式定义同)。而我们对照感兴趣的便是当p=1时,该度量便是加权Manhattan范数,而当p=2时便是加权欧几里得范数,当p=∞时便是max1£i£和记娱乐App;l wi|xi-yi|了。根据这些DM,我们定义SM为bmax - dp(x,y)。

别的还有一些其他的定义措施,比如

(2.2)

(2.3)

其他懒得列出了,先查阅资料,这里不胪陈了。

对付实向量的相似性测度,实际中常用的有:

内积:(2.4)

Tanimoto测度:(2.5)

其他:(2.6)

------------------------------------------------take a nap------------------------------------------------------------

对付离散值的向量,首先必须要搞清楚一个观点,这里在《模式识别》的中文译作中我感到翻译的并不好理解,以是这里展开阐明一下,那便是一个叫做相依表(contingency table)的观点。对付一个向量x,其元素值属于有限集F={0,1,…,k-1},此中k是正整数。令A(x,y)=[aij], i, j=0,1,…,k-1是一个k阶方阵,此中元和记娱乐App素aij代表在x中所有i值所在的位置在y的同样位置有j值的个数。附原文:the number 和记娱乐Appof places where x has the i-th symbol and y has the j-th symbol。举例来说吧,k=3,且x=[0,1,2,1,2,1],y=[1,0,2,1,0,1],那么A(x,y) = [0 1 0, 1 2 0, 1 0 1]。以第一个0(a00)为例阐明,0在A中的位置抉择i=0,j=0,在x中0所在的位置是第一个位置,而y中0所在的位置为第二个和第五个,两个向量中没有相同位置上的相同0元素,是以A中第一个元素a00为0,而A中第二个为1(a01),以是i=0,j=1,在x中0所在的位置是第一个,而y中1所在的位置为第一、四、六个,是以有一个相同,以是a01=1。

关于谋略矩阵A这里附加java代码实现,可参考:

1/** *//**

2 *

3 * @param k

4 * the number of finite set F

5 * @param x

6 * the vector x belongs to F^l

7 * @param y

8 * the vector y belongs to F^l

9 * @return the contingency table A

10 * @author $Jia Yu

11 */

12 public Integer[][] calContingencyTable(Integer k, Vector x,

13 Vector y) {

14 if (x.size() != y.size())

15 throw new IllegalArgumentException(

16 "The two vectors are not the same size!");

17 Integer[][] A = new Integer[k][k];

18 Integer count_ij;

19 for (int i = 0; i 汉明间隔:(2.7)

L1间隔:(2.8)

同样,相似性测度有

Tanimoto测度:(2.9)

此中的nx( ny)表示x(y)中非零元素的个数。

书籍每每教给我们的是根基而不是利用,这些根基常识在实际利用中才会获得更多的改进和变更。大概我们不会简单的在聚类中利用这些测度观点,然则繁杂的组合都是滥觞于根基。是以,对测度的根基观点必然要紧紧把握。在前一阶段做图像瓜分时,聚类算法履行的条件之一测度,我就做过多个实验,L1和L2范数,Tanimoto测度等。当然不合的图像特性有不合的谋略间隔措施,总之实际的履历奉告我,根基踏实后,在利用起来是相称的顺手啊~~~(最最少不会被繁杂公式吓到)

3. 特殊环境处置惩罚

斟酌到实例向量的特性类型每每是繁杂混杂的,这种环境下,若何谋略隔邻测度呢?一些偷懒的做法便是将所有值都看作是实值类型,把混杂向量算作实向量来处置惩罚。然则现实应用中,这样做的效果每每差强人意。斟酌将实值类型转换成离散类型,这便是闻名的离散化了,特性的离散化操作时特性或属性过滤(filter)的一个紧张的方面。当然我最保举的照样基于自己开拓的利用处景,设计相关的隔邻测度。这样和记娱乐App可能通用性对照差,然则假如是问题驱动的话,或者目标驱动,那么这个作为一个solution也不掉精良性。当然引入隐隐测度的观点也是一种办理措施,这里就不细说了,详细利用可以参看有关隐隐和不确定性的文章。别的一点必要阐明便是实例向量中部分特性损掉的环境,对付损掉数据,假如我们知道数据的散播,那么合理假设是一个替代规划,然则假如为了省事,常用的做法是直接丢弃该实例向量,或者好点的做法是取所有实例的匀称数据作为该维度的替代数据。

4. 点与聚拢之间的测度

跟着聚类历程的赓续进行,层次徐徐深入,聚类已经不仅仅是判断点与点之间的相似程度了,点与聚拢的相似程度也必要谋略。而若何定义向量x和聚类C之间的隔邻性,从而判断是否将x归类为C。以下三个定义常常用到。

最大年夜隔邻函数Max proximity function: (4.1)

最小隔邻函数Min proximity function:(4.2)

匀称隔邻函数Average proximity function:(4.3)

此中nc是聚拢C的势。

可以看到,这样的定义在观点理论层次上仍然将点视作点,将聚类视作聚拢。另一种环境则是将聚类视作一个点,由于点与点之间的隔邻测度已经可以谋略,那么将聚拢视为一个点,就将这个问题归约到了点与点之间的问题了。对聚类进行表达,主要有以下几种表达:

1)点表达:将聚类视作一个点,可所以均值点(mean vector),也可所以均值中间(mean center),也可所以中值中间(median center)。关于这几个观点和公式,任何的统计课本里都有阅读,我就不逐一罗列了。(主要贴公式真的很累,怀念Tex)

2)超平面表达:线性聚类中常用。不表。有兴趣者去查资料。

3)超球面表达:球形聚类中常用。同上。

统统的进修都为利用,根据实际利用的不合,我们在定义这种点与聚拢之间测度时刻也有很大年夜的机动性。

5. 聚拢与聚拢之间的测度

同样的,对付聚拢与聚拢的测度,可以同点与聚拢的测度类似。只要记着一点,那便是聚拢与聚拢间的隔邻测度是建立在点与点之间的测度的根基上的。以是隔邻测度的根基在点与点之间。当然聚类结果的优化是一个反复试验的历程,此中也要斟酌领域专家的意见。

6. 小结

对付隔邻测度的进修,乍一看像是纯数学常识的进修,着实则是对我们开始聚类算法钻研之前的一个夯实根基的复习历程。

7. 参考文献及保举涉猎

[1]Pattern Recognition Third Edition, Sergios Theodoridis, Konstantinos Koutroumbas

[2] http://zh.wikipedia.org/wiki/%E6%B5%8B%E5%BA%A6%E8%AE%BA

[3]模式识别第三版, Sergios Theodoridis, Konstantinos Koutroumbas著, 李晶皎, 王爱侠, 张广源等译

免责声明:以上内容源自网络,版权归原作者所有,如有侵犯您的原创版权请告知,我们将尽快删除相关内容。

您可能还会对下面的文章感兴趣: