ibanana

箭厂胡同文创空间/META-PROJECT​(13张)

辛几何&李代数

康威常数2

康威常数2

六、具体的应用:&1&,&2&和&3&的比例先解释一下这里&应用&的意思。许多读者看到这个理论的第一个(或第二个第三个……)反应也许会是&那这个理论在实际中有什么用途呢&?边说边看理论中的&说&&看&过程其实是一种被称为&游程编码&的编码方式。这种编码方式有时被用作数据压缩的方式,如在一些图像格式中。也许因为是这个原因,康威的论文在第二次发表时,刊登在一本和... 阅读全文

六、具体的应用:“1”,“2”和“3”的比例

先解释一下这里“应用”的意思。许多读者看到这个理论的第一个(或第二个第三个……)反应也许会是“那这个理论在实际中有什么用途呢“?

边说边看理论中的“说”“看”过程其实是一种被称为“游程编码”的编码方式。这种编码方式有时被用作数据压缩的方式,如在一些图像格式中。也许因为是这个原因,康威的论文在第二次发表时,刊登在一本和通信有关的学术论文集上。(第一次发表在剑桥大学数学学会的会刊Eureka上。)如果要强调边看边说理论有什么实际应用,也许这是个好的切入点。

不过我觉得这理论其实并没有什么实际用途,至少到目前为止没看见它有。它的价值在于它的美,而它的美源于它起源的质朴和内容的(相对)深刻以及形式的奇诡之间的强烈对比。一个数学理论,它是美的,这就是很好的价值了。

本节和后面所说的“应用”,是用康威的理论去回答一些问题。这些问题并不依赖于理论而存在;从原则上说,以直接产生边看边说序列再作观察的方式也能回答这些问题;但从现实上这样做非常困难,或根本不可能。本节想问的问题就是,从1开始的边看边说序列,它的第100,或是第1000000项有多少个数字,其中分别有多少“1”,“2”和“3”?

用直接写出每一项的方法,我们很容易计算出这个序列的前面几项的长度:

 

1, 2, 2, 4, 6, 6, 8, 10, 14, 20, 26, 34, 46, 62, 78, ……

 

但是这个直接生成数字串并作统计的方法会变得越来越困难,所需要的计算量和储存空间越来越大。根据算术定理,序列长度以指数增长。取康威常数为1.3,以非常粗略的方式估计,它的第100项的长度大约会是1.3100≈2×1011,也就是千亿这个数量级,生成新数字串的计算量变得非常大。而它的第1000项的长度则要超过10100,此时光是储存数字串也变得不可能,因为可观测宇宙内的原子总量据估计也仅有1080个。如果我们想知道第1000000项数字串有多长,其中分别有多少“1”,“2”和“3”,靠直接生成数字串的方法是完全不可行的。

但通过康威理论,这个问题就容易解决了。

我们知道,从数字串1开始的边看边说序列在第8项演化成由一个72铪元素和一个50锡元素组成的化合物。从这一天起,通过查询元素列表中的“一天后衰变物”一栏,每天演化出来的化合物中的各元素数量都可以通过前一天化合物中各元素的数量来计算:比如说,如果前一天的化合物中有100个31镓元素,那么次日的化合物中就会因此产生100个1氢元素,200个20钙元素,100个30锌元素,100个63铕元素和100个89锕元素。由分割的原理,化合物中的每一个元素都可以看作是在独立演化而不和化合物中其他(同种或不同种的)元素的演化过程相互干扰。92种元素中的每一种都可如此算出次日产生的元素数量,求和后就可得出次日产生的化合物中每种元素的含量。下面给出了第8项到第20项以及第99和第100项的结果:

康威常数2

接下来当然就很简单了,统计一下每种元素里“1”,“2”和“3”的数量,乘以化合物中此种元素的数量,再分别相加,就得到了化合物中“1”,“2”和“3”的数量。计算的结果是,第100项有511247092564个数字,其中有253103530928个"1",63796211233个"2"和94347350403个"3"。“1”,“2”和“3”在此项中的比例大约分别是49.507084658%,32.038560926%和18.454354416%。(上面这三个百分比相加不严格等于100%,因为分别有尾数的四舍五入。下同。) 注意到这个结果和我们上面粗略的估计千亿这个数量级是相符的。

对第100项可以这样算,对第1000000项也同样可以这样算,没有什么原则上的不同。只是对第1000000项来说,其中所含的元素数量实在太多,如果在编程时使用普通的32位或64位甚至128位的整数类形来表示是远远不够的,必须使用支持任意长度整数的数据类型,比如Java语言中的BigInteger。不过在此无法将这些数字具体写出来:第1000000项的长度以十进制数表示出来的话会有115137位,写出来将是一本中篇小说的篇幅。“1”,“2”和“3”的数量也一样无法具体写出,它们在此项中的比例分别约为49.507077868%,32.038585700%和18.454336321%。

看来当项数比较大时,“1”,“2”和“3”在数字串中的比例会趋向定值。这其实是算术引理的推论。因为随着项数趋于无穷,各元素在数字串中的比例趋近于它的丰度。以每种元素中“1”,“2”和“3”的数目乘以它的丰度,再分别相加能得到三个数字a,b和c,将它们归一化操作(即分别除以a+b+c)后就得到了当项数趋于无穷时“1”,“2”和“3”的比例的理论值,结果是约49.507077857%,32.038585734%和18.454336411%,和上面的结果相符。

我们可以问,为什么上面使用的计算长度的方法要比直接产生此项数字串再统计其长度的暴力法的计算速度快得多。因为在这种方法中,元素之间的顺序这个信息被省略而不参与计算。在前面的表中,我们只知道每一项化合物中每种元素有多少,但不知道它们分别处于化合物的什么位置。依照化学中表示物质组成的化学式来作比方的话,直接产生某项数字串类似于要知道物质的结构式,而上面的计算则只是得到了物质的实验式。而我们要知道数字串的长度或是其中“1”,“2”和“3”的数量,却恰恰并不需要知道元素之间的顺序。

 

七、具体的应用:第1000000项的某位数字

前面一节中的计算因省略计算元素之间的信息而变得迅速,但康威的理论也同样能帮助我们快速地知道,以1开始的边说边看序列的某项数字串的某个具体位置的数字是什么。

比如我们可以计算出,序列的第1000000项是以“132113213221133112”开始的。这我们甚至可以用手算:它的第8项以72铪开头,于是第9项以71镥开头,然后依次以70镱,69铥,68铒,67钬,66镝,65铽开头,第16项又以67钬开头,我们发现了67钬→66镝→65铽→67钬……这个循环,所以此后所有3n的项都以65铽开头,3n+1的项都以67钬开头,3n+2的项都以66镝开头,于是第999999项以65铽开头,而第1000000项以65铽一天后的衰变物,也就是6764钆开头。要计算第1000000项是以什么结尾的可用类似办法。这其实是起首引理和结尾引理的推论。

任意给定自然数n,要计算第1000000项数字串的第n位是什么数字则比较麻烦一点,但原则上来说也不难,当然一般不能用手算。序列在第8项演化成7250锡。而按照前面的方法,我们可以精确计算72铪演化1000000-8=999992天后产生的化合物的长度d;如果d大于等于n,那么原问题就转化为72铪演化999992天后数字串第n位是什么数字,反之则转化为50锡演化999992天后数字串第n-d位数字是什么。这种方法可以一直继续下去直到求出结果:当化合物中有超过一个元素时,我们求出第一个元素最终产物的长度,以便知道我们感兴趣的那一位数字是否由它产生,如果不是,则可以抛弃这个元素(并修正所求数字所在的位数);当化合物中只有一个元素,则将其代换为它一天后的衰变物,再重复这个步骤。

上面的算法的具体实现则需要一点技巧,因为单独一次计算某元素在若干天后产物的长度虽然并不耗时,但如果每次使用都需要重新计算的话,所用的总时间也是惊人的。所以可以预先计算,要用时再查表。可是如果所有计算结果都储存的话,需要的空间相当大(大概超过2To)。笔者采用折衷的方式,储存每隔1000天的结果,将所需空间削减为原需的千分之一,中间结果则在需要时再当场计算填充。具体的程序实现属于编程和算法问题,在此就不详细介绍了。在一台并不很新的个人电脑上,笔者的程序用大约20分钟生成上面所说的元素产物长度表格,每回答一个“第1000000项数字串中间第n位是什么”的问题则需要大约10分钟。计算结果:序列从第1040000位开始的几个数字是3222112,它其实是一个3锂元素的结尾部分;第1090000位开始的几个数字是312,它其实是一个23钒元素的结尾部分。

八、线性代数的语言

现在我们来讨论本文最有意思的部分,关于算术定理的证明。这部分证明必须用到线性代数的知识,所以从现在起我假设读者了解线性代数的一般知识。

根据元素列表中的“一天后衰变物”一栏,我们定义一个92×92的矩阵M,它在第i行第j列处的值为第j号普通元素一天后衰变物中的第i号普通元素的数量。比如说1氢的一天后衰变物仍是1氢,于是矩阵的第1列只有在第1行处的值为0,其余均为0;而31镓的一天后衰变物是63208912030锌,于是M的第31列在第1、30、63和89行处的值为1,在第20行处的值为2,在其余行处的值为0。我们把这个矩阵称为边看边说矩阵

矩阵M的规模比较大,在网页上不容易完整地表示出来。好在它的元素很简单,大多数是0,其余的基本都是1,只有一个值是2,所以我们可以用下图中点阵的方式来表示这个矩阵,其中每个白点表示此处值为0,黑点表示1,红点表示2。

