汗青-home

*（come from：http://simple-is-better.com/news/729#dig） <有学习价值> 尝试了一下用Python实现的K-Means Clustering算法，抽样了10000篇百科词条，分为1000个类，分词后词语总数为130000左右。如果把1000个类定义为1000个向量，每个向量的元素个数为130000，K-Means Clustering算法的第一步是初始化这1000个向量的值，如果每个向量元素的值用float型存储，则需要的内存为： 1000 * 130000 * sizeof(float) 约 520M 左右。 最初用Python的list存储，动态扩展列表大小，结果内存用到近3G还没初始化完成，只好赶紧kill掉了。 改用 NumPy 存成固定数组的类别，发现内存使用量和计算结果基本一致，而且NumPy支持数组的数学计算，确实方便了不少，但即便如此，性能仍不够理想，K-Means算法第一次迭代花了一个小时还没完成。 怀疑K-Means算法的pearson距离计算时间较长（没有用profile工具论证过），用 Cython 重新改写了该算法，并尽可能缓存计算中间结果。第一轮迭代耗时1个多小时，算是有了进步。 由于K-Means算法费CPU较多，改写了计算逻辑，用multiprocessing模块并行计算，在4核的CPU上速度提升了4倍，第一轮迭代花了约30分钟。但multiprocessing需要fork多个进程，每个进程的内存使用量均在600M上下想，4个进程占用了2.4G内存，代价有些大。而且计算结果在不同的进程间传递，性能开销也是存在的。 multiprocessing + 共享内存可以解决这个问题，但Python的数据结构不好表示。 继而想到写C的动态链接库，用Python的ctypes模块调用该动态链接库完成计算过程，C的动态链接库则创建系统线程，这样能有效躲过Python的GIL。问题是C代码有时候确实需要访问Python的数据对象，这只能通过Python的C扩展模块实现了，但C的扩展模块能访问ctypes的原始C指针吗？如果只能通过Python的C API访问，则GIL是绕不开的，我们的目标是尽可能少地锁住Python虚拟机。 解决办法是修改Python的ctypes源码，让它导出函数 addressof 的C API，这样在其他的C扩展模块里就能拿到ctypes的原始数据块指针。addressof的返回结果是一个long的PyObject包装对象，通过 PyLong_AsVoidPtr调用即可获取其值。 因此最后的解决办法是下载Python的源码，修改模块_ctypes的源码，通过Capsule导出C API。继而编写Python的C扩展模块，创建线程池，直接操作ctypes定义的数据内存。由于Python数据结构是非线程安全的，访问它们仍需获得GIL，但用到的可能性很小。程序的主体逻辑仍由Python代码构造，包括必要的ctypes数据结构。 代码改写后一次K-Means迭代不到一分钟就完成了，4颗CPU全跑满，内存仅占用600M左右，跟预期完全一致。 总结 Python大多数时间能如我们预期那样工作 涉及到数值计算和海量循环，Python表现极其糟糕 Cython + NumPy 可解决部分计算问题和内存问题，但GIL无法避免 multiprocessing能解决SMP/GIL问题，但内存问题解决不了，也许共享内存+ctypes是个办法，没尝试过 ctypes + C的动态链接库创建系统线程能解决GIL和内存共享问题，但无法在C中操作Python对象 ctypes + Python C扩展意义不大，因为C扩展无法直接操作ctypes的数据指针 [...]

                              hanqing *School of Software Engineering, South China University of Technology, Guangzhou, China Abstract. Nowadays, pattern recognition is a research focus meanwhile it has produced lots applications in our society. Classification is a pivotal and important method to achieve the recognition. In this paper, we introduce and summarize a classification [...]

