三七大数据平台技术解决方案-V1.0.doc

三七数据大数据技术解决方案北京三七数据技术有限公司2017年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.第一种处理方