康威常数2

M的点阵表示

矩阵M包含了普通化合物演化的几乎所有信息。说“几乎”是因为它和第六节中的计算一样,忽略了演化过程中各元素间顺序的信息。对任意一个普通化合物C,我们都可以写出一个有92个分量的列向量u来,它的第i个分量是C中第i号普通元素的数量,我们称它为普通化合物C对应的向量

任何一个普通化合物C,如果它在次日演化成C',那么容易看出,C'对应的向量u'=Mu,也就是说“左乘M”代表了“演化1天”的操作(但是忽略了元素次序)。想知道C'再过一天的演化结果所对应的向量,只要在u'左边再乘以一个M,所以是M2u,这是C演化2天后所得化合物对应的向量。如此下去,C在第n天的演化结果所对应的向量就是Mnu这就把(忽略了元素顺序的)普通化合物演化过程完全地用线性代数的语言表述出来

比如第六节中那个表格现在就可以用矩阵的语言相当简明地表达。令u是第50、72分量为1,其余分量为0的列向量(对应于第8天的普通化合物7250锡),“化合物中元素个数”一栏表述的其实就是向量Mn-8u的各个分量,其中n是以1开始的边看边说序列的项数。

于是我们可以用线性代数的语言和工具来表述和研究边看边说序列的演化问题。算术定理叙述的,实际上就是当n趋向于无穷时,矩阵Mn的性质。康威在论文中提到的Perron–Frobenius定理,就是这样一个阐述矩阵的幂的极限性质的定理。我们先来看一下它的经典形式。

 

九、Perron–Frobenius定理

如果A是一个其中元素都是正实数的m阶正方矩阵。Perron–Frobenius定理断言,A的特征多项式必定有一个单的正实根μ,而且它严格大于所有其他的根的绝对值(其他的根有可能是复数)。我们知道这个根μ是A的一个特征值,Perron–Frobenius定理说,它必定有一个所有分量都是正实数的特征向量v。因为μ是单根,所以它的特征空间是1维的,就是由v生成的。

当我们说一个矩阵的“特征向量”时,我们通常指的是它的特征向量,也就是说Avvv是一个列向量(或可以说是一个m×1的矩阵)。但A同样也有关于μ的特征向量w,它可以看作是A的转置矩阵tA的(右)特征向量的转置,是一个行向量(或可以说是一个1×m的矩阵),满足wAww当然也可取成其中分量都是正实数的,而且我们还增加一个要求,要求wv=1(行向量乘以列向量的结果可以看作是一个数,也叫这两个向量的内积),这可以通过将w乘以合适的系数做到。

 

Perron–Frobenius定理进一步说,当自然数n趋向于无限时,矩阵序列{(1/μn)An}的极限是矩阵vw(不要和上面的wv=1的要求搞混了,列向量乘以行向量的结果是m阶正方矩阵)。

这实在是一个非常漂亮的定理!要是它适用于边看边说矩阵M的话,Mn在n趋于无穷时的性质就可以通过计算M的特征值和特征向量得到,算术定理也就唾手可得了。

很遗憾,至少是在康威写作论文的那个时代,Perron–Frobenius定理对M并不适用——它的系数充满了不是正数的0。Perron–Frobenius定理也存在着其他一些形式。在某些形式里,条件被放宽为矩阵的元素可以是大于或等于0的实数,但矩阵必须是不可约的或是对称的,或是存在某个k使得Mk的元素都严格大于0,这些也是M所不能满足的——因为M显然不对称,而由于1氢元素的性质,M的第一列除了第一项外都等于0,这使得它是可约的,而且对任何自然数n,Mn的第一列除了第一项外也都等于0。

在这里岔开去说一点,Perron–Frobenius定理是相当有用的一个定理。在实际当中我们常会碰到元素均大于0或是均大于等于0的矩阵,最常见的有马尔科夫链的状态转移矩阵和图论中的邻接矩阵。Google公司搜索引擎的核心技术PageRank(网页排名)就是基于转移矩阵理论和对上面所说的那个特征值的计算,而Perron–Frobenius定理则保证了这个特征值的存在性。从理论上来说,Google要对付的那个矩阵的行和列数,和它搜集的网页数相等,是当之无愧的巨无霸矩阵。如何对它作特征值计算,大概是Google最重要的商业秘密之一,当然这是本文的题外话了。

十、加强版算术定理

因为前面所说的那些形式的Perron–Frobenius定理都不能应用于边看边说矩阵M,于是康威就在论文中用直观的方法证明了一个猴版的结论,也就是前面介绍的算术定理。之所以称它是“猴版”,是因为其结论是不完全的。它只是说,从任何一个普通化合物开始,每一步演化得到的数字串的长度和上一步相比,越来越趋近于康威常数λ,却没有对演化n天后的数字串的长度作直接的估算。下面这幅11钠,29铜和62钐开始演化后30天内序列中数字串长度的统计图很直观地显示了这个定理的正确性。注意到图中纵轴是对数坐标轴,指数函数在这样的坐标系中的图像是直线。随着项数的增长,图中的三条曲线很快都近似直线。三条直线的斜率都一样,通过算术定理我们知道这斜率就是康威常数λ。

康威常数2

长度的增长

但是算术定理无法说明的是,三条直线高低不同的位置是由什么决定的。如果把三条直线所对应的指数函数写成y=cλn的形式,我们就要问:对于每种不同的普通化合物,它所对应的c是由什么决定的,如何计算呢?下面的表中,我们对若干项n计算了以上述三种普通元素开始的边看边说序列的“演化n天后数字串的长度/λn”的值,也即上述c的经验值:

演化天数112962
09.00000006.00000006.0000000
19.20543826.13695886.1369588
28.23862014.70778299.4155658
38.12572596.32000909.0285843
48.31120756.92600638.3112075
57.43830765.313076910.094846
66.92880356.521226810.596994
76.56586336.87852359.3798047
86.23604325.756347510.553304
95.51976066.255728710.855529
105.22232546.77490879.5977873
205.29914806.12589489.9309221
505.29850206.050634010.037356
1005.29939126.050388710.035343
10005.29939036.050390710.035341
100005.29939036.050390710.035341
1000005.29939036.050390710.035341

看来,与11钠,29铜,62钐相对应的c值应该分别大约是5.2993903,6.0503907和10.035341。29铜和62钐的长度都是6,可是对应的c值却差许多;11钠的长度是9,可是对应的c值却反而小于29铜和62钐的。也就是说,从两个初始长度相同的化合物出发,接着用相同时间演化出来的化合物长度可以差许多,甚至有可能初始长度长的化合物,接下去演化出来的化合物的长度反而短。算术定理无法告诉我们这是为什么,更不能对每种化合物预言和它对应的c值。

康威的论文写于1980年代。二十多年后,代数学家们对Perron–Frobenius定理的研究更加深入,与其说现在我们有Perron–Frobenius定理,不如说我们有Perron–Frobenius理论,我们拥有了当年康威所没有的工具。文献[2]中的定理2.4简直就是为边看边说矩阵M量身定造的。它说,如果一个n阶实系数正方矩阵A有一个绝对值最大的正特征值,而且和它相关的左右特征向量都可以取分量非负的话,那么前面Perron–Frobenius定理中所叙述的“当自然数n趋向于无限时,矩阵序列{(1/μn)An}的极限是矩阵vw”的结论同样成立。

注意到在原版Perron–Frobenius定理中,关于存在绝对值最大的正特征值以及正分量的左右特征向量的命题,是结论的一部分,在上面的定理中则成了条件的一部分。对于矩阵M,这个条件是可以独立计算和验证的。关于矩阵的特征多项式、特征值和特征向量的理论,是线性代数的基础知识,在此我就不重复了。

康威证明了,M的92次的特征多项式可以被因式分解,去掉那些根为0或±1的因子,剩下的就是我们在算术定理中看到的那个71次多项式。下图是这个多项式的解的图示,最右方红点即康威常数λ。

康威常数2

71次多项式的解。图中心为原点,每一小格边长为0.5

在这里值得一提的是幂法求特征值的迭代算法(具体方法可以以“幂法 特征值”为关键词在网上查询)。本来这个算法有点鸡肋,因为它只能求绝对值最大的特征值(如果改变一下也可求绝对值最小的特征值,称为反幂法),所以如果要求所有的特征值就不适用了。可是这里我们恰恰只需要求绝对值最大的特征值,用求所有特征值的算法求出一堆特征值来到反而还得另去筛选出绝对值最大的来,反而麻烦。而且幂法能同时求出这个特征值和相关的特征向量。这简直是要睡觉就有人送上了枕头!笔者用这个方法轻松地就求出了M这个绝对值最大的特征值小数点后三百位的值和精确程度类似的相应的特征向量,虽然这么精确的数据其实没什么大用处。

于是我们就有了比原版算术定理更强的
加强版算术定理
1) 边看边说矩阵M有一个在其所有特征值中绝对值最大的特征值λ。λ为正实数,是M的特征多项式的单根。
2) M有一个关于λ的,分量都是正实数的,分量之和为1的(右)特征向量v,我们称v丰度向量
3) M有一个关于λ的,分量都是正实数的左特征向量w,满足wv=1。我们称w富度向量
4) 当自然数n趋向于无限时,矩阵序列{(1/λn)Mn}的极限为矩阵vw