1.数据分类和聚类有什么区别（*reference1） 简单地说，分类(Categorization or Classification)就是按照某种标准给对象贴标签(label)，再根据标签来区分归类。 简单地说，聚类是指事先没有“标签”而通过某种成团分析找出事物之间存在聚集性原因的过程。   区别是，分类是事先定义好类别 ，类别数不变 。分类器需要由人工标注的分类训练语料训练得到，属于有指导学习范畴。聚类则没有事先预定的类别，类别数不确定。 聚类不需要人工标注和预先训练分类器，类别在聚类过程中自动生成 。分类适合类别或分类体系已经确定的场合，比如按照国图分类法分类图书；聚类则适合不存在分类体系、类别数不确定的场合，一般作为某些应用的前端，比如多文档文摘、搜索引擎结果后聚类(元搜索)等。       分类的目的是学会一个分类函数或分类模型(也常常称作分类器 ),该模型能把数据库中的数据项映射到给定类别中的某一个类中。 要构造分类器，需要有一个训练样本数据集作为输入。训练集由一组数据库记录或元组构成，每个元组是一个由有关字段(又称属性或特征)值组成的特征向量，此外，训练样本还有一个类别标记。一个具体样本的形式可表示为：(v1,v2,…,vn; c)；其中vi表示字段值，c表示类别。分类器的构造方法有统计方法、机器学习方法、神经网络方法等等。       聚类(clustering)是指根据“物以类聚”原理，将本身没有类别的样本聚集成不同的组，这样的一组数据对象的集合叫做簇，并且对每一个这样的簇进行描述的过程。它的目的是使得属于同一个簇的样本之间应该彼此相似，而不同簇的样本应该足够不相似。与分类规则不同，进行聚类前并不知道将要划分成几个组和什么样的组，也不知道根据哪些空间区分规则来定义组。其目的旨在发现空间实体的属性间的函数关系，挖掘的知识用以属性名为变量的数学方程来表示。聚类技术正在蓬勃发展，涉及范围包括数据挖掘、统计学、机器学习、空间数据库技术、生物学以及市场营销等领域，聚类分析已经成为数据挖掘研究领域中一个非常活跃的研究课题。常见的聚类算法包括：K-均值聚类算法、K-中心点聚类算法、CLARANS、 BIRCH、CLIQUE、DBSCAN等。 2.           reference： 1.http://zhidao.baidu.com/question/344172205.html

    “始终坚信真理来源于自然与社会生活” ——题记     生物是神奇的，人是高智慧的生物，而人类生活的社会是最复杂但同时又是最合理的数据结构。     同其他学科一样，信息技术也从人类社会和自然界中得到巨大的启发。其中为人们所熟知的面向对象程序设计思想等等。自然就是如此奇妙：人们绞尽脑汁地追求真理，而其实自己本身就是真理的载体或者自己就生活在真理之中。仿生学的巨大成就无时无刻不在向我们展示上述论述的证明过程。可悲的人啊，不要再觉得自己生活在谎言与欺骗之中，其实你生活的是真理的世界。     本文我们聊一聊语义网和本体论的某些初步见解，其中你也许会发现语义网其实是现实社会结构的网络表现。想到这觉得人们利用计算机虚拟现实越发有趣，会不会计算机本身就是现实社会的另一个维度？     语义网（semantic web）是对未来网络的一个设想，在这样的网络中，信息都被赋予了明确的含义，计算机能够自动地处理和集成网上可用的信息。它的核心是：通过给万维网上的文档(如:HTML)添加能够被计算机所理解的语义(Meta data)，从而使整个互联网成为一个通用的信息交换媒介。从语义网的设想不难看出要实现语义网首先必须对网络的信息进行标记和识别，而且必须能够被计算机所理解。而本体论（ontology，本身是一个哲学概念）似乎可以完成上述任务。                                                                                                     【图1】      似乎跟哲学扯上关系的所有东西都有点令人费解。某些哲学文献给出的定义是：指一切实在的最终本性，这种本性需要通过认识论而得到认识，因而研究一切实在最终本性的为本体论，研究如何认识则为认识论，这是以本体论与认识论相对称。简言之，本体论就是对象的本原。但人类思维取决于知识，知识是通过认识完成的。这样说来，本体论似乎永远不可达；因为我们可达的只是认识论而已。如【图1】，左侧的“石头”是本体，而右侧小孩脑海中的的只是认识的“石头”。这不就是老子说过的“道可道，非常道”。看来几千年前老子就明白了这个道理，算了我们还是不要再扯淡了，免得跑偏了主题。      通常意义上讲，本体论研究的就是在某些领域内的概念、对象、属性以及它们之间的关系。 O = <C,O,P,R> 可以理解为本体论（O）是一个三元组（至少），包括概念（C）、对象（O）、属性（P）以及他们之间的关系（R）。     容易理解，要实现语义网的设想只要能够在网络上组织起对应的计算机可以认识的本体就可以了。如果将【图1】中的人换成计算机，而左侧的石头换成网络的资源；而仍然可以在计算机搜索到左侧石头时，可以在数据库中映射出“石头”的概念，那么语义网就实现了。当然，这只是个例子。事实上远没有这么简单。     人可以认出左侧的对象是一个“石头”，并且人同样会认出另外的石头；虽然他们都对应同样的概念-“石头”，但是确实不同的实体。人可以区分，这是因为不同的石头（对象）的属性不同。颜色、质地、纹理、尺寸、形状等这些都是对象石头的属性。同样，语义网中的资源（对象）必须有属性的描述。现在，不同特点的网络有不同的类型的资源和属性描述。例如，有的网页本事就是对象，而它的属性描述可能是文本或者html；而有的协同标签系统中，tag作为属性。     概念（concept）是本体论中另一个重要的术语。在【图1】中，左侧的石头对应概念“石头”，同时它也可能对应概念“矿产”、或者“观赏石头”等等。我们有理由相信，右侧的人在第一时间将它映射为概念“石头”是受到他的知识（认知心理）的影响。而知识来源于对本体的认知，不同的环境下本体不同；因而不同的人会有不同的认知。所以在语义网中，面对不同的数据，即使是相同的本体计算机会有不同的理解。     【图2】     另一方面，概念是有层次（level）的。概念有子概念、父概念的结构关系。一般说来一个对象拥有的属性越多，他的概念层次越高。例如【图2】所示，概念“动物”一定既包含“鸟”概念的属性，又包含“哺乳动物”概念的属性。虽然对象都是在树的叶子层，但在被赋予认知的概念时是有层次的。     社会亦然：即使是在人无高低贵贱之分的号子下，身份（职位）还是层次明显；而身份不就是你一个人在社会这个本体论中的概念吗？而社会中处于高层的人一般都有更多的技术和各方面的能力，设想：一个在某方面不如他的下属的管理者很难在工作中驾驭他的属下。例如，在软件开发中管理者一般是拥有技术和能力而又有丰富经验的人。所以说，多掌握几方面的知识还是不错的，可以帮助你在社会的本体论中映射出高层次的概念呦！   待续…

  聚类算法是数据处理的重要手段，是将数据对象分成类或者簇的过程，使同一个簇里的对象具有高的相似性，而不同簇中的对象高度相异。如图【1】将所有的对象划分成三个簇以及探查出一个噪声对象（point b）的结果是非常令人满意的。 【图1】 归纳化的假设： 1.如果知道聚类后的几个簇的中心（或者是重心等其他的几何以及其他度量的位置），那么一次遍历便可以完成聚类过程； 2.如果知道每个对象的所属类，那么类/簇的中心也很容易确定。 其实，聚类分析的一个目标就是要完成对象所属的确定以及类的中心。从上面的假设可以看出这两个目标互为因果，要解决这个问题就要打破其中的某个环节。 （一）、K-means K-means 首先假设随机标记的几个点作为中心，完成一次聚类；然后重新评估中心，不断迭代直至中心不再变化。 从上述描述不难看出k-means 方法的问题所在： 随机选取“几个”，即“K值”必须事先给出。 对于K值的确定，目前还没有智能化的公认的方法；在实际中如果要应用k-means常常要人为设定。 随机选取的对象作为初始化的各个类的中心，往往会对最终的结果产生很大的影响。 这个弱点导致k-means方法对outline是敏感的。特别的当随机选取的初始化中心本身距离很近时效果会变的非常差劲。 【图2】   【图3】     例如如果初始化选在了point a,b,c， 那么经过数次的迭代之后效果是十分理想的；但如果选在了point a，d,e; 那么 最后的结果可能是如图【3】一般；左侧的类即使经过多次迭代让然会被划分到一个类里，效果是十分差劲的。 另一方面，对含有大量噪声对象的数据集，k-means方法不能将噪声识别。事实上，当初始化的中心距离很近而且与它划分到同一类的对象都是类噪声的对象（不足以较大幅度影响类中心的评估）时，就会产生上述差的效果。 非正式的优化办法 根据上述的分析在初始化中心时，初始化选取的对象最好是恰好对应于最终的几个类里的成员对象；那效果无疑是最好的。现实中最好的效果往往只是我们的想象而已。 现实中我们只能是我们的做法尽量接近于上述情况。例如在初始化前首先将全部对象遍历一遍，而选取所有对象中的差异化最大的对象作为初始化的中心（我们有理由相信差异化尺度大的对象应该不属于好的聚类结果里的同一类）。 （二）、层次聚类以及评估办法    

         数学一向被认为是严谨、规范的学科，但在数学中也有一些并没有明确或者统一的形式化定义的概念。本文介绍几个在日常中常常提及以及在其他学科有所应用的相关概念。 （一）、“平凡”与“非平凡” 数学中，术语“平凡”（“平凡的”）经常用于结构非常简单的对象。有时亦会用明显或乏趣这两个词代替。对非数学工作者来说，它们有时可能比其他更复杂的对象更难想象或理解。 例如： 明显因子：对于每个正整数 n 来说，1、-1、n 和 -n 都是它的明显因子。 空集：不包含任何元素的集合； 平凡群：只含单位元的群； 平凡环：定义于单元素集合的环。 “平凡” 也用于一个方程具有非常简单的结构的解，但是为了完整性不能省略。这种解称为平凡解。例如，考虑微分方程  y’ = y 这里 y = f(x) 为函数，其导数为 y′。 y = 0，0 函数是平凡解； y (x) = ex，指数函数是一个非平凡解。 平凡也经常指证明中容易的情形，为了完整性而不能省略。比如，数学归纳法证明分为两部分：“奠基情形”是对一个特殊起始值比如 n = 0 或 n= 1 证明定理；然后归纳步骤证明如果定理对特定值 n 成立，那么对 n+1 也成立。奠基情形经常是显然的而确认为平凡。（但是，也有归纳步骤是平凡的而奠基情形却困难的例子。关于多项式的定理经常是这种类型，证明对变元的个数用归纳法。证明如果系数环 A 是唯一分解整环那么A[X1,...,Xn] 是唯一分解整环，归纳步骤只要简单的写成 A[X1,...,Xn] = A[X1,...,Xn-1][Xn]，而一个变元的奠基情形是困难的。）类似地，我们可能想证明某种性质对一个集合中所有元素都成立。证明的主要部分将考虑非空集合，详细检验其元素；如果集合是空集，性质对其所有元素都成立，因为没有一个元素。（参见en:Vacuous truth） 数学界一个常见的笑话是说“平凡”和“被证明的”是同义词——这就是说，任何定理如果已经知道成立就可以认为是“平凡”的。另一个笑话是关于两个数学家讨论一个定理。第一个数学家说某个定理是“平凡的”。另一个要求一个解释，然后他进行了 20 分钟的解说。解说完了之后，第二个数学家同意这个定理是平凡的。这个笑话指出对平凡性判断的主观性。举个例子，对微积分很熟练的人，会认为这个定理 是平凡的。但对一个初学者来说，可能一点也不显然。 注意到平凡性也取决于语境。泛函分析中的证明可能会给出一个数，平凡地假设存在这样的大数。在初等数论中证明自然数的基本结论时，证明也许和自然数有一个后继（也是自然数成立，或者将其作为一个公理）非常相关。 其实可以注意到在一定的情景和应用下将“平凡”与“非平凡”狭隘的理解为“简单”和“复杂”是无可厚非的。比如数据挖掘领域的“非平凡”可以理解为： 平凡的东西是很容易得到的,也比较浅显,或者说是可以比较准确的预测的。 获得此类的知识不需要太多的技巧和应用专门的工具，只要对于此领域比较熟悉，能够熟练的预测事物的发展趋势。而数据挖掘有时候强调的是，所挖掘的知识往往不易通过简单的分析就能够得到，这些知识可能隐含在表面现象的内里， 需要经常大量数据的比较分析，应用一些专门对付大数据量的工具，才有可能得到。 reference：维基（http://zh.wikipedia.org/wiki/%E7%8E%AF）

