辛几何&李代数

耸人听闻的中微子武器

耸人听闻的中微子武器

菅原宽孝(Hiritaka Sugawara)曾是日本颇有名气的粒子物理学理论家,在上世纪九十年代担任过日本高能加速器研究机构(KEK)的总主任,为推动亚洲高能物理学实验的发展做出了贡献。2003年春天,刚刚退休的菅原与两位日本学者合作,在网上贴出了一篇别出心裁、震惊世界的奇文,题目是&利用超高能中微子束流摧毁原子弹&(arXiv:hep-ph/030506... 阅读全文

菅原宽孝(Hiritaka Sugawara)曾是日本颇有名气的粒子物理学理论家,在上世纪九十年代担任过日本高能加速器研究机构(KEK)的总主任,为推动亚洲高能物理学实验的发展做出了贡献。2003年春天,刚刚退休的菅原与两位日本学者合作,在网上贴出了一篇别出心裁、震惊世界的奇文,题目是“利用超高能中微子束流摧毁原子弹”(arXiv:hep-ph/0305062)。

耸人听闻的中微子武器

 

在这篇旨在献给日本中微子之父小柴昌俊的学术论文中,菅原等人提出了一个能让核武器持有者身处险境的想法:制备能量高达一千万亿电子伏(1000 TeV)的中微子束流,然后将它射向地球上任何一个地方的核武库,摧毁或引爆核弹头,从而达到阻碍各国发展核武器和实现核裁军的目的。这种假想的中微子武器采用的基本原理是中微子的弱相互作用性质:一方面,中微子可以轻易穿越地球屏障,并穿透核武库的所有保护层;另一方面,超高能量的中微子束流在传播过程中与周围的物质发生相对较强的相互作用(其反应截面正比于中微子的能量),沿途产生大量强子,这些高能强子(尤其是中子)打到核弹头内的钚或铀元素后会触发核裂变反应,起到点燃核弹头的作用,从而使之熔化、蒸发或爆炸。

 

毫无疑问,上述想法是目前的实验技术根本无法实现的。首先,要产生1000 TeV中微子束流,需要更高能量的质子打靶,产生带电p介子,后者衰变成m子,而m子在储存环中发生衰变可以产生中微子。其次,实现上述过程需要建造周长至少1000公里的超级加速器,而目前正在运行的大型强子对撞机(LHC)的环形隧道周长仅为27公里。第三,这样一个超级加速器依赖一个10特斯拉左右的超级磁场的存在,以便通过控制带电粒子的方向来对伴随的中微子作定向聚焦。而要产生如此高强度的磁场,需要至少花费上千亿美元先制备一个超大磁铁。第四,要使超级加速器得以运行,消耗的总电功率将超过500亿瓦,相当于甚至超过整个英国的总耗电功率。此外,这样一个庞然大物的运行对周围环境所造成的辐射危害也是难以估量的。

耸人听闻的中微子武器

 

菅原等人的论文出台之后虽然被广泛报道并引起了轩然大波,但他们的想法因不具备现实可行性而在学术界内却没有得到重视。20085月,工作单位飘忽不定的华人物理学家阿尔佛雷德·唐(Alfred Tang)在网上贴出了一篇关于中微子武器的新论文,题目是“中微子反核武器”(arXiv:0805.3991)。该论文几年之内四易其稿,最新版本出现在20136月。唐与菅原等人的动机相同,就是要利用高能量的中微子束流实现远程摧毁核弹头的军事目的。他的具体想法如下:首先利用加速器制备出能量约为45兆电子伏(45 GeV)或高于此数值的正反中微子束流;然后使之聚焦到某处核武库,让束流对撞得以发生在Z粒子共振峰上,这样反应截面会很大;最后Z粒子的衰变产物(如伽马射线)会点燃或引爆核弹头。

 

唐所设想的中微子反核武器装置虽然要求的中微子束流能量较低,但也很难实现。一般说来,从两个加速器中引出的中微子和反中微子束流具有固定的方向,要想让它们恰好在地球另一端的核武库中实现有效对撞并产生足够数量的Z粒子,操纵者必须精确知晓三者的方位,并保证高强度束流的准直性。这使得该想法的技术难度大增而实用性大打折扣,核弹头通常是可移动的,但加速器的位置却必须固定。能量处于45兆电子伏附近的中微子束流也会和大气中微子发生反应而损耗,原因在于后者的能量在很大程度上处于10100千兆电子伏的范围。

 

所以我们有理由相信,开发中微子武器仍旧只是一个遥不可及的梦想,而且利用它来摧毁核武库的后果很可能是灾难性的。除非中微子束流的远程攻击能够保证核弹安全地分解并失效,否则一旦引发任何形式的核爆炸,其后果都与常规的核打击没有本质区别,而且从根本上背离了核裁军的目的。

耸人听闻的中微子武器

 

事实上,“中微子技术”是一部分物理学家近年来特别关注的研究课题。他们的出发点很简单,就是期待在可望的将来像应用光子技术那样实现中微子技术的广泛应用。目前已经被探讨的可能性包括利用中微子勘探油田、发展针对地球和恒星内部结构的中微子断层摄影术、利用中微子预测地震、利用中微子探测器监视有效距离内的核试验、通过中微子实现远程通讯(例如与外星人的交流,以及与深水潜艇的秘密通讯),等等。所有此类研究都基于中微子的极强穿透性、直线传播特点和振荡效应,但是它们都无一例外地需要建造超级加速器或者大型探测器。也许有一天,中微子技术的突破能够让科学家们实现这些梦想。

收起全文

辛几何&李代数

阶级与秩序

阶级与秩序

圣谛尚不为,何阶级之有! &&青原行思禅师 Order without liberty and liberty without order are equally destructive. &&Theodore Roosevelt   1 引子 笔者来自穷乡僻壤,因此家乡话里就保有一些化石级的文化... 阅读全文

 

圣谛尚不为,何阶级之有!

——青原行思禅师

Order without liberty and liberty without order are equally destructive.

——Theodore Roosevelt

  1 引子

笔者来自穷乡僻壤,因此家乡话里就保有一些化石级的文化痕迹。旧时待客,主人会根据客人的阶级层次决定接待规格,俗谓看人下菜碟。对于拥有这种自觉的人,文化点的表述是具有较高的阶级觉悟,俺们老家的土话就说这人“长就一对阶级眼”,属于天赋异禀的一类。阶级繁杂且森严,是中国文化的精髓。历史上不仅是对官员,就连嫔妃、奴才、太监和教授都分成三六九等,都有系统科学的标识和具体而微的待遇安排。比如,汉朝是个有文化的朝代,帝妇初分为皇后、夫人、美人、良人、八子、七子、长使、少使八等,后又引入婕妤、妌娥、容华、充依、五官、顺常和无涓(共和、娱灵、保林、良使和夜者)共十五等。清朝帝妇则分为皇后、皇贵妃、贵妃、妃、嫔、贵人、常在和答应,从命名上就能看到文化的缺乏。不同阶级之间,有递补、提拔、贬谪与自甘堕落,但平时一般各以本分,这正应了原子中电子的隧穿、受激向上跃迁、受激向下跃迁和自发向下跃迁,以及大多时间在稳定状态上的无所事事。

用来区分人或物之不同等级的汉语词包括阶-级、秩-序、品(秩)、次(幂)等词,用这些词加以翻译的英文词有level,order,degree,grade,rank,等等。这些词在数学物理中频繁出现,且意义多有不同甚至混淆, 中西文皆然。中文的阶级,其中的阶(堦)见于台阶,庭阶寂寂,是实体,而级,见于拾(shè) 级而上,由计数(enumeration)而来,有抽象的内容。容易理解,台阶是一种实用的、但也被故意符号化了的存在,许多建筑在面前都筑起多层次的台阶,陡然而出威严(图1)。阶-级、秩-序这种得自自然和日常生活的词必然散布于数学物理的表述,弄不清level,order,degree,grade,rank 这些词的用法,看数学物理和看宫斗剧一样有点稀里糊涂。学物理者,将一双阶级眼用在这里,正得其宜也。

   2 Level

谈到汉译为阶级的词,容易想到的一个便是level, 见于energy level (能级),但这可能是误解。英语的level,来自拉丁语的libra,与平、衡有关。水平的线或者面,即为level,如sea level (海平面),on a level line (水平线上)。牛顿流体在重力场下的静止状态,其表面的法向应该是重力的方向,此即waterseeks its level 之意。利用这个事实,可以制作水平仪(level,见图2),这是工程中必不可少的工具。Level 不是级,而是阶、阶之面。在日常用法中,level 不仅表示层面,还暗含平衡之意, 如high-leveltalk,不仅是说会谈的层次高,而且是对等的。Level 还有equally advanced in development & even or uniform in some characters (等间距的、均匀分布的),因此level暗含“equal in importance, rank, degree, etc.”的意思,这也可能是我们愿意拿级来翻译level 的原因。但是,把energy level 翻译成能级还好,习惯性地把atomic level,sub-levels 中的level也翻译成“ 能级”这就麻烦了,它掩盖了轨道(也许就是个数学的函数)自身的排列问题,这里的level强调的也许只是轨道可分辨这个事实。在象levels of consciousness,levels of difficulty 这样的概念中,谈论的都是抽象概念的分层次,没有定量的成分。许多时候,把level 译成层次、层面也许是更合适的,哪怕是energy level。比如加速器的energylevel,如在例句LHC experiments run at the highest energy level 中,就应该译成“能量水平”, 目前欧洲大型强子对撞机就运行在13 TeV 的能量水平上。此外,象the macroscopic level of quantum mechanics一文,显然讨论的是量子力学的宏观层次。

  3 Degree

Degree, 来自拉丁语动词degradare,就是英文的degrade,是一串台阶(steps or stages)的意思,注意它更多强调了降序的排列,这一点从a cousin in the second degree (二度表亲,拥有同一个太爷爷、太奶奶辈分的前辈)一词中很容易看出来。Degree 和grade (gradus) 意义相同,两者可连用。我们在学校里学习的难易程度也是分级的(同学,你物理是第几grade 的?)。如果是沿着不易觉察的台阶或者刻度一点一点向前(向上)推进,这就是一个gradual(逐渐的)过程。达到一定程度就能graduate (毕业、爬到头了), 就可以receive a degree (获得一个学位,拿到一个刻度标记)了。常用的摄氏温标(temperature scale)的量度名称为degree Celsius (摄氏度),也称degree centrigrade (100 刻度制),后一词透露了其是如何被定义的。将标准大气压(维也纳夏季的气压)下冰—水混合物的温度定为0 ℃,把水的沸点定为100 ℃。利用稀薄空气在等压条件下体积随温度线性变换的假设,可以根据稀薄气体体积相较于0 ℃下的增量给0 ℃到100 ℃间的任意温度赋值。这就是摄氏温标的定义。注意,对于稀薄空气,在0 ℃到100 ℃之间温度每增加1 ℃,体积增加约1/267。明白了这一点,也就明白了作为对摄氏温标之拓展的绝对温标,其唯一的定标点,水的三相点,为什么会定为273.16 K了。一般中文教科书中论及摄氏温标,只含含糊糊地来一句“标准大气压下冰水混合物的温度定为0 ℃,水的沸点定为100 ℃,此为摄氏温标”,显然漏掉了太多的信息。编书者当年囿于条件不能知道细节可以理解,但根本没注意到定义的不完整就让人不能理解了。早期的来自物质体积变化的、直观的一排刻度,那真是degree,如今的电子式的温度计,显示的就是“一个”数值,则需要符号℃,°F 的提醒才会想起degree来(图3)。

有可视标度的是真degree,纯数字的就靠外加符号的提醒了

Degree 可用作对一般程度的或者干脆就是直观存在的度量。一个圆, 其上可以划上刻度, 分为360°,那是对每年天数的取整,不具有绝对的意义。在反射光的degree of polarization(偏振度)概念中,degree 反映的是程度,其取值在0到100%之间。Degree 或者grade 还被用来衡量抽象概念的程度,如马克思的《政治经济学批判》一书中有句云:“Der Tauschwert der Waren,so als allgemeine Äquivalenz und zugleich als Grad dieser Äquivalenz in einer spezifischen Ware,oder in einer einzigen Gleichung der Waren mit einer spezifischen Ware ausgedrückt,ist Preis (商品的交换价值,作为一般等价以及在某特定商品中此等价的程度值,或者表达为该商品同某一特定商品的等值关系,是价格)”。在degrees of degeneracy(简并度),degrees of freedom (自由度)等概念中,degree 是个正整数。简并度,即对应同一能量之不同状态的数目,在德语中简并度的说法为Entartungsgrad,可见degree 就是grade。自由度就是描述体系所需的独立变量数。仔细体会这个定义,“ 描述体系所需的独立变量数”,则自由度的多少取决于如何描述。描述一个粒子在三维空间中的位置需要3个变量,则描述由N(N≥3)个粒子组成的刚体的构型就需要6个独立变量,或者说刚体运动的自由度为6。在热力学—统计力学中有所谓的能量均分定理,谓每一个自由度对比热的贡献都是一个R/2,R是气体普适常数。如果不深入了解这个能量均分定理成立的条件,许多人都难以理解水分子H2O何以有18个自由度,而水(蒸汽)的比热也一直是温度的函数。就比热问题而言,自由度是能量表示涉及的自由度,这包括动能涉及的动量自由度和势能涉及的位置自由度。有趣的是,某些晶体的晶格可看作是两套或多套亚格子(sublattice)套构而成的,这也可以看成是一类自由度。炭单层的六角晶格是由两套三角格子构成的,其中电子的波函数可以比照电子自旋写成两分量的形式。

  Degree 作为函数或者方程的指标, 汉译为次( 次幂) 或者阶。比如 , 函 数

  阶级与秩序

  是? th-degree Legendre polynomial,汉译? - 阶勒让德多项式。The degree of a monomial,汉译单项式的次幂,是变量指数的和,比如项x2y3的degree 是5。单变量的代数方程(univariate polynomial equation),以变量的最高次幂命名,简称为一元二次方程(a second degree monic polynomial equation)、三次(third degree)方程等等。当然了,这类方程有专门的、简单的称谓quadratic,cubic,quartic,quintic,sextic polynomial equations,分别为二次、三次、四次、五次和六次代数方程。五次以上的多项式方程不存在代数解(unsolvable by radicals),对这个问题的理解带来了群论的诞生。群论对物理学的影响,怎样高度评价都不为过。物理学最深刻的学问,所谓的the fearful symmetry(了不起的对称性),来自对一元代数方程的摆弄。对一元多项式解的探索,是一场惊心动魄的天才的游戏。与解方程有关的还有topological degree theory。如果方程有某个容易得到的解,degree theory 可用来证明其它非平凡解的存在。Degree theory看起来和fixed-point theory(固定点理论), knot theory( 纽结理论) 有关,具体内容笔者不懂,此处不论。

  4 Order

Order 简直就是一个充斥数学和物理学领域的一个词汇。Order 的西语本意也是“放成一溜儿(straightrow,regular series)”的意思,可作为名字和动词使用。Order frequently refers to orderliness, a desire for organization。存在总是表现出某种意义上的order,这让认识世界成为可能。Objects should be ordered in order to bring in some order and clarity(为了有序和明晰,应该为对象排序),这几乎成了科学家的共识。排序、分类是研究的前期准备。

Order 是个用得太多的词,可以想见它的汉译会花样繁多。Order 在物理语境中一般被译成序,如orderparameter (序参量),topological order(拓扑序),off-diagonal long-rangeorder (非对角长程有序),等等。过去分词形式ordered 用作形容词,如晶体就是ordered structure (有序结构)。Order 的对立面是disorder,formless,最无序的存在是chaos (混沌),指the disorder of formless matter and infinite space (由无形的物质和无限的空间一起构成的无序)。混沌被当作有序之宇宙出现之前的状态,也就是说当前的有序状态是自完全无序中发生的,order out of chaos,哈,多哲学。

Order 出现的语境,更多的还是和排序有关,比如lexicographical ordering (字典编纂采用的排序),electrons are always added in order of increasing energy(电子按照能量递增的顺序被加进来),the order of differentiation or integration( 微分、积分的次序),等。微分、积分以及乘积的顺序有时候没关系(immaterial),有时候关系重大,结果依赖于顺序的就意味着别样的数学结构和物理,比如非交换代数或者物理里的非对易算符。有时候,有些源自order 的词从我们的角度来看,会以为排序的意思不明显,比如coordinates和ordinate 就给译成了坐标和纵坐标(vertical ordinate),但请记住这里的关键是这些数值具有排序的含义在里边。有些地方把笛卡尔坐标系的x-轴称为horizontal ordinate(水平坐标),但其实有时候x-轴的对象不是可排序的量,如职工工资分布图,工资是可排序的,职工则无所谓序。当我们把y-轴理解为ordinate时x-轴有专有名词abscissa,是个标记(锯痕?)而已。此外,如lineardimensions are of the order of L,汉译为线性尺度在L的量级,字面上可看到的意思是若排列的话,该尺度应该可与L 等量齐观的。Order of magnitude,量之大小在序列中的位置,汉译干脆就是数量级。

数字的用法分为ordinal numbers( 序数) 和cardinal number ( 基数),前者明显与order有关,而后者也不免和order 有关。一个集合的元素数目,是集合的cardinality (集合的势),而群的元素数,当然也是cardinality, 又被称为order of group,汉译“群阶”。与此同时,群元素g 的period (周期),即使得gm=1 成立的最小整数m,也称为该群元素的order。群阶和元素的阶反映了群的内在结构。大致说来,一个群,其群阶的因子分解越复杂,这个群的结构就越复杂。不仅群和群元素有order 的概念,群的特征标(character)也有order的说法。

Order 在许多场合下有排序的意思,与其连用的数词应是序数词,如second-order differential equation(二阶微分方程),third-order recurring sequences (二阶递归序列),first-order approximation (一阶近似),等等。物理学的方程被限制在(第)二阶(偏)微分方程的层面,学会了解二阶(偏)微分方程,一个纯数学家也许比许多物理学家更象物理学家。量子力学以及后继的发展被有些人频繁以革命誉之,属不通之论,其governing equations 模样可以变得复杂可怕,但属于二阶微分方程却是不变的。

  5 Rank

中文的秩,序也,次也,可连用为秩序、秩次(官阶的高下),还有秩叙(次序)、秩然(秩序井然)、秩如等词。秩既然用来表示官阶的高下,相应的标识就有秩服(区别官阶的服饰)、秩俸(分级别的俸禄)等委婉语。秩被用来翻译英文数理概念中的rank,日常表述的rank,如military rank (军阶)还是用阶级加以翻译。中国古代的官员有华丽花哨的秩服,今天各国军队的military rank 则用华丽花哨的徽章(insignia)加以标识。

Rank,与range,arrange 同源,意为to arrange in order,特别是排成行。作为及物和非及物动词用,rank 一般是排序的意思,如to rank third on a list ( 位列第三), qualitative ranking of various ions toward their ability to precipitate a mixture of hen egg white proteins (根据使得鸡蛋白沉淀的能力把离子定性地加以排序), Alfred Nobel 在设立诺贝尔奖时将物理学排在第一位(ranked physics as the first one), 等等。Rank 作为名词表示次序,汉语的翻译比较随意, 比如people from allranks of life (各阶层人民),a poet of the first rank ( 一流诗人), 等等。Rank 作为排序的意思强调是排成行,国际象棋棋盘上空格的行与列,英文用的即是rank 与file;相应地,对于矩阵的行与列,英文用的是row与column。

Rank 作为科学概念我们知道有rank of a matrix 矩阵的秩的说法。Rank 是矩阵的一个基本特征。把矩阵的行(列)看成一组矢量,这组矢量中线性无关的矢量的数量即是所谓的rank,也即行(列)矢量所张空间的维度。对于一个矩阵,行和列具有相同的秩,也就是矩阵的秩。考虑到矩阵同线性方程组和线性变换(算符)相联系,因此矩阵A 的秩是线性方程组A·x=c 非简并性的度量,也是线性变换y=A·x 之像空间的维度。

在物理上,我们知道能量是标量(scalar),动量、位置是矢量(vector),而角动量L= r? ×p?是贋矢量等等,这些可以用张量(tensor)的语言统一处理。张量是描述张量之间线性关系的几何对象(有点循环定义的味道哈),张量的rank (也叫order或者degree)就是用来表示张量的数列的维度,也即所需指标的个数。由此可知,能量,动量(位置)和角动量分别是rank-0,rank-1 和rank-2张量。针对某个标量(质量,电荷)的空间分布定义的四极矩张量, Q=∫Ωρ(3rirj - |r|2δij)d3r , 就是无迹的rank-2 张量。电位移D (矢量)对应力张量σ(rank-2张量)的响应,或者应变张量ε(rank-2 张量)对电场E (矢量)的响应,相应的系数就是rank-3张量。

涉及线性行为的代数、变换和算符等概念都会有rank 这个特征,因此有(李)代数的秩,(不可约)张量算符的秩等说法。Module (模式)概念也有秩的说法,比如rank 2 的自由Z-module 不过是Ok = Z ?ωZ 的一种装酷的说法而已,其中ω ∈Ok ,Ok 为一代数整数集合。对椭圆曲线y2=x3+Ax+B 也有rank 这么一个量,比如椭圆曲线y2=x3-2 和y2=x3-4, 其Mordell—Weil rank 就是1。这种秩有什么意思,怎么计算,笔者不懂。

收起全文

辛几何&李代数

数据挖掘十大经典算法

数据挖掘十大经典算法

一、 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方法也可以认为是一种前剪枝;后剪枝是指构造出完整的决策树之后再来考查哪些子树可以剪掉。 
在分类回归树中可以使用的后剪枝方法有多种,比如:代价复杂性剪枝、最小误差剪枝、悲观误差剪枝等等。这里我们只介绍代价复杂性剪枝法。 

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

收起全文

辛几何&李代数

“星系自转速度曲线”讨论

“星系自转速度曲线”讨论

1.&&暗物质&产生&引力&&[1]1.1&暗物质&大量存在在宇宙学中,&暗物质&是指无法通过电磁波的观测进行研究,也就是不与电磁力产生作用的物质。人们目前只能通过引力产生的效应得知,而且已经发现宇宙中有大量&暗物质&的存在。1.2&星系自转速度曲线&美国女天文学家薇拉& 鲁宾观测星系转速时,发现星系外侧的行星旋转速度较牛顿引力预期的快,故推测是有数量庞大的... 阅读全文

 1.“‘暗物质’产生‘引力’” [1]

    1.1“暗物质”大量存在

    在宇宙学中,“暗物质”是指无法通过电磁波的观测进行研究,也就是不与电磁力产生作用的物质。人们目前只能通过引力产生的效应得知,而且已经发现宇宙中有大量“暗物质”的存在。

    1.2“星系自转速度曲线”

    美国女天文学家薇拉· 鲁宾观测星系转速时,发现星系外侧的行星旋转速度较牛顿引力预期的快,故推测是有数量庞大的质能拉住星系外侧组成,以使其不致因过大的离心力而脱离星系。

 

“星系自转速度曲线”讨论
图1

    2.“‘暗能量’均匀分布” [2]

    2.1“超流体特性” [3][4]

    在物理宇宙学中,暗能量是一种充溢空间的、增加宇宙膨胀速度的难以察觉的能量形式。

暗能量在宇宙中各向同性,密度非常小,且不与通常物质发生任何除引力之外的已知的相互作用(即电磁、强、弱相互作用)。

    2.2“量大、均匀、密度小,有‘负压’”

    暗能量的密度(ρ0)又非常之小,大概1029 克/厘米3(ρ0=1029 克/厘米3),因此地球上的实验室应当很难直接发现它。但是因为暗能量应该充满了所有的宇宙空间,因此它占宇宙质能总量的68%,这显著地影响了宇宙整体的演化。目前的两类暗物质理论——宇宙常数理论和基本标量场理论,都包含了暗能量的两种重要性质——均匀和负压。

    3.“引力”与“质量”

    3.1“引力”源于“质量”

    “万有引力”源于“质量”。根据牛顿定律,若设质量分别为M、m的两质点间的作用力为F,G为引力常数,r为两质点间的距离,则有①:

“星系自转速度曲线”讨论 

    3.2“质能方程”

    爱因斯坦著名的质能方程式②:

“星系自转速度曲线”讨论    

    其中,E表示能量,m代表质量,而c则表示光速常量。

    4.“暗物质”的“质量”与“暗能量”的“能量”

    因为“引力”源于“质量”,而“暗物质”产生“引力”,所以我们可以认为,“暗物质”具有可以产生“引力”的“质量”。

    上述的“暗能量” :“不与通常物质发生任何除引力之外的已知的相互作用(即电磁、强、弱相互作用)”,亦昭示着“暗能量”含有“质量”的“基因”。

    在这里,我们假设“暗能量”与“普通能量”一样也满足“质能方程”,即若“暗能量”为E0,则E0=m0c2,其中c为光速常量,m0就是“暗能量”E0的“质量”,称为“暗能量质量”。并且,我们认为“暗能量”E0的“引力效应”,就是“暗能量质量”m0产生的。

    于是,“暗物质”的“质量”与“暗能量”的“能量”,在“扩展了的”“质能方程”下,就得到了“统一”。不仅如此,我们还把产生“引力效应”的“原因”“统一”于“质量”之下:“普通物质质量”、“暗物质质量”和“暗能量质量”。

    也就是说,凡是具有“质量”的“物质”,无论是“普通物质”,还是所谓的“暗物质”、“暗能量”,都产生“引力”且满足“万有引力公式” ①。

    或者说,在上述“广义的‘能量’、‘质量’”以及其满足的“扩展了的‘质能方程’”下,“引力”的来源和遵循的定律公式都是“等效同式”的。

    因此,我们可以有“质量万有引力公式” ①,也可以有“能量万有引力公式”③:[5]

“星系自转速度曲线”讨论

 

    其中,F为两“能量点”(或“能量中心”)之间的作用力,G为引力常数,E、E2分别为两“能量点”(或“能量中心”)的能量,r为两“能量点”(或“能量中心”)间的距离。这里的“能量点”(或“能量中心”)的“能量”,可以是“普通能量”,比如“球状闪电” 的“能量球”, [6]也可以是密度ρ0=1029 克/厘米3、占宇宙质能总量的68%的“暗能量”。

    5.“银河系中心”“引力”讨论

    5.1“银河系中心质量”“引力”

    若设在球面上作环绕运动(圆周运动)的物体的速度大小为v,中心质量为m,球面半径为r,G为引力常数,则有r=Gm/v2,即④:

“星系自转速度曲线”讨论

 

    太阳位于一条叫做猎户臂的支臂上,距离银河系中心约2.64万光年,太阳的轨道速度是217千米/秒。[7]

假定太阳距离银河系中心约2.64万光年的轨道上,其速度217千米/秒,是完全由中心质量m的万有引力产生的。由1光年=9.4607×1015米,若记r=2.64万光年=2.64×104×9.4607×1015米=2.4976248×1020米,v=217千米/秒=2.17×105米/秒,取G=6.67×10-11 牛顿·米2 /千克2,则有:

    m=rv2/G=2.4976248×1020×(2.17×1052/(6.67×10-11

=2.4976248×1020×(4.7089×1010)/(6.67×10-11

=11.7610658445×1030/(6.67×10-11

=1.7632782376×1041(千克)

≈1.76×1041(千克)

    即“银河系中心质量”m≈1.76×1041(千克)。

    明显地,根据牛顿“万有引力定律”,“银河系中心质量”m≈1.76×1041千克会对银河系的恒星产生“引力”。

    5.2“银河系‘暗能量’”“引力”

    5.2.1“暗能量”“球状均匀分布”

    因为“暗能量”在宇宙空间中是“均匀分布”的,所以“暗能量”在银河系的分布,可以看成是围绕“银河系中心”“球面状或球状均匀分布”。其密度为ρ0=1029 克/厘米3=1026千克/米3

 

“星系自转速度曲线”讨论
图2

    漩涡星系的星体分布具有扁平的盘状结构。图2是一般漩涡星系的测面示意图,其中A是星系核,B是发光盘,C是星系核外围球状分布的晕状物质,D是发光盘的平面延伸区域,在此部分发现大量的氢气云,半径已延伸到几十kpc(pc为秒差距,kpc为千秒差距),边界在何处仍未知。E是一个包含D的大球体,其半径目前也是未知的。[8]

    若设到银河系中心为r的球体(体积为4πr3/3)内的“暗能量”为E0,根据“质能方程”,则有“暗能量E0的质量”m0=E0/c204πr3/3=(4πρ0/3)r3

    5.2.2“暗能量”“中心引力作用”

    《“光子球面”对“引力”的“屏蔽效应”》 [9]一文认为,“能量球面”或“球状能量”的“能量”对球面或球外的作用力,与“能量球面”或“球状能量”的“能量”集中于球心一点的作用力是“等效的”;

“能量球面” 或“球状能量” 对球面或球外的相互作用是以一个“整体”呈现的——相当于全部集中在球心。

 

“星系自转速度曲线”讨论
图3

    可见,“银河系中心”产生“引力”的“质量”有两个:一个是“普通质量”m≈1.76×1037千克,另一个是“围绕银河系中心均匀球状分布”的“暗能量质量”m0=(4πρ0/3)r3

    所以,若设恒星Q到绕银河系中心旋转的半径为r,则可以认为恒星Q“受到的来自银河系中心的‘万有引力’”,是由“质量”M产生的,而M=m+m0

    6.“星系自转速度曲线”讨论

    6.1“‘暗能量质量’越来越大”

    由④有v2=Gm/r即v=√Gm/r。

    因此,若设上述恒星Q的旋转速度大小为v,则有v=√GM/r=√G(m+m0)/r。

    下面,我们讨论:v2=G(m+m0)/r=Gm/r+Gm0/r。

    又m0=(4πρ0/3)r3,可有:Gm0/r=G(4πρ0/3)r3/r=(4πGρ0/3)r2

    若取G=6.67×10-11 牛顿·米2 /千克2,π=3.14,ρ0=1029 克/厘米3=1026千克/米3,则有:

    Gm0/r=(4πGρ0/3)r2

=(4×3.14×6.67×10-11×1026/3)r2

=(12.25×6.67×10-11×1026/3)r2

=(83.7752×10-37/3)r2

=(27.9250666667×10-37)r2

=(2.79250666667×10-38)r2

    所以,v2=G(m+m0)/r=Gm/r+Gm0/r

=Gm/r+(2.79250666667×10-38)r2

    可见,恒星Q的旋转速度的平方由两部分组成,一部分是银河系中心质量产生的,数值为Gm/r,其大小随半径r的增大而减小;另一部分是由“暗能量质量”产生的,但是,因为随着半径的增大“暗能量质量”也在增大,是一个变量,是一个不断增大的数值,所以这部分随着半径的增大而增大。

    6.2“暗能量质量在‘中尺度’上的影响才开始明显”

    若设v12=Gm/r,v02=(2.79250666667×10-38)r2,则有v2=v12+v02

    明显地,对于v02=(2.79250666667×10-38)r2来说,由于数值2.79250666667×10-38较小,在10-38数量级,当r不大时,v02太小了,对v2的影响很小。也就是对恒星Q的旋转速度影响很小。所以,在一个“较小尺度内”——“恒星—行星系统内”,比如在太阳系内,其表现很“微弱”、“作用不明显”,几乎没有影响;但是,在“星系团”或“超星系团”等“中尺度”上,比如在银河系的中部或边缘部分,随着半径r的增大r2增大明显,其影响逐渐增加。

    比如,当r=5.37kpc时,由1pc=3.2616光年,1光年=9.4607×1015米,可得:

    r=5.37kpc

=5.37×1000×3.2616光年

=17.514792×1000光年

=1.7514792万光年

=1.657021926744×1020米。

    代入:v02=(2.79250666667×10-38)r2

=(2.79250666667×10-38)×(1.657021926744×10202

=(2.79250666667×10-38)×(2.745721665710399×1040

=7.667446056316546×102

=766.7446056316546(米/秒)2

≈766.75米/秒2

    也就是说,当r=5.37kpc时,由v2=v12+v02有:

v2=v12+v02=Gm/r+v02≈ Gm/r+766.75,即v2≈Gm/r+766.75。

    于是,可以看出当r>=5.37kpc时,“暗能量质量”在银河系中心产生的“引力”,已经上升到了“不可忽视”的程度了,其影响开始明显。

    6.3“恒星旋转速度在‘中尺度’附近平坦”

    若令v12=v02,则有Gm/r=(2.79250666667×10-38)r2,即:

r3=Gm/(2.79250666667×10-38)。

    代入G=6.67×10-11 牛顿·米2 /千克2,有r3=Gm/(2.79250666667×10-38)=(6.67×10-11)m/(2.79250666667×10-38)=(2.388535031844283×1027)m。

    若取:“银河系中心质量”m≈1.76×1041千克,则有:

    r3=(2.388535031844283×1027)m

=(2.388535031844283×1027)×1.76×1041

=2.388535031844283×1.76×1068

=4.203821656045938×1068

=420.3821656045938×1066

    可得:r=7.491143118824429×1022米。

    由1pc=3.2616光年,1光年=9.4607×1015米,记:

    T=7.491143118824429×1022/9.4607×1015光年

=0.791817002845924×1022/1015光年

=0.791817002845924×107光年

=7.91817002845924×106光年

=7.91817002845924×102万光年

≈791.817万光年

≈2427.695kpc。

    所以说,银河系里,在“中尺度”上,“普通中心质量”使得恒星的旋转速度随半径的增大而“减小”。但是,“暗能量质量”因随半径的增大而增加,导致了“暗能量质量”使得恒星的旋转速度随着半径的增大而“增大”。两者在r=2427.695kpc(791.817万光年)的“T”点对恒星的速度影响“相当”,其结果是保持了“v2的稳定”。因此,在距离银河系中心大约5.37kpc(1.7514792万光年)<r<2427.695kpc(791.817万光年)的广大区域里,恒星的旋转速度曲线是平坦的——这是因为:上述“减小”与“增大”的幅度在这个区域内是“相当”的。

“星系自转速度曲线”讨论
图4

 

“星系自转速度曲线”讨论
图5

    6.4“恒星旋转速度在‘更大尺度’上逐渐增大”

    从上述的分析中可以看到,上述中的“T”点是“银河系中心普通质量”m与“银河系内‘暗能量质量’m0对恒星的“引力作用”的“相当点”。在这个点向外,m0对恒星的“引力作用”,将大于m对恒星的“引力作用”,并且m0的“增大”“幅度”大于m的“减小”“幅度”,所以当r>2427.695kpc(791.817万光年)时,随着半径的增大,恒星的速度将逐渐增大,恒星的旋转曲线也将缓慢上升。

 

“星系自转速度曲线”讨论
图6

    综上所述,我们用银河系中心质量的万有引力和“暗能量”对银河系的作用,对银河系内恒星的旋转曲线进行了讨论,不仅能够在一定程度上解释“旋转曲线”的“平坦”,还预判了在“更大尺度”上,“旋转曲线”将上升——其来源就是:“暗物质”是“暗能量”的“作用表现”。

    7.“空间波”是“暗能量”

    《“空间波”是“暗能量”和“暗物质”吗?!》 [10]一文认为,变化的“引力场”产生“空间场”,变化的“空间场”产生“引力场”。“空间波”:由变化的“引力场”与变化的“空间场”相互激发而产生。“空间波”就是“暗能量”:占宇宙总量的95%以上,主导着宇宙的演化——“暗能量”、“暗物质”效应。

    整个“宇宙空间”都充满了“空间波”——“空间波流体”——“空间波海洋”。就像地球海洋里的“水”那样:一方面,“小尺度”上,“水”对轮船有“压强”——相当于“宇宙空间“的“暗物质“效应;另一方面,轮船还受到“洋流”的整体影响——相当于“宇宙空间“的“暗能量“效应。

 

“星系自转速度曲线”讨论
图7

 

收起全文

辛几何&李代数

异常数据的剔除与遗失数据的弥补

异常数据的剔除与遗失数据的弥补

在处理实验数据的时候,我们常常会遇到个别数据偏离预期或大量统计数据结果的情况,如果我们把这些数据和正常数据放在一起进行统计,可能会影响实验结果的正确性,如果把这些数据简单地剔除,又可能忽略了重要的实验信息。这里重要的问题是如何判断异常数据,然后将其剔除。判断和剔除异常数据是数据处理中的一项重要任务,目前的一些方法还不是十分完善,有待进一步研究和探索。 ... 阅读全文

在处理实验数据的时候,我们常常会遇到个别数据偏离预期或大量统计数据结果的情况,如果我们把这些数据和正常数据放在一起进行统计,可能会影响实验结果的正确性,如果把这些数据简单地剔除,又可能忽略了重要的实验信息。这里重要的问题是如何判断异常数据,然后将其剔除。判断和剔除异常数据是数据处理中的一项重要任务,目前的一些方法还不是十分完善,有待进一步研究和探索。

目前人们对异常数据的判别与剔除主要采用物理判别法和统计判别法两种方法。

所谓物理判别法就是根据人们对客观事物已有的认识,判别由于外界干扰、人为误差等原因造成实测数据偏离正常结果,在实验过程中随时判断,随时剔除。

 

统计判别法是给定一个置信概率,并确定一个置信限,凡超过此限的误差,就认为它不属于随机误差范围,将其视为异常数据剔除。

第一节  拉依达准则

如果实验数据的总体x是服从正态分布的,则

异常数据的剔除与遗失数据的弥补

式中,μ与σ分别表示正态总体的数学期望和标准差。此时,在实验数据中出现大于μ+3σ或小于μ—3σ数据的概率是很小的。因此,根据上式对于大于μ+3σ或小于μ—3σ的实验数据作为异常数据,予以剔除。

具体计算方法如下:

对于实验数据x1, x2, x3,……xn先计算其均值

 异常数据的剔除与遗失数据的弥补

i=1,2,3,n

再计算残差

异常数据的剔除与遗失数据的弥补

则标准差

异常数据的剔除与遗失数据的弥补

如果某个测量值异常数据的剔除与遗失数据的弥补的残差满足

异常数据的剔除与遗失数据的弥补

则认为xd异常数据,予以剔除

 

拉依达准则是最常用的异常数据判定与剔除准则

第二节  肖维勒准则

如果某个测量值 异常数据的剔除与遗失数据的弥补的残差满足

 异常数据的剔除与遗失数据的弥补

 

xd被视为异常数据,予以剔除。上式中,wn可查表得到。其中,残差vd和标准差σ的计算方法同上。

第三节  格拉布斯准则

对于服从正态分布的实验数据:

 x1, x2, x3,……xn

将实验数据按值的大小排成顺序统计量:

 x(1),x(2), x(3),……≤x(n)

格拉布斯导出了

  异常数据的剔除与遗失数据的弥补

    的分布。取置信度α,可得T0(n, α),

  异常数据的剔除与遗失数据的弥补

    如果

  异常数据的剔除与遗失数据的弥补

则认为xd为异常数据,应予剔除

T0(n, α)的值可查表得到

T0(n, α)值表

异常数据的剔除与遗失数据的弥补 

异常数据的剔除与遗失数据的弥补 

采用格拉布斯方法判定异常数据的过程如下:

1. 选定危险率α

α是一个较小的百分数,例如1%2.5%5%,它是采用格拉布斯方法判定异常数据出现误判的几率。

2. 计算T

如果x(1)是可疑数据,则令

异常数据的剔除与遗失数据的弥补

如果x(n)是可疑数据,则令

  异常数据的剔除与遗失数据的弥补

其中

 异常数据的剔除与遗失数据的弥补

异常数据的剔除与遗失数据的弥补

3. 根据nα,查表得到T0(n, α)值

4. 如果T≥T0(n, α),则所怀疑的数据是异常数据,应予剔除。如果T< T0(n, α),则所怀疑的数据不是异常数据,不能剔除。

 

采用此法判异常数据产生误判的几率为α

第四节  狄克逊准则

狄克逊准则是通过极差比判定和剔除异常数据。与一般比较简单极差的方法不同,该准则为了提高判断效率,对不同的实验量测定数应用不同的极差比进行计算。该准则认为异常数据应该是最大数据和最小数据,因此该其基本方法是将数据按大小排队,检验最大数据和最小数据是否异常数据。具体做法如下:

 

将实验数据xi按值的大小排成顺序统计量

x(1),x(2), x(3),……≤x(n)

按表1-3-1计算f0值,然后根据表1-3-1f0f(n,a)进行比较,如果

 f0 > f(n,a)

    则判定该数据为异常数据,予以剔除。

1-3-1   狄克逊系数f(n,a)f0的计算公式

 

异常数据的剔除与遗失数据的弥补

第五节  t检验准则(罗马诺夫斯基准则)

t检验准则与狄克逊准则相似,也是检验最大实验数据和最小实验数据。首先将实验数据按大小排列

 x(1),x(2), x(3),……≤x(n)

对最小数据和最大数据分别进行检验,如果

  异常数据的剔除与遗失数据的弥补

   

     异常数据的剔除与遗失数据的弥补

x(1)x(n)是异常数据,应予剔除。

式中异常数据的剔除与遗失数据的弥补 异常数据的剔除与遗失数据的弥补 分别为不包括x(1)x(n)的均值和标准差。即

 

 异常数据的剔除与遗失数据的弥补

 异常数据的剔除与遗失数据的弥补

 

t检验中的K(n,α)可查表得到。

第六节  遗失数据的弥补

在一些情况下,每个实验点都是经过精心设计选择的,此时每个实验数据都是十分重要的。但是,如果不慎遗失了某些实验数据,或某些实验操作失误缺少了某些实验数据,该如何处理呢?当然最好的办法是补做这些实验。但是,本节要介绍的是一种特殊情况——实验数据遗失,而又无法补做实验时的处理方法,也就是如何用数学的方法来弥补遗失的实验数据。

这里方法主要有两种:

一、当实验数据有重复,并且每一批实验至少有一个数据没有遗失时,可以用未遗失的数据的平均值代替遗失的数据。

1-3-2所示为一组实验数据,其中ab为遗失的数据,现在我们来弥补这两个数据:

1-3-2  有重复实验数据的弥补

   异常数据的剔除与遗失数据的弥补

异常数据的剔除与遗失数据的弥补 =(1.5+2.4+3.5+3.3+2.2+2.1)/6=2.5

异常数据的剔除与遗失数据的弥补 =(1.2+1.4+1.2+1.3+1.6+1.5)/6=1.37

这样我们就得到了遗失数据的估计值。

二、如果没有重复 数据得实验,则用下法弥补:

1-3-3所示为一组实验数据,其中ab为遗失的数据。与表1-3-2不同的是,这组数据没有重复数据。现在我们来弥补这两个数据:

1-3-3  没有重复实验数据的弥补

异常数据的剔除与遗失数据的弥补

  异常数据的剔除与遗失数据的弥补

则总离差平方和

LT=3.522.322.02a2+2.02+1.92+2.02+1.52+1.22+1.42+b2+0.32-c

组间离差平方和

LA=[7.82+(3.9+a)2+4.72+(1.7+b)2]/3 - c

LB=[(6.9+a)2+(5.8+b)2+5.42]/4 – c

剩余离差平方和

Le= LT- LA- LB

合理的ab值应使剩余离差平方和Le最小,因此,我们的任务是求得Le最小时的ab值。为此。对Le求偏导数,并令其等于零:

异常数据的剔除与遗失数据的弥补

可求得

a=2.95

b=0.53





收起全文

辛几何&李代数

近场光学原理简介

近场光学原理简介

所谓近场光学,是相对于远场光学而言。传统的光学理论,如几何光学、物理光学等,通常只研究远离光源或者远离物体的光场分布,一般统称为远场光学。远场光学在原理上存在着一个远场衍射极限,限制了利用远场光学原理进行显微和其它光学应用时的最小分辨尺寸和最小标记尺寸。而近场光学则研究距离光源或物体一个波长范围内的光场分布。在近场光学研究领域,远场衍射极限被打破,分辨率极限... 阅读全文

 

   

    所谓近场光学,是相对于远场光学而言。传统的光学理论,如几何光学、物理光学等,通常只研究远离光源或者远离物体的光场分布,一般统称为远场光学。远场光学在原理上存在着一个远场衍射极限,限制了利用远场光学原理进行显微和其它光学应用时的最小分辨尺寸和最小标记尺寸。而近场光学则研究距离光源或物体一个波长范围内的光场分布。在近场光学研究领域,远场衍射极限被打破,分辨率极限在原理上不再受到任何限制,可以无限地小,从而基于近场光学原理可以提高显微成像与其它光学应用时的光学分辨率。

 

1. 远场光学的衍射分辨极限

远场光学的分辨率受到衍射效应的限制。1873年,德国科学家阿贝(Abbe)根据衍射理论首次推导出衍射分辨极限,即能够被光学分辨的两点间的距离总是大于波长的一半。后来,瑞利(Rayleigh)将阿贝衍射理论归纳为一个公式:

 

 

1-1

这就是人们所熟知的瑞利判据。该判据表明,当且仅当物体上两点之间的距离d大于或等于不等式右边所规定的量时,才被看作是分开的两点。这个量与入射光在真空中的波长l、物方折射率n以及显微物镜在物方的半孔径角q有关。nsin(q)通常也被称作数值孔径(Numerical ApertureN.A.)。

由瑞利判据可知,提高分辨率包括两种方法:其一,尽可能选择短的辐射波长,如利用蓝光、紫外光、x射线、电子等;其二,提高数值孔径,但若不考虑较少和较难使用的油浸物镜(N.A. = 1.5左右)与固体浸没透镜,数值孔径的最大值不超过1,因此远场光学的分辨极限最高只能达到l/2

 

2. 近场光学的超衍射极限分辨率

当光和物体发生相互作用后,在物体表面(xy面)形成携带物体信息的光场分布,可以使用该场(即z = 0平面上的场)的复振幅的分布特性来表示样品。与空间频谱的关系由傅立叶变换确定:

 

 

1-2

fxfy分别为沿xy方向的空间频率分量,反比于物体的结构尺寸。当光传播到探测平面z时,复振幅和空间频谱满足同样的关系:

 

 

1-3

光场分布满足标量亥姆霍兹方程:

 

 

1-4

其中,为总空间频率。将式1-3代入式1-4得:

 

 

1-5

为待定系数,由初始条件确定。z = 0处为物平面,其空间频谱为,因此有:

 

 

1-6

将上式代入式1-3得:

 

 

 

1-7

可见,探测面z上的光场分布是z = 0平面上的平面波乘以传播因子后的线性叠加,波的性质和传播方向取决于fxfy的大小。

当时,式1-6的指数部分为虚宗量,此时在z = 0平面上形成空间频率满足的平面波,即空间频率的每一分量都可以向前传播形成辐射波或传播波,为波的相位变化因子。

当时,对应于光场分布的高空间频率fxfy,即物体上的小尺寸结构,式1-6变成:

 

 

1-8

指数部分的宗量为实数,表明振幅随z的增加呈指数规律衰减,即该波只局域在物体表面而不能向远处传播,形成局域在物体表面的近场隐失波。而式1-7则表示以光波频率振荡的波在xy方向可以传播,沿z方向衰减。

从以上分析可以看到,在物体表面的近场光包含两种成分,一种是可以向远处传播的传播场;另一种是被局域在物体表面,在物体之外迅速衰减的非辐射隐失场。隐失场是非均匀场,其性质与样品的性质和结构有密切关系。这种场因物质的存在而存在,不能在自由空间独立地存在。

物体亚波长结构的信息隐藏在隐失场中。隐失场的强度随着离物体距离的增大而迅速衰减,衰减的速度与空间频率成正比,所以结构越是精细,场就越被强烈地束缚在物体表面。而远场只有传播波,仅包含电磁场的低空间频率部分,不包含样品的亚波长结构信息。瑞利判剧建立在远场探测传播场的基础之上,仅在远场成立,而近场的隐失场并不受它的约束。因而,若想获得超衍射极限的分辨率,必须利用近场隐失场。

 

3. 隐失波场的探测

    近场探测的原理是:(1)无论用传播场还是隐失场照明,高频物体均产生隐失场;(2)所产生的隐失场不服从瑞利判据,它们能够在远小于波长的距离上显示局部的强烈变化;(3)通过采用一个小的有限物体(如孔径或者无孔径探针)将隐失场转换成传播场和隐失场的方法,这种不可探测的高频局部场可以反过来转换成传播场;(4)将后者导向合适的远端探测器。注意,隐失场—传播场的转换是线性的:被探测到的场正比于给定点的隐失场的坡印廷矢量。那么传播场将忠实地复制隐失场局域的剧烈变化。因此,用探测器探测到的传播场中包含物体的高频信息。为了产生二维图象,使这个小的有限物体沿物体表面进行扫描,由所得到的探测数据重构图象。

 

 

 

             近场探测原理

近场光学原理简介

 

 

镀金属膜纳米光纤探针截面图(SII

4.近场光学/纳米光学的应用

基于近场光学技术的光学分辨率可以达到纳米量级,突破了传统光学的分辨率衍射极限,这将为科学研究的诸多领域,尤其是纳米科技的发展提供有力的操作、测量方法和仪器系统。目前,基于隐失场探测的近场扫描光学显微镜、纳米局域测量表征的近场拉曼光谱仪已经成为纳米物理、纳米生物学、纳米化学、纳米材料科学等领域中的重要工具,并且应用范围正在不断地扩大。而基于近场光学/纳米光学的其它应用,如纳米光刻和超高密度近场光存储、纳米结构表面等离子光学元器件、纳米尺度粒子的捕获与操纵等等,也吸引了众多科学工作者的注意。

收起全文

辛几何&李代数

折纸几何公理

折纸几何公理

1991 年,日裔意大利数学家藤田文章(Humiaki Huzita) 指出了折纸过程中的 6 种基本操作,也叫做折纸几何公理。假定所有折纸操作均在理想的平面上进行,并且所有折痕都是直线,那么这些公理描述了通过折纸可能达成的所有数学操作: 1. 已知 A 、 B 两点,可以折出一条经过 A 、 B 的折痕 2. 已知 A 、 B 两点,可以把点 ... 阅读全文

 

1991 年,日裔意大利数学家藤田文章(Humiaki Huzita) 指出了折纸过程中的 6 种基本操作,也叫做折纸几何公理。假定所有折纸操作均在理想的平面上进行,并且所有折痕都是直线,那么这些公理描述了通过折纸可能达成的所有数学操作:

1. 已知 A 、 B 两点,可以折出一条经过 A 、 B 的折痕
折纸几何公理
2. 已知 A 、 B 两点,可以把点 A 折到点 B 上去
折纸几何公理
3. 已知 a 、 b 两条直线,可以把直线 a 折到直线 b 上去
折纸几何公理
4. 已知点 A 和直线 a ,可以沿着一条过 A 点的折痕,把 a 折到自身上
折纸几何公理
5. 已知 A 、 B 两点和直线 a ,可以沿着一条过 B 点的折痕,把 A 折到 a 上
折纸几何公理
6. 已知 A 、 B 两点和 a 、 b 两直线,可以把 A 、 B 分别折到 a 、 b 上
折纸几何公理

容易看出,它们实际上对应着不同的几何作图操作。例如,操作 1 实际上相当于连接已知两点,操作 2 实际上相当于作出已知两点的连线的垂直平分线,操作 3 则相当于作出已知线段的夹角的角平分线,操作 4 则相当于过已知点作已知线的垂线。真正强大的则是后面两项操作,它们确定出来的折痕要满足一系列复杂的特征,不是尺规作图一两下能作出来的(有时甚至是作不出来的)。正是这两个操作,让折纸几何有别于尺规作图,折纸这门学问从此处开始变得有趣起来。

更有趣的是,操作 5 的解很可能不止一个。在大多数情况下,过一个点有两条能把点 A 折到直线 a 上的折痕。

折纸几何公理

操作 6 则更猛:把已知两点分别折到对应的已知两线上,最多可以有三个解!

折纸几何公理

一组限定条件能同时产生三个解,这让操作 6 变得无比灵活,无比强大。利用一些并不太复杂的解析几何分析,我们能得出操作 6 有三种解的根本原因:满足要求的折痕是一个三次方程的解。也就是说,给出两个已知点和两条对应的已知线后,寻找符合要求的折痕的过程,本质上是在解一个三次方程!

尺规作图到底局限在哪里

相比于折纸的几何操作,尺规作图就显得有些不够“强大”了。不妨让我们先来回顾一下尺规作图里的五个基本操作:

过已知两点作直线给定圆心和圆周上一点作圆寻找直线与直线的交点寻找圆与直线的交点寻找圆与圆的交点

这5项操作看上去变化多端,但前3项操作都是唯一解,后两项操作最多也只能产生两个解。从这个角度来看,尺规作图最多只能解决二次问题,加减乘除和不断开方就已经是尺规作图的极限了。能解决三次问题的折纸规则,势必比尺规作图更加强大。

正因为如此,一些尺规作图无法完成的任务,在折纸几何中却能办到。比如折纸法可以实现作正七边形,而这是无法用尺规作图办到的。

我们有更简单的例子来说明,用折纸法能完成尺规作图办不到的事情。“倍立方体”问题是古希腊三大尺规作图难题之一,它要求把立方体的体积扩大到原来的两倍,本质上是求作 2 的立方根。由于尺规作图最多只能开平方,因而它无法完成“倍立方体”的任务。但是,折纸公理 6 相当于解三次方程,解决“倍立方体”难题似乎是游刃有余。

有意思的是,用纸片折出 2 的立方根比想象中的更加简单。取一张正方形纸片,将它横着划分成三等份(方法有很多,大家不妨自己想想)。然后,将右边界中下面那个三等分点折到正方形内上面那条三等分线上,同时将纸片的右下角顶点折到正方形的左边界。那么,纸片的左边界就被分成了 3√2 : 1 两段。

折纸几何公理

利用勾股定理和相似三角形建立各线段长度的关系,我们不难证明它的正确性。强烈建议大家自己动笔算一算,来看看三次方程是如何产生的。

第7个折纸公理

本文写到这里,大家或许以为故事就结束了吧。 10 年以后也就是 2001 年,事情又有了转折: 数学家羽鳥公士郎(Koshiro Hatori)发现,上述的 6 个折纸公理并不是完整的。 他给出了折纸的第 7 个定理。从形式上看,第 7 公理与已有的公理如出一辙,并不出人意料,很难想象这个公理整整十年里竟然一直没被发现。继续阅读之前,大家不妨先自己想想,这个缺失的操作是什么。这段历史背景无疑让它成为了一个非常有趣的思考题。

补充的公理是:

7. 已知点 A 和 a 、 b 两直线,可以沿着一条垂直于 b 的折痕,把 A 折到 a 上。
折纸几何公理

后来,这 7 条公理就合称为了藤田-羽鳥公理(Huzita–Hatori 公理),你可以在维基百科 上读到这个条目。在 2003 年的一篇文章中,世界顶级折纸 艺术家 罗伯特•朗 (Robert J. Lang )对这些公理进行了一番整理和分析,证明了这 7 条公理已经包含折纸几何中的全部操作了。

看,艺术家都是先搞数学的!

罗伯特•朗注意到,上述 7 项基本操作其实是由一些更基本的操作要素组合而成的,例如“把已知点折到已知线上”、“折痕经过已知点”等等。说得更贴切一些,这些更加基本的操作要素其实是对折痕的“限制条件”。在平面直角坐标系中,折痕完全由斜率和截距确定,它等价于一个包含两个变量的方程。不同的折叠要素对折痕的限制力是不同的,例如“把已知点折到已知点上”就同时要求 x1' = x2 并且 y1' = y2 ,可以建立出两个等量关系,一下子就把折痕的两个变量都限制住了。而“折痕经过已知点”则只能列出一个方程,只能确定一个变量(形式上通常表示为与另一个变量的关系),把折痕的活动范围限制在一个维度里。

不难总结出,基本的折叠限制要素共有 5 个:

(1) 把已知点折到已知点上,确定 2 个变量(2) 把已知点折到已知线上,确定 1 个变量(3) 把已知线折到已知线上,确定 2 个变量(4) 把已知线折到自身上,确定 1 个变量(5) 折痕经过已知点,确定 1 个变量

而折痕本身有 2 个待确定的变量,因此符合要求的折纸操作只有这么几种: (1) , (2) + (2) , (3) , (4) + (4) , (5) + (5) , (2)+(4) , (2) + (5) , (4) + (5) 。但是,这里面有一种组合需要排除掉: (4) + (4) 。在绝大多数情况下, (4) + (4) 实际上都是不可能实现的。如果给出的两条直线不平行,我们无法折叠纸张使得它们都与自身重合,因为没有同时垂直于它们的直线。

另外 7 种则正好对应了前面 7 个公理,既无重合,又无遗漏。折纸几何至此便有了一套完整的公理。

不过,折纸的学问远远没有到此结束。如果允许单次操作同时包含多处折叠,折纸公理将会更复杂,更强大。折纸的极限究竟在哪里,这无疑是一个非常激动人心的话题。

在这里,简单展示几个折纸几何学的例子,分别是三等分角、黄金比例和正六边形。图片由果壳美术设计师 V晶V 制作

折纸几何公理

 

折纸几何公理

 

折纸几何公理

收起全文

辛几何&李代数

欧拉和高斯之间差了几个伯努利

欧拉干完活儿之后没有高斯那个&把脚手架都拆了&的装逼习惯,反而保留所有的motivation和details以便后来者无论智商高低都能follow,导致所有人全特么能看懂他的工作,然后就把欧拉当成了接地气的导师,而不是高高在上的天才&逼格不知不觉间就下来了(但欧拉本人会在意这个?开玩笑!)&欧拉跟高斯的风格对比一下就会发现,很像唐诗中的杜甫和李白。李白有很多... 阅读全文

欧拉干完活儿之后没有高斯那个“把脚手架都拆了”的装逼习惯,反而保留所有的motivation和details以便后来者无论智商高低都能follow,导致所有人全特么能看懂他的工作,然后就把欧拉当成了接地气的导师,而不是高高在上的天才…逼格不知不觉间就下来了(但欧拉本人会在意这个?开玩笑!)…
欧拉跟高斯的风格对比一下就会发现,很像唐诗中的杜甫和李白。李白有很多天外奇想超越时代,把它们一一地写出来,看着就要比杜甫炫酷很多,所以粉丝也多——然而学的人少,因为无迹可寻。
然后人们就觉得杜甫比李白接地气很多——特别是有法可依,这就方便上手自学。然而,一入了门就会发现——看似初等的格律(数学技巧),背后是惊才绝艺,只不过历史主宰了他的取材(研究的问题)罢了。
其实真相是,高斯在天上,欧拉在地平线——我们不能因为二者垂直方向的高低而忽略了两者都是无穷远的事实……

P.S. 如果欧拉也“拆脚手架”,后来的拉马努金看着就像个trivial case。当然欧拉不能真拆,因为当时没有如后来的哈代一般的人物(伯努利在欧拉面前没优势可言,要是等到欧拉死后高斯来验算,那三大数学家里也不会有高斯




收起全文

辛几何&李代数

Linux过时了- 塔能鲍姆-托瓦兹辩论(Tanenbaum–Torvalds debate)

Linux过时了- 塔能鲍姆-托瓦兹辩论(Tanenbaum–Torvalds debate)

塔能鲍姆-托瓦兹辩论(英语:Tanenbaum&Torvalds debate),由Minix创作者安德鲁&斯图尔特&塔能鲍姆(Andrew Stuart &Andy& Tanenbaum,昵称&安迪&,网络上的代号为&ast&)与Linux核心的作者林纳斯&托瓦兹(Linus Torvalds)之间,进行的网络论战,讨论的主题在于操作系统架构的选择。199... 阅读全文

塔能鲍姆-托瓦兹辩论(英语:Tanenbaum–Torvalds debate),由Minix创作者安德鲁·斯图尔特·塔能鲍姆(Andrew Stuart “Andy” Tanenbaum,昵称“安迪”,网络上的代号为“ast”)与Linux核心的作者林纳斯·托瓦兹(Linus Torvalds)之间,进行的网络论战,讨论的主题在于操作系统架构的选择。1992年在Usenet讨论组群comp.os.minix上发起。塔能鲍姆认为,以微内核架构设计的操作系统,在理论上,比宏内核架构更加优越,Linux采用的宏内核架构是过时的。但是林纳斯·托瓦兹以开发实务上的观点展开反击,并比较Minix与Linux的性能差异。稍后一些著名的黑客也加入讨论,如彼得·麦唐纳(Peter MacDonald,他创造了第一个linux发行版,Softlanding Linux System。他也协助发展了Wine软件)、大卫·米勒(David Stephen Miller,网络昵称为 DaveM,负责Linux核心网络功能以及SPARC平台的制作。他也参与其他开源软件的开发,是GCC督导委员会的成员之一)、曹子德(西奥多·曹,英语:Theodore Y. Ts’o,中文姓名曹子德,小名泰德·曹Ted Tso,他是Linux内核在北美最早的开发者,负责ext2、ext3与ext4档案系统的开发与维护工作。他也是e2fsprogs的开发者。为自由标准组织的创始者之一,也曾担任Linux基金会技术长)。这场辩论影响了Linux核心的设计走向。这场辩论有时也被视为一场口水战。

这个话题在 2006 年塔能鲍姆在 《Computer》杂志发表题为《我们能让操作系统可靠和安全吗?》的文章后被再次提起。尽管塔能鲍姆本人提到,他并不是想借这篇文章重启内核设计的论战,但是这篇文章本身和 Slashdot 技术网站上附加的 1992 年论战的归档共同使战火重燃。

Linux过时了- 塔能鲍姆-托瓦兹辩论(Tanenbaum–Torvalds debate)

林纳斯·托瓦兹(Linus_Torvalds)

托瓦兹通过一个在线论坛反驳了塔能鲍姆的论点,几个技术新闻网站随即开始对其进行报道。这使 Jonathan Shapiro 回应称,大多数经过实际检验的安全可靠的计算机系统,都使用更近似于微内核的模式设计。

辩论过程

虽然初步的辩论显得相对温和,当事人双方仅仅平淡了讨论了有关内核设计的话题。但随着每一轮的发帖,辩论开始逐步变得详细和复杂,甚至跨足于内核设计之外的其它领域,如”微处理器架构将在未来战胜其它架构”,但其中也包括了一些人身攻击、意气之争的言词辩论。除了塔能鲍姆和托瓦兹,Linux开发社区中一些著名黑客也加入辩论,包括彼得·麦唐纳,早期的 Linux 内核开发者和第一个发行版 Softlanding Linux System 的创建者;大卫·米勒,Linux 内核的核心开发者之一;和曹子德,北美洲第一个 Linux 内核开发者。

Linux 是过时的

第一条有关这场辩论的记录,在1992年1月29日,塔能鲍姆在 comp.os.minux 上发表了他的批评。在题为《Linux 是过时的》(Linux is obsolete)的帖子中,塔能鲍姆指出宏内核在整体设计上是有害的。虽然他最初并没有加入高深的技术细节,来解释他认为微内核更好的原因,但他也表明,这关乎可移植性,Linux内核对Intel 80386架构的耦合度太高,但处理器架构的进化很快。不应该在某个特定架构上开发操作系统,所有的操作系统都应该具备可以被移植到其他处理器平台的能力。他提到,在1991年仍然以宏内核来设计操作系统,是“回到1970年代的巨大退步“(a giant step back into the 1970s),现代的操作系统,应该像GNU Hurd一样采用微核心架构。

托瓦兹在一天之后反击,他首先攻击Minix在设计上有缺陷(缺少多线程是一个主要例子)。托瓦兹说,他用自己私人的时间来开发,完全没有获利,免费将代码贡献出去(当时塔能鲍姆的Minix源代码,仍然要购买才能取得),因此,对于Minix设计不良,塔能鲍姆不能用“这只是兴趣”来为来辩护。托瓦兹说,从哲学及美学的观点出发,微核心的确是一个比较好的架构,但是采用微核心架构的GNU Hurd根本没有如期被成功开发出来,所以他才要开发Linux。托瓦兹强调,操作系统核心主要的功能都倚靠硬件特性,所以内核本身不需要过度具备可移植性,让高级的软件应用程序接口具备可移植性才是更重要的。Linux内核采用集成式核心架构,是因为它能够简化核心设计,这是一个权衡下的结果(An acceptable trade-off)。以Linux来跟Minix比较,移植程序到Linux上是更容易的。托瓦兹进一步说,可移植性是那些写不出新程序的人才需要的(Portability is for people who cannot write new programs)。Linux一开始针对Intel 80386架构来开发,一部份的理由是为了托瓦兹自己买的电脑就是80386,这正好可以让他对80386架构了解更多。Linux一开始就是准备自己使用的,如果想要移植到别的平台,代码都是开放的,想要的人可以自己做。

收起全文
更多热门小站