事实上定理中的λ就是康威常数λ。在原版定理中它是一个神秘的71次多项式的根;而在加强版定理中,它被明确为边看边说矩阵的唯一的绝对值最大的特征值。下面我们来看看如何由上述加强版定理推导出原版算术定理。

注意到在文献[2]定理2.4中,v并不是被唯一确定的,而是可以被乘以任意一个正实数,而在上述加强版定理中,对丰度向量v有一个“分量之和为1”的附加要求,v就被唯一确定了。正如它的名字所暗示的,v的各个分量就是各普通元素的丰度:第1个分量对应着1氢的丰度,第2个分量对应着2氦的丰度,等等。

富度向量w因此也被唯一确定,我们可以定义第n号普通元素的富度w的第n个分量。从线性代数的观点来看,wv是相对于同一个特征值的左右特征向量,是对偶的数学对象,所以我们可以把丰度和富度看作是对偶的概念。丰度的英文为abundance,于是和它对偶的富度可以反译回去称作coabundance。

我们不仅可以对普通元素定义其富度,而且可以对一般的普通化合物定义它的富度:普通化合物的富度就是组成它的普通元素的富度之和(同一种元素多次出现则对其富度多次求和)。比如化合物63208912030锌的富度就等于63铕、89锕、1氢、30锌的富度加上两倍20钙的富度。上述定义可以用线性代数的语言简单地写为:令C是一种普通化合物,设它所对应的列向量是u,那么它的富度就是富度向量wu的内积wu

在讨论富度的实际意义前,我们先列出所有普通元素的长度、丰度和富度:

元素长度丰度富度
120.09179038325.6080827086
2320.00323729693.2519030758
3270.00422006662.4945994020
4420.00226388604.4173991800
5340.00295115043.3886745994
6280.00384705252.5995195528
7240.00501493021.9941430512
8180.00653734911.5297467197
9140.00852193971.1734990753
10120.01110900680.9002144354
1190.01448144880.6905723633
12100.01885044121.0642759581
13100.02457300670.8164272141
1470.03203281300.6262975226
15120.01489588671.5173799538
16100.01941793921.1640122836
1760.02531278420.8929369292
1840.03299717010.6849896438
1940.04301436090.5254691533
2020.05607254310.4030978184
21160.00930209742.2191977577
22140.01212600281.7023906526
2380.01580718161.3059376632
2450.02060588261.0018107052
25120.02686136021.2489541407
2680.03501585850.9580975139
2750.04564587730.7349756218
2880.01387112421.0277878559
2960.01808208220.7884364666
3030.02357139130.6048252645
31170.00144789062.3774502059
32230.00188743722.8607239388
33262.72462160762.7242698891
34203.55175479442.0898415106
35164.62998681521.6031589076
36146.03554556821.2298150218
37107.86780000890.9434155159
3871.02562852490.7237127697
3971.33698603150.7923865601
40231.74286459972.2353942193
41282.27195867522.9203125825
42202.96167368522.2402297523
43153.86077049431.7185247131
44213.28994805762.3970976690
45244.28870150422.8757958978
46185.59065379452.2060801198
47127.28784920561.6923278521
48109.50027456451.2982182892
4980.00123843420.9958890202
5050.00161439470.7639662365
5170.00210448821.1205778552
52130.00274336301.9384007646
53180.00357618562.5239203970
54140.00466183431.9361494381
5580.00607706121.4852586679
5660.00792191881.1393714076
5750.01032683330.8740344241
58100.01346182521.5435278845
5980.01754852931.1840708803
6060.02287586390.9083242769
6130.02982045620.6967935837
6260.01540811521.3077219948
6370.02008566871.0031795014
64110.02166297281.6425976370
65160.02823935892.2970039458
66120.03681218641.7620773240
6770.04798752941.3517244937
6890.00109859561.5714588817
69140.00120490842.0785360303
70100.00157069121.5944862492
7160.00204751731.2231620535
7250.00266909700.9383118918
73322.42077366663.2519030758
74273.15566552522.4945994020
75421.69288018084.4173991800
76342.20680012293.3886745994
77282.87673447752.5995195528
78243.75004567391.9941430512
79184.88847429831.5297467197
80146.37250397551.1734990753
81128.30705132930.9002144354
8290.00108288830.6905723633
83100.00141162861.0642759581
84100.00184016700.8164272141
8570.00239879980.6262975226
86120.00312702091.5173799538
87100.00407631341.1640122836
8860.00531378950.8929369292
8940.00692693520.6849896438
9040.00758190470.5254691533
9120.00988359860.4030978184
9211.02562852490.3092243383

任取一种普通化合物C,设它所对应的列向量是u,那么n天后C演化成的化合物所对应的列向量就是Mnu。根据加强版算术定理的3),我们知道当n趋于无穷时,(1/λn)Mnu会趋于vwu。所以对Mnu在n充分大时的性质的研究可以转化为对vwu的性质的研究。

因为矩阵的乘法满足结合律,所以vwu=v(wu),而上面我们已经知道,wuwu的内积,即化合物C的富度,它是一个实数,令它为d,则vwu=dv。这证明了从任何一种普通化合物出发,Mnu在n充分大时和λndv差不多;也就是说,经过足够长时间后,它里面的各元素的百分比就会趋近于丰度向量的各分量。这就是原版算术定理中“每种元素在这些数字串中的比例越来越趋近一个大于0的常数值”这一部分。

我们定义量长向量是这样的行向量,它的各分量分别为各普通元素长度:(2, 32, 27, 42, ……),记它为r。那么容易看出u所对应的化合物的数字串长度就是ru。所以量长向量有测量化合物长度的功能。r和丰度向量v的内积则是一个常量,记它为L,我们可称其为量长常数。(如果滥用一下术语,我们可以说L是丰度向量v所对应的化合物的数字串长度。当然不可能真有哪种化合物所对应的向量会是v,因为v的分量都不是整数,甚至不是有理数。)根据上面的表格容易计算出L≈7.6739102369。对应于Mnu的化合物的长度为rMnu,它约等于rvwuλn=drvλn=dLλn。换句话说,当n相当大时,dLλn是C在n天后演化结果的长度的很好的估计。

这下我们看出来了,dL就是对本节开始想求的c,即化合物的富度乘以量长常数。对11钠,29铜和62钐来说,其富度乘以量长常数的值分别约为5.2993903280,6.0503906721和10.0353412031。这三个数字和前面计算的经验值完全符合。

严格地写成命题的话就有:
量长推论)令普通化合物C的富度为d,它在第n天后演化结果的长度为hn,那么当n趋向于无穷时,dLλn/hn趋向于1,其中L为量长常数。

从这个结论很容易推出原版算术定理中“从任何一个普通化合物开始,每一步演化得到的数字串的长度和上一步相比,越来越趋近于固定常数λ”这部分。于是原版算术定理完全得证。

十一、更多的推论

一件有趣的事情是,如果我们将上面的r由量长向量换成每个分量都是1的行向量(1, 1, 1, 1, ……),那么ru就是u所对应的化合物中的元素个数(于是这个向量我们可以类似地称为计件向量,即以“件数”来称呼化合物中元素的个数),而rv精确地等于1(可称其为计件常数,滥用一下术语的话,丰度向量v所对应的化合物中恰好有1件元素)。对应于Mnu的化合物中的元素件数为rMnu,它约等于rvwuλn=drvλn=dλn。即在n相当大时,dλn是C在n天后演化结果中元素件数的很好的估计。

严格地写成命题的话就有:
计件推论)令普通化合物C的富度为d,它在第n天后演化结果中的元素件数为sn,那么当n趋向于无穷时,dλn/sn趋向于1。

如果再翻译回原版定理的说法,那就是“从任何一个普通化合物开始,每一步演化得到的元素个数和上一步相比,越来越趋近于固定常数λ。”事实上,这才是原版中的原版。康威的论文中的算术定理就是以化合物中元素个数为对象论证的,而不是象在本文上篇中那样,以化合物长度为对象。

这下我们达到了思路广的境界——量长和计件向量只是两个特定的向量而已,而每给定一个92个分量的行向量,上面的论证都可以被照葫芦画瓢地小小改编一下得到一个相应的推论。当然,这个行向量如果随便给就太没意思了,我在下面提几个有某种实际意义的例子。

令C是一个普通化合物,我们定义它的重量是它的所有数字之和。比如1氢的重量是2+2=4,11钠的重量是1+2+3+2+2+2+1+1+2=16。那么我们可以定义称重向量为各分量是各元素重量的行向量(4, 56, 47, 72, ……),定义称重常数则是称重向量和丰度向量v的内积,约等于12.964860969。我们有
称重推论)令普通化合物C的富度为d,它在第n天后演化结果的重量为wn,那么当n趋向于无穷时,dLλn/hn趋向于1,其中L为称重常数。

类似地我们可以引入“计1向量”、“计2向量”和“计3向量”,其分量分别是各元素中的“1”、“2”和“3”的个数,同样可定义“计1常数”、“计2常数”和“计3常数”,得到类似上面推论的“计1推论”、“计2推论”和“计3推论”。

十二、附记

如果对照康威原论文和本文内容的话,读者会发现在定理和引理的叙述方面有一些不同,最明显的是本文的化学定理变成是完全关于普通化合物的命题了,原本其中关于包含任意字符的数字串的部分,被移动到宇宙学定理中。这样的改动主要是出于科普文介绍的方便,康威从文章一开始就考虑包含任意字符的数字串,而笔者则需要注意循序渐进,以及将不同难度的问题分开。



收起全文