“数据挖掘”和“知识发现”通常被相提并论，并在许多场合被认为是可以相互替代的术语。对数据挖掘有多种定义，例如“识别出巨量数据中有效的、新颖的、潜在有用的、最终可理解的模式的非平凡过程”（有关“平凡”与“非平凡”的问题参见本人博客的“几个模糊数学概念的理解”一文）。其实顾名思义，数据挖掘就是试图从海量数据中找出有用的知识。大体上看，数据挖掘可以视为机器学习和数据库的交叉，它主要利用机器学习界提供的技术来分析海量数据，利用数据库界提供的技术来管理海量数据。       机器学习和数据挖掘技术已经开始在多媒体、计算机图形学、计算机网络乃至操作系统、软件工程等计算机科学的众多领域中发挥作用，特别是在计算机视觉和自然语言处理领域，机器学习和数据挖掘已经成为最流行、最热门的技术，以至于在这些领域的顶级会议上相当多的论文都与机器学习和数据挖掘技术有关。总的来看，引入机器学习和数据挖掘技术在计算机科学的众多分支领域中都是一个重要趋势。      现在很少有人不知道互联网搜索引擎的用处，但可能很多人并不了解，机器学习和数据挖掘技术正在支撑着这些搜索引擎。其实，互联网搜索引擎是通过分析互联网上的数据来找到用户所需要的信息，而这正是一个机器学习和数据挖掘任务。      事实上，机器学习和数据挖掘都是人工智能发展带来的技术。在人工智能发展的历史上出现过很多极具影响的技术和算法，比如BP学习算法（连接主义学习）就是最成功的神经网络学习算法之一，在当时迅速成为最流行的算法，并在很多应用中都取得了极大的成功。然而，连接主义学习技术也有其局限，一个常被人诟病的问题是其“试错性”。简单地说，在此类技术中有大量的经验参数需要设置，例如神经网络的隐层结点数、学习率等，夸张一点说，参数设置上差之毫厘，学习结果可能谬以千里。在实际工程应用中，人们可以通过调试来确定较好的参数设置，但对机器学习研究者来说，对此显然是难以满意的。       世纪 90 年代中期，统计学习粉墨登场并迅速独占鳌头。正是在连接主义学习技术的局限性凸显出来之后，人们才把目光转向了统计学习。      学习不仅在信息科学中占有重要地位，还有一定的自然科学色彩。与此不同，数据挖掘则是一个直接为实际应用而生的学科领域。20 世纪 60 年代，早期的数据库问世，人们开始利用计算机对数据进行管理；到了 70 年代之后，随着关系数据库的出现和发展，人们管理数据的能力越来越强，收集存储的数据也越来越多。如果只利用数据库进行一些简单的事务处理，显然没有对数据进行充分的利用，从数据中挖掘出有用的知识，才可以更好地实现数据的价值。      89年 8 月，第 11 届国际人工智能联合会议（IJCAI’89）在美国底特律举行，GTE实验室的G. iatetsky-Shapiro在J.G. Carbonell、W. Frawley、K. Parsaye、J.R. Quinlan、M. Siegel、 R. Uthurusamy等人的支持下，组织了一个名为“在数据库中发现知识”的研讨会，这个研讨会后来被认为是数据挖掘成为一个领域的标志。早期人们一直称其为“数据挖掘与知识发现”，但随着该领域的发展壮大，越来越多的人直接称其为数据挖掘。值得注意的是，数据挖掘的对象早就不限于数据库，而可以是存放在任何地方的数据，甚至包括Internet上的数据。      数据挖掘受到了很多学科领域的影响，其中数据库、机器学习、统计学无疑影响最大。数据库提供数据管理技术，机器学习和统计学提供数据分析技术。统计学主要是通过机器学习来对数据挖掘发挥影响，而机器学习和数据库则是数据挖掘的两大支撑技术。      挖掘作为一个独立的学科领域，必然会有一些相对“独特”的东西。对数据挖掘来说，除了处理海量数据的能力外还有很独特一个能力，这就是关联分析。通过数据的分析往往会发现一些表面上无法发现的匪夷所思的因果关系，这也是数据挖掘目前很重要的一方面的价值

半夜三更一个牛人给做了个网站