三七大数据平台关键技术解决专项方案V.doc

三七数据大数据技术处理方案北京三七数据技术7月31日目 录1概述62面临挑战62.1数据采集102.2数据清洗102.3数据存放122.4数据并行处理122.5数据分析122.6可视化122.7传统处理方案分析123相关技术研究123.1参考模型框架123.2数据采集123.2.1结构化数据采集123.2.2半结构化数据采集123.2.3非结构化文本数据中信息抽取153.3数据清洗和数据质量确保153.3.1数据质量概念及分类153.3.2数据清洗原理183.3.3单数据源中数据清洗203.4数据集成和融合373.4.1多数据源集成问题分类383.4.2数据标准化研究403.4.3数据集成步骤413.4.4多数据源中反复实体清理413.4.5数据不一致性问题研究433.5数据存放和处理433.5.1并行和分布式处理理论433.5.2并行RDBMS473.5.3Hadoop493.5.4Hadoop扩展和优化533.5.5NoSQL583.5.6查询优化1103.6大数据中数据挖掘1123.6.1传统数据挖掘概述1123.6.2大数据时代数据挖掘发展新趋势1203.6.3WEB数据挖掘1243.6.4超数据集成挖掘方法和技术研究1533.6.5数据挖掘网格技术1863.7大规模机器学习2083.7.1机器学习概述2093.7.2扩展机器学习必需性2113.7.3面临挑战2133.7.4概率图模型2143.7.5集成学习2153.8可视化和可视化分析2253.8.1概述2253.8.2可视化技术2253.8.3可视化分析2273.8.4文本可视化分析2283.8.5网络可视化分析2303.8.6移动轨迹数据可视化分析2303.8.7交互式可视化分析2303.9数据溯源技术研究2303.9.1概述2313.9.2模式级数据溯源2323.9.3实例级数据溯源2323.9.4数据溯源应用分类2333.9.5未来研究方向2343.10同时技术研究2353.10.1概述2353.10.2通信程序2353.10.3数据库复制技术2393.10.4ETL技术2423.10.5事务处理2443.10.6XML技术2463.11数据共享技术2483.12安全技术研究2493.12.1安全风险分析2493.12.2安全技术需求2503.12.3身份认证和密匙协商2513.12.4访问控制技术2513.12.5入侵检测技术2523.13隐私保护技术研究2533.13.1概述2533.13.2隐私保护技术手段2543.13.3匿名技术研究2564总体技术处理方案2584.1总体描述2584.2功效框架2584.3技术架构2584.3.1数据采集层2584.3.2数据管理层2584.3.3数据分析层2584.3.4数据展示层2584.3.5数据应用层2584.4和传统数据处理方案对比2585实施方案设计和提议2581 概述（关键是描述大数据定义，大数据特点，大数据起源，大数据行业趋势，大数据应用。能够把行业研究汇报总结放在这里）2 面临挑战大数据分析面临巨大挑战，以下我们从5方面来讨论：l 异构性和非完整性当用户使用信息时，能够容忍大量异构性。实际上，自然语言丰富性和微妙能够提供有价值深度。然而，机器分析通常期望是同构数据，无法了解自然语言微妙之处。所以，经过机器进行数据分析第一步就是必需仔细地定义数据结构。很多数据分析系统全部要求好数据结构。少部分结构化设计对于部分目标可能愈加有效，不过计算机系统有效性则有赖于多个数据大小和结构一致性。半结构化数据有效表示，访问和分析需要愈加深入工作。即便是在数据清洗和错误纠正以后，数据还可能是不完整和错误。在数据分析得过程中应该有效地管理这种不完整性和这些错误。这是一个很大挑战。近期相关概率数据或不确定数据管理可能能够在这方面取得部分进展。l 数据大小任何人对大数据第一个想法就是它大小。多年来，对大数据而且快速增加数据管理一直是很含有挑战问题。在过去，这些挑战全部是经过愈加快处理器来应正确。不过现在我们面临一个基础事实是，数据量增加速度超出了CPU速率增加速度。首先，在过去5年，处理器技术已经有了巨大转变，依据摩尔定理处理器主频每18个月就会翻倍，现在因为功率和散热限制，单个处理器主频基础上停滞不前了，业界全部在经过多核技术来生产处理器。在过去，大型数据处理系统需要避免在计算机群中跨节点并行机制；现在，则需要处理在一个节点内并行机制。不幸是，过去应用于跨节点数据处理并行数据处理技术并不能直接用于节点内并行处理，因为架构看上去很不一样。比如，在单个节点中多核之间通常会共享Caches和内存通道。另外，在未来出于规律考虑，我们可能不会连续使用系统中硬件，数据处理系统可能需要主动第管理处理器功耗。这些改变要求我们重新思索怎样设计，搭建和运行数据处理组件。第二个巨大转变是向云计算迁移，云计算将多个分离计算任务汇聚到很大计算机群中，每个计算任务含有不一样性能目标。在大计算机群中资源共享要求新方法来决定怎样运行和实施数据处理工作，方便我们能够经济有效地满足每个计算任务目标；还要求我们能够应对系统失效，这在越来越计算机群中发生得愈加频繁。在这种情况下，说明式编程方案愈加有效，甚至是那些在做复杂机器学习任务程序，因为为了取得好整体性能，跨多个用户程序全局优化是是十分必需。依靠用户驱动程序优化有可能造成较差群整体性能。系统驱动整体优化要求程序是足够透明，比如在关系型数据库中，说明式查询语言就是这么设计。第三个转变是传统I/O子系统发生了巨大改变。多年来，永久性数据关键是存在硬盘上。硬盘随机访问I/O性能比次序I/O性能要慢很多，通常数据处理引擎经过格式化数据，和查询处理方法设计来克服这些限制。现在，硬盘正在逐步被固态驱动器替换，其它技术如相变内存正在出现。这些新型存放技术在随机访问I/O性能比次序I/O性能之间不存在那么大差异，这就要求我们重新思索数据处理系统中存放子系统设计。存放子系统这种改变影响基础上触及数据处理每个方面，包含查询处理算法，查询排队算法，数据库设计，并发性控制方法和恢复方法。l 立即性数据大小另一面是速度。需要处理数据集越大，分析所需要时间就越长。设计系统假如能够有效地处理大数据，那么这么系统就能够快速地处理一个给定大小数据集。不过，这里处理速度不完全是谈到大数据时通常所谈到速度，在大数据中还需要应对数据获取速度挑战。现实中有很多情况需要立即得到分析得结果。比如，假如怀疑一个欺诈性信用卡交易，在交易完成之前我们就应该标识出这么交易，这么能够从根本上预防欺诈性交易发生。很显然，对一个用户消费历史进行全方面实时分析是不太可行。我们需要预先取得部分结果，方便我们能够经过在新数据上少许渐进式计算就能够快速地做决定。给定一个大数据集，通常需要找到满足一个特定准则那些数据。在数据分析得过程中，这种类型搜索有可能反复地发生。为了找到适合数据，每次对整个数据集进行搜索显然是不现实。我们需要实现建立索引结构来快速找到符合要求数据。这里问题是，因为每个索引结构是根据部分类型准则来设计。当需要使用大数据时，有可能定义新型准则，这时就需要设计新索引结构来支持新准则。比如，考虑一个流量管理系统，l 数据隐私性数据隐私性是另外一个关键问题，尤其是在大数据中显得愈加关键。对于电子医疗统计，有严格法律要求能够做什么，不能够做什么。对于其它数据，就没有那么硬性要求，尤其是在美国。然而，公众还是很担心个人数据不正当使用，尤其是经过链接多个数据源数据。对隐私性管理既是技术上问题，也是社会学问题，需要从这两个领域去寻求处理方案。比如，我们考虑从基于位置服务中搜集到数据。这些新架构要求用户把她们位置信息共享给业务提供商，这是一个很显著隐私性问题。假如只是隐藏用户身份信息，而没有隐藏她位置信息，这并不是一个好处理方案。因为能够从位置信息推理出被查询者身份信息。比如，我们能够经过多个静态连接点（如基站）跟踪用户位置信息。一段时间后，用户就会留下部分踪迹，这些踪迹能够和特定住所和办公地点相关联，从而能够确定用户身份。其它多个个人信息如相关个人健康（比如在癌症诊疗中心去过）或宗教偏好（比如去过教堂）等也能够经过观察匿名用户移动和使用模式推理取得。通常来说，研究结果表明在用户身份和她们移动模式之间存在很强相关性。将用户位置信息隐藏起来远比隐藏用户身份信息要困难得多。这是因为在基于位置服务中，为了成功数据访问和数据搜集，就需要用到用户位置信息，而用户身份信息就能够不需要。还有很多其它含有挑战性研究课题。比如，我们没有找到好数据共享方法，怎样在限制个人信息披露前提下，还确保在共享数据中有足够有用信息。现在相关差异化隐私研究是处理这个问题关键一步，不过这个研究删除掉信息太多了，在很多实际情况中无法用。另外，实际中数据不是静态，而是会伴随时间推移发生改变而且变得更大。还有一个关键方向是重新思索在大数据中信息共享安全性研究。今天很多在线业务全部要求我们共享个人信息，不过除了访问控制之外，对于其它方面如共享数据意味着什么，共享数据是怎样链接，和怎样让用户对数据共享能够进行更细颗粒控制等则一无所知。l 人力介入和协作尽管机器分析取得了很大进展，但还是存在人能够轻易检测出很多模式，计算机算法却极难做到。理想方案是，大数据分析并不完全是计算机算法，而是设计成明确地把人放到分析环路中。新可视化分析尝试根据这种原理去做，最少是在整个管道中建模和分析得步骤。实际上在整个管道全部步骤人力介入全部有类似价值。在今天复杂世界中，通常需要来自各个不一样领域多个教授去真正了解到底在发生什么。一个大数据分析系统应该支持来自多个教授输入，并共享分析结果。这些教授有可能在空间和时间上是分离，数据系统应该接收这种分布式教授输入，并支持多个教授之间协作。一个现在比较流行利用人聪慧才智来处理问题新方法众包方法。Wikipedia在线百科全书就是众包数据最著名例子，信息时由未经审查陌生人提供，通常她们提供信息时正确。不过，还是存在部分个人有其它动机和角色，有些人出于某种原因有意提供错误信息以误导她人。即使大部分这种错误会被其它人发觉而且纠正，我们需要技术来支撑。我们也需要一个框架来分析这些带有矛盾陈说众包数据。作为人，我们能够查看相关饭店评价，有些是正面，有些是负面，然后我们形成一个总结性评定，基于此评定我们能够决定是否去这个饭店试试。我们期望计算机能够做类似事情。在一个特定类型众包，即参与感测中不确定性和错误问题愈加显著。在这种情况下，每个持有手机人能够作为一个多模传感器，搜集多种类型数据，比图片，图像，声音，时间，速度，方向，加速度等数据。这里比较大挑战是数据搜集设备内在不确定性。搜集到数据在时间和空间上相关性能够用来愈加好地评定数据正确性。2.1 数据采集2.2 数据清洗伴随信息化建设不停深入，企机关积累了大量电子数据，这些数据很关键。为了使信息系统中数据更正确、一致，能支持正确决议，就要求所管理数据正确、可靠。所以，企业数据质量管理正在取得越来越多关注。不过，因为多种原因，如数据录入错误、不一样起源数据引发不一样表示方法、数据间不一致等，造成企业现有系统数据库中存在这么或那样脏数据，关键表现为：不正确字段值、反复统计、拼写问题、不正当值、空值、不一致值、缩写词不一样，不遵照引用完整性等。依据“进去是垃圾，出来也是垃圾（garbage in，garbage out）”这条原理，若不进行清理，这些脏数据会扭曲从数据中取得信息，影响信息系统运行效果，也为企业构建数据仓库、建立决议支持系统、应用商务智能带来隐患。显见，数据清理问题关键性是不言而喻。另外，从市场上众多相关产品，也能够明白这一点。然而，因为数据清理本身部分特点，比如：1)数据清理是具体应用问题，常常要具体问题具体分析，难于归纳出通用方法；2)数据清理问题数学建模困难。对于数据清理有很多内容值得研究，比如：3)在数据清理研究中，尽管检测相同反复统计受到最多关注，采取了很多方法，但检测效率和检测精度并不令人满意。尤其是在数据量很大时，耗时太多，有待于愈加好方法。在相同反复统计检测中采取长度过滤方法优化相同检测算法，避免了无须要编辑距离计算，从而提升了相同反复统计检测效率；4)在数据清理相关研究中，数据清理整体框架研究正逐步成为研究热点。对此，提出一个可扩展数据清理软件平台，该软件平台含有开放规则库和算法库，经过在规则库中定义清理规则和从算法库中选择适宜清理算法，可使该软件平台适适用于不一样数据源，从而使其含有较强通用性和适应性；5)现在，对数据清理研究关键集中在结构化数据上。因为半结构化数据 XML（Extensible Markup Language，可扩展标识语言）快速增加和广泛应用，其在数据清理中越来越关键。为了使 XML 数据源中数据更正确、一致，怎样清理这些 XML 相同反复数据，全部是值得研究；6)另外，相关数据清理在部分业务领域中应用也是值得研究。当然，对任何现实世界中数据源，人工完成数据清理是没有问题。部分单位每十二个月要花费上百万元来查找数据错误，手工清理是劳累、费时和易犯错。对于少许数据数据源来说，采取人工清理就能够了，但对于规模较大数据源，手工清理是不可行，必需借助信息技术，采取自动清理方法。当然，在自动清理过程中，仍需要人来参与，我们要做就是尽可能降低人参与。2.3 数据存放2.4 数据并行处理2.5 数据分析2.6 可视化2.7 传统处理方案分析3 相关技术研究3.1 参考模型框架3.2 数据采集3.2.1 结构化数据采集3.2.2 半结构化数据采集Internet上数据和传统数据库中数据不一样，传统数据库全部有一定数据模型，能够依据模型来具体描述特定数据，同时能够很好地定义和解释相关查询语言。而Internet上数据很复杂，没有特定模型描述，每一站点数据全部各自独立设计，而且数据本身含有自述性和动态可变性，其结构也不可琢磨，是一个我们称之为半结构化数据。所谓半结构化是相对于结构化(传统数据库)和非结构化(如一本书、一张图片等)而言。不过Internet上存在数据既不是完全结构化也不是完全非结构化，因为它页面也含有一定描述层次，存在一定结构，所以我们将它称为半结构化数据。假如想要利用Internet上数据进行数据挖掘，必需先要研究站点之间异构数据集成问题，只有将这些站点数据全部集成起来，提供给用户一个统一视图，才有可能从巨大数据资源中获取所需东西。其次，还要处理Web上数据查问询题，因为假如所需数据不能很有效地得到，对这些数据进行分析、集成、处理就无从谈起。针对Internet上数据半结构化特点，寻求一个半结构化数据模型则成为了处理上述问题关键所在。另外，除了要定义这么一个半结构化数据模型外，还需要一项技术能够自动地从现有数据中将这个模型抽取出来，这就是所谓模型抽取技术。所以半结构化数据模型及其抽取技术是面向Internet数据挖掘技术实施前提。l 半结构化数据定义半结构化数据有两层含义，一个是指在物理层上缺乏结构数据，另一个是指在逻辑层上缺乏结构数据。有部分结构化数据，为用于web页面显示而和html语言标识符号嵌在一起，组成了物理上半结构化数据。Internet中有大量丰富数据，这些数据多存在于html文件中，没有严格结构及类型定义，这些全部是逻辑层半结构化数据。Internet上数据和传统数据库中数据不一样，传统数据库全部有一定数据模型，能够依据模型来具体描述特定数据.而上数据很复杂，没有特定模型描述，每一站点数据全部各自独立设计，而且数据本身含有自述性和动态可变性.所以，Internet上数据含有一定结构性，但因自述层次存在，是一个非完全结构化数据，这也被称为半结构化数据。半结构化是上数据最大特点。半结构化数据关键起源有3方面:1、在WWW等对存放数据无严格模式限制情形下，常见有HTML、XML和SGML文件；2、在邮件、电子商务、检索和病历处理中，存在着大量结构和内容均不固定数据3、异构信息源集成情形下，因为信息源上互操作要存取信息源范围很广，包含各类数据库、知识库、电子图书馆和文件系统等。半结构化数据含有以下特点:1、隐含模式信息：即使含有一定结构，但结构和数据混合在一起，没有显式模式定义(HMTL文件是一个经典)。2、不规则结构：一个数据集合可能由异构元素组成，或用不一样类型数据表示相同信息。3、没有严格类型约束：因为没有一个预先定义模式，和数据在结构上不规则性，造成缺乏对数据严格约束。l 半结构化数据数据模型半结构化数据是缺乏严格、完整结构数据。这类数据并非毫无结构，但它们结构可能是隐含、不完整，甚至可能是需要不停修改。要对这么数据进行查询等处理，首要问题就是对半结构化数据进行描述。因为没有强制性模式限制，使半结构化数据含有很大灵活性，能够满足网络这种复杂分布式环境需要，但同时也给数据描述和处理带来了很大困难。l 半结构化数据表示具体地，象WWW这种数据模型可表示成3种关系： Obj(oid)，Ref(source，label，destination)，Val(oid，value) 其中Obj表示一个无限对象集合，比如WWW上网页，网页中内容全部可看成是对象。Ref(o1，label，o2)表示从源对象o1到目标对象o2间存在一个联络，这种联络语义信息用标识label表示。在我们实现中，这种联络不仅包含了网页间存在链接，而且当某个网页Pageobj包含多个含有相同意义对象o1，o2，on时，能够引入一个虚拟对象Vobj，这么，网页代表对象Pageobj作为源对象，虚拟对象Vobj作为其目标对象，而o1，o2，on又作为Vobj目标对象，而且Vobj和o1，o2，on联络全部有相同标识。如，在我校图书馆资源网页中，包含对象期刊网，而其具体题目等内容在另一个页面，这么对象中国期刊网和链接所指页面就是源和目标对象关系。关系Val（oid，value）提供了原子对象取值信息，比如能够将每一篇论文作为一个对象，它值为论文题目。3.2.3 非结构化文本数据中信息抽取3.3 数据清洗和数据质量确保3.3.1 数据质量概念及分类数据质量是一个相正确概念。在不一样时期，数据质量有着不一样定义和评定标准。20世纪80年代以来，国际上普遍认为，数据质量标准基础上是围绕着以提升数据正确性为出发点和标准。然而，伴随质量本身含义不停进行延伸，数据质量概念也由原来狭义转变为广义，其中，基于实际需要，融入了很多数据质量考察和评判标准，正确性不再是衡量数据质量惟一指标。上世纪90年代，美国麻省理工学院开展了全方面数据质量管理TDQM(Total Data Quality Management)活动，该活动借鉴了物理产品质量管理体系成功经验，提出了以信息生产系统生产数据产品为基础质量管理体系。该活动提出，应充足、客观、全方面地了解用户信息需求，将数据看作含有生命周期产品，并对此进行管理，要设置数据产品管理员来管理数据生产整个过程和结果。在数据生产过程中形成质量维度，如正确性(Accuracy)、完整性(Completeness)、一致性(Consistence)等，已经成为数据质量评定基础要求;另外，用户对数据满意程度也已成为衡量数据质量关键指标之一。现在，还未形成系统化数据质量评定指标，数据质量评定往往只零碎地针对系统中比较关键质量指标，如一致性问题、复杂性问题、完整性问题等来进行。在数据质量评定领域已经得到使用产品，如CRG完整度分析器 IA (Integrity Analyzer)，能够实现对数据完整性严格检验，这里完整性包含实体完整性、引用完整性、域完整性和用户自定义完整性。数据质量描述通常能够分为不一样层次，不过到现在为止，还没有形成专门用于表示这种层次性统一术语，比如，有用类和域表示这种层次，而 ISO TC211则用数据质量元素及子元素来表示。不一样应用领域对数据质量描述也是不一样，所以，建立反应应用领域特点数据质量框架，是数据质量评定所要处理首要问题。数据质量评定是面向应用，一样数据在不一样应用背景下接收度是不一样，比如对于数据挖掘，一样数据在一个挖掘专题下表现良好，而在另一个挖掘专题下却得不到有意义结果。所以，需求分析实际上是维度选择过程，数据质量评定从一个或多个维度出发，以动态或静态方法审阅数据。所谓动态评定方法，是指从数据产生机制上对数据质量进行评定，而静态方法只考虑数据本身。即使动态评定方法能够更根本全方面地对数据质量做出评价，但在很多应用背景下，如数据挖掘，往往受条件限制，无法得悉数据产生机制信息。面向数据挖掘数据质量评定DM-QDA(Data Mining Oriented Data Quality Assessment)是含有实际意义，因为数据挖掘常常是一个庞大工程，需要投入较多时间、人力和物力，所以在数据挖掘工程真正开始之前，对数据挖掘可行性分析显得尤为关键，而为数据挖掘可行性提供指导正是数据质量评定意义所在。数据质量定义为数据一致性（consistency）、正确性（correctness）、完整性（completeness）和最小性（minimality）这 4 个指标在信息系统中得到满足程度，把“适合使用”作为衡量数据质量初步标准。通常说来，评价数据质量最关键多个指标是：1)正确性（Accuracy）：正确性是指数据源中实际数据值和假定正确数据值一致程度；2)完整性（Completeness）完整性是指数据源中需要数值字段中无值缺失程度；3)一致性（Consistency）一致性是指数据源中数据对一组约束满足程度；4)唯一性（Uniqueness）唯一性是指数据源中统计和编码是否唯一；5)适时性（Timeliness）适时性是指在所要求或指定时间提供一个或多个数据项程度；6)有效性（Validity）有效性是指维护数据足够严格以满足分类准则接收要求。当建立一个信息系统时候，即使进行了良好设计和计划，也不能确保在全部情况下，信息系统中数据质量全部能满足用户要求。用户录入错误、企业合并和企业环境伴随时间推移而改变，这些全部会影响所存放数据质量。信息系统中可能存在数据质量问题有很多个，总结起来关键有以下多个：1)反复统计反复统计是指在一个数据源中有指现实世界同一个实体反复信息，或在多个数据源中有指现实世界同一个实体反复信息。2)不完整数据因为录入错误等原因，字段值或统计未被记入数据库，造成信息系统数据源中应该有字段或统计缺失。3)不正确数据因为录入错误，数据源中数据未立即更新，或不正确计算等，造成数据源中数据过时，或部分数据和现实实体中字段值不相符。4)无法了解数据值无法了解数据值是指因为一些原因，造成数据源中部分数据难以解释或无法解释，如伪值、多用途域、古怪格式、密码数据等。5)不一致数据数据不一致包含了多个问题，比如，由不一样数据源来数据很轻易发生不一致；同一数据源数据也会因位置、单位以立即间不一样产生不一致。在以上这些问题中，前三种问题在数据源中出现最多。依据数据质量问题产生原因，数据质量问题可分成单数据源问题和多数据源问题两个方面3.3.2 数据清洗原理经过以上对数据质量问题分析，能够看出：数据质量问题是信息化建设中一个关键问题，为了提升信息系统数据质量，研究数据清理很关键。数据清理（data cleaning）也称数据清洗。数据清理三个关键领域包含：数据仓库（Data Warehouse，DW）、数据库中知识发觉（Knowledge Discovery in Databases，KDD）和综合数据质量管理（Total Data Quality Management，TDQM）。数据清理在不一样应用领域其要求不完全相同，如在数据仓库环境下，数据清理是 ETL（Extraction抽取、Transition 转换、Load 加载，ETL）过程一个关键部分，要考虑数据仓库集成性和面向专题需要，包含数据清理及结构转换；在 KDD 中，数据清理关键是提升数据可利用性，如去除噪声、无关数据、空值，考虑时间次序和数据改变等，但关键内容还是一样。现在，对于数据清理没有统一定义。我们认为数据清理是一个消除数据中错误和不一致，处理对象识别问题过程，把数据清理定义为反复统计合并/清理问题。通常来说，从广义上讲，数据清理是将数据库精简以除去反复统计，并使剩下部分转换成标准可接收格式过程；而狭义上数据清理是特指在构建数据仓库和实现数据挖掘前对数据源进行处理，使数据实现正确性、完整性、一致性、唯一性、适时性、有效性以适应后续操作过程。通常说来，数据清理包含以下多个步骤：1)数据分析数据分析是指从数据中发觉控制数据通常规则，比如字段域、业务规则等。经过对数据分析，可定义出数据清理规则，并选择适宜清理算法。2)数据检测数据检测是指依据预定义清理规则及相关数据清理算法，检测数据是否正确，比如是否满足字段域、业务规则等，或检测统计是否是反复统计。3)数据修正数据修正是指手工或自动地修正检测到错误数据或处理反复统计。对于数据清理应该满足：数据清理应该能检测和消除全部关键错误和不一致，包含单数据源和多数据源集成时；数据清理方法能被这么工具支持，人工检测和编程工作要尽可能少，并含有可扩展性。3.3.3 单数据源中数据清洗1.2.3.3.13.23.33.3.13.3.23.3.3l 单数据源中相同反复统计清理因为数据输入错误、不标准缩写词，或其它原因，数据库中可能包含相关现实世界同一实体反复统计。即使关系数据库系统不许可含有反复主键值统计输入，不过因为数据输入错误，不管主键值是否被这些错误影响，关系数据库不能再确保不存在反复统计。所以，在数据清理中，相同反复统计检测和清除是一个关键问题。数据源中反复统计可分成完全反复统计和相同反复统计。完全反复统计是指在数据表中除了主键外，其它各字段完全相同统计，或是在那些设计差数据库中，没有主键，全部字段完全相同统计。相同反复统计是指那些客观上表示现实世界同一实体，不过因为在格式、拼写上有些差异而造成数据库系统不能正确识别统计。通常情况下，对多个统计可能指同一现实世界实体这种情况较感爱好，而不是在语句组成上相同统计。为了降低数据源中冗余信息，反复统计清理是一项关键任务。 要想清理数据源中相同反复统计，必需要先经过某种方法检测出相同反复统计，然后采取一定策略清除这些反复统计，从而达成清理目标。在相同反复统计检测方面已经有了部分结果。在一个数据表中，完全反复统计标准检测方法是先将数据库中统计排序，然后，经过比较邻近统计是否相等来检测完全反复统计。完全反复统计不管以统计哪一个部分进行分类，在分类排序后，全部能确保相互相邻。这种方法可被扩展后用来检测相同反复统计，研究人员在此基础上提出了很多方法，比如，将整条统计作为一个字符串进行排序，经过计算整个字符串编辑距离来检测统计是否相同； Sorted-Neiberhood 方法以用户定义健作为排序键进行排序，然后，经过一组规则定义相等理论判定统计是否相同，其基础思想可描述以下：根据用户定义排序键对整个数据表进行排序，将可能匹配统计排列在一起。当然，根据某个排序键排一次序往往是不够，需要根据不一样排序键对数据数次排序，再将结果结合起来。具体说来，Sorted-Neiberhood 算法分为三步：1、创建排序键：抽取统计中关键字段或字段一部分组成每条统计排序键，排序键选择对于检测结果正确性至关关键。2、统计排序：用第一步生成排序键对统计排序。3、合并：定义一个固定大小窗口，在统计列表上移动，比较窗口内统计是否相同。Sorted-Neiberhood 算法时间复杂度和定义窗口大小相关，窗口大小为 2时，复杂度为 O ( NlogN)，窗口大小为 N 时，复杂度为O (N2)。在现在常见相同反复统计清理方法中，Sorted-Neiberhood 算法是较为流行匹配和合并算法，而且该算法已被应用到多个相关数据清理软件之中。先计算各统计 N-Gram 值，然后以各统计 N-Gram 值为排序键进行排序，再经过采取一个高效应用无关 Pair-wise 比较算法，经过计算两统计中单词间编辑距离来判定统计相同是否，并采取一个改善优先队列算法来正确地聚类相同反复统计,该算法使用固定大小优先队列次序扫描已排序统计,经过比较目前统计和队列中统计距离来聚类相同反复统计；提出一个检测多语言数据反复统计综合方法。上述这些方法基础思想能够总结为：先对数据表中统计排序，然后用某种方法检测相邻统计是否为反复统计，不一样之处是所采取排序方法和相同检测方法不一样。本章在对这些方法研究基础上，吸收这些方法思想，来处理相同反复统计清理问题，并对算法关键步骤进行改善，提升了相同反复统计检测效率和检测精度。相同反复统计清理方法相同反复统计清理方法总体描述相同反复统计清理过程可总结为：统计排序统计相同检测相同反复统计合并/清除。其清理过程可描述以下：首先，把数据源中需要清理数据经过 JDBC（Java DataBase Connectivity,Java 数据库连接）接口调入到系统中来；然后，实施数据清理，统计排序模块从算法库中调用排序算法，实施统计之间排序；在统计已排序基础上，统计相同检测模块从算法库中调用相同检测算法，作邻近范围内统计间相同检测，从而计算出统计间相同度，并依据预定义反复识别规则，来判定是否为相同反复统计。为了能检测到更多反复统计，一次排序不够，要采取多轮排序，多轮比较，每次排序采取不一样键，然后把检测到全部反复统计聚类到一起，从而完成反复统计检测；最终，对所检测出每一组相同反复统计依据预定义合并/清除规则，完成相同反复统计合并处理。统计排序为了能查找到数据源中全部反复统计，必需比较每一个可能统计对，如此以来，检测相同反复统计是一个很昂贵操作，当数据源中数据量很大时，这会造成是一个无效和不可行方案。为了降低统计之间比较次数，提升检测效率，常见方法是仅比较相互距离在一定范围统计，即先对数据表中统计排序，然后对邻近统计进行比较。比如，在整个分类后数据表中经过移动一个固定大小窗口，比较周围统计。一个大小为 W 窗口，在数据库中一次移动一个统计，新统计和这个窗口中其它 W-1 个统计相比较。这么，统计比较次数从 O（T2 ）降低到 O（TW ），其中，T 为数据库中统计总数。所以，当数据源中数据量很大时，应该采取统计排序方法。对于统计排序方法，使用某种应用相关键来将相同统计聚类到邻近位置。依据用户定义键值来重排表统计，并采取滑动窗口来 Pair-wise比较窗口内统计。是先计算统计 N-Gram 值，然后按该值进行排序；针对多语言文本情况，采取序值表方法来进行排序。该方法说明以下：对于西文字符，排序就是按西文字符字典序排列，但对于汉字来说，存在多个排序方法。在国家标准 GB2312-80 中共搜集汉字 6763 个，分成两级，一级汉字字库包含汉字 3755 个，按拼音字母排序，二级汉字字库包含汉字 3008 个，按部首排序。由此可见汉字本身编码不满足任何一个统一序值规则，不适合作序值使用。为了处理序值不统一问题，采取建立序值文件方法。现在，汉字通常有以下三种排序方法：拼音序、笔划序、部首序。对于汉字多种不一样排序方法，分别建立对应于 GB2312-80 汉字基础集序值表。序值表中序值存放按对应汉字在汉字基础集中出现次序进行。所以，依据汉字内码（0XB0A1-0XF7FE）能够直接计算出序值表中存放对应序值入口地址，计算公式以下：其中，c1 为汉字内码第一个字节（区码）；c2 为汉字内码第二个字节（位码）；N 为序值编码长度，N=2（用两个字节来存放序值）；headoffset 是序值表中存放第一个汉字（“啊”字编码 OXBOA1）位置。序值表相当于自定义一个编码，不一样排序方法对应各自序值表。序值表大小只有几十 K，能够存放在内存中。依据上述公式，汉字内码可直接映射为获取序值地址索引，很便于使用。对于要排序字段，依据以上方法把该字段中全部字符转换成对应序值，然后，采快速排序算法能够对统计进行排序。在此排序基础上，再采取相同反复统计检测算法对相邻统计进行检测，从而提升了检测效率。按以上方法重排统计后，相同统计被放在较靠近位置，从而能够在相对集中范围内作统计相同检测。不过因为排序时对错误位置很敏感，不能确保排序后反复统计全部在一起。所以这种方法也有一定不足。另外，对整个数据库统计进行重排开销也很大。所以，从实用角度考虑，在实际应用中，对于小批量数据，如统计总数小于 5 万时，没有必需采取复杂统计排序算法，能够直接进行统计比较，从而提升相同反复统计查全率。统计相同检测统计相同检测是相同反复统计清理过程中一个关键步骤，经过统计相同检测，能够判定两条统计是不是相同反复统计。对于统计相同检测，通常采取 Pair-wise 比较算法，它是一个比较成熟方法。相同反复统计合并/清除当完成相同反复统计检测以后，对检测出反复统计要进行处理。对于一组相同反复统计，通常有两种处理方法：1.第一个处理方法第一个处理方法是把一组相同反复统计中一个统计看成是正确，其它统计看成是含有错误信息反复统计。于是，任务就是删除数据库中反复统计。在这种情况下，部分常见处理规则是：1)人工规则人工规则是指由人工从一组相同反复统计中选出一条最正确统计保留，并把其它反复统计从数据库中删除掉，这种方法最简单。2)随机规则随机规则是指从一组相同反复统计中随机地选出一条统计保留，并把其它反复统计从数据库中删除掉。3)最新规则在很多情况下，最新统计能愈加好地代表一组相同反复统计。比如，越靠近目前日期信息正确性可能越高，常常使用账户上地址要比退休账户上地址权威部分。基于这种分析，最新规则是指选择每一组相同反复统计中最新一条统计保留，并把其它反复统计从数据库中删除掉。4)完整规则完整规则是指从一组相同反复统计中选择最完整一条统计保留，并把其它反复统计从数据库中删除掉。5)实用规则因为反复率越高信息可能越正确部分，比如，假如三条统计中两个供给商电话号码是相同，那么反复电话号码可能是正确。基于这种分析，实用规则是指从一组相同反复统计中选择和其它统计匹配次数最多一条统计保留，并把其它反复统计从数据库中删除掉。能够把以上方法定义成规则，存放在规则库中，供用户依据具体业务要求选择使用。2.第二种处理方法第二种处理方法是把每一条相同反复统计看成是信息源一部分。于是，目标就是合并一组反复统计，产生一个含有更完整信息新统计。该方法通常要由人工进行处理。在