辛几何&李代数

数据挖掘十大经典算法

数据挖掘十大经典算法

一、 C4.5C4.5算法是机器学习算法中的一种分类决策树算法,其核心算法是ID3 算法. C4.5算法继承了ID3算法的优点,并在以下几方面对ID3算法进行了改进:1) 用信息增益率来选择属性,克服了用信息增益选择属性时偏向选择取值多的属性的不足;2) 在树构造过程中进行剪枝;3) 能够完成对连续属性的离散化处理;4) 能够对不完整数据进行处理。C4.5... 阅读全文

 

 一、 C4.5  
C4.5算法是机器学习算法中的一种分类决策树算法,其核心算法是ID3 算法.   C4.5算法继承了ID3算法的优点,并在以下几方面对ID3算法进行了改进:  
1) 用信息增益率来选择属性,克服了用信息增益选择属性时偏向选择取值多的属性的不足;  
2) 在树构造过程中进行剪枝;  
3) 能够完成对连续属性的离散化处理;  
4) 能够对不完整数据进行处理。  
C4.5算法有如下优点:产生的分类规则易于理解,准确率较高。其缺点是:在构造树的过程中,需要对数据集进行多次的顺序扫描和排序,因而导致算法的低效。

1、机器学习中,决策树是一个预测模型;他代表的是对象属性与对象值之间的一种映射关系。树中每个节点表示某个对象,而每个分叉路径则代表的某个可能的属性值,而每个叶结点则 
对应从根节点到该叶节点所经历的路径所表示的对象的值。决策树仅有单一输出,若欲有复数输出,可以建立独立的决策树以处理不同输出。  
2、 从数据产生决策树的机器学习技术叫做决策树学习,  通俗说就是决策树。  
3、决策树学习也是数据挖掘中一个普通的方法。在这里,每个决策树都表述了一种树型结构,他由他的分支来对该类型的对象依靠属性进行分类。每个决策树可以依靠对源数据库的分割 
进行数据测试。这个过程可以递归式的对树进行修剪。当不能再进行分割或一个单独的类可以被应用于某一分支时,递归过程就完成了。另外,随机森林分类器将许多决策树结合起来 
以提升分类的正确率。 

决策树是如何工作的?   
1、决策树一般都是自上而下的来生成的。  
2、选择分割的方法有好几种,但是目的都是一致的:对目标类尝试进行最佳的分割。 
3、从根到叶子节点都有一条路径,这条路径就是一条―规则  
4、决策树可以是二叉的,也可以是多叉的。  
对每个节点的衡量:  
1)         通过该节点的记录数  
2)         如果是叶子节点的话,分类的路径  
3)         对叶子节点正确分类的比例。  
有些规则的效果可以比其他的一些规则要好。  
由于ID3算法在实际应用中存在一些问题,于是Quilan提出了C4.5算法,严格上说C4.5只能是ID3的一个改进算法。相信大家对ID3算法都很.熟悉了,这里就不做介绍。  
C4.5算法继承了ID3算法的优点, 并在以下几方面对ID3算法进行了改进:  
1) 用信息增益率来选择属性,克服了用信息增益选择属性时偏向选择取值多的属性的不足; 
2) 在树构造过程中进行剪枝;  
3) 能够完成对连续属性的离散化处理;  
4) 能够对不完整数据进行处理。  
C4.5算法有如下优点:产生的分类规则易于理解,准确率较高。其缺点是:在构造树的过程中,需要对数据集进行多次的顺序扫描和排序,因而导致算法的低效。此外,C4.5只适合于 
能够驻留于内存的数据集,当训练集大得无法在内存容纳时程序无法运行。  来自搜索的其他内容:  
 C4.5算法是机器学习算法中的一种分类决策树算法,其核心算法是ID3算法.  分类决策树算法是从大量事例中进行提取分类规则的自上而下的决策树. 决策树的各部分是:  
             根:    学习的事例集.  
             枝:    分类的判定条件.  
             叶:    分好的各个类.  

  ID3算法  
   1.概念提取算法CLS  
1)      初始化参数C={E},E包括所有的例子,为根.  
2)        IF      C中的任一元素e同属于同一个决策类则创建一个叶子      
               节点YES终止.  
           ELSE      依启发式标准,选择特征Fi={V1,V2,V3,...Vn}并创建  
                       判定节点  
   
划分C为互不相交的N个集合C1,C2,C3,...,Cn;  
3)      对任一个Ci递归.  
    2.      ID3算法  
1)      随机选择C的一个子集W    (窗口).  
2)      调用CLS生成W的分类树DT(强调的启发式标准在后).  
3)      顺序扫描C搜集DT的意外(即由DT无法确定的例子).  
4)      组合W与已发现的意外,形成新的W.  
  
  
5)      重复2)到4),直到无例外为止.  
   
启发式标准:  
       只跟本身与其子树有关,采取信息理论用熵来量度.  
       熵是选择事件时选择自由度的量度,其计算方法为  
               P    =    freq(Cj,S)/|S|;  
       INFO(S)=    -    SUM(    P*LOG(P)    )    ;        SUM()函数是求j 从1到n和.  
       Gain(X)=Info(X)-Infox(X);  
       Infox(X)=SUM(    (|Ti|/|T|)*Info(X);  
为保证生成的决策树最小,ID3 算法在生成子树时,选取使生成的子树的熵(即Gain(S))最小的 
的特征来生成子树.  
   
  3、  ID3算法对数据的要求  
1).      所有属性必须为离散量.  
2).      所有的训练例的所有属性必须有一个明确的值.  
3).      相同的因素必须得到相同的结论且训练例必须唯一.  
   
   C4.5对ID3算法的改进:  
       1.      熵的改进,加上了子树的信息.  
             Split_Infox(X)=    -    SUM(      (|T|/|Ti|    )    *LOG(|Ti|/|T|)      );  
             Gain    ratio(X)=      Gain(X)/Split    Infox(X);  
        2.      在输入数据上的改进.  
         1)  
因素属性的值可以是连续量,C4.5 对其排序并分成不同的集合后按照ID3 算法当作离散量进 行处理,但结论属性的值必须是离散值.  
       2)    训练例的因素属性值可以是不确定的,以    ?    表示,但结论必须是确定的  
       3.      对已生成的决策树进行裁剪,减小生成树的规模. 

二、数据挖掘十大经典算法(2) k-means  
术语“k-means”最早是由James MacQueen在1967年提出的,这一观点可以追溯到1957年 Hugo Steinhaus所提出的想法。1957年,斯图亚特·劳埃德最先提出这一标准算法,当初是作为一门应用于脉码调制的技术,直到1982年,这一算法才在贝尔实验室被正式提出。1965年, E.W.Forgy发表了一个本质上是相同的方法,1975年和1979年,Hartigan和Wong分别提出了一个更高效的版本。 
算法描述 
输入:簇的数目k;包含n个对象的数据集D。 
输出:k个簇的集合。 
方法: 
从D中任意选择k个对象作为初始簇中心; 
repeat; 
根据簇中对象的均值,将每个对象指派到最相似的簇; 
更新簇均值,即计算每个簇中对象的均值; 
计算准则函数; 
until准则函数不再发生变化。 
算法的性能分析 
   1)优点 
(1)k-平均算法是解决聚类问题的一种经典算法,算法简单、快速。 
(2)对处理大数据集,该算法是相对可伸缩的和高效率的,因为它的复杂度大约是O(nkt),其中n是所有对象的数目,k是簇的数目,t是迭代的次数。通常k<<n。这个算法经常以局部最优结束。 
(3)算法尝试找出使平方误差函数值最小的k个划分。当簇是密集的、球状或团状的,而簇与簇之间区别明显时,它的聚类效果很好。 
   2)缺点 
