数据处理 订阅
数据(Data)是对事实、概念或指令的一种表达形式,可由人工或自动化装置进行处理。数据经过解释并赋予一定的意义之后,便成为信息。数据处理(data processing)是对数据的采集、存储、检索、加工、变换和传输。数据处理的基本目的是从大量的、可能是杂乱无章的、难以理解的数据中抽取并推导出对于某些特定的人们来说是有价值、有意义的数据。数据处理是系统工程和自动控制的基本环节。数据处理贯穿于社会生产和社会生活的各个领域。数据处理技术的发展及其应用的广度和深度,极大地影响了人类社会发展的进程。 展开全文
数据(Data)是对事实、概念或指令的一种表达形式,可由人工或自动化装置进行处理。数据经过解释并赋予一定的意义之后,便成为信息。数据处理(data processing)是对数据的采集、存储、检索、加工、变换和传输。数据处理的基本目的是从大量的、可能是杂乱无章的、难以理解的数据中抽取并推导出对于某些特定的人们来说是有价值、有意义的数据。数据处理是系统工程和自动控制的基本环节。数据处理贯穿于社会生产和社会生活的各个领域。数据处理技术的发展及其应用的广度和深度,极大地影响了人类社会发展的进程。
信息
处理软件
管理数据的文件、数据库系统等
外文名
data processing
领    域
社会生产和社会生活
中文名
数据处理
步    骤
对数据的采集、存储、检索等
目    的
转化为有用信息
数据处理基本信息
处理软件数据处理离不开软件的支持,数据处理软件包括:用以书写处理程序的各种程序设计语言及其编译程序,管理数据的文件系统和数据库系统,以及各种数据处理方法的应用软件包。为了保证数据安全可靠,还有一整套数据安全保密的技术。方式根据处理设备的结构方式、工作方式,以及数据的时间空间分布方式的不同,数据处理有不同的方式。不同的处理方式要求不同的硬件和软件支持。每种处理方式都有自己的特点,应当根据应用问题的实际环境选择合适的处理方式。数据处理主要有四种分类方式①根据处理设备的结构方式区分,有联机处理方式和脱机处理方式。②根据数据处理时间的分配方式区分,有批处理方式、分时处理方式和实时处理方式。③根据数据处理空间的分布方式区分,有集中式处理方式和分布处理方式。④根据计算机中央处理器的工作方式区分,有单道作业处理方式、多道作业处理方式和交互式处理方式。数据处理对数据(包括数值的和非数值的)进行分析和加工的技术过程。包括对各种原始数据的分析、整理、计算、编辑等的加工和处理。比数据分析含义广。随着计算机的日益普及,在计算机应用领域中,数值计算所占比重很小,通过计算机数据处理进行信息管理已成为主要的应用。如测绘制图管理、仓库管理、财会管理、交通运输管理,技术情报管理、办公室自动化等。在地理数据方面既有大量自然环境数据(土地、水、气候、生物等各类资源数据),也有大量社会经济数据(人口、交通、工农业等),常要求进行综合性数据处理。故需建立地理数据库,系统地整理和存储地理数据减少冗余,发展数据处理软件,充分利用数据库技术进行数据管理和处理。
收起全文
精华内容
参与话题
问答
  • 教你如何迅速秒杀掉:99%的海量数据处理面试题

    万次阅读 多人点赞 2012-03-22 12:51:07
    教你如何迅速秒杀掉:99%的海量数据处理面试题作者:July出处:结构之法算法之道blog前言 一般而言,标题含有“秒杀”,“99%”,“史上最全/最强”等词汇的往往都脱不了哗众取宠之嫌,但进一步来讲,如果读者读罢...

          教你如何迅速秒杀掉:99%的海量数据处理面试题

    本文经过大量细致的优化后,收录于我的新书《编程之法:面试和算法心得》第六章中,新书目前已上架京东/当当


    作者:July
    出处:结构之法算法之道blog



    前言

       一般而言,标题含有“秒杀”,“99%”,“史上最全/最强”等词汇的往往都脱不了哗众取宠之嫌,但进一步来讲,如果读者读罢此文,却无任何收获,那么,我也甘愿背负这样的罪名 :-),同时,此文可以看做是对这篇文章:十道海量数据处理面试题与十个方法大总结的一般抽象性总结。

        毕竟受文章和理论之限,本文将摒弃绝大部分的细节,只谈方法/模式论,且注重用最通俗最直白的语言阐述相关问题。最后,有一点必须强调的是,全文行文是基于面试题的分析基础之上的,具体实践过程中,还是得具体情况具体分析,且各个场景下需要考虑的细节也远比本文所描述的任何一种解决方法复杂得多。

        OK,若有任何问题,欢迎随时不吝赐教。谢谢。



    何谓海量数据处理?

       所谓海量数据处理,无非就是基于海量数据上的存储、处理、操作。何谓海量,就是数据量太大,所以导致要么是无法在较短时间内迅速解决,要么是数据太大,导致无法一次性装入内存。

        那解决办法呢?针对时间,我们可以采用巧妙的算法搭配合适的数据结构,如Bloom filter/Hash/bit-map/堆/数据库或倒排索引/trie树,针对空间,无非就一个办法:大而化小,分而治之(hash映射),你不是说规模太大嘛,那简单啊,就把规模大化为规模小的,各个击破不就完了嘛。

        至于所谓的单机及集群问题,通俗点来讲,单机就是处理装载数据的机器有限(只要考虑cpu,内存,硬盘的数据交互),而集群,机器有多辆,适合分布式处理,并行计算(更多考虑节点和节点间的数据交互)。

        再者,通过本blog内的有关海量数据处理的文章:Big Data Processing,我们已经大致知道,处理海量数据问题,无非就是:

    1. 分而治之/hash映射 + hash统计 + 堆/快速/归并排序;
    2. 双层桶划分
    3. Bloom filter/Bitmap;
    4. Trie树/数据库/倒排索引;
    5. 外排序;
    6. 分布式处理之Hadoop/Mapreduce。

        下面,本文第一部分、从set/map谈到hashtable/hash_map/hash_set,简要介绍下set/map/multiset/multimap,及hash_set/hash_map/hash_multiset/hash_multimap之区别(万丈高楼平地起,基础最重要),而本文第二部分,则针对上述那6种方法模式结合对应的海量数据处理面试题分别具体阐述。


    第一部分、从set/map谈到hashtable/hash_map/hash_set

        稍后本文第二部分中将多次提到hash_map/hash_set,下面稍稍介绍下这些容器,以作为基础准备。一般来说,STL容器分两种,

    • 序列式容器(vector/list/deque/stack/queue/heap),
    • 关联式容器。关联式容器又分为set(集合)和map(映射表)两大类,以及这两大类的衍生体multiset(多键集合)和multimap(多键映射表),这些容器均以RB-tree完成。此外,还有第3类关联式容器,如hashtable(散列表),以及以hashtable为底层机制完成的hash_set(散列集合)/hash_map(散列映射表)/hash_multiset(散列多键集合)/hash_multimap(散列多键映射表)。也就是说,set/map/multiset/multimap都内含一个RB-tree,而hash_set/hash_map/hash_multiset/hash_multimap都内含一个hashtable

        所谓关联式容器,类似关联式数据库,每笔数据或每个元素都有一个键值(key)和一个实值(value),即所谓的Key-Value(键-值对)。当元素被插入到关联式容器中时,容器内部结构(RB-tree/hashtable)便依照其键值大小,以某种特定规则将这个元素放置于适当位置。

         包括在非关联式数据库中,比如,在MongoDB内,文档(document)是最基本的数据组织形式,每个文档也是以Key-Value(键-值对)的方式组织起来。一个文档可以有多个Key-Value组合,每个Value可以是不同的类型,比如String、Integer、List等等。 
    { "name" : "July",  
      "sex" : "male",  
        "age" : 23 }  

    set/map/multiset/multimap

        set,同map一样,所有元素都会根据元素的键值自动被排序,因为set/map两者的所有各种操作,都只是转而调用RB-tree的操作行为,不过,值得注意的是,两者都不允许两个元素有相同的键值。
        不同的是:set的元素不像map那样可以同时拥有实值(value)和键值(key),set元素的键值就是实值,实值就是键值,而map的所有元素都是pair,同时拥有实值(value)和键值(key),pair的第一个元素被视为键值,第二个元素被视为实值。
        至于multiset/multimap,他们的特性及用法和set/map完全相同,唯一的差别就在于它们允许键值重复,即所有的插入操作基于RB-tree的insert_equal()而非insert_unique()。

    hash_set/hash_map/hash_multiset/hash_multimap

        hash_set/hash_map,两者的一切操作都是基于hashtable之上。不同的是,hash_set同set一样,同时拥有实值和键值,且实质就是键值,键值就是实值,而hash_map同map一样,每一个元素同时拥有一个实值(value)和一个键值(key),所以其使用方式,和上面的map基本相同。但由于hash_set/hash_map都是基于hashtable之上,所以不具备自动排序功能。为什么?因为hashtable没有自动排序功能。
        至于hash_multiset/hash_multimap的特性与上面的multiset/multimap完全相同,唯一的差别就是它们hash_multiset/hash_multimap的底层实现机制是hashtable(而multiset/multimap,上面说了,底层实现机制是RB-tree),所以它们的元素都不会被自动排序,不过也都允许键值重复。

        所以,综上,说白了,什么样的结构决定其什么样的性质,因为set/map/multiset/multimap都是基于RB-tree之上,所以有自动排序功能,而hash_set/hash_map/hash_multiset/hash_multimap都是基于hashtable之上,所以不含有自动排序功能,至于加个前缀multi_无非就是允许键值重复而已。如下图所示:

        此外,

    • 关于什么hash,请看blog内此篇文章
    • 关于红黑树,请参看blog内系列文章
    • 关于hash_map的具体应用:请看这里,关于hash_set:请看此文

        OK,接下来,请看本文第二部分、处理海量数据问题之六把密匙。



    第二部分、处理海量数据问题之六把密匙

    密匙一、分而治之/Hash映射 + Hash_map统计 + 堆/快速/归并排序

    1、海量日志数据,提取出某日访问百度次数最多的那个IP。
        既然是海量数据处理,那么可想而知,给我们的数据那就一定是海量的。针对这个数据的海量,我们如何着手呢?对的,无非就是分而治之/hash映射 + hash统计 + 堆/快速/归并排序,说白了,就是先映射,而后统计,最后排序:
    1. 分而治之/hash映射:针对数据太大,内存受限,只能是:把大文件化成(取模映射)小文件,即16字方针:大而化小,各个击破,缩小规模,逐个解决
    2. hash_map统计:当大文件转化了小文件,那么我们便可以采用常规的hash_map(ip,value)来进行频率统计。
    3. 堆/快速排序:统计完了之后,便进行排序(可采取堆排序),得到次数最多的IP。

       具体而论,则是: “首先是这一天,并且是访问百度的日志中的IP取出来,逐个写入到一个大文件中。注意到IP是32位的,最多有个2^32个IP。同样可以采用映射的方法,比如%1000,把整个大文件映射为1000个小文件,再找出每个小文中出现频率最大的IP(可以采用hash_map对那1000个文件中的所有IP进行频率统计,然后依次找出各个文件中频率最大的那个IP)及相应的频率。然后再在这1000个最大的IP中,找出那个频率最大的IP,即为所求。”--十道海量数据处理面试题与十个方法大总结

        关于本题,还有几个问题,如下:

          1、Hash取模是一种等价映射,不会存在同一个元素分散到不同小文件中的情况,即这里采用的是mod1000算法,那么相同的IP在hash取模后,只可能落在同一个文件中,不可能被分散的。因为如果两个IP相等,那么经过Hash(IP)之后的哈希值是相同的,将此哈希值取模(如模1000),必定仍然相等。
          2、那到底什么是hash映射呢?简单来说,就是为了便于计算机在有限的内存中处理big数据,从而通过一种映射散列的方式让数据均匀分布在对应的内存位置(如大数据通过取余的方式映射成小树存放在内存中,或大文件映射成多个小文件),而这个映射散列方式便是我们通常所说的hash函数,设计的好的hash函数能让数据均匀分布而减少冲突。尽管数据映射到了另外一些不同的位置,但数据还是原来的数据,只是代替和表示这些原始数据的形式发生了变化而已。

        OK,有兴趣的,还可以再了解下一致性hash算法,见blog内此文第五部分:http://blog.csdn.net/v_july_v/article/details/6879101

    2、寻找热门查询,300万个查询字符串中统计最热门的10个查询

        原题:搜索引擎会通过日志文件把用户每次检索使用的所有检索串都记录下来,每个查询串的长度为1-255字节。假设目前有一千万个记录(这些查询串的重复度比较高,虽然总数是1千万,但如果除去重复后,不超过3百万个。一个查询串的重复度越高,说明查询它的用户越多,也就是越热门),请你统计最热门的10个查询串,要求使用的内存不能超过1G。

        解答:由上面第1题,我们知道,数据大则划为小的,如如一亿个Ip求Top 10,可先%1000将ip分到1000个小文件中去,并保证一种ip只出现在一个文件中,再对每个小文件中的ip进行hashmap计数统计并按数量排序,最后归并或者最小堆依次处理每个小文件的top10以得到最后的结。

        但如果数据规模比较小,能一次性装入内存呢?比如这第2题,虽然有一千万个Query,但是由于重复度比较高,因此事实上只有300万的Query,每个Query255Byte,因此我们可以考虑把他们都放进内存中去(300万个字符串假设没有重复,都是最大长度,那么最多占用内存3M*1K/4=0.75G。所以可以将所有字符串都存放在内存中进行处理),而现在只是需要一个合适的数据结构,在这里,HashTable绝对是我们优先的选择。

        所以我们放弃分而治之/hash映射的步骤,直接上hash统计,然后排序。So,针对此类典型的TOP K问题,采取的对策往往是:hashmap + 堆。如下所示:

    1. hash_map统计:先对这批海量数据预处理。具体方法是:维护一个Key为Query字串,Value为该Query出现次数的HashTable,即hash_map(Query,Value),每次读取一个Query,如果该字串不在Table中,那么加入该字串,并且将Value值设为1;如果该字串在Table中,那么将该字串的计数加一即可。最终我们在O(N)的时间复杂度内用Hash表完成了统计;
    2. 堆排序:第二步、借助堆这个数据结构,找出Top K,时间复杂度为N‘logK。即借助堆结构,我们可以在log量级的时间内查找和调整/移动。因此,维护一个K(该题目中是10)大小的小根堆,然后遍历300万的Query,分别和根元素进行对比。所以,我们最终的时间复杂度是:O(N) + N' * O(logK),(N为1000万,N’为300万)。

        别忘了这篇文章中所述的堆排序思路:“维护k个元素的最小堆,即用容量为k的最小堆存储最先遍历到的k个数,并假设它们即是最大的k个数,建堆费时O(k),并调整堆(费时O(logk))后,有k1>k2>...kmin(kmin设为小顶堆中最小元素)。继续遍历数列,每次遍历一个元素x,与堆顶元素比较,若x>kmin,则更新堆(x入堆,用时logk),否则不更新堆。这样下来,总费时O(k*logk+(n-k)*logk)=O(n*logk)。此方法得益于在堆中,查找等各项操作时间复杂度均为logk。”--第三章续、Top K算法问题的实现
        当然,你也可以采用trie树,关键字域存该查询串出现的次数,没有出现为0。最后用10个元素的最小推来对出现频率进行排序。

    3、有一个1G大小的一个文件,里面每一行是一个词,词的大小不超过16字节,内存限制大小是1M。返回频数最高的100个词。
           由上面那两个例题,分而治之 + hash统计 + 堆/快速排序这个套路,我们已经开始有了屡试不爽的感觉。下面,再拿几道再多多验证下。请看此第3题:又是文件很大,又是内存受限,咋办?还能怎么办呢?无非还是:

    1. 分而治之/hash映射:顺序读文件中,对于每个词x,取hash(x)%5000,然后按照该值存到5000个小文件(记为x0,x1,...x4999)中。这样每个文件大概是200k左右。如果其中的有的文件超过了1M大小,还可以按照类似的方法继续往下分,直到分解得到的小文件的大小都不超过1M。
    2. hash_map统计:对每个小文件,采用trie树/hash_map等统计每个文件中出现的词以及相应的频率。
    3. 堆/归并排序:取出出现频率最大的100个词(可以用含100个结点的最小堆)后,再把100个词及相应的频率存入文件,这样又得到了5000个文件。最后就是把这5000个文件进行归并(类似于归并排序)的过程了。
    4、海量数据分布在100台电脑中,想个办法高效统计出这批数据的TOP10。
        如果每个数据元素只出现一次,而且只出现在某一台机器中,那么可以采取以下步骤统计出现次数TOP10的数据元素:
    1. 堆排序:在每台电脑上求出TOP10,可以采用包含10个元素的堆完成(TOP10小,用最大堆,TOP10大,用最小堆,比如求TOP10大,我们首先取前10个元素调整成最小堆,如果发现,然后扫描后面的数据,并与堆顶元素比较,如果比堆顶元素大,那么用该元素替换堆顶,然后再调整为最小堆。最后堆中的元素就是TOP10大)。
    2. 求出每台电脑上的TOP10后,然后把这100台电脑上的TOP10组合起来,共1000个数据,再利用上面类似的方法求出TOP10就可以了。
        但如果同一个元素重复出现在不同的电脑中呢,如下例子所述:


        这个时候,你可以有两种方法:
    • 遍历一遍所有数据,重新hash取摸,如此使得同一个元素只出现在单独的一台电脑中,然后采用上面所说的方法,统计每台电脑中各个元素的出现次数找出TOP10,继而组合100台电脑上的TOP10,找出最终的TOP10。
    • 或者,暴力求解:直接统计统计每台电脑中各个元素的出现次数,然后把同一个元素在不同机器中的出现次数相加,最终从所有数据中找出TOP10。
    5、有10个文件,每个文件1G,每个文件的每一行存放的都是用户的query,每个文件的query都可能重复。要求你按照query的频度排序。

       方案1:直接上:

    1. hash映射:顺序读取10个文件,按照hash(query)%10的结果将query写入到另外10个文件(记为a0,a1,..a9)中。这样新生成的文件每个的大小大约也1G(假设hash函数是随机的)。
    2. hash_map统计:找一台内存在2G左右的机器,依次对用hash_map(query, query_count)来统计每个query出现的次数。注:hash_map(query,query_count)是用来统计每个query的出现次数,不是存储他们的值,出现一次,则count+1。
    3. 堆/快速/归并排序:利用快速/堆/归并排序按照出现次数进行排序,将排序好的query和对应的query_cout输出到文件中,这样得到了10个排好序的文件(记为)。最后,对这10个文件进行归并排序(内排序与外排序相结合)。根据此方案1,这里有一份实现:https://github.com/ooooola/sortquery/blob/master/querysort.py
         除此之外,此题还有以下两个方法:
        方案2:一般query的总量是有限的,只是重复的次数比较多而已,可能对于所有的query,一次性就可以加入到内存了。这样,我们就可以采用trie树/hash_map等直接来统计每个query出现的次数,然后按出现次数做快速/堆/归并排序就可以了。

        方案3:与方案1类似,但在做完hash,分成多个文件后,可以交给多个文件来处理,采用分布式的架构来处理(比如MapReduce),最后再进行合并。

    6、 给定a、b两个文件,各存放50亿个url,每个url各占64字节,内存限制是4G,让你找出a、b文件共同的url?

        可以估计每个文件安的大小为5G×64=320G,远远大于内存限制的4G。所以不可能将其完全加载到内存中处理。考虑采取分而治之的方法。

    1. 分而治之/hash映射遍历文件a,对每个url求取,然后根据所取得的值将url分别存储到1000个小文件(记为这里漏写个了a1)中。这样每个小文件的大约为300M遍历文件b,采取和a相同的方式将url分别存储到1000小文件中(记为)。这样处理后,所有可能相同的url都在对应的小文件()中,不对应的小文件不可能有相同的url。然后我们只要求出1000对小文件中相同的url即可
    2. hash_set统计:求每对小文件中相同的url时,可以把其中一个小文件的url存储到hash_set中。然后遍历另一个小文件的每个url,看其是否在刚才构建的hash_set中,如果是,那么就是共同的url,存到文件里面就可以了。

        OK,此第一种方法:分而治之/hash映射 + hash统计 + 堆/快速/归并排序,再看最后4道题,如下:

    7、怎么在海量数据中找出重复次数最多的一个?

        方案:先做hash,然后求模映射为小文件,求出每个小文件中重复次数最多的一个,并记录重复次数。然后找出上一步求出的数据中重复次数最多的一个就是所求(具体参考前面的题)。

    8、上千万或上亿数据(有重复),统计其中出现次数最多的前N个数据。

        方案:上千万或上亿的数据,现在的机器的内存应该能存下。所以考虑采用hash_map/搜索二叉树/红黑树等来进行统计次数。然后利用堆取出前N个出现次数最多的数据。

    9、一个文本文件,大约有一万行,每行一个词,要求统计出其中最频繁出现的前10个词,请给出思想,给出时间复杂度分析。

        方案1:如果文件比较大,无法一次性读入内存,可以采用hash取模的方法,将大文件分解为多个小文件,对于单个小文件利用hash_map统计出每个小文件中10个最常出现的词,然后再进行归并处理,找出最终的10个最常出现的词。
        方案2:通过hash取模将大文件分解为多个小文件后,除了可以用hash_map统计出每个小文件中10个最常出现的词,也可以用trie树统计每个词出现的次数,时间复杂度是O(n*le)(le表示单词的平准长度),最终同样找出出现最频繁的前10个词(可用堆来实现),时间复杂度是O(n*lg10)。

    10. 1000万字符串,其中有些是重复的,需要把重复的全部去掉,保留没有重复的字符串。请怎么设计和实现?

    • 方案1:这题用trie树比较合适,hash_map也行。
    • 方案2:from xjbzju:,1000w的数据规模插入操作完全不现实,以前试过在stl下100w元素插入set中已经慢得不能忍受,觉得基于hash的实现不会比红黑树好太多,使用vector+sort+unique都要可行许多,建议还是先hash成小文件分开处理再综合。
        上述方案2中读者xbzju的方法让我想到了一些问题,即是set/map,与hash_set/hash_map的性能比较?共计3个问题,如下:
    • 1、hash_set在千万级数据下,insert操作优于set? 这位blog:http://t.cn/zOibP7t 给的实践数据可靠不? 
    • 2、那map和hash_map的性能比较呢? 谁做过相关实验?
    • 3、那查询操作呢,如下段文字所述?

        或者小数据量时用map,构造快,大数据量时用hash_map?

    rbtree PK hashtable

        据朋友№邦卡猫№的做的红黑树和hash table的性能测试中发现:当数据量基本上int型key时,hash table是rbtree的3-4倍,但hash table一般会浪费大概一半内存。

        因为hash table所做的运算就是个%,而rbtree要比较很多,比如rbtree要看value的数据 ,每个节点要多出3个指针(或者偏移量) 如果需要其他功能,比如,统计某个范围内的key的数量,就需要加一个计数成员。

        且1s rbtree能进行大概50w+次插入,hash table大概是差不多200w次。不过很多的时候,其速度可以忍了,例如倒排索引差不多也是这个速度,而且单线程,且倒排表的拉链长度不会太大。正因为基于树的实现其实不比hashtable慢到哪里去,所以数据库的索引一般都是用的B/B+树,而且B+树还对磁盘友好(B树能有效降低它的高度,所以减少磁盘交互次数)。比如现在非常流行的NoSQL数据库,像MongoDB也是采用的B树索引。关于B树系列,请参考本blog内此篇文章:从B树、B+树、B*树谈到R 树。更多请待后续实验论证。

    11. 一个文本文件,找出前10个经常出现的词,但这次文件比较长,说是上亿行或十亿行,总之无法一次读入内存,问最优解。
        方案1:首先根据用hash并求模,将文件分解为多个小文件,对于单个文件利用上题的方法求出每个文件件中10个最常出现的词。然后再进行归并处理,找出最终的10个最常出现的词。

    12. 100w个数中找出最大的100个数。
        方案1:采用局部淘汰法。选取前100个元素,并排序,记为序列L。然后一次扫描剩余的元素x,与排好序的100个元素中最小的元素比,如果比这个最小的要大,那么把这个最小的元素删除,并把x利用插入排序的思想,插入到序列L中。依次循环,知道扫描了所有的元素。复杂度为O(100w*100)。
        方案2:采用快速排序的思想,每次分割之后只考虑比轴大的一部分,知道比轴大的一部分在比100多的时候,采用传统排序算法排序,取前100个。复杂度为O(100w*100)。
        方案3:在前面的题中,我们已经提到了,用一个含100个元素的最小堆完成。复杂度为O(100w*lg100)。

        接下来,咱们来看第二种方法,双层捅划分。


    密匙二、多层划分

    多层划分----其实本质上还是分而治之的思想,重在“分”的技巧上!
      适用范围:第k大,中位数,不重复或重复的数字
      基本原理及要点:因为元素范围很大,不能利用直接寻址表,所以通过多次划分,逐步确定范围,然后最后在一个可以接受的范围内进行。

    问题实例:

    13、2.5亿个整数中找出不重复的整数的个数,内存空间不足以容纳这2.5亿个整数。
        有点像鸽巢原理,整数个数为2^32,也就是,我们可以将这2^32个数,划分为2^8个区域(比如用单个文件代表一个区域),然后将数据分离到不同的区域,然后不同的区域在利用bitmap就可以直接解决了。也就是说只要有足够的磁盘空间,就可以很方便的解决。

    14、5亿个int找它们的中位数。

    1. 思路一:这个例子比上面那个更明显。首先我们将int划分为2^16个区域,然后读取数据统计落到各个区域里的数的个数,之后我们根据统计结果就可以判断中位数落到那个区域,同时知道这个区域中的第几大数刚好是中位数。然后第二次扫描我们只统计落在这个区域中的那些数就可以了。
      实际上,如果不是int是int64,我们可以经过3次这样的划分即可降低到可以接受的程度。即可以先将int64分成2^24个区域,然后确定区域的第几大数,在将该区域分成2^20个子区域,然后确定是子区域的第几大数,然后子区域里的数的个数只有2^20,就可以直接利用direct addr table进行统计了。
    2.   思路二@绿色夹克衫:同样需要做两遍统计,如果数据存在硬盘上,就需要读取2次。
      方法同基数排序有些像,开一个大小为65536的Int数组,第一遍读取,统计Int32的高16位的情况,也就是0-65535,都算作0,65536 - 131071都算作1。就相当于用该数除以65536。Int32 除以 65536的结果不会超过65536种情况,因此开一个长度为65536的数组计数就可以。每读取一个数,数组中对应的计数+1,考虑有负数的情况,需要将结果加32768后,记录在相应的数组内。
      第一遍统计之后,遍历数组,逐个累加统计,看中位数处于哪个区间,比如处于区间k,那么0- k-1的区间里数字的数量sum应该<n/2(2.5亿)。而k+1 - 65535的计数和也<n/2,第二遍统计同上面的方法类似,但这次只统计处于区间k的情况,也就是说(x / 65536) + 32768 = k。统计只统计低16位的情况。并且利用刚才统计的sum,比如sum = 2.49亿,那么现在就是要在低16位里面找100万个数(2.5亿-2.49亿)。这次计数之后,再统计一下,看中位数所处的区间,最后将高位和低位组合一下就是结果了。

    密匙三:Bloom filter/Bitmap

    Bloom filter

    关于什么是Bloom filter,请参看blog内此文:

      适用范围:可以用来实现数据字典,进行数据的判重,或者集合求交集
      基本原理及要点:
      对于原理来说很简单,位数组+k个独立hash函数。将hash函数对应的值的位数组置1,查找时如果发现所有hash函数对应位都是1说明存在,很明显这个过程并不保证查找的结果是100%正确的。同时也不支持删除一个已经插入的关键字,因为该关键字对应的位会牵动到其他的关键字。所以一个简单的改进就是 counting Bloom filter,用一个counter数组代替位数组,就可以支持删除了。
      还有一个比较重要的问题,如何根据输入元素个数n,确定位数组m的大小及hash函数个数。当hash函数个数k=(ln2)*(m/n)时错误率最小。在错误率不大于E的情况下,m至少要等于n*lg(1/E)才能表示任意n个元素的集合。但m还应该更大些,因为还要保证bit数组里至少一半为0,则m应该>=nlg(1/E)*lge 大概就是nlg(1/E)1.44倍(lg表示以2为底的对数)。
      举个例子我们假设错误率为0.01,则此时m应大概是n的13倍。这样k大概是8个。
      注意这里m与n的单位不同,m是bit为单位,而n则是以元素个数为单位(准确的说是不同元素的个数)。通常单个元素的长度都是有很多bit的。所以使用bloom filter内存上通常都是节省的。

      扩展:

      Bloom filter将集合中的元素映射到位数组中,用k(k为哈希函数个数)个映射位是否全1表示元素在不在这个集合中。Counting bloom filter(CBF)将位数组中的每一位扩展为一个counter,从而支持了元素的删除操作。Spectral Bloom Filter(SBF)将其与集合元素的出现次数关联。SBF采用counter中的最小值来近似表示元素的出现频率。

       可以看下上文中的第6题:

    “6、给你A,B两个文件,各存放50亿条URL,每条URL占用64字节,内存限制是4G,让你找出A,B文件共同的URL。如果是三个乃至n个文件呢?

      根据这个问题我们来计算下内存的占用,4G=2^32大概是40亿*8大概是340亿,n=50亿,如果按出错率0.01算需要的大概是650亿个bit。现在可用的是340亿,相差并不多,这样可能会使出错率上升些。另外如果这些urlip是一一对应的,就可以转换成ip,则大大简单了。

        同时,上文的第5题:给定a、b两个文件,各存放50亿个url,每个url各占64字节,内存限制是4G,让你找出a、b文件共同的url?如果允许有一定的错误率,可以使用Bloom filter,4G内存大概可以表示340亿bit。将其中一个文件中的url使用Bloom filter映射为这340亿bit,然后挨个读取另外一个文件的url,检查是否与Bloom filter,如果是,那么该url应该是共同的url(注意会有一定的错误率)。”

    Bitmap

        下面关于Bitmap的应用,可以看下上文中的第13题,以及另外一道新题:

    “13、在2.5亿个整数中找出不重复的整数,注,内存不足以容纳这2.5亿个整数。

        方案1:采用2-Bitmap(每个数分配2bit,00表示不存在,01表示出现一次,10表示多次,11无意义)进行,共需内存2^32 * 2 bit=1 GB内存,还可以接受。然后扫描这2.5亿个整数,查看Bitmap中相对应位,如果是00变01,01变10,10保持不变。所描完事后,查看bitmap,把对应位是01的整数输出即可。
        方案2:也可采用与第1题类似的方法,进行划分小文件的方法。然后在小文件中找出不重复的整数,并排序。然后再进行归并,注意去除重复的元素。

    15、给40亿个不重复的unsigned int的整数,没排过序的,然后再给一个数,如何快速判断这个数是否在那40亿个数当中?
        方案1:frome oo,用位图/Bitmap的方法,申请512M的内存,一个bit位代表一个unsigned int值。读入40亿个数,设置相应的bit位,读入要查询的数,查看相应bit位是否为1,为1表示存在,为0表示不存在。


    密匙四、Trie树/数据库/倒排索引

    Trie树

      适用范围:数据量大,重复多,但是数据种类小可以放入内存
      基本原理及要点:实现方式,节点孩子的表示方式
      扩展:压缩实现。
      问题实例:

    1. 上面的第2题:寻找热门查询:查询串的重复度比较高,虽然总数是1千万,但如果除去重复后,不超过3百万个,每个不超过255字节。
    2. 上面的第5题:有10个文件,每个文件1G,每个文件的每一行都存放的是用户的query,每个文件的query都可能重复。要你按照query的频度排序。
    3. 1000万字符串,其中有些是相同的(重复),需要把重复的全部去掉,保留没有重复的字符串。请问怎么设计和实现?
    4. 上面的第8题:一个文本文件,大约有一万行,每行一个词,要求统计出其中最频繁出现的前10个词。其解决方法是:用trie树统计每个词出现的次数,时间复杂度是O(n*le)(le表示单词的平准长度),然后是找出出现最频繁的前10个词。

        更多有关Trie树的介绍,请参见此文:从Trie树(字典树)谈到后缀树

    数据库索引
      适用范围:大数据量的增删改查
      基本原理及要点:利用数据的设计实现方法,对海量数据的增删改查进行处理。

    倒排索引(Inverted index)
      适用范围:搜索引擎,关键字查询
      基本原理及要点:为何叫倒排索引?一种索引方法,被用来存储在全文搜索下某个单词在一个文档或者一组文档中的存储位置的映射。
     以英文为例,下面是要被索引的文本:
        T0 = "it is what it is"
        T1 = "what is it"
        T2 = "it is a banana"
        我们就能得到下面的反向文件索引:
        "a":      {2}
        "banana": {2}
        "is":     {0, 1, 2}
        "it":     {0, 1, 2}
        "what":   {0, 1}
     检索的条件"what","is"和"it"将对应集合的交集。

      正向索引开发出来用来存储每个文档的单词的列表。正向索引的查询往往满足每个文档有序频繁的全文查询和每个单词在校验文档中的验证这样的查询。在正向索引中,文档占据了中心的位置,每个文档指向了一个它所包含的索引项的序列。也就是说文档指向了它包含的那些单词,而反向索引则是单词指向了包含它的文档,很容易看到这个反向的关系。
      扩展:
      问题实例:文档检索系统,查询那些文件包含了某单词,比如常见的学术论文的关键字搜索。

        关于倒排索引的应用,更多请参见:


    密匙五、外排序

      适用范围:大数据的排序,去重
      基本原理及要点:外排序的归并方法,置换选择败者树原理,最优归并树
    问题实例:
      1).有一个1G大小的一个文件,里面每一行是一个词,词的大小不超过16个字节,内存限制大小是1M。返回频数最高的100个词。
      这个数据具有很明显的特点,词的大小为16个字节,但是内存只有1M做hash明显不够,所以可以用来排序。内存可以当输入缓冲区使用。

        关于多路归并算法及外排序的具体应用场景,请参见blog内此文:


    密匙六、分布式处理之Mapreduce

        MapReduce是一种计算模型,简单的说就是将大批量的工作(数据)分解(MAP)执行,然后再将结果合并成最终结果(REDUCE)。这样做的好处是可以在任务被分解后,可以通过大量机器进行并行计算,减少整个操作的时间。但如果你要我再通俗点介绍,那么,说白了,Mapreduce的原理就是一个归并排序。

    适用范围:数据量大,但是数据种类小可以放入内存
    基本原理及要点:将数据交给不同的机器去处理,数据划分,结果归约。
    问题实例:

    1. The canonical example application of MapReduce is a process to count the appearances of each different word in a set of documents:
    2. 海量数据分布在100台电脑中,想个办法高效统计出这批数据的TOP10。
    3. 一共有N个机器,每个机器上有N个数。每个机器最多存O(N)个数并对它们操作。如何找到N^2个数的中数(median)?

        更多具体阐述请参见blog内:

    其它模式/方法论,结合操作系统知识

        至此,六种处理海量数据问题的模式/方法已经阐述完毕。据观察,这方面的面试题无外乎以上一种或其变形,然题目为何取为是:秒杀99%的海量数据处理面试题,而不是100%呢。OK,给读者看最后一道题,如下:
        非常大的文件,装不进内存。每行一个int类型数据,现在要你随机取100个数
        我们发现上述这道题,无论是以上任何一种模式/方法都不好做,那有什么好的别的方法呢?我们可以看看:操作系统内存分页系统设计(说白了,就是映射+建索引)。
        Windows 2000使用基于分页机制的虚拟内存。每个进程有4GB的虚拟地址空间。基于分页机制,这4GB地址空间的一些部分被映射了物理内存,一些部分映射硬盘上的交换文 件,一些部分什么也没有映射。程序中使用的都是4GB地址空间中的虚拟地址。而访问物理内存,需要使用物理地址。 关于什么是物理地址和虚拟地址,请看:
    • 物理地址 (physical address): 放在寻址总线上的地址。放在寻址总线上,如果是读,电路根据这个地址每位的值就将相应地址的物理内存中的数据放到数据总线中传输。如果是写,电路根据这个 地址每位的值就将相应地址的物理内存中放入数据总线上的内容。物理内存是以字节(8位)为单位编址的。 
    • 虚拟地址 (virtual address): 4G虚拟地址空间中的地址,程序中使用的都是虚拟地址。 使用了分页机制之后,4G的地址空间被分成了固定大小的页,每一页或者被映射到物理内存,或者被映射到硬盘上的交换文件中,或者没有映射任何东西。对于一 般程序来说,4G的地址空间,只有一小部分映射了物理内存,大片大片的部分是没有映射任何东西。物理内存也被分页,来映射地址空间。对于32bit的 Win2k,页的大小是4K字节。CPU用来把虚拟地址转换成物理地址的信息存放在叫做页目录和页表的结构里。 
        物理内存分页,一个物理页的大小为4K字节,第0个物理页从物理地址 0x00000000 处开始。由于页的大小为4KB,就是0x1000字节,所以第1页从物理地址 0x00001000 处开始。第2页从物理地址 0x00002000 处开始。可以看到由于页的大小是4KB,所以只需要32bit的地址中高20bit来寻址物理页。 
        返回上面我们的题目:非常大的文件,装不进内存。每行一个int类型数据,现在要你随机取100个数。针对此题,我们可以借鉴上述操作系统中内存分页的设计方法,做出如下解决方案:

        操作系统中的方法,先生成4G的地址表,在把这个表划分为小的4M的小文件做个索引,二级索引。30位前十位表示第几个4M文件,后20位表示在这个4M文件的第几个,等等,基于key value来设计存储,用key来建索引。

        但如果现在只有10000个数,然后怎么去随机从这一万个数里面随机取100个数?请读者思考。更多海里数据处理面试题,请参见此文第一部分:http://blog.csdn.net/v_july_v/article/details/6685962



    参考文献

    1. 十道海量数据处理面试题与十个方法大总结
    2. 海量数据处理面试题集锦与Bit-map详解
    3. 十一、从头到尾彻底解析Hash表算法
    4. 海量数据处理之Bloom Filter详解
    5. 从Trie树(字典树)谈到后缀树
    6. 第三章续、Top K算法问题的实现
    7. 第十章、如何给10^7个数据量的磁盘文件排序
    8. 从B树、B+树、B*树谈到R 树
    9. 第二十三、四章:杨氏矩阵查找,倒排索引关键词Hash不重复编码实践
    10. 第二十六章:基于给定的文档生成倒排索引的编码与实践
    11. Hadhoop框架与MapReduce模式中谈海量数据处理
    12. 第十六~第二十章:全排列,跳台阶,奇偶排序,第一个只出现一次等问题
    13. http://blog.csdn.net/v_JULY_v/article/category/774945
    14. STL源码剖析第五章,侯捷著;
    15. 2012百度实习生招聘笔试题:http://blog.csdn.net/hackbuteer1/article/details/7542774
    16. Redis/MongoDB绝佳站点:http://blog.nosqlfan.com/
    17. 国外一面试题网站:http://www.careercup.com/


    后记

        经过上面这么多海量数据处理面试题的轰炸,我们依然可以看出这类问题是有一定的解决方案/模式的,所以,不必将其神化。然这类面试题所包含的问题还是比较简单的,若您在这方面有更多实践经验,欢迎在本文评论下与大家不吝分享
        不过,相信你也早就意识到,若单纯论海量数据处理面试题,本blog内的有关海量数据处理面试题的文章已涵盖了你能在网上所找到的70~80%。但有点,必须负责任的敬告大家:无论是这些海量数据处理面试题也好,还是算法也好,面试时70~80%的人不是倒在这两方面,而是倒在基础之上(诸如语言,数据库,操作系统,网络协议等等),所以,无论任何时候,基础最重要,没了基础,便什么都不是
        最后,推荐几个求职/算法/刷题的相关课程,包括LeetCode直播刷题等等,感兴趣的可以看下:https://www.julyedu.com/category/index/1
        OK,本文若有任何问题,欢迎随时不吝留言,评论,赐教,谢谢。完。

    重大消息:我的新书《编程之法:面试和算法心得》终于在2015年10月14日起上架开卖了!京东抢购地址http://item.jd.com/11786791.html。京东、当当、亚马逊等各大网店均已有现货销售。

    展开全文
  • 凯斯西储大学轴承数据处理+自制CNN数据集

    千次阅读 热门讨论 2019-05-29 11:25:34
    对于凯斯西储大学轴承数据的下载,现在网上随便一个帖子都可以下载到。 在下载数据的时候,发现里面分了正常数据、驱动端、风扇端等类别,然后在具体的某一类,比如驱动端里面又区分了不同类别的故障数据。具体可以...

    对于凯斯西储大学轴承数据的下载,现在网上随便一个帖子都可以下载到。
    在下载数据的时候,发现里面分了正常数据、驱动端、风扇端等类别,然后在具体的某一类,比如驱动端里面又区分了不同类别的故障数据。具体可以参见相关说明,或者参见其他帖子。
    然后下载其中某一个类别的某一个故障数据文件后,文件类型是.mat格式,可以使用MATLAB打开,打开后发现里面又区分了三种类型的数据,在这里插入图片描述
    如上图,这里不太清楚为什么在已经区分了正常、驱动端、风扇端数据类别的情况下,文件里面还要再分成这几类????难道又分了不同位置的故障数据?有点搞不清
    当然,如果需要进行处理这些数据,用来机器学习、CNN的话,并不是需要网站中的所有数据,自然可以只选择我们需要的,比如选择驱动端+0HP的故障数据
    处理数据步骤为:
    ①对于数据的处理,由于轴承信号数据是时间序列的数据,但是在训练使用的时候有些不方便,这里我是把同一类别的数据随机分组,将一维的序列分成二维,具体一组多少数据,看自己分类吧。下载的文件每一个都进行如此操作(可以使用程序在调用数据的时候处理)。
    ②然后将每个类别的数据文件对应建立标签文件。
    ③这样处理之后,每一类故障数据都对应着一个数据文件和一个标签文件,然后将所有类别的数据文件整合到一起组合成训练网络需要的数据集,再将数据集按比例分成训练集和测试集即可。
    以上为使用凯斯西储大学自制数据集的过程,如有错误,还请大佬指点,欢迎交流!!

    展开全文
  • 为了方便使用,博文中附上了包括数据集整理及数据预处理在内的所有代码及处理好的数据集,同时对代码进行了解释,其要点如下:UCI数据集介绍、不同数据集的整理程序、148个整理好的数据集与对应程序。

    介绍图
    摘要:本文对机器学习中的UCI数据集进行介绍,带你从UCI数据集官网出发一步步深入认识数据集,并就下载的原始数据详细讲解了不同类型的数据集整理如何通过程序进行整理。为了方便使用,博文中附上了包括数据集整理及数据预处理在内的所有代码及处理好的数据集,同时对代码进行了解释,其要点如下:

    \color{#4285f4}{点}\color{#ea4335}{击}\color{#fbbc05}{跳}\color{#4285f4}{转}\color{#34a853}{至}\color{#ea4335}{博}\color{#4285f4}{文}\color{#ea4335}{涉}\color{#fbbc05}{及}\color{#4285f4}{的}\color{#34a853}{全}\color{#ea4335}{部}\color{#fbbc05}{文}\color{#4285f4}{件}\color{#34a853}{下}\color{#ea4335}{载}\color{#fbbc05}{页}


    前言

      UCI\color{#4285f4}{U}\color{#ea4335}{C}\color{#fbbc05}{I}\color{#4285f4}数据集作为机器学习算法比较中的绝对经典经常出现在大多数论文或研究中。为了验证机器学习算法性能,UCI数据集通常用作为通用数据集,但官网提供的原始数据可能有格式不一致、缺失数据、包含特殊字符等问题,通常不能直接用于算法程序中,数据集的查找、下载、整理等可能会给初学者带来一定困扰。

    UCI官网配图
      对于数据集的查找整理确实是件费时费力的事情,是不是总有“论文就一篇,数据找半天”的问题?这里就来探讨下数据集整理的那些事。其实早前作者就写了一篇关于UCI数据集处理的博文:UCI数据集整理(附论文常用数据集)介绍了如何用程序整理数据集,这里会更加深入地介绍不同类型的数据集处理方法及数据预处理。本文较长建议结合右侧的目录阅读。


    1.UCI数据集介绍

      这一节先从UCI数据集官网出发介绍数据集的属性、格式等信息,在我的博文:UCI数据集整理(附论文常用数据集)中也有部分介绍,对数据集熟悉或想看数据处理代码干货的朋友也可以直接跳转至下一节。下面先看一下对UCI数据集的介绍。

    1.1 UCI数据集官网介绍

      UCI\color{#4285f4}{U}\color{#ea4335}{C}\color{#fbbc05}{I}\color{#4285f4}(University of California Irvine)数据集是美国加州大学欧文分校提出的一种适合模式识别和机器学习方向的开源数据集,很多学者选择使用UCI上的数据集来验证自己所提算法的正确性。博文写作时已拥有488个数据集,数据集还在不断扩充中,这些数据集主要分为二值分类问题、多分类问题以及回归拟合问题。UCI数据集提供了各个数据集的上主要属性,可以根据自己提出的各类算法在其数据集上做实验结果论证,证明自己所提算法的合理性。
    uci官网
    UCI数据集官网地址:https://archive.ics.uci.edu/ml/index.php
    UCI数据集数据地址:https://archive.ics.uci.edu/ml/datasets.php

      我在下图所示的UCI数据集官网截图中对其页面主要部分进行了标注,可以看出主页中主要包括了数据集页面入口、最新数据集、经典数据集及数据集的最近消息等。数据集页面入口提供了进入官网查看全部数据集的链接,为了方便用户查找在「最新数据集」和「经典数据集」区域整理了最新收录以及引用最多的几个数据集。如果只是简单测试下代码,直接点击页面上提供的数据集链接下载几个数据集就可以了,如果还需要更多数据集那就进入数据集页面入口,该页面发布有全部的数据集。

    首页介绍
      下图(图中页面已翻译)所示的全部数据集页面是一个按类型排列的数据表,可以按照数据集名称、任务类型、属性类型、数据类型等进行排列查找,点击想要的数据集链接可进入该数据集详情页。值得注意的是,右上角有一个搜索框,用户可以通过输入数据集名字搜索数据集,不过比较可惜亲测下来该搜索在没有外网VPN的加持下可能不能打开网页 (当然不能用的还有搜数据集的利器——谷歌数据集搜索)。
    在这里插入图片描述
      现在以官网数据集页面中的Adult(成年人收入)数据集为例,介绍以下数据集详情页面,点击链接进入Adult数据集页面,页面主要情况如下图1.1.1所示。对于需要特别关注的地方我已经用红色标记,主要包括数据集下载页面链接、数据集说明下载链接、数据量、属性数、是否确实数据及属性信息。当然其他的信息不可说没有必要,当我们要选用某个数据集进行测试时,了解更多的相关信息有助于更好根据数据情况对算法做出调整。页面最后面的相关论文和引用文献也能帮助了解专业情况。

    adult数据集页面

    图1.1.1 Adult数据集页面

    这里对上面提及的几个重要部分做个简介:

    • 数据量(Number of Instances):或称实例数,表示数据集有多少行数据。
    • 属性数(Number of Attributes):表示数据集每行有多少个特征属性,决定了数据集复杂程度。
    • 属性信息(Attribute Information):这里介绍了数据集的分类类别,及每个属性表示的意义。例如上图数据集中介绍了成年人收入的两种分类类别:> 50K, <= 50K,属性情况:年龄、工作类别、教育程度等14个属性。
    • 是否缺失数据(Missing Values):这体现了数据集中是否有某些数据缺失,如有缺失,则应特别注意在数据处理时需要补充数据或删除无效数据。
    • 属性类型(Attribute Characteristics):一般有Categorical(类别型), Integer(整数型), Real(实数型)这三种。值得注意的是,如果这一栏中有Categorical型表示该数据集中可能会包含字符串,处理数据时需要用对应数字代替。

    1.2 数据集文件认识

    下载链接
      如上图所示,点击Data Folder进入Adult数据集文件下载目录页面,可以看到该数据集的文件目录如下图所示。点击下载链接即可下载该数据集,Adult数据集已经划分好训练和测试数据集(一般的数据集未划分则只有一个数据文件),所以这里需要分别下载下图所示的两处文件,如下在链接上右键,点击“链接另存为”即可下载文件。

    数据集下载
      上面下载的文件格式类型为data型,该文件在MATLAB中可以直接打开(也可以右击选择打开方式为记事本打开),打开的文件内容如下图(加的红线分割左侧为属性,右侧为标记):

    Adult文件内容

    图1.2.1 Adult文件数据详情

      可以看到文件中的数据中既有英文字符串又有整数,果然同前面介绍页中的“属性类型”显示的那样为Categorical型和Integer性。刚学习的朋友可能不太能明白这一堆数据里面到底是些什么,这一堆奇怪的数据真的能被算法直接计算吗?其实在上面一小节中已经有所提及,前面我们看到Adult数据集详情页面中“Attribute Information(属性信息)”那一栏(如图1.2.2)介绍的该数据集的类别有两个:> 50K, <= 50K,也就是收入超过50K和不超过50K两类。这说明每行最后面的那一栏是就标签,这实际是一个二分类任务的数据集,每行前面的14个数据分别是年龄、工作类别、教育程度等14个属性,如下图1.2.2:

    属性信息

    图1.2.2 Adult数据集属性信息

      再仔细看图1.2.1中的数据,结合图1.2.2可以知道每行的第一个属性表示的是年龄,它是个连续的整数型数据。而第二个属性为工作类别,它是一个英文字符串表示的字符型离散值,在整个数据集中这一属性实际可能取值是:Private, Self-emp-not-inc, Self-emp-inc, Federal-gov, Local-gov, State-gov, Without-pay, Never-worked这几个工作类别,也就是前面说的Categorical型,同样的还有第4,6,7…个属性表示的教育程度、婚姻状况、职业等等。这为我们后面用程序整理数据集提供了思路,既然是有限类别的,那我们就可以用类似1,2,3…这样的数字代替对应的英文字符串从而转化为一个纯数字的数据文件供算法程序使用了,后面一章将详细介绍。

      前面的图1.2.1中展示的是数据集前12行的数据,但如果我们再仔细浏览后面的数据还有一些值得注意的地方,如下图1.2.3标记的第15行数据。

    adult缺失数据信息

    图1.2.3 Adult数据集缺失数据部分

      该行数据的第14个属性表示为“?”意味着该处数据缺失,也就是国籍不详(第14个属性表示国籍),此外还有其他少数的几行有部分数据缺失。这和前面图1.1.1中的描述的“存在数据缺失”相符,数据缺失在机器学习中也很常见,因为数据的采集过程可能比较复杂,有些数据缺失在所难免。对于缺失的数据我们要做的也很简单,那就是“补上还能用的数据,或者删掉无效的数据”就可以了,下一章会详细讲述。

    存在缺失数据

    1.3 不同类型的UCI数据集

      上面两个小节以Adult数据集为例从头到尾介绍了一遍如何认识和理解数据集文件中的数据,读者应该对UCI数据集有了一个基本认识。其实Adult数据集算是一个比较“复杂麻烦”的数据集了,大多的数据集不会有那么多英文字符和数据缺失。大多的数据集属性为数字,类别标签可能是数字或英文字符,数据也比较完整是无需我们处理缺失数据的。在我的博文《UCI数据集整理(附论文常用数据集)》中也有介绍,有兴趣的可以点过去看一下。之所以说得这么复杂是因为这个数据集几乎包含了UCI数据集中的所有可能的“麻烦问题”。接下来简单列举总结下UCI数据集文件中数据的几种类型,这将决定了我们后面采用怎样的方式整理数据集。

      为了后面叙述方便,原谅我不太专业地根据文件中的数据是否部分包含英文字符、是否为纯数字、是否缺失数据将其分为三个难度:“纯数字、无缺失”,“部分英文字符、无缺失”,“部分or全部英文字符、有缺失”来分别介绍。当然还有“纯数字、有缺失”等组合,但是也可以参考第三种对缺失的处理方式,为了避免重复叙述这里就省略了。这三种情况的代表数据集有Glass数据集Abalone数据集Adult数据集,三个数据集的部分数据截图如下:

    glass数据集
    abalone数据集
    Adult数据集
      上面的三个数据集建议读者按照前面两小节的方法对照每个数据集详情页面上的介绍再研究一下,对于这三个数据集的介绍这里就不一一展开了,下面一节将以这三个数据集的整理为例讲述如何通过程序整理这三种数据集文件。


    2. 不同数据集的整理

      这一节就上节提到的UCI数据集中常见三种文件数据类型如何通过程序整理进行详细介绍。首先之所以需要整理数据集,是因为我们下载的UCI数据集文件常常可能含有英文字符串、缺失数据、存在无效数据等问题或者下载下来的数据集文件格式不一致导致我们无法通过统一的程序使用它。那么什么样的数据格式是我们想要的呢?

      还是以Adult数据集为例,其中的英文字符需要换成对应的数字表示,缺失的数据需要补充,另外数据集的分类标记:> 50K, <= 50K分别用数字> 0, 1代替并由最后一列移至首位(标记一般在数据首位,也可以放在末尾)。Adult数据集的原始数据文件与整理完成后的数据文件对比如下图所示:

    adult原始数据

    图2.1 Adult数据集原始数据

    Adult整理后的数据

    图2.2 Adult数据集整理后的数据

      很明显整理后的数据干净整洁、易于读取,而且在部分属性特征上更加适合机器学习算法处理,其中每行数据的第一个数字为分类标记。类似图2.2正是我们需要的数据格式,为了统一使用方便,博文中的数据集都整理为这种形式。接下来从易到难分别介绍“纯数字、无缺失”,“部分英文字符、无缺失”,“部分or全部英文字符、有缺失”三种情况下的数据如何通过程序整理,以下部分全部采用Matlab\color{#4285f4}{M}\color{#ea4335}{a}\color{#fbbc05}{t}\color{#4285f4}{l}\color{#34a853}{a}\color{#ea4335}{b}编程实现。

    2.1 “纯数字、无缺失”数据集

      以Glass数据集为例,首先在Glass数据集下载页下载Glass原始数据集,其数据文件部分数据如下图所示。其特点为纯数字,无缺失和特殊数据因此无需特殊处理技巧。由Glass数据集详情页上的介绍,该数据集为一个分类数为6,属性数为9的数据集。

    glass数据集
      在下载的数据文件存放路径处新建Matlab\color{#4285f4}{M}\color{#ea4335}{a}\color{#fbbc05}{t}\color{#4285f4}{l}\color{#34a853}{a}\color{#ea4335}{b}程序,创建一个命名为main.m的文件,并在编辑器键入如下代码:

    % glass
    % author: wuxian, website: https://wuxian.blog.csdn.net
    clear;
    clc;
    
    data_name = 'glass';
    fprintf('开始处理数据集: %s ...\n', data_name);
    
    n_entradas= 9; % 属性数
    n_clases= 6; % 类别数
    n_patrons(1)= 214; % 数据量(行数)
    n_fich= 1;
    fich{1}= 'glass.data'; % 文件路径名
    
    n_max= max(n_patrons);
    x = zeros(n_fich, n_max, n_entradas); % 用于存放提取出的属性数据
    cl= zeros(n_fich, n_max);             % 用于存放数据标签
    
    n_patrons_total = sum(n_patrons); % 用于显示进度
    n_iter=0;
    
    for i_fich=1:n_fich
        f=fopen(fich{i_fich}, 'r'); % 打开文件
        if -1==f
            error('打开数据文件出错 %s\n', fich{i_fich});
        end
        
        for i=1:n_patrons(i_fich) % 循环对每行数据进行处理
            n_iter=n_iter+1;
            fprintf('%5.1f%%\r', 100*n_iter/n_patrons_total); % 显示处理进度
            
            fscanf(f,'%i',1); % 第一个数字为序号,无需记录
            for j = 1:n_entradas
                temp=fscanf(f, ',%f',1); % 读取下一个数据,以逗号分隔
                x(i_fich,i,j) = temp;    % 保存一个数值到x
            end
            t=fscanf(f,',%i',1);
            if t >= 5  % 原数据标记中没有5,所以后面标号需要-1
                t = t - 1;
            end
            
            cl(i_fich,i) = t - 1;  	% 原标记从1开始,改为从0开始
        end
        fclose(f);% 关闭文件
    end
    
    
    %% 处理完成,保存文件
    fprintf('现在保存数据文件...\n')
    data = squeeze(x); % 数据
    label = cl';% 标签
    dataSet = [label,data];
    dir_path=['./预处理完成/',data_name];
    if exist('./预处理完成/','dir')==0   %该文件夹不存在,则直接创建
        mkdir('./预处理完成/');
    end
    saveData(dataSet,dir_path); % 保存文件至文件夹
    fprintf('预处理完成\n')
    
    
    %% 子函数,用于保存txt/data/mat三种类型文件
    function saveData(DataSet,fileName)
    % author:wuxian
    % DataSet:整理好的数据集
    % fileName:数据集的名字
    
    %% Data为整理好的数据集矩阵
    mat_name = [fileName,'.mat'];
    save(mat_name, 'DataSet')  % 保存.mat文件
    data_name = [fileName,'.data'];
    save(data_name,'DataSet','-ASCII'); % 保存data文件
    
    % 保存txt文件
    txt_name = [fileName,'.txt'];
    f=fopen(txt_name,'w');
    [m,n]=size(DataSet);
    for i=1:m
        for j=1:n
            if j==n
                if i~=m
                    fprintf(f,'%g \n',DataSet(i,j));
                else
                    fprintf(f,'%g',DataSet(i,j));
                end
            else
                fprintf(f,'%g,',DataSet(i,j));
            end
        end
    end
    fclose(f);
    
    % save iris.txt -ascii Iris
    % dlmwrite('iris.txt',Iris);
    end
    

      以上程序代码的思路是提取每行中每个数据的属性和标签分别保存到与x, cl两个矩阵中,然后通过调用子函数saveData( )保存数据为txt, data, mat格式文件。数据提取的过程是通过遍历每行数据,利用fscanf( )函数逐个读取每个逗号分隔的数据,最后在第52行将得到的属性和标签合并成一个矩阵并将标签放在第一列。运行程序后整理好的文件将保存在“预处理完成”的文件夹中,保存的文件及整理后的数据如下:

    保存文件与整理好的数据
    以上整理好的数据集第一列为标签(取值有0, 1, 2, 3, 4, 5),其余列为属性并与原数据集一致。

    2.2 “部分英文字符、无缺失”数据集

      相比前一小节中纯数字的原始数据集,最为常见的数据恐怕还是部分带一些英文字符的了。有些数据集的某些特征取值为有限个数的离散值,例如Abalone数据集,从Abalone数据集下载页下载该数据集,打开部分数据如下图所示:

    abalone数据集

      从上图数据中可以看出只有第一列的属性为英文字符,其它属性都是数字,根据Abalone数据集详情页上的介绍,该数据集的第一列属性是鲍鱼的性别,有雄性(M)、雌性(F)及幼期(I)三个取值,所以这里需将第一个属性中的英文字符“M, F, I”分别用数字“-1, 0, 1”代替。

      另外该数据集要预测的物理量是鲍鱼的年龄,原始数据集年龄那一列数据(最后一列)实际为连续取值,在该数据集的“属性信息”中有介绍到该数据集既可以作为连续值预测也可以用于分类任务。所以这里在处理Abalone数据集的标签时需要将连续数值离散化,我们可以根据鲍鱼年龄age的取值分为:“age<9,9<age<11,age>11age<9, 9<age<11, age>11”三类,分别用数字“-1, 0, 1”表示。这是针对这一单个数据集而言的,如果数据集标签本身就是可以直接用于分类的,就无需进行离散化了。

      按照上面的分析,处理这种数据集时我们只需替换第一列英文字符并将最后一列的标签离散化。在下载的数据文件存放路径处新建Matlab\color{#4285f4}{M}\color{#ea4335}{a}\color{#fbbc05}{t}\color{#4285f4}{l}\color{#34a853}{a}\color{#ea4335}{b}程序,创建一个命名为main.m的文件,并在编辑器键入如下代码:

    %% abalone
    % author: wuxian, website: https://wuxian.blog.csdn.net
    clear;
    clc;
    data_name = 'abalone';
    fprintf(['处理数据集: ',data_name,'abalone 原始数据 ...\n']);
    fich= [data_name,'.data'];
    
    n_entradas= 8; % 属性数
    n_clases= 3;  % 分类数
    n_fich= 1; % 数据集个数
    n_patrons= 4177; % 数据量(行数)
    
    x = zeros(n_patrons, n_entradas); % 用于存放提取出的属性数据
    cl= zeros(1, n_patrons);% 用于存放数据标签
    
    f=fopen(fich, 'r');% 打开文件
    if -1==f
        error('打开文件出错 %s\n', fich);
    end
    for i=1:n_patrons % 循环对每行数据进行处理
        
        fprintf('%5.1f%%\r', 100*i/n_patrons(1));% 显示处理进度
        
        t = fscanf(f, '%c', 1); % 读取一个字符数据
        switch t % 将对应字符替换为数字
            case 'M'
                x(i,1)=-1;
            case 'F'
                x(i,1)=0;
            case 'I'
                x(i,1)=1;
        end
        
        for j=2:n_entradas
            fscanf(f,'%c',1); % 中间有分隔符,后移1个位置
            x(i,j) = fscanf(f,'%f', 1);% 依次读取这一行所有属性
        end
        
        fscanf(f,'%c',1); 
        t = fscanf(f,'%i', 1); % 读取最后的标记值
        % 根据范围将连续的标记值离散化为三类
        if t < 9
            cl(1,i)=0;
        elseif t < 11
            cl(1,i)=1;
        else
            cl(1,i)=2;
        end
        fscanf(f,'%c',1);
        
    end
    fclose(f);
    
    %% 处理完成,保存文件
    fprintf('现在保存数据文件...\n')
    data = x; % 数据
    label = cl';% 标签
    dataSet = [label,data];
    dir_path=['./预处理完成/',data_name];
    if exist('./预处理完成/','dir')==0   %该文件夹不存在,则直接创建
        mkdir('./预处理完成/');
    end
    saveData(dataSet,dir_path); % 保存文件至文件夹
    fprintf('预处理完成\n')
    
    
    %% 子函数,用于保存txt/data/mat三种类型文件
    function saveData(DataSet,fileName)
    % DataSet:整理好的数据集
    % fileName:数据集的名字
    
    %% Data为整理好的数据集矩阵
    mat_name = [fileName,'.mat'];
    save(mat_name, 'DataSet')  % 保存.mat文件
    data_name = [fileName,'.data'];
    save(data_name,'DataSet','-ASCII'); % 保存data文件
    
    % 保存txt文件
    txt_name = [fileName,'.txt'];
    f=fopen(txt_name,'w');
    [m,n]=size(DataSet);
    for i=1:m
        for j=1:n
            if j==n
                if i~=m
                    fprintf(f,'%g \n',DataSet(i,j));
                else
                    fprintf(f,'%g',DataSet(i,j));
                end
            else
                fprintf(f,'%g,',DataSet(i,j));
            end
        end
    end
    fclose(f);
    
    % save iris.txt -ascii Iris
    % dlmwrite('iris.txt',Iris);
    end
    

      和前面整理的思路类似,这里还是使用x, cl两个矩阵保存从原始文件中提取的属性和标签,其中读取每个数值点采用循环调用fscanf( )函数逐个移动文件指针的方式读取,将提取的数据属性保存在x矩阵中。代码第25-33行读取出第一个属性值并根据它的取值不同分别对x的第一个元素赋不同的数字。代码第41-49行读取最后一列数值,并根据其值的取值范围将其划分为三个标签值的其中一个。至于各数据点之间的逗号分割符,程序中使用fscanf( )函数移动指针到下一个数据位置而并未赋值到变量中,从而跳过了逗号分隔符,如代码第36,40,50行。运行以上代码,得到整理完成的数据文件及部分数据截图如下:

    整理后的abalone数据集
    以上整理好的数据集第一列为标签(取值有0, 1, 2),其余列为属性,第一个属性已处理为数字(取值有-1, 0, 1

    2.3 “部分英文字符、有缺失”数据集

      经过前面两个例子的介绍我们再来看一个更加复杂点的数据集类型即除了有英文字符还有缺失数据的部分。以Adult数据集为例,这个数据集前面已多有介绍,改数据集有划分好的训练集和测试集,所以从AdultData Folder下载adult.dataadult.test两个数据文件,部分数据如下图:

    adult数据集
      字符型离散值转化为数值型:我们可以将某个需要转化为数值型的字符型属性的全部可能取值存放在一个元胞数组中并记取值个数为nn,而转化后的数值范围一般取[1,1][-1, 1],所以我们在[1,1][-1, 1]的取值范围内平均取nn个实数{1,3nn1,...,2k1nn1,...,n3n1,1},k=1,2,3,...,n1,n\{-1, \frac{3-n}{n-1}, ..., \frac{2k-1-n}{n-1}, ...,\frac{n-3}{n-1}, 1\}, k=1,2,3, ...,n-1, n用来代替这些字符型属性。比方说Adult原始数据的第2个属性表示工作类型有’Private’, ‘Self-emp-not-inc’, ‘Self-emp-inc’, ‘Federal-gov’, ‘Local-gov’, ‘State-gov’, ‘Without-pay’, 'Never-worked’将被分别替换为数值1,57,37,17,17,37,57,1-1, -\frac{5}{7}, -\frac{3}{7}, -\frac{1}{7}, \frac{1}{7}, \frac{3}{7}, \frac{5}{7}, 1。在程序中比对字符串然后可按以上公式顺序赋值为相应的数值。

      缺失数据处理:对于缺失数据的处理其实现在并没有一个很好的解决方式,一般来说缺失的数据点较少时可以直接删去,较常见的是采用该属性的均值、中值或众数来填充缺失,当然也可以直接补充为某些特定值。直接删去数据会导致数据量减少,而均值填补主要用于连续资料的缺失,这里的数据集属性大多为离散量,使用均值并不是一个很好的方法。以上方法大家可以分别尝试一下,这里直接对缺失的数据补充特定值0处理。

      在下载的数据文件存放路径处新建Matlab\color{#4285f4}{M}\color{#ea4335}{a}\color{#fbbc05}{t}\color{#4285f4}{l}\color{#34a853}{a}\color{#ea4335}{b}程序,创建一个命名为main.m的文件,并在编辑器键入如下代码:

    %% adult
    % author:wx  website:https://wuxian.blog.csdn.net
    clear;
    clc;
    
    data_name = 'adult';% 数据集名
    fprintf('lendo problema adult...\n');
    
    n_entradas= 14; % 属性数
    n_clases= 2; % 分类数
    n_fich= 2; % 文件数,含有训练和测试集
    fich{1}= 'adult.data';% 训练数据路径
    n_patrons(1)= 32561; % 训练集数据量
    
    fich{2}= 'adult.test'; % 测试数据路径
    n_patrons(2)= 16281;   % 测试数据量
    
    n_max= max(n_patrons);
    x = zeros(n_fich, n_max, n_entradas); % 属性数据
    cl= zeros(n_fich, n_max);             % 标签
    
    discreta = [0, 1, 0, 1, 0, 1, 1, 1, 1, 1, 0, 0, 0, 1]; % 1表示该位置的属性需要将字符型离散值转化为数值型
    
    % 字符型离散值的所有取值
    workclass = {'Private', 'Self-emp-not-inc', 'Self-emp-inc', 'Federal-gov', 'Local-gov', 'State-gov', 'Without-pay', 'Never-worked'};
    education = {'Bachelors', 'Some-college', '11th', 'HS-grad', 'Prof-school', 'Assoc-acdm', 'Assoc-voc', '9th', '7th-8th', '12th', 'Masters', '1st-4th', '10th', 'Doctorate', '5th-6th', 'Preschool'};
    marital = {'Married-civ-spouse', 'Divorced', 'Never-married', 'Separated', 'Widowed', 'Married-spouse-absent', 'Married-AF-spouse'};
    occupation = {'Tech-support', 'Craft-repair', 'Other-service', 'Sales', 'Exec-managerial', 'Prof-specialty', 'Handlers-cleaners', 'Machine-op-inspct', 'Adm-clerical', 'Farming-fishing', 'Transport-moving', 'Priv-house-serv', 'Protective-serv', 'Armed-Forces'};
    relationship = {'Wife', 'Own-child', 'Husband', 'Not-in-family', 'Other-relative', 'Unmarried'};
    race = {'White', 'Asian-Pac-Islander', 'Amer-Indian-Eskimo', 'Other', 'Black'};
    sex = {'Male', 'Female'};
    country = {'United-States', 'Cambodia', 'England', 'Puerto-Rico', 'Canada', 'Germany', 'Outlying-US(Guam-USVI-etc)', 'India', 'Japan', 'Greece', 'South', 'China', 'Cuba', 'Iran', 'Honduras', 'Philippines', 'Italy', 'Poland', 'Jamaica', 'Vietnam', 'Mexico', 'Portugal', 'Ireland', 'France', 'Dominican-Republic', 'Laos', 'Ecuador', 'Taiwan', 'Haiti', 'Columbia', 'Hungary', 'Guatemala', 'Nicaragua', 'Scotland', 'Thailand', 'Yugoslavia', 'El-Salvador', 'Trinadad&Tobago', 'Peru', 'Hong', 'Holand-Netherlands'};
    
    % 字符型离散值的所有取值个数
    n_workclass=8; 
    n_education=16; 
    n_marital=7; 
    n_occupation=14; 
    n_relationship=6; 
    n_race=5; 
    n_sex=2; 
    n_country=41;
    
    for i_fich = 1:n_fich
        f=fopen(fich{i_fich}, 'r');
        if -1==f
            error('打开数据文件出错 %s\n', fich{i_fich});
        end
        
        for i=1:n_patrons(i_fich)
            fprintf('%5.1f%%\r', 100*i/n_patrons(i_fich)); % 显示进度
            
            for j = 1:n_entradas
                if discreta(j)==1
                    s = fscanf(f,'%s',1); 
                    s = s(1:end-1); % 去掉字符串末尾的逗号
                    if strcmp(s, '?')  % 对于缺失值补0
                        x(i_fich,i,j)=0;
                    else
                        % 确定具体的属性位置并赋相应变量
                        if j==2
                            n = n_workclass; p=workclass;
                        elseif j==4
                            n = n_education; p=education;
                        elseif j==6
                            n = n_marital; p=marital;
                        elseif j==7
                            n = n_occupation; p=occupation;
                        elseif j==8
                            n = n_relationship; p=relationship;
                        elseif j==9
                            n = n_race; p=race;
                        elseif j==10
                            n = n_sex; p=sex;
                        elseif j==14
                            n = n_country; p=country;
                        end
                        % 根据读取的字符值按排列顺序转化为-11之间的分数值
                        a = 2/(n-1); b= (1+n)/(1-n);
                        for k=1:n
                            if strcmp(s, p(k))
                                x(i_fich,i,j) = a*k + b; 
                                break
                            end
                        end
                    end
                else %0的位置(原数据就是数值型)直接读取原数据
                    temp = fscanf(f,'%g',1); 
                    x(i_fich,i,j) = temp; 
                    fscanf(f,'%c',1);
                end
    
            end
            
            s = fscanf(f,'%s',1);
            % 将标签转化为数值型(0,1if strcmp(s, '<=50K')||strcmp(s, '<=50K.')
                cl(i_fich,i)=0;
            elseif strcmp(s, '>50K')||strcmp(s, '>50K.')
                cl(i_fich,i)=1;
            else
                error('类别标签 %s 读取出错\n', s)
            end
    
        end
        fclose(f);
    end
    
    
    %% 处理完成,保存文件
    fprintf('现在保存数据文件...\n')
    dir_path=['./预处理完成/',data_name];
    if exist('./预处理完成/','dir')==0   %该文件夹不存在,则直接创建
        mkdir('./预处理完成/');
    end
    data_train =  squeeze(x(1,1:n_patrons(1),:)); % 数据
    label_train = squeeze(cl(1,1:n_patrons(1)))';% 标签
    dataSet_train = [label_train, data_train];
    saveData(dataSet_train,[dir_path,'_train']); % 保存文件至文件夹
    
    data_test =  squeeze(x(2,1:n_patrons(2),:)); % 数据
    label_test = squeeze(cl(2,1:n_patrons(2)))';% 标签
    dataSet_test = [label_test,data_test];
    saveData(dataSet_test,[dir_path,'_test']);
    
    fprintf('预处理完成\n')
    
    
    %% 子函数,用于保存txt/data/mat三种类型文件
    function saveData(DataSet,fileName)
    % DataSet:整理好的数据集
    % fileName:数据集的名字
    
    %% Data为整理好的数据集矩阵
    mat_name = [fileName,'.mat'];
    save(mat_name, 'DataSet')  % 保存.mat文件
    data_name = [fileName,'.data'];
    save(data_name,'DataSet','-ASCII'); % 保存data文件
    
    % 保存txt文件
    txt_name = [fileName,'.txt'];
    f=fopen(txt_name,'w');
    [m,n]=size(DataSet);
    for i=1:m
        for j=1:n
            if j==n
                if i~=m
                    fprintf(f,'%g \n',DataSet(i,j));
                else
                    fprintf(f,'%g',DataSet(i,j));
                end
            else
                fprintf(f,'%g,',DataSet(i,j));
            end
        end
    end
    fclose(f);
    
    % save iris.txt -ascii Iris
    % dlmwrite('iris.txt',Iris);
    end
    

      这里代码在前面一个的基础上做了改进,对于原文件属性是数值型的直接读取到x矩阵中,对于字符型的属性按照顺序对应为[-1, 1]上的离散数值。运行以上代码,得到整理完成的数据文件及部分数据截图如下:

    整理后的adult数据集
    以上整理好的数据集第一列为标签(取值有0, 1),其余列为属性,其中的字符型属性已处理为数值型。

      至此不同数据集的整理程序就介绍到这里了,UCI\color{#4285f4}{U}\color{#ea4335}{C}\color{#fbbc05}{I}\color{#4285f4}数据集数量众多,虽然没有统一的整理代码但经过这三个例子大家可以参考修改整理自己需要的数据集了。如果您有更好的整理方法欢迎在下方留言哦。


    3. 148个整理好的数据集与对应程序

      博主在三年的机器学习学习和研究中已累计整理了148个论文和研究中常用的UCI数据集,后面还会继续整理更多数据集并更新下载资源。查找、下载和整理数据集是件费时费力的事情,完整整理好足够论文或研究学习中需要的数据集可能会花费好多天甚至数周的时间,为了减少重复整理数据的繁冗工作,这里博主将自己整理好的148UCI数据集分享给大家,其中每个文件夹中都包含了以下内容:

    1. 从官网下载的完整原始数据文件
    2. 整理数据集、归一化及划分训练测试数据集的完整Matlab\color{#4285f4}{M}\color{#ea4335}{a}\color{#fbbc05}{t}\color{#4285f4}{l}\color{#34a853}{a}\color{#ea4335}{b}程序文件
    3. 整理完成后的数据集文件

    您可以直接使用里面整理好的数据集文件,也可以修改或重新运行整理的程序代码,整理好的148UCI数据集截图如下:

    整理好的全部文件目录
    文件中的所有程序代码均在Matlab\color{#4285f4}{M}\color{#ea4335}{a}\color{#fbbc05}{t}\color{#4285f4}{l}\color{#34a853}{a}\color{#ea4335}{b} R2016b中测试运行通过,整理的好数据集也是经过检查和自行使用过的,每个子文件夹里面的文件内容截图如下,下面提供了下载链接欢迎前去下载。

    文件夹详情图

    【资源获取】
      若您想获得博文中介绍的整理Glass数据集、Abalone数据集及Adult数据集涉及的完整程序文件(包含三个数据的原始文件、整理数据集程序代码文件及整理好的文件)扫描以下二维码并关注公众号“AI技术研究与分享”,后台回复“UC20200223”获取。
    公众号二维码

    148个整理好的UCI数据集下载】

      为大家提供优质的资源是博主一直坚持的动力,若您想获得上述介绍的148个整理好的UCI数据集(已包含本文中介绍的三个数据集),可以点击如下链接到博主的面包多网页上下载,面包多网站可以直接点击解锁,完成后可解锁页面下方的下载链接图标,点击即可下载。

    下载链接:博主在面包多网站上的完整资源下载页


    结束语

      由于博主能力有限,博文中提及的方法即使经过试验,也难免会有疏漏之处。希望您能热心指出其中的错误,以便下次修改时能以一个更完美更严谨的样子,呈现在大家面前。同时如果有更好的实现方法也请您不吝赐教。

    展开全文
  • 普林斯顿Stata教程 - Stata数据处理

    千次阅读 2018-06-04 11:46:41
    译者:谢作翰 | 连玉君 | (知乎 | 简书 | 码云)   原文链接:Princeton Stata 在线课程 (Princeton University - Stata Tutorial ) ...普林斯顿Stata教程 - Stata数据管理 普林斯顿Stata教程 ...

    译者:谢作翰 | 连玉君 | (知乎 | 简书 | 码云)

    原文链接:Princeton Stata 在线课程 (Princeton University - Stata Tutorial )

    连享会计量方法专题……

    专题链接

    目录

    1.1 数据读取

    • 1.1.1 自由格式数据
    • 1.1.2 固定格式数据

    1.2 数据文档

    • 1.2.1 数据标签与注释
    • 1.2.2 变量标签和注释
    • 1.2.3 值标签
    • 1.2.4 多语言标签

    1.3 创建新变量

    • 1.3.1 生成和替换
    • 1.3.2 运算符,表达式及函数
      1.4 变量重编码

    1.1 数据读取

    在本节中,我们将讨论如何读取原始数据文件。如果您的数据来自其他统计软件包(如SAS或SPSS),请考虑使用诸如Stat/Transfer
    www.stattransfer.com)或DBMSCopy(www.dataflux.com)之类的工具。Stata可以使用fdause命令来读取SAS文件help fdause。Stata还可以导入和导出Excel电子表格,输入help import excel以了解更多信息,并且可以从关系数据库读取数据,输入help odbc简介。

    1.1.1 自由格式数据

    如果数据是自由格式——变量由空格,逗号或制表符分隔,则可以使用infile命令。有关自由格式文件的示例,请参阅http://data.princeton.edu/wws509/datasets上提供的计划生育工作数据(请阅读说明并单击effort.raw)。这实质上是一个包含四列的文本文件,其中一列带有国家名称,另一列带有数字变量,由空格分隔。我们可以使用该命令将数据读入Stata

    infile str14 country setting effort change using http://data.princeton.edu/wws509/datasets/effort.raw
    

    infile命令后面跟着变量的名称。由于国家名称是一个字符串而不是数字变量,因此我们在名称前加上str14,它将变量的类型设置为最多14个字符的字符串。所有其他变量都是数字。

    using后面跟着文件的名称,该文件可以是计算机,本地网络或互联网上的文件。在这个例子中,我们直接从互联网上读取文件。更多信息help infile1
    还可以选择webuse命令读取该数据库:

    webuse set http://data.princeton.edu/wws509/datasets
    webuse effort
    

    首先将默认网址设置为普林斯顿数据库,然后直接用webuse命令读取相关文件。webuse 在stata小白系列中有更多介绍。
    可用list查看所读入数据:

     list in 1/3
    
         ┌─────────────────────────────────────┐
         │ country   setting   effort   change │
         ├─────────────────────────────────────┤
      1. │ Bolivia        46        0        1 │
      2. │  Brazil        74        0       10 │
      3. │   Chile        89       16       29 │
         └─────────────────────────────────────┘
    

    1.1.2 固定格式数据

    调查数据通常采用固定格式,每个案例有一个或多个记录,每个记录中的每个变量都处于固定位置。

    读取固定格式数据的最简单方法是使用该infix命令指定每个变量所在的列。正如它发生的那样,努力数据整齐排列在列中,所以我们可以阅读它们如下:

    infix str country 4-17 setting 23-24 effort 31-32 change 40-41 using 
         http://data.princeton.edu/wws509/datasets/effort.raw, clear
    

    这表示country要从第4-17列读取名称, setting从第23-24 列读取名称。str指定该country是一个字符串变量,但不必指定宽度,因为宽度从列数限定中可以看出。

    如果有大量的变量,应该考虑在一个单独的文件上输入名字和位置,这个文件又被称为字典,然后可以用infix命令中调用字典。下面尝试将以下字典内容输入到名为effort.dct的文件中:

    infix dictionary using http://data.princeton.edu/wws509/datasets/effort.raw {
      str country  4-17
          setting 23-24
          effort  31-32
          change  40-41
    }
    

    字典只接受*注释,但必须出现在第一行之后。保存此文件后,可以使用以下命令读取数据:

    infix using effort.dct, clear
    

    请注意,您现在“使用”字典,它反过来“使用”数据文件。您可以使用表单指定它作为infix命令的选项,而不是在字典中指定数据文件的名称。infix using dictionaryfile, using(datafile).第一个’using’指定字典,第二个’using’是指定数据文件的选项。如果要使用一个字典来读取以相同格式存储的多个数据文件,这一点尤其有用。更多信息,请参阅help infix。如果您的观测值跨越多个记录或线条,infix只要所有观测记录的记录数量相同(不一定全部相同),仍然可以使用它们来读取它们。欲了解更多信息,请参阅help infix。

    infile命令也可以用于固定格式的数据和字典。这是一个非常强大的命令,它提供了许多不适用的选项infix; 例如它可以让你在字典中定义变量标签,但是语法有点复杂。看help infile2

    1.2 数据文档

    在将数据读入Stata之后,准备一些文档很重要。在本节中,我们将看到如何创建数据集,变量和值标签,以及如何为数据或变量创建注释。

    1.2.1 数据标签与注释

    Stata允许您使用label data命令标记您的数据集,然后标记最多80个字符(Stata SE中为244)。您还可以使用notes命令,然后使用冒号和文本添加最多约64K字符的注释:

    label data "Family Planning Effort Data"
    . notes:  Source P.W. Mauldin and B. Berelson (1978). 
       Conditions of fertility decline in developing countries, 1965-75. 
       Studies in Family Planning, 9:89-147
    

    数据用户可以键入notes以查看您的注释。仔细记录您的数据总是会带来回报。

    1.2.2 变量标签和注释

    您可以(也应该)使用label variable 命令来标记变量。命令后跟变量名称和标签(引号包围,最多80k字符)。使用infile命令,您可以将这些标签添加到字典中。否则,你应该准备一个带有所有标签的do文件。以下是如何为我们的数据集中的三个变量定义标签:

    label variable setting "Social Setting"
    label variable effort  "Family Planning Effort"
    label variable change  "Fertility Change"
    

    Stata还允许您使用该命令将注释添加到特定变量notes varname: text。请注意,该命令后面跟着一个变量名,然后是一个冒号:

    . notes change: Percent decline in the crude birth rate (CBR) 
      the number of births per thousand population between 1965 and 1975.
    

    键入describe,然后notes检查我们到目前为止的工作。

    1.2.3 值标签

    您还可以标记分类变量的值。我们的数据集没有任何分类变量,但我们创建一个。我们将复制effort变量,然后将其分为三类,0-4,5-14和15+,它们分别代表弱,中等和强壮三个程度(前两行中使用的generaterecode在下一节介绍,我们还展示了如何用一个命令完成所有这些步骤):

     generate effortg = effort 
     recode effortg 0/4=1 5/14=2 15/max=3
     (effortg: 20 changes made)
     label define effortg 1 "Weak" 2 "Moderate" 3 "Strong", replace
     label values effortg effortg
     label variable effortg "Family Planning Effort (Grouped)"
    

    Stata采用两步法来定义标签。首先定义一个标签集,使用label define命令将整数代码与标签(最多80k)相关联。然后,使用label values命令将该组标签与变量相关联。通常,标签集和变量使用相同的名称,就像我们在示例中所做的那样。

    这种方法的一个优点是可以为多个变量使用同一组标签。规范的例子是label define yesno 1 “yes” 0 “no”,它可以与数据集中的所有0-1变量相关联,使用每个变量的形式命令label values variablename yesno。定义标签时,如果标签是单个单词,则可以省略引号,但为了清晰起见,我更愿意使用它们。

    可以使用add或者modify选项修改标签集,使用label dir(仅列出名称)或label list(列出名称和标签)列出标签集,并使用label save将它们保存到一个do文件。输入help label以了解更多信息。您也可以使用不同语言的标签,如下所述。

    1.2.4 多语言标签

    一个Stata文件可以用多种语言存储标签,并且您可以从一组到另一组自由移动。我将通过为我们的数据集创建西班牙语标签来说明。遵循Stata建议,我们将使用ISO标准的双字母语言代码,en代表英文,es代表西班牙语。

    首先我们使用label language用来重命名当前语言为en,并创建一个新的语言集es

     label language en, rename
    (language default renamed en)
     label language es, new
    (language es now current language)
    

    西班牙语标签定义不会覆盖相应的英文标签,而是并行存在。值标签命名时需小心些,不能直接将标签集取名effortg.因为effortg仅表示变量和标签之间的关联。你需要定义一个新的标签集; 我们在此取名ffortg_es,结合旧名称和新语言代码,然后将其与变量effortg相关联:

    label define effortg_es 1 "Débil" 2 "Moderado" 3 "Fuerte"
    label values effortg effortg_es
    

    您可能想要尝试命令describe现在。可以尝试用表格输出:

    table effortg
    

    接下来,我们将语言改回英文并再次运行表格:

    label language en
    table effortg
    

    更多信息,请键入 help label_language.

    1.3 创建新变量

    Stata创建新变量最重要的命令是generate/replacerecode,他们经常一起使用。

    1.3.1 生成和替换

    generate命令使用可以结合常量,变量,函数,算术和逻辑运算符的表达式创建新变量.

    gen settingsq = setting^2.
    

    如果你打算在回归中使用这个项,而且知道线性和二次项是高度相关的。那么在平方之前将变量中心化可能是个好主意。这里我们运行summarize,并使用quietly来抑制输出,从存储结果中检索均值r(mean):

    quietly summarize setting
    gen settingcsq = (setting - r(mean))^2
    

    请注意,我为此变量使用了不同的名称。Stata不会让你用generate来覆盖现有的变量。如果你真的想替换旧变量的值使用replace。您也可以使用drop var_names从数据集中删除一个或多个变量。

    1.3.2 运算符,表达式及函数

    下表显示了您可以在表达式中使用的标准算术,逻辑和关系运算符:

    运算符及表达式

    Stata有大量的函数,这里有一些常用的数学函数,输入help mathfun可以查看完整列表:

    函数

    当参数是数据集中的变量时,这些函数会自动应用于所有观察值。

    Stata还具有生成随机数的功能(在模拟中很有用),即uniform()。它还有一套广泛的函数来计算概率分布(p值所需的)和它们的反函数(临界值所需的),请参阅help density functions以获取更多信息。
    还有一些专门的函数用于处理字符串,请参阅help string functions,处理日期函数,请参阅help date functions

    1.4 变量重编码

    recode命令作用是将数字变量转化为类别变量。例如,假设一项生育率调查中对年龄在15岁至49岁的女性进行单身年龄分析.您想以5年为一个区间对样本分组。可以使用命令:

    gen age5 = int((age-15)/5)+1 if !missing(age)
    

    但这只适用于间隔规则的情况。也可以其实用如下方法:

    recode age (15/19=1) (20/24=2) (25/29=3) (30/34=4)
               (35/39=5) (40/44=6) (45/49=7), gen(age5)
    

    括号中的每个表达式都是一个重新编码规则,由值的列表或范围组成,后跟等号和新值。使用斜线指定的范围包括两个边界,因此15/19是15到19,其也可以被指定为15 16 17 18 19或甚至15 16 17/19。您可以使用min参考最小值并max参考最大值,如在min/19和中44/max。当规则的形式为range = value时,括号可以省略,但它们通常有助于使命令更具可读性。

    值被分配到它们落在的第一个类别。从未分配给某个类别的值将保持原样。您可以使用else(或*)作为最后一个子句来引用尚未分配的任何值。或者,您可以使用missingnonmissing引用未分配的缺失值和非缺失值; 这些必须是最后两个语句,不能与其他语句相结合。

    在我们的例子中,我们还使用了gen()选项生成一个新的变量age5,在这种情况下,新变量默认替换现有变量的值。我强烈建议您在重新编码之前制作原始变量副本。
    您也可以在重编码时指定值标签。选项label(label_name)允许您为创建的标签分配一个名称(默认与变量名称相同)。下面是一个示例,显示如何在一步进行重编码和做值标签。(上文中需使用四个命令)。

    recode effort (0/4=1 Weak) (5/14=2 Moderate) (15/max=3 Strong)
         , generate(efffortg) label(effortg)
    

    对原始和重新编码的变量进行交叉制表以检查转换是否按预期工作通常是一个好主意。

    关于我们

    • 「Stata 连享会」 由中山大学连玉君老师团队创办,定期分享实证分析经验, 公众号:StataChina
    • 公众号推文同步发布于 CSDN简书知乎Stata专栏。可在百度中搜索关键词 「Stata连享会」查看往期推文。
    • 点击推文底部【阅读原文】可以查看推文中的链接并下载相关资料。
    • 欢迎赐稿: 欢迎赐稿。录用稿件达 三篇 以上,即可 免费 获得一期 Stata 现场培训资格。
    • E-mail: StataChina@163.com
    • 往期推文:计量专题 || 精品课程 || 简书推文 || 公众号合集

    点击此处-查看完整推文列表

    连享会计量方法专题……


    欢迎加入Stata连享会(公众号: StataChina)

    原文

    原文链接:Princeton Stata 在线课程 (Princeton University - Stata Tutorial )

    展开全文
  • Python数据处理

    千次阅读 2019-05-27 19:13:25
    作者通过循序渐进的练习,详细介绍如何有效地获取、清洗、分析与呈现数据,如何将数据处理过程自动化,如何安排文件编辑与清洗任务,如何处理更大的数据集,以及如何利用获取的数据来创作引人入胜的故事。...
  • 视音频数据处理入门:RGB、YUV像素数据处理

    万次阅读 多人点赞 2016-01-29 17:01:12
    有段时间没有写博客了,这两天写起博客来竟然感觉有些兴奋,仿佛找回了原来的感觉。前一阵子在梳理以前文章的时候,发现自己虽然总结了各种视音频应用程序,却还缺少一个适合无视音频背景人员学习的“最基础”的程序...
  • Spark快速大数据处理

    万人学习 2019-04-24 19:32:53
    5.Spark2实时大数据处理 6.Oozie5-大数据流程引擎 课程特点: 1.最新API: Hadoop3/Spark2/Hive3/Oozie5 2.手工搭建集群环境:编译+搭建 3.配套资源:分阶段镜像+课件+安装资源,其中安装...
  • Python使用Pandas对csv文件进行数据处理

    万次阅读 多人点赞 2018-04-13 18:43:22
    今天接到一个新的任务,要对一个140多M的csv文件进行数据处理,总共有170多万行,尝试了导入本地的MySQL数据库进行查询,结果用Navicat导入直接卡死....估计是XAMPP套装里面全默认配置的MySQL性能不给力,又尝试用R搞一下...
  • 视音频数据处理入门:PCM音频采样数据处理

    万次阅读 多人点赞 2016-01-29 23:32:13
    本文分别介绍如下几个PCM音频采样数据处理函数:  分离PCM16LE双声道音频采样数据的左声道和右声道  将PCM16LE双声道音频采样数据中左声道的音量降一半  将PCM16LE双声道音频采样数据的声音速度提高一倍  将PCM1
  • Tableau Prep 数据处理工具使用入门

    万次阅读 2018-04-28 14:08:26
    1. 什么是Tableau Prep 2018.04, Tableau 推出全新的数据...简而言之,Prep是一款简单易用的数据处理工具(部分ETL工作)。之所以使用Tableau Prep, 是因为我们在使用BI工具进行数据可视化展示时,常常数据不具有...
  • 海量数据处理面试题集锦

    万次阅读 多人点赞 2011-08-14 14:07:13
    十七道海量数据处理面试题与Bit-map详解作者:小桥流水,redfox66,July。前言 本博客内曾经整理过有关海量数据处理的10道面试题(十道海量数据处理面试题与十个方法大总结),此次除了重复了之前的10道面试题之后...
  • python .txt文件读取及数据处理总结

    万次阅读 多人点赞 2017-11-30 18:27:32
    1、处理包含数据的文件最近利用Python读取txt文件时遇到了一个小问题,就是在计算两个np.narray()类型的数组时,出现了以下错误: TypeError: ufunc 'subtract' did not contain a loop with signature matching ...
  • 【spark论文翻译】An Architecture for Fast and General Data Processing on Large Cluster 大型集群上的快速和通用数据处理架构。CSDN CODE翻译社区出品。 之前上传的版本图表有问题,这版已经修复。请更新谢谢。
  • MODIS NDVI数据处理相关问题

    万次阅读 多人点赞 2014-05-03 23:39:28
    现NDVI产品数据处理过程中遇到以下问题: 问题1: NDVI是归一化植被指数,它的取值范围是-1—1,如何理解? 方法 : 对于陆地表面覆盖来说,云、雨、雪在可见光比近红外波段有较高的反射作用,所以NDVI为负值...
  • 数据处理之标准化/归一化方法

    万次阅读 2016-07-10 16:48:44
    数据处理之标准化/归一化方法归一化方法(Normalization Method)1.把数变为(0,1)之间的小数 主要是为了数据处理方便提出来的,把数据映射到0~1范围之内处理,更加便捷快速,应该归到数字信号处理范畴之内。2.把...
  • 点云数据处理方法

    万次阅读 多人点赞 2018-09-07 10:25:02
    这篇博客主要介绍三维计算机视觉中点云数据处理面对的问题,主要方法和技术,概述其特点。这篇博客主要介绍最基本的点云数据处理技术和概念,不会有任何代码。 ICP点云配准就是我们非常熟悉的点云处理算法之一。...
  • 海量数据处理技巧

    万次阅读 2018-08-02 20:07:18
    数据时代来临,数据量的爆炸式增长是最为显著的特征。当高性能硬件的普及还跟不上这样的数据大潮时,如何在有限的时空资源...需要明确的一点是,现实情况复杂多变,所以对于海量数据处理这样大的主题,是不可能用一...
  • 这一系列博文将介绍一下机器学习中的数据预处理问题,以UCI数据集为例详细介绍缺失值处理、连续特征离散化,特征归一化及离散特征的编码等问题,同时会附上处理的Matlab程序代码,这篇博文先介绍缺失值的处理,要点...
  • 谈谈MATLAB大数据处理

    万次阅读 2016-02-23 16:19:51
    摘要: 今天多数的大数据方案都是依托Hadoop环境来做结构化和非结构化数据处理,如何把自己的Hadoop算法快速部署到实际的生产环境当中去,对很多企业的大数据部署也提出了挑战。CSDN专访MathWorks中国资深技术专家...
  • 十道海量数据处理面试题与十个方法大总结

    万次阅读 多人点赞 2011-03-26 10:16:00
    海量数据处理:十道面试题与十个海量数据处理方法总结作者:July、youwang、yanxionglu。时间:二零一一年三月二十六日本文之总结:教你如何迅速秒杀掉:99%的海量数据处理面试题。有任何问题,欢迎随时交流、指正。...
  • 数据处理流程

    万次阅读 2019-02-21 16:53:13
    数据处理流程 1. 数据处理流程 网站流量日志数据分析是一个纯粹的数据分析项目,其整体流程基本上就是依据数据的处理流程进行。有以下几个大的步骤: 1.1 数据采集 &nbsp;&nbsp;&nbsp;&nbsp;&...
  • 【学习笔记】python实现excel数据处理

    万次阅读 多人点赞 2019-02-27 20:03:44
    Excel固然功能强大,也有许多函数实现数据处理功能,但是Excel仍需大量人工操作,虽然能嵌入VB脚本宏,但也容易染上宏病毒。python作为解释性语言,在数据处理方面拥有强大的函数库以及第三方库,excel作为主要基础...
  • 废话不多扯,就是在其他浏览器中调用接口返回数据然后可以很顺利的进行处理,但在IE(9-11)中发现发送请求是成功的而且也能抓到服务端返回来的数据。却发现在处理返回来的数据的时候处理的有点问题,怎么搞就是不行...
  • 缺失数据处理-插值法

    万次阅读 2017-06-01 14:48:59
    数据挖掘中,原始海量的数据中存在着大量不...因此数据预处理工作必不可少,而其中常见工作的就是数据集的缺失值处理数据缺失值处理可分两类。一类是删除缺失数据,一类是进行数据插补。本文是对数据插补的介绍。
  • excel数据处理

    千次阅读 2019-01-12 21:08:25
    excel大部分常用操作
  • 数据处理——One-Hot Encoding

    万次阅读 多人点赞 2015-03-03 16:54:06
    一、One-Hot Encoding  One-Hot编码,又称为一位有效编码,主要是采用位状态寄存器来对个状态进行编码,每个状态都由他独立的寄存器位,并且在任意时候只有一位有效。  在实际的机器学习的应用任务中,特征有...
  • 处理这种海量数据的方法无非就是分治和”人海”战术。使用人海战术的前提是问题的划分能够支持这种人海战术,其手段无非是切割(纵向,横向)和负载均衡。纵向分隔主要是按业务(功能)来分,也就是所谓面向服务...
  • NetCDF数据处理

    千次阅读 2017-08-19 09:51:37
    1.NetCDF数据下载  NECP/NCAR再分析数据库,ICOADS数据库,包括气温、降雨、湿度、下行辐射、上行辐射等; 分辨率0.06°、0.25°、1.0°、2.5°等。  https://www.esrl.noaa.gov/psd/data/gridded/ 2.NetCDF数据...

空空如也

1 2 3 4 5 ... 20
收藏数 559,673
精华内容 223,869
热门标签
关键字:

数据处理