不确定数据管理

2020-03-01 166浏览

  • 1.不确定数据管理 金澈清
  • 2.大纲 1.应用背景和数据模型 2.不确定时空数据库 3.不确定数据集成 4.不确定数据世系管理 5.ranking 查询 6.NN 查询 7.Inversed NN 8.skyline
  • 3.一、应 用背景和数据模型 应应 应应应 应应 应
  • 4.信息世界的不确定性 1. 原始数据不准 确 2. 聚集数据集 3. 隐私保护 4. 缺失值处理 应用背景 5. 数据集成 6. 更多应用 ····
  • 5.原始数据不精确 仪器精度 网络传输 外部环境影响 应用举例 传感器网络 RFID 读卡器，读准率仅 60%-70%
  • 6.传感器网络的架构 服务 外部用户 因特网 本地用户 网关 PDA 传感器节点 网关 多跳低能耗的无线网络 • 传感器节点经由多跳无线网络（ multi-hop wireless networks ）连接 • 数据在传感器网络之中路由并且被获得 • 网关将传感器簇和有线网络 / 因特网连接起来 • 服务处理传感器簇中产生的数据，并向固定 / 移动外部用户提供信息 • 本地用户可以从无线网络中直接获取并处理数据 • 面向查询的处理模型
  • 7.RFID 应 用Source:Sun and RFID
  • 8.聚集数据集 局部聚集 各条聚集记录可以被视为是服从一个概率分布 应用举例 人口数据集合
  • 9.
  • 10.隐私保护 应 保 持数据 应应应应 的敏感性， 应应应应应应应应 一个混沌的数据集 应应应应应应 以概率密度函数替代原始数据 应用举例：位置业务（ LBS ） 移动对象的当前位置以及位置变迁信息涉及用户隐私 从物理设备采集的数据再加上一层保护 以区域描述物体位置，隐藏对象的真实位置
  • 11.动机 : LBS 中的隐私问题 去大使馆 怎么走？ LBS 提供者 唯一身份 位置信息 去购物中心 怎么走？
  • 12.隐私 & QoS 权衡 隐私要求 位置匿名 L 包含至少 k-1 其他用户 • 敏感的位置 : 诊所 , 夜总会 l(x,y) 包括至少 k-1 个其他请求  身份匿名 – 敏感消息 : 政治性的 , 金融性的 k- 匿名模型 位置点 l(x,y) r2 r3 r1 覆盖的区域 L r4
  • 13.应用背景四 • 缺失值处理 • 缺失数据是应应 典的不确定数据的 应 应 应 应 应 应 应 应应 用 • 经插值后的缺失数据可以看作服从某个概率分布的随机变量，或者看作 是数据具有预先定义好的误差。 • 一些数据记录通过统计方法得到，比如通过预测和插值得到的数据记录 ，在这种情况下，推断得到的数据可以被精确地估计。 • 应用举例 • 在数据清洗应 用中非常常 应应应应应应
  • 14.空缺值 • 数据并不是永远有效的 • 例如，很多应 应 应 的应 应 多属性 应应应应 以应 应 取，比 应应应应应 在应 应 售数据中客 应应应应应应 的收入 应应 情况很应 掌握。 应应应 • 数据空缺可能是由于 • 装应应 的故障 应应 • 由于和其他数据不一致而被删除了 • 由于理解错误而未被录入 • 某些数据在应应 入的 应 应应 候并不认 应 应 应 应应 是重要的，因此没 应 应 应 应 应 应 应 应应 入 • …… • 空缺的数据可能需要被推断出来
  • 15.如何应对空缺值？ • 忽略该记录 : 当类标号缺少时通常这样做（假定挖掘任务涉及分类或者描述）。除非元组有多个属 性缺少值，否则该方法不是很有效。当每个属性缺少值的百分比变化很大时，它的性能非常差。 • 手动填充空缺值：一般地说，该方法很费时，并且当数据集很大、缺少很多值时，该方法可能行不 通。 • 使用一个全局的常数代表缺失值 ，例如 “ unknown”, 但是这可能会引入一个新类型 ?! • 使用平均值来取代缺失值 • 使用与给定元组属同一类的所有样本的平均值：例如，若将顾客按 credit_risk 分类，使用具有相 同信用度的应 客的平均收入替 应 应 应 应 应 应 应 应 income 中的空缺值 • 使用最可能的值去填充缺失值：例如贝叶斯公式或者决策树
  • 16.数据集成 相异模式 数据不一致性 应用举例：万维网（ Web ） 万维网（ Web ）是 Internet 上最重要的应用 从海量 Web 数据中自动抽取重要信息
  • 17.网页信息抽取的不确定性 • 抽取条目可能存在错误 ! • 对于各个条目，提供置信分数 • 以简单的 人名条目 抽取为例 C = 首字母大写的单词 D = 在人名字典中找得到的单词 信息抽取规则 精度 1. [CD] [CD] 0.9 2. [CD] 0.6 Last evening I met the candidate Shiv Vaithyanathan for dinner. We had an interesting conversation and I encourage you to get an update. His host Bill can be reached at X-2465. 抽取的条目 概率 Shiv Vaithyanathan 0.9 Bill 0.6 [CD] [CD] [CD]
  • 18.迫切需要新技术处理这类问题 以经典确定性技术（ deterministic technology ）解决上 述问题？ 数据清洗无法有效处理所有类型的不准确数据 例如， RFID 数据的不准确性表现为漏读、多读、脏数据等 多种情况，分应应 采用不同方法 应 应 应 应 应 应应 行应应 理，例如建立概率模型、 应应应应应应应应应应 机器学应应 建模、网 应 应 应 RFID 应 应 应器 应应 最应 化 应应应 度策略等，然而并没 应应应 应应应 有出现能够有效处理所有不准确类型的技术。 因此，迫切发展不确定性数据库管理技术
  • 19.概率关系数据库 从上世纪 80 年代后期开始，至今仍在继续 为何现在博得学术界的关注？ 应用驱动 多种数据类型，如不匹配数据值、不精确查询、不一致数据、不匹配的 模式等。 Xml, 数据流， ··· 是最主要的驱动力量 技术驱动 处理不确定性数据比处理确定性数据更难 部分现有方法回避了复杂度 研究成果有助于更好地管理概率数据库
  • 20.挑战一：庞大的可能世界实例集合 共有 24 个实例（ instance ）， 每个实例 = 各记录发生或不发生的情况
  • 21.• 描述所有实例，在各实例中，各元组出现或不出现 I P( I ) 1 • 两种不确定性 • 存在级不确定性（ Existential Uncertainty ） • 描述元组在数据库中的存在性 • 元组的存在（ / 不存在）会影响其他元组的存在（ / 不存在） • 元组间存在更复杂的相关性 • 属性级不确定性（ Attributer Level Uncertainty ） • 元组存在，值不确定 • 以概率分布函数或者具体概率参数表示 • 易于处理
  • 22.可能世界 • 元组之间存在依赖关系的情况
  • 23.属性域 : int, int,char(30), char(30),varchar(55), varchar(55),datetime datetime 关系模式 : 值域大小 : 232, 2240, 2440, 264 Employee(name:varchar(55),Employee(name:varchar(55),dob:datetime,salary:int)'>dob:datetime,salary:int)