(1)k-平均方法只有在簇的平均值被定义的情况下才能使用,不适用于某些应用,如涉及有分类属性的数据不适用。 
(2)要求用户必须事先给出要生成的簇的数目k。 
(3)对初值敏感,对于不同的初始值,可能会导致不同的聚类结果。 
(4)不适合于发现非凸面形状的簇,或者大小差别很大的簇。 
(5)对于"噪声"和孤立点数据敏感,少量的该类数据能够对平均值产生极大影响。 
算法的改进 
针对算法存在的问题,对K-means算法提出一些改进: 
一是数据预处理, 
二是初始聚类中心选择, 
三是迭代过程中聚类种子的选择。 
1、首先对样本数据进行正规化处理,这样就能防止某些大值属性的数据左右样本间的距离。给定一组含有n个数据的数据集,每个数据含有m个属性,分别计算每一个属性的均值、标准差对每条数据进行标准化。 
3、其次,初始聚类中心的选择对最后的聚类效果有很大的影响,原K-means算法是随机选取k个数据作为聚类中心,而聚类的结果要是同类间尽可能相似,不同类间尽可能相异,所以初始聚类中心的选取要尽可能做到这一点。采用基于距离和的孤立点定义来进行孤立点的预先筛选,并利用两两数据之间的最大距离在剩余数据集合中寻找初始聚类中心。但对于实际数据,孤立点个数往往不可预知。在选择初始聚类中心时,先将孤立点纳入统计范围,在样本中计算对象两两之间的距离,选出距离最大的两个点作为两个不同类的聚类中心,接着从其余的样本对象中找出已经选出来的所有聚类中心的距离和最大的点为另一个聚类中心,直到选出k个聚类中心。这样做就降低了样本输入顺序对初始聚类中心选择的影响。 
聚类中心选好以后,就要进行不断的迭代计算,在K-means算法中,是将聚类均值点(类中所有数据的几何中心点)作为新的聚类种子进行新一轮的聚类计算,在这种情况下,新的聚类种子可能偏离真正的数据密集区,从而导致偏差,特别是在有孤立点存在的情况下,有很大的局限性。在选择初始中心点时,由于将孤立点计算在内,所以在迭代过程中要避免孤立点的影响。这里根据聚类种子的计算时,采用簇中那些与第k-1轮聚类种子相似度较大的数据,计算他们的均值点作为第k轮聚类的种子,相当于将孤立点排除在外,孤立点不参与聚类中心的计算,这样聚类中心就不会因为孤立点的原因而明显偏离数据集中的地方。在计算聚类中心的时候,要运用一定的算法将孤立点排除在计算均值点那些数据之外,这里主要采用类中与聚类种子相似度大于某一阈值的数据组成每个类的一个子集,计算子集中的均值点作为下一轮聚类的聚类种子。为了能让更多的数据参与到聚类中心的计算种去,阈值范围要包含大多数的数据。在第k-1轮聚类获得的类,计算该类中所有数据与该类聚类中心的平均距离S,选择类中与聚类种子相似度大于2S的数据组成每个类的一个子集,以此子集的均值点作为第k轮聚类的聚类种子。在数据集中无论是否有明显的孤立点存在,两倍的平均距离都能包含大多数的数据。 
对孤立点的改进—基于距离法 
经典k均值算法中没有考虑孤立点。所谓孤立点都是基于距离的, 是数据U集中到U中最近邻居的距离最大的对象, 换言之, 数据集中与其最近邻居的平均距离最大的对象。针对经典k均值算法易受孤立点的影响这一问题, 基于距离法移除孤立点, 具体过程如下: 
首先扫描一次数据集, 计算每一个数据对象与其临近对象的距离, 累加求其距离和, 并计算出距离和均值。如果某个数据对象的距离和大于距离和均值, 则视该点为孤立点。把这个对象从数据集中移除到孤立点集合中, 重复直到所有孤立点都找到。最后得到新的数据集就是聚类的初始集合。 
对随机选取初始聚类中心的改进 
经典k均值算法随机选取k个点作为初始聚类中心进行操作。由于是随机选取, 则变化较大, 初始点选取不同, 获得聚类的结果也不同。并且聚类分析得到的聚类的准确率也不一样。对k均值算法的初始聚类中心选择方法—随机法进行改进, 其依据是聚类过程中相同聚类中的对象是相似的, 相异聚类中的对象是不相似的。因此提出了一种基于数据对象两两间的距离来动态寻找并确定初始聚类中心的思路, 具体过程如下: 
首先整理移除孤立点后的数据集U,记录数据个数y,令m=1。比较数据集中所有数据对象两两之间的距离。找出距离最近的2个数据对象形成集合Am;比较Am中每一个数据对象与数据对象集合U中每一个对象的距离,在U中找出与Am 中最近的数据对象,优先吸收到Am 中,直到Am 中的数据对象个数到达一定数值,然后令m=m+1。再从U中找到对象两两间距离最近的2个数据对象构成Am,重复上面的过程,直到形成k个对象集合。这些集合内部的数据是相似的,而集合间是相异的。 可以看出,这种聚类方法同时满足以下2个条件:①每个组至少包含一个数据对象; ②每个数据对象必须属于且仅属于一个组。即数据对象Xi ∈Ai ,且U={{A1 ∪A2 ∪…∪Ak} ∪A0} ,且Ai ∩Aj =Φ。最后对k个对象集合分别进行算术平均,形成k个初始聚类中心。 
  
近似的k平均算法已经被设计用于原始数据子集的计算。 从算法的表现上来说,它并不保证一定得到全局最优解,最终解的质量很大程度上取决于初始化的分组。由于该算法的速度很快,因此常用的一种方法是多次运行k平均算法,选择最优解。  
k平均算法的一个缺点是,分组的数目k是一个输入参数,不合适的k可能返回较差的结果。另外,算法还假设均方误差是计算群组分散度的最佳参数。

三、数据挖掘十大经典算法(3) Svm  
支持向量机,英文为Support  Vector  Machine,简称SV机(论文中一般简称SVM)。它是一 
种监督式学习的方法,它广泛的应用于统计分类以及回归分析中。  
   
支持向量机属于一般化线性分类器.他们也可以认为是提克洛夫规范化(Tikhonov  Regularization)方法的一个特例.这族分类器的特点是他们能够同时最小化经验误差与最大化 
几何边缘区.因此支持向量机也被称为最大边缘区分类器。在统计计算中,最大期望(EM) 算法是在概率(probabilistic)模型中寻找参数最大似然估计的算法,其中概率模型依赖于无 
法观测的隐藏变量(Latent  Variabl)。最大期望经常用在机器学习和计算机视觉的数据集聚 (Data Clustering)领域。最大期望算法经过两个步骤交替进行计算:

第一步是计算期望(E), 也就是将隐藏变量象能够观测到的一样包含在内从而计算最大似然的期望值;

另外一步是最 大化(M),也就是最大化在  E 步上找到的最大似然的期望值从而计算参数的最大似然估计。 M 步上找到的参数然后用于另外一个  E 步计算,这个过程不断交替进行。  
   
Vapnik等人在多年研究统计学习理论基础上对线性分类器提出了另一种设计最佳准则。其原 理也从线性可分说起,然后扩展到线性不可分的情况。甚至扩展到使用非线性函数中去,这 
种分类器被称为支持向量机(Support Vector Machine,简称SVM)。支持向量机的提出有很深的 理论背景。支持向量机方法是在近年来提出的一种新方法。  
SVM 的主要思想可以概括为两点:  

 (1) 它是针对线性可分情况进行分析,对于线性不可分 的情况,通过使用非线性映射算法将低维输入空间线性不可分的样本转化为高维特征空间使 
其线性可分,从而使得高维特征空间采用线性算法对样本的非线性特征进行线性分析成为可 能;

(2) 它基于结构风险最小化理论之上在特征空间中建构最优分割超平面,使得学习器得 到全局最优化,并且在整个样本空间的期望风险以某个概率满足一定上界。  
在学习这种方法时,首先要弄清楚这种方法考虑问题的特点,这就要从线性可分的最简单情 况讨论起,在没有弄懂其原理之前,不要急于学习线性不可分等较复杂的情况,支持向量机

在设计时,需要用到条件极值问题的求解,因此需用拉格朗日乘子理论,但对多数人来说, 以前学到的或常用的是约束条件为等式表示的方式,但在此要用到以不等式作为必须满足的 条件,此时只要了解拉格朗日理论的有关结论就行。  
   
介绍  
支持向量机将向量映射到一个更高维的空间里,在这个空间里建立有一个最大间隔超平面。 在分开数据的超平面的两边建有两个互相平行的超平面。分隔超平面使两个平行超平面的距 离最大化。假定平行超平面间的距离或差距越大,分类器的总误差越小。一个极好的指南是 C.J.C Burges的《模式识别支持向量机指南》。van der Walt 和  Barnard 将支持向量机和其他 分类器进行了比较。  
   
   
动机 

有很多个分类器(超平面)可以把数据分开,但是只有一个能够达到最大分割。  我们通常希望分类的过程是一个机器学习的过程。这些数据点并不需要是中的点,而可以是 任意(统计学符号)中或者  (计算机科学符号) 的点。我们希望能够把这些点通过一个n-1维的 超平面分开,通常这个被称为线性分类器。有很多分类器都符合这个要求,但是我们还希望 找到分类最佳的平面,即使得属于两个不同类的数据点间隔最大的那个面,该面亦称为最大 间隔超平面。如果我们能够找到这个面,那么这个分类器就称为最大间隔分类器。  
   
四、数据挖掘十大经典算法(4)Apriori  
Apriori算法是种最有影响的挖掘布尔关联规则频繁项集的算法。它的核心是基于两阶段频集思想的递推算法。该关联规则在分类上属于单维、单层、布尔关联规则。在这里,所有支持度大于最小支持度的项集称为频繁项集(简称频集),也常称为最大项目集。 
在Apriori算法中,寻找最大项目集(频繁项集)的基本思想是:算法需要对数据集进行多步处理。第一步,简单统计所有含一个元素项目集出现的频数,并找出那些不小于最小支持度的项目集,即一维最大项目集。从第二步开始循环处理直到再没有最大项目集生成。循环过程是:第k步中,根据第k-1步生成的(k-1)维最大项目集产生k维侯选项目集,然后对数据库进行搜索,得到侯选项目集的项集支持度,与最小支持度进行比较,从而找到k维最大项目集。

从算法的运行过程,我们可以看出该Apriori算法的优点:简单、易理解、数据要求低,然而我们也可以看到Apriori算法的缺点:

(1)在每一步产生侯选项目集时循环产生的组合过多,没有排除不应该参与组合的元素;

(2)每次计算项集的支持度时,都对数据库D中的全部记录进行了一遍扫描比较,如果是一个大型的数据库的话,这种扫描比较会大大增加计算机系统的I/O开销。而这种代价是随着数据库的记录的增加呈现出几何级数的增加。因此人们开始寻求更好性能的算法,如F-P算法。 

五、数据挖掘十大经典算法(5) EM  
 最大期望算法(Expectation-maximization algorithm,又译期望最大化算法)在统计中被用于寻找,依赖于不可观察的隐性变量的概率模型中,参数的最大似然估计。 
在统计计算中,最大期望(EM)算法是在概率模型中寻找参数最大似然估计或者最大后验估计的算法,其中概率模型依赖于无法观测的隐藏变量(Latent Variable)。最大期望经常用在机器学习和计算机视觉的数据聚类(Data Clustering)领域。最大期望算法经过两个步骤交替进行计算,第一步是计算期望(E),利用对隐藏变量的现有估计值,计算其最大似然估计值;第二步是最大化(M),最大化在 E 步上求得的最大似然值来计算参数的值。M 步上找到的参数估计值被用于下一个 E 步计算中,这个过程不断交替进行。 

M是一个在已知部分相关变量的情况下,估计未知变量的迭代技术。 EM的算法流程如下:

  1. 初始化分布参数
  2. 重复直到收敛:
    1. E步骤:估计未知参数的期望值,给出当前的参数估计。
    2. M步骤:重新估计分布参数,以使得数据的似然性最大,给出未知变量的期望估计。

应用于缺失值

最大期望过程说明 
我们用  表示能够观察到的不完整的变量值,用  表示无法观察到的变量值,这样  和  一起组成了完整的数据。 可能是实际测量丢失的数据,也可能是能够简化问题的隐藏变量,如果它的值能够知道的话。例如,在混合模型(Mixture Model)中,如果“产生”样本的混合元素成分已知的话最大似然公式将变得更加便利(参见下面的例子)。 
估计无法观测的数据 
让  代表矢量 :  定义的参数的全部数据的概率分布(连续情况下)或者概率聚类函数(离散情况下),那么从这个函数就可以得到全部数据的最大似然值,另外,在给定的观察到的数据条件下未知数据的条件分布可以表示为:

数据挖掘十大经典算法


六、数据挖掘十大经典算法(6) PageRank  

PageRank,网页排名,又称网页级别、Google左侧排名或佩奇排名,是一种由搜索引擎根据网页之间相互的超链接计算的技术,而作为网页排名的要素之一,以Google公司创办人拉里·佩奇(Larry Page)之姓来命名。Google用它来体现网页的相关性和重要性,在搜索引擎优化操作中是经常被用来评估网页优化的成效因素之一。Google的创始人拉里·佩奇和谢尔盖·布林于1998年在斯坦福大学发明了这项技术。


PageRank通过网络浩瀚的超链接关系来确定一个页面的等级。Google把从A页面到B页面的链接解释为A页面给B页面投票,Google根据投票来源(甚至来源的来源,即链接到A页面的页面)和投票目标的等级来决定新的等级。简单的说,一个高等级的页面可以使其他低等级页面的等级提升。 

PageRank让链接来"投票" 
一个页面的“得票数”由所有链向它的页面的重要性来决定,到一个页面的超链接相当于对该页投一票。一个页面的PageRank是由所有链向它的页面(“链入页面”)的重要性经过递归算法得到的。一个有较多链入的页面会有较高的等级,相反如果一个页面没有任何链入页面,那么它没有等级。 
2005年初,Google为网页链接推出一项新属性nofollow,使得网站管理员和网志作者可以做出一些Google不计票的链接,也就是说这些链接不算作"投票"。nofollow的设置可以抵制垃圾评论。 
Google工具条上的PageRank指标从0到10。它似乎是一个对数标度算法,细节未知。PageRank是Google的商标,其技术亦已经申请专利。 
PageRank算法中的点击算法是由Jon Kleinberg提出的。 

PageRank算法 

1.PageRank  
基本思想:如果网页T存在一个指向网页A的连接,则表明T的所有者认为A比较重要,从而把T的一部分重要性得分赋予A。这个重要性得分值为:PR(T)/C(T)  
其中PR(T)为T的PageRank值,C(T)为T的出链数,则A的PageRank值为一系列类似于T的页面重要性得分值的累加。  
优点:是一个与查询无关的静态算法,所有网页的PageRank值通过离线计算获得;有效减少在线查询时的计算量,极大降低了查询响应时间。  
不足:人们的查询具有主题特征,PageRank忽略了主题相关性,导致结果的相关性和主题性降低;另外,PageRank有很严重的对新网页的歧视。  
2.Topic-Sensitive PageRank(主题敏感的PageRank)  
基本思想:针对PageRank对主题的忽略而提出。核心思想:通过离线计算出一个  PageRank向量集合,该集合中的每一个向量与某一主题相关,即计算某个页面关于不同主题的得分。 
主要分为两个阶段:主题相关的PageRank向量集合的计算和在线查询时主题的确定。 

优点:根据用户的查询请求和相关上下文判断用户查询相关的主题(用户的兴趣)返回查询结果准确性高。  
不足:没有利用主题的相关性来提高链接得分的准确性。  
3.Hilltop  
基本思想:与PageRank的不同之处:仅考虑专家页面的链接。主要包括两个步骤:专家页面搜索和目标页面排序。  
优点:相关性强,结果准确。  
不足:专家页面的搜索和确定对算法起关键作用,专家页面的质量决定了算法的准确性,而 
  
专家页面的质量和公平性难以保证;忽略了大量非专家页面的影响,不能反应整个Internet的民意;当没有足够的专家页面存在时,返回空,所以Hilltop适合对于查询排序进行求精。  
那么影响google PageRank的因素有哪些呢?  
1 与pr高的网站做链接:  
2 内容质量高的网站链接  
3加入搜索引擎分类目录  
4 加入免费开源目录  
5 你的链接出现在流量大、知名度高、频繁更新的重要网站上  
6 google对DPF格式的文件比较看重。  
7 安装Google工具条  
8 域名和tilte标题出现关键词与meta标签等  
9 反向连接数量和反向连接的等级  
10 Google抓取您网站的页面数量  
11导出链接数量

七、数据挖掘十大经典算法(7) AdaBoost  

AdaBoost,是英文"Adaptive Boosting"(自适应增强)的缩写,是一种机器学习方法,由Yoav Freund和Robert Schapire提出。

AdaBoost方法的自适应在于:前一个分类器分错的样本会被用来训练下一个分类器。AdaBoost方法对于噪声数据和异常数据很敏感。但在一些问题中,AdaBoost方法相对于大多数其它学习算法而言,不会很容易出现过拟合现象。

AdaBoost方法中使用的分类器可能很弱(比如出现很大错误率),但只要它的分类效果比随机好一点(比如两类问题分类错误率略小于0.5),就能够改善最终得到的模型。而错误率高于随机分类器的弱分类器也是有用的,因为在最终得到的多个分类器的线性组合中,可以给它们赋予负系数,同样也能提升分类效果。 

如果某个样本点已经被准确地分类,那么在构造下一个训练集中,它被选中的概率就被降低;

相反,如果某个样本点没有被准确地分类,那么它的权重就得到提高。通过这样的方式,AdaBoost方法能“聚焦于”那些较难分(更富信息)的样本上。

在具体实现上,最初令每个样本的权重都相等,对于第k次迭代操作,我们就根据这些权重来选取样本点,进而训练分类器Ck。然后就根据这个分类器,来提高被它分错的的样本的权重,并降低被正确分类的样本权重。然后,权重更新过的样本集被用于训练下一个分类器Ck[2]。整个训练过程如此迭代地进行下去。 

Adaboost算法的具体步骤如下:   
1. 给定训练样本集  ,其中  分别对应于正例样本和负例样本;  为训练的最大循环次数;  
2. 初始化样本权重  ,即为训练样本的初始概率分布;  
3. 第一次迭代:  
(1)  训练样本的概率分布  下,训练弱分类器:  
(2) 计算弱分类器的错误率:  
(3) 选取  ,使得  最小  
(4) 更新样本权重:  
(5) 最终得到的强分类器:  
Adaboost算法是经过调整的Boosting算法,其能够对弱学习得到的弱分类器的错误进行适应 
性调整。上述算法中迭代了次的主循环,每一次循环根据当前的权重分布对样本x定一个分 
布P,然后对这个分布下的样本使用若学习算法得到一个错误率为的弱分类器  ,对于这个算 
法定义的弱学习算法,对所有的  ,都有,而这个错误率的上限并不需要事先知道,实际上。 
每一次迭代,都要对权重进行更新。更新的规则是:减小弱分类器分类效果较好的数据的概 
率,增大弱分类器分类效果较差的数据的概率。最终的分类器是个弱分类器的加权平均。 

八、数据挖掘十大经典算法(8) kNN  

1、K最近邻(k-Nearest  Neighbor,KNN)分类算法,是一个理论上比较成熟的方法,也是最简单的机器学习算法之一。该方法的思路是:如果一个样本在特征空间中的k个最相似(即特征空 
间中最邻近)的样本中的大多数属于某一个类别,则该样本也属于这个类别。 
2、KNN算法中,所选择的邻居都是已经正确分类的对象。该方法在定类决策上只依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别。  KNN方法虽然从原理上也依赖于极限定理,但在类别决策时,只与极少量的相邻样本有关。由于KNN方法主要靠周围有限的邻近的样本, 
而不是靠判别类域的方法来确定所属类别的,因此对于类域的交叉或重叠较多的待分样本集来说,KNN方法较其他方法更为适合。  
3、KNN算法不仅可以用于分类,还可以用于回归。通过找出一个样本的k个最近邻居,将这些邻居的属性的平均值赋给该样本,就可以得到该样本的属性。更有用的方法是将不同距离的 
邻居对该样本产生的影响给予不同的权值(weight),如权值与距离成正比。  
4、 该算法在分类时有个主要的不足是 ,当样本不平衡时,如一个类的样本容量很大,而其他类样本容量很小时,有可能导致当输入一个新样本时,该样本的K个邻居中大容量类的样本占多数。因此可以采用权值的方法(和该样本距离小的邻居权值大)来改进。

      该方法的另一个不足之处是计算量较大,因为对每一个待分类的文本都要计算它到全体已知样本的距离,才能求得它的K个最近邻点。目前常用的解决方法是事先对已知样本点进行剪辑,事先去除对分类作用不大的样本。该算法比较适用于样本容量比较大的类域的自动分类,而那些样本容量较小的类域采用这种算法比较容易产生误分。 
算法分类过程如下: 
1 首先我们事先定下k值(就是指k近邻方法的k的大小,代表对于一个待分类的数据点,我们要寻找几个它的邻居)。这边为了说明问题,我们取两个k值,分别为3和9; 
2 根据事先确定的距离度量公式(如:欧氏距离),得出待分类数据点和所有已知类别的样本点中,距离最近的k个样本。 
3 统计这k个样本点中,各个类别的数量。根据k个样本中,数量最多的样本是什么类别,我们就把这个数据点定为什么类别。 

训练样本是多维特征空间向量,其中每个训练样本带有一个类别标签。算法的训练阶段只包含存储的特征向量和训练样本的标签。 在分类阶段,k是一个用户定义的常数。一个没有类别标签的向量 (查询或测试点)将被归类为最接近该点的K个样本点中最频繁使用的一类。

 一般情况下,将欧氏距离作为距离度量,但是这是只适用于连续变量。在文本分类这种非连续变量情况下,

另一个度量——重叠度量(或海明距离)可以用来作为度量。

通常情况下,如果运用一些特殊的算法来计算度量的话,K近邻分类精度可显著提高,如运用大边缘最近邻法或者近邻成分分析法。 
“多数表决”分类的一个缺点是出现频率较多的样本将会主导测试点的预测结果,那是因为他们比较大可能出现在测试点的K邻域而测试点的属性又是通过K领域内的样本计算出来的。解决这个缺点的方法之一是在进行分类时将样本到测试点的距离考虑进去。 
K值得选择 
如何选择一个最佳的K值取决于数据。一般情况下,在分类时较大的K值能够减小噪声的影响。但会使类别之间的界限变得模糊。一个较好的K值能通过各种启发式技术来获取,比如,交叉验证。 
噪声和非相关性特征向量的存在会使K近邻算法的准确性减小。对于选择特征向量进行分类已经作了很多研究。一个普遍的做法是利用进化算法优化功能扩展[3],还有一种较普遍的方法是利用训练样本的互信息进行选择特征。 
K近邻算法也适用于连续变量估计,比如适用反距离加权平均多个K近邻点确定测试点的值。该算法的功能有: 
1、从目标区域抽样计算欧式或马氏距离; 
2、在交叉验证后的RMSE基础上选择启发式最优的K邻域; 
3、计算多元k-最近邻居的距离倒数加权平均。 

九、数据挖掘十大经典算法(9) Naive Baye 

简介 
贝叶斯分类的基础是概率推理,就是在各种条件的存在不确定,仅知其出现概率的情况下,如何完成推理和决策任务。概率推理是与确定性推理相对应的。而朴素贝叶斯分类器是基于独立假设的,即假设样本每个特征与其他特征都不相关。举个例子,如果一种水果其具有红,圆,直径大概4英寸等特征,该水果可以被判定为是苹果。 
尽管这些特征相互依赖或者有些特征由其他特征决定,然而朴素贝叶斯分类器认为这些属性在判定该水果是否为苹果的概率分布上独立的。朴素贝叶斯分类器依靠精确的自然概率模型,在有监督学习的样本集中能获取得非常好的分类效果。在许多实际应用中,朴素贝叶斯模型参数估计使用最大似然估计方法,换而言之朴素贝叶斯模型能工作并没有用到贝叶斯概率或者任何贝叶斯模型。 
尽管是带着这些朴素思想和过于简单化的假设,但朴素贝叶斯分类器在很多复杂的现实情形中仍能够取得相当好的效果。2004年,一篇分析贝叶斯分类器问题的文章揭示了朴素贝叶斯分类器取得看上去不可思议的分类效果的若干理论上的原因。尽管如此,2006年有一篇文章详细比较了各种分类方法,发现更新的方法(如boosted trees和随机森林)的性能超过了贝叶斯分类器。朴素贝叶斯分类器的一个优势在于只需要根据少量的训练数据估计出必要的参数(变量的均值和方差)。由于变量独立假设,只需要估计各个变量的方法,而不需要确定整个协方差矩阵。 

两种分类模型:

分类是将一个未知样本分到几个预先已知类的过程。数据分类问题的解决是一个两步过程:

第一步,建立一个模型,描述预先的数据集或概念集。通过分析由属性描述的样本(或实例,对象等)来构造模型。假定每一个样本都有一个预先定义的类,由一个被称为类标签的属性 
确定。为建立模型而被分析的数据元组形成训练数据集,该步也称作有指导的学习。 在众多的分类模型中,应用最为广泛的两种分类模型是:

决策树模型(Decision Tree Model)和朴素贝叶斯模型(Naive  Bayesian  Model,NBC) 。

决策树模型通过构造树来解决分类问题。

1、首先利用训练数据集来构造一棵决策树,一旦树建立起来,它就可为未知样本产生一个分类。在分类问题中使用决策树模型有很多的优点,决策树便于使用,而且高效;根据决策树可以 
很容易地构造出规则,而规则通常易于解释和理解;决策树可很好地扩展到大型数据库中,同时它的大小独立于数据库的大小;决策树模型的另外一大优点就是可以对有许多属性的数据集构造决策树。

决策树模型也有一些缺点,比如处理缺失数据时的困难,过度拟合问题的出现,以及忽略数据集中属性之间的相关性等。  
2、和决策树模型相比,朴素贝叶斯模型发源于古典数学理论,有着坚实的数学基础,以及稳定的分类效率。同时,NBC模型所需估计的参数很少,对缺失数据不太敏感,算法也比较简单。 
理论上,NBC模型与其他分类方法相比具有最小的误差率。

但是实际上并非总是如此,这是因为NBC模型假设属性之间相互独立,这个假设在实际应用中往往是不成立的,这给NBC 
模型的正确分类带来了一定影响。在属性个数比较多或者属性之间相关性较大时,NBC模型的分类效率比不上决策树模型。而在属性相关性较小时,NBC模型的性能最为良好。  

贝叶斯分类器特点 
1、 需要知道先验概率 
先验概率是计算后验概率的基础。在传统的概率理论中,先验概率可以由大量的重复实验所获得的各类样本出现的频率来近似获得,其基础是“大数定律”,这一思想称为“频率主义”。而在称为“贝叶斯主义”的数理统计学派中,他们认为时间是单向的,许多事件的发生不具有可重复性,因此先验概率只能根据对置信度的主观判定来给出,也可以说由“信仰”来确定。 
2、按照获得的信息对先验概率进行修正 
在没有获得任何信息的时候,如果要进行分类判别,只能依据各类存在的先验概率,将样本划分到先验概率大的一类中。而在获得了更多关于样本特征的信息后,可以依照贝叶斯公式对先验概率进行修正,得到后验概率,提高分类决策的准确性和置信度。 
3、分类决策存在错误率 
由于贝叶斯分类是在样本取得某特征值时对它属于各类的概率进行推测,并无法获得样本真实的类别归属情况,所以分类决策一定存在错误率,即使错误率很低,分类错误的情况也可能发生。 

十、数据挖掘十大经典算法(10) CART  

分类回归树(CART,Classification And Regression Tree)也属于一种决策树, 分类回归树是一棵二叉树,且每个非叶子节点都有两个孩子,所以对于第一棵子树其叶子节点数比非叶子节点数多1。 

决策树生长的核心是确定决策树的分枝准则。 
1、 如何从众多的属性变量中选择一个当前的最佳分支变量; 
也就是选择能使异质性下降最快的变量。 
异质性的度量:GINI、TWOING、least squared deviation。 
前两种主要针对分类型变量,LSD针对连续性变量。 
代理划分、加权划分、先验概率 
2、 如何从分支变量的众多取值中找到一个当前的最佳分割点(分割阈值)。 
(1) 分割阈值: 
 A、数值型变量——对记录的值从小到大排序,计算每个值作为临界点产生的子节点的异质性统计量。能够使异质性减小程度最大的临界值便是最佳的划分点。 
 B、分类型变量——列出划分为两个子集的所有可能组合,计算每种组合下生成子节点的异质性。同样,找到使异质性减小程度最大的组合作为最佳划分点。 
   

在决策树的每一个节点上我们可以按任一个属性的任一个值进行划分。 按哪种划分最好呢?有3个标准可以用来衡量划分的好坏:GINI指数、双化指数、有序双化指数。

终止条件:

一个节点产生左右孩子后,递归地对左右孩子进行划分即可产生分类回归树。这里的终止条件是什么?什么时候节点就可以停止分裂了? 

满足以下一个即停止生长。 
(1) 节点达到完全纯性; 
(2) 数树的深度达到用户指定的深度; 
(3) 节点中样本的个数少于用户指定的个数; 
(4) 异质性指标下降的最大幅度小于用户指定的幅度。 

剪枝

当分类回归树划分得太细时,会对噪声数据产生过拟合作用。因此我们要通过剪枝来解决。剪枝又分为前剪枝和后剪枝:前剪枝是指在构造树的过程中就知道哪些节点可以剪掉,于是干脆不对这些节点进行分裂,在N皇后问题和背包问题中用的都是前剪枝,上面的χ2方法也可以认为是一种前剪枝;后剪枝是指构造出完整的决策树之后再来考查哪些子树可以剪掉。 
在分类回归树中可以使用的后剪枝方法有多种,比如:代价复杂性剪枝、最小误差剪枝、悲观误差剪枝等等。这里我们只介绍代价复杂性剪枝法。 

预测 
回归树——预测值为叶节点目标变量的加权均值 
分类树——某叶节点预测的分类值应是造成错判损失最小的分类值。

收起全文

★·°遇見、堇色年華 ﹏

【十里桃花】佐酒

【十里桃花】佐酒

我看见微尘漂浮在,你郑重其事的美好,衣服头发上的余光, 停滞逗留, 泥土里被露水浸透,麦子青翠里生长出偏黄,一口呛喉的酒,凝望里挂着锈迹斑斑的鱼钩,灰黑色的铜钱,氧化着侵蚀想你的愁,江湖里歌者唱一朝忘记,红楼里戏子演一出从头,我会感到天长地久,忙于赶路却错过,黄昏的消瘦。... 阅读全文

【十里桃花】佐酒

我看见微尘漂浮在, 
你郑重其事的美好, 
衣服头发上的余光, 

停滞逗留, 

泥土里被露水浸透, 
麦子青翠里生长出偏黄, 
一口呛喉的酒, 
凝望里挂着锈迹斑斑的鱼钩, 
灰黑色的铜钱, 
氧化着侵蚀想你的愁, 
江湖里歌者唱一朝忘记, 
红楼里戏子演一出从头, 
我会感到天长地久, 
忙于赶路却错过, 
黄昏的消瘦。

收起全文

辛几何&李代数

BloomFilter——大规模数据处理利器

BloomFilter——大规模数据处理利器

  BloomFilter是由Bloom在1970年提出的一种多哈希函数映射的快速查找算法。通常应用在一些需要快速判断某个元素是否属于集合,但是并不严格要求100%正确的场合。 一.实例   为了说明BloomFilter存在的重要意义,举一个实例:   假设要你写一个网络蜘蛛(web crawler)。由于网络间的链接错综复杂,蜘蛛在网络... 阅读全文

 

  Bloom Filter是由Bloom在1970年提出的一种多哈希函数映射的快速查找算法。通常应用在一些需要快速判断某个元素是否属于集合,但是并不严格要求100%正确的场合。

 

实例 

  为了说明Bloom Filter存在的重要意义,举一个实例:

  假设要你写一个网络蜘蛛(web crawler)。由于网络间的链接错综复杂,蜘蛛在网络间爬行很可能会形成“环”。为了避免形成“环”,就需要知道蜘蛛已经访问过那些URL。给一个URL,怎样知道蜘蛛是否已经访问过呢?稍微想想,就会有如下几种方案:

  1. 将访问过的URL保存到数据库。

  2. 用HashSet将访问过的URL保存起来。那只需接近O(1)的代价就可以查到一个URL是否被访问过了。

  3. URL经过MD5或SHA-1等单向哈希后再保存到HashSet或数据库。

  4. Bit-Map方法。建立一个BitSet,将每个URL经过一个哈希函数映射到某一位。

  方法1~3都是将访问过的URL完整保存,方法4则只标记URL的一个映射位。

 

  以上方法在数据量较小的情况下都能完美解决问题,但是当数据量变得非常庞大时问题就来了。

  方法1的缺点:数据量变得非常庞大后关系型数据库查询的效率会变得很低。而且每来一个URL就启动一次数据库查询是不是太小题大做了?

  方法2的缺点:太消耗内存。随着URL的增多,占用的内存会越来越多。就算只有1亿个URL,每个URL只算50个字符,就需要5GB内存。

  方法3:由于字符串经过MD5处理后的信息摘要长度只有128Bit,SHA-1处理后也只有160Bit,因此方法3比方法2节省了好几倍的内存。

  方法4消耗内存是相对较少的,但缺点是单一哈希函数发生冲突的概率太高。还记得数据结构课上学过的Hash表冲突的各种解决方法么?若要降低冲突发生的概率到1%,就要将BitSet的长度设置为URL个数的100倍。

 

  实质上上面的算法都忽略了一个重要的隐含条件:允许小概率的出错,不一定要100%准确!也就是说少量url实际上没有没网络蜘蛛访问,而将它们错判为已访问的代价是很小的——大不了少抓几个网页呗。 

 

Bloom Filter的算法 

 

  废话说到这里,下面引入本篇的主角——Bloom Filter。其实上面方法4的思想已经很接近Bloom Filter了。方法四的致命缺点是冲突概率高,为了降低冲突的概念,Bloom Filter使用了多个哈希函数,而不是一个。

    Bloom Filter算法如下:

    创建一个m位BitSet,先将所有位初始化为0,然后选择k个不同的哈希函数。第i个哈希函数对字符串str哈希的结果记为h(i,str),且h(i,str)的范围是0到m-1 。

 

(1) 加入字符串过程 

 

  下面是每个字符串处理的过程,首先是将字符串str“记录”到BitSet中的过程:

  对于字符串str,分别计算h(1,str),h(2,str)…… h(k,str)。然后将BitSet的第h(1,str)、h(2,str)…… h(k,str)位设为1。

 BloomFilter——大规模数据处理利器

  图1.Bloom Filter加入字符串过程

  很简单吧?这样就将字符串str映射到BitSet中的k个二进制位了。

 

(2) 检查字符串是否存在的过程 

 

  下面是检查字符串str是否被BitSet记录过的过程:

  对于字符串str,分别计算h(1,str),h(2,str)…… h(k,str)。然后检查BitSet的第h(1,str)、h(2,str)…… h(k,str)位是否为1,若其中任何一位不为1则可以判定str一定没有被记录过。若全部位都是1,则“认为”字符串str存在。

 

  若一个字符串对应的Bit不全为1,则可以肯定该字符串一定没有被Bloom Filter记录过。(这是显然的,因为字符串被记录过,其对应的二进制位肯定全部被设为1了)

  但是若一个字符串对应的Bit全为1,实际上是不能100%的肯定该字符串被Bloom Filter记录过的。(因为有可能该字符串的所有位都刚好是被其他字符串所对应)这种将该字符串划分错的情况,称为false positive 。

 

(3) 删除字符串过程 

   字符串加入了就被不能删除了,因为删除会影响到其他字符串。实在需要删除字符串的可以使用Counting bloomfilter(CBF),这是一种基本Bloom Filter的变体,CBF将基本Bloom Filter每一个Bit改为一个计数器,这样就可以实现删除字符串的功能了。

 

  Bloom Filter跟单哈希函数Bit-Map不同之处在于:Bloom Filter使用了k个哈希函数,每个字符串跟k个bit对应。从而降低了冲突的概率。

 

Bloom Filter参数选择 

 

   (1)哈希函数选择

     哈希函数的选择对性能的影响应该是很大的,一个好的哈希函数要能近似等概率的将字符串映射到各个Bit。选择k个不同的哈希函数比较麻烦,一种简单的方法是选择一个哈希函数,然后送入k个不同的参数。

   (2)Bit数组大小选择 

     哈希函数个数k、位数组大小m、加入的字符串数量n的关系可以参考参考文献1。该文献证明了对于给定的m、n,当 k = ln(2)* m/n 时出错的概率是最小的。

     同时该文献还给出特定的k,m,n的出错概率。例如:根据参考文献1,哈希函数个数k取10,位数组大小m设为字符串个数n的20倍时,false positive发生的概率是0.0000889 ,这个概率基本能满足网络爬虫的需求了。  

 

Bloom Filter实现代码 

    下面给出一个简单的Bloom Filter的Java实现代码:

 

import java.util.BitSet;

publicclass BloomFilter 
{
/* BitSet初始分配2^24个bit */ 
privatestaticfinalint DEFAULT_SIZE =1<<25
/* 不同哈希函数的种子,一般应取质数 */
privatestaticfinalint[] seeds =newint[] { 571113313761 };
private BitSet bits =new BitSet(DEFAULT_SIZE);
/* 哈希函数对象 */ 
private SimpleHash[] func =new SimpleHash[seeds.length];

public BloomFilter() 
{
for (int i =0; i < seeds.length; i++)
{
func[i] 
=new SimpleHash(DEFAULT_SIZE, seeds[i]);
}
}

// 将字符串标记到bits中
publicvoid add(String value) 
{
for (SimpleHash f : func) 
{
bits.set(f.hash(value), 
true);
}
}

//判断字符串是否已经被bits标记
publicboolean contains(String value) 
{
if (value ==null
{
returnfalse;
}
boolean ret =true;
for (SimpleHash f : func) 
{
ret 
= ret && bits.get(f.hash(value));
}
return ret;
}

/* 哈希函数类 */
publicstaticclass SimpleHash 
{
privateint cap;
privateint seed;

public SimpleHash(int cap, int seed) 
{
this.cap = cap;
this.seed = seed;
}

//hash函数,采用简单的加权和hash
publicint hash(String value) 
{
int result =0;
int len = value.length();
for (int i =0; i < len; i++
{
result 
= seed * result + value.charAt(i);
}
return (cap -1& result;
}
}
}

收起全文
人人小站
更多热门小站
X 人人网小程序,你的青春在这里