Chunqiu Zeng,DB&KE Lab,CS Department, SCU

Chunqiu Zeng,DB&KE Lab,CS Department, SCU
不确定数据聚类关键技术研究答辩人: 曾春秋指导教师: 唐常杰教授 2018/12/28 Chunqiu Zeng,DB&KE Lab,CS Department, SCU

不确定数据聚类关键技术研究引言研究背景本文工作不确定数据建模不确定数据聚类实验及性能分析结论及未来工作 2018/12/28 Chunqiu Zeng,DB&KE Lab,CS Department, SCU

引言:研究背景数据是用于表达和描述真实的现实世界的一种载体观测和收集的数据具有固有的不确定性客观存在,本身是确定的
由于人们有限的解析和理解现实世界能力,以及人们获取数据的能力, 数据的不确定性始终存在 2018/12/28 Chunqiu Zeng,DB&KE Lab,CS Department, SCU

引言:研究背景论文P7 直接选择下拉列表的第一条不确定数据的普遍性缺失性直接忽略,然后匆匆完成注册 2018/12/28 Chunqiu Zeng,DB&KE Lab,CS Department, SCU

引言:研究背景不确定数据的普遍性缺失性模糊性人们经常说:”他比较年轻”. 这个 ”年轻”没有确定的标准,过于模糊而不确定论文P7
2018/12/28 Chunqiu Zeng,DB&KE Lab,CS Department, SCU

引言:研究背景不确定数据的普遍性缺失性模糊性时效性
论文P7 不确定数据的普遍性缺失性模糊性时效性由于不能得到未来数据, 专家利用过去最近一端时间的股市行情来分析股市的未来发展方向 2018/12/28 Chunqiu Zeng,DB&KE Lab,CS Department, SCU

引言:研究背景不确定数据的普遍性缺失性模糊性时效性精确度
论文P7 不确定数据的普遍性缺失性模糊性时效性精确度利用GPS定位运动物体时,往往只能给出以某个位置为中心,某个距离为半径的圆形区域 2018/12/28 Chunqiu Zeng,DB&KE Lab,CS Department, SCU

引言:研究背景不确定数据的普遍性缺失性模糊性时效性精确度一致性
论文P7 不确定数据的普遍性缺失性模糊性时效性精确度一致性描述某个人的年龄在37到45岁之间或年龄为35岁。这两个结论最多只有一个成立。 2018/12/28 Chunqiu Zeng,DB&KE Lab,CS Department, SCU

引言:研究背景不确定数据的普遍性缺失性模糊性时效性精确度一致性歧义性
论文P8 不确定数据的普遍性缺失性模糊性时效性精确度一致性歧义性拼音”Wang Wei”，对应很多中文名字：王伟，王维，王蔚，汪卫，汪伟……，仅DBLP就有7个结果。 2018/12/28 Chunqiu Zeng,DB&KE Lab,CS Department, SCU

引用：研究背景论文P9 多种不确定性混合出现 25 or 26 ？ 57 or 51 ？缺失单身or 已婚？存在？确定 2018/12/28 Chunqiu Zeng,DB&KE Lab,CS Department, SCU

引言：研究背景不确定数据研究现状不确定数据库不确定数据的查询
论文P13 不确定数据研究现状不确定数据库不确定数据的查询 Stanford的Trio，Cornell的MayBMS，Maryland的ProbDB等。 U-TopK查询，U-kRanks查询，PT-k查询，Pk-topk查询，skyline查询等。 2018/12/28 Chunqiu Zeng,DB&KE Lab,CS Department, SCU

引言：研究背景论文P14 不确定数据挖掘把数据挖掘应用于不确定数据利用模糊数学模型本文的重点 2018/12/28 Chunqiu Zeng,DB&KE Lab,CS Department, SCU

引言：研究背景不确定数据的聚类问题实际的分布，应有的聚类结果，a属于A 采样结果的分布，应有的聚类结果，a被记录为b，划为类B
论文P16 不确定数据的聚类问题实际的分布，应有的聚类结果，a属于A 采样结果的分布，应有的聚类结果，a被记录为b，划为类B 随着多次采样，a的位置可能在区域C上变化。如何聚类划分点a呢? 2018/12/28 Chunqiu Zeng,DB&KE Lab,CS Department, SCU

不确定数据聚类关键技术研究引言研究背景本文工作不确定数据建模不确定数据聚类实验及性能分析结论及未来工作 2018/12/28 Chunqiu Zeng,DB&KE Lab,CS Department, SCU

引言：本文工作提出不确定对象模型，并对不确定数据进行了形式化建模提出了基于不确定数据上的划分聚类算法提出基于剪枝技术的聚类算法，对不确定数据聚类算法进行了改进泛化不确定数据聚类算法为确定数据聚类算法，有效的提高了算法的效率详实的实验及效率、准确率的分析 2018/12/28 Chunqiu Zeng,DB&KE Lab,CS Department, SCU

不确定数据聚类关键技术研究引言不确定数据建模不确定对象可能世界语义不确定数据聚类实验及性能分析结论及未来工作 2018/12/28 Chunqiu Zeng,DB&KE Lab,CS Department, SCU

不确定数据建模论文P17 定义3.1（空间不确定点）给定一个n维的向量空间Rn。 (1)如果点p∈Rn以概率c出现某个事件中，则称t＝<p，c>为一个n维空间不确定点。 (2)给定两个不确定点t1＝<p1，c1> 和t2＝<p2，c2>，如果有p1=p2=p，称t1和t2是同点项，记为t1≃t2；反之t1和t2不是同点项，记为t1≄t2。两个同点项可以合并为另一个同点项，即t= t1 + t2 =<p，c1+c2>，其中t≃t1、t≃t2。一个空间点＋空间点发生的概率基于不确定点定义，给出同点项的定义 2018/12/28 Chunqiu Zeng,DB&KE Lab,CS Department, SCU

不确定数据建模论文P17 空间不确定点举例：由姓名，年龄，婚姻状况三个维度构成张三实体可以表示为： t=<(张三，51，单身)，42%> t1=<(张三，51，单身)，40%>和t2＝<(张三，51，单身)，2%> 同点项。 t= t1 + t2 =<p，c1+c2>，其中t≃t1、t≃t2 2018/12/28 Chunqiu Zeng,DB&KE Lab,CS Department, SCU

不确定数据建模论文P17 定义3.2（空间不确定对象）给定一个n维不确定点的集合S，设t1，t2S，t1t2，满足t1≄t2且令e=∑t.c ，e<=1。n维空间不确定对象u是满足下列条件的二元组u=<S，e>： (1)对于tS，不确定对象u以概率t.c被赋予t.p； (2)对于t′∉S，不确定对象u以概率0取值t′.p。其中称S为u的不确定区域，e为不确定对象u的存在率，也是不确定区域S的发生概率。灰色区域为u的不确定区域S 不确定对象u以t.c概率发生为t.p 2018/12/28 Chunqiu Zeng,DB&KE Lab,CS Department, SCU

不确定数据聚类关键技术研究引言不确定数据建模不确定对象可能世界语义不确定数据聚类实验及性能分析结论及未来工作 2018/12/28 Chunqiu Zeng,DB&KE Lab,CS Department, SCU

不确定对象建模论文P20 不确定对象的集合——不确定数据集(UD) 不确定数据集的可能世界(p20 定义3.3) 每一个不确定对象以某个概率选择一种可能情况发生然后把这些可能结果构成一个可能数据集合，这个数据集合发生概率为不确定对象发生情况的联合概率产生的数据集合及其概率构成的2元组称为可能世界 2018/12/28 Chunqiu Zeng,DB&KE Lab,CS Department, SCU

不确定数据建模论文P21 可能世界举例：不确定数据集 2个不确定对象可能情况组合不确定对象（u）不确定对象区域（S）存在率（e） uD {<（邓文，51，已婚），40%> <（邓文，57，已婚），60%>} 100% uW {<（王灿，23，单身），32％> <（王灿，23，已婚）， 8%>} 40％联合概率可能世界（PW）实例（W）概率（prob） PW1 {（邓文，51，已婚）} 24% PW2 {（邓文，51，已婚），（王灿，23，单身）} 12.8% PW3 （王灿，23，已婚）} 3.2% PW4 {（邓文，57，已婚）} 36% PW5 {（邓文，57，已婚）， 19.2% PW6 4.8% 可能世界集合 2018/12/28 Chunqiu Zeng,DB&KE Lab,CS Department, SCU

不确定数据聚类关键技术研究引言不确定数据建模不确定数据聚类不确定数据聚类算法 PA-UK-Median剪枝算法 MA-UK-Means改进算法实验及性能分析结论及未来工作 2018/12/28 Chunqiu Zeng,DB&KE Lab,CS Department, SCU

不确定数据聚类把不确定数据集中的每一个不确定对象划分到指定的簇中。使得簇内的不确定对象尽量相似，簇间对象尽量相异
论文P24 问题描述4.1：不确定数据聚类问题描述： GIVEN：n维不确定数据集UD FIND：一个包含K个簇的集合Φ＝{C1，C2，…，Ck} 和一个映射函数φ SATIFY： (1)令Ci∈Φ，Ci的元素为空间不确定点t，其中t.p是n维空间Rn上的一个空间点即t.p∈Rn，令某个空间点pci为Ci的中心代表。 (2) 对∀u∈UD，∀t∈u.S，φ(u，t) = pci，即能通过函数φ把t划分给与自身最为相似的簇Ci中。 (3) 使得每一个簇Ci内的对象尽量相似，簇间的对象尽量相异把不确定数据集中的每一个不确定对象划分到指定的簇中。使得簇内的不确定对象尽量相似，簇间对象尽量相异 2018/12/28 Chunqiu Zeng,DB&KE Lab,CS Department, SCU

不确定数据聚类不确定数据聚类——不同方式不确定对象，两个已有的簇在不确定对象中，不同的不确定点划分给离自身最近的簇——未指定聚类
论文P26 不确定数据聚类——不同方式不确定对象，两个已有的簇在不确定对象中，不同的不确定点划分给离自身最近的簇——未指定聚类在不确定对象中，所有不确定点划分给一个最近的簇 ——指定聚类 2018/12/28 Chunqiu Zeng,DB&KE Lab,CS Department, SCU

不确定数据聚类论文P28 聚类簇中心点不确定数据上的UK-Means目标代价函数不确定数据上的UK-Median目标代价函数簇C的质心 u中某个t所述簇的中心不确定点个数距离平方和的期望距离和的期望 u中某个t所述簇的中心 2018/12/28 Chunqiu Zeng,DB&KE Lab,CS Department, SCU

不确定数据聚类未指定不确定数据聚类指定不确定数据聚类 UA-UK-Means的簇中心点映射函数
论文P28 未指定不确定数据聚类 UA-UK-Means的簇中心点映射函数 UA-UK-Median的簇中心点映射函数指定不确定数据聚类 A-UK-Means的簇中心点映射函数 A-UK-Median的簇中心点映射函数定理4.1证明了两者等价 u中每一个不确定点t划分到离其距离平方最近的簇 u中每一个不确定点t划分到离其距离最近的簇定理4.1证明了两者不等价 u中所有不确定点t划分到离其距离平方期望最小的簇 u中所有不确定点t划分到离其距离的期望最小的簇 2018/12/28 Chunqiu Zeng,DB&KE Lab,CS Department, SCU

不确定数据聚类未指定聚类算法 UA-UK-Means UA-UK-Median 算法描述 2018/12/28 Chunqiu Zeng,DB&KE Lab,CS Department, SCU

算法4.3:unassigned_kcluster:在未指定聚类中，相应的UA-UK-Means和UA-UK-Median算法输入：簇的个数K 不确定数据UD 输出：输出K个簇的集合Φ＝{C1，C2，……，Ck} 过程（1） Begin （2）从UD中随机选择K个不同的不确定对象u，并在每个u.S上选择一个不确定点t，把t.p作为每一个簇的中心代表（3） Repeat （4） Cost⟵0 //目标代价（5） For each u∈UD （6） For each t∈u.S （7） <pc,d> ⟵ unassigned_φ(u,t) （8）把t指派到pc所对应的簇中（9）如果是UA-UK-Means时， Cost ⟵ d2×t.p + Cost //累计期望代价如果是UA-UK-Median时，Cost ⟵ d×t.p + Cost //累计期望代价（10） EndFor （11）（12） For each C∈Φ （13）根据式4.4重新计算C 的中心代表pc （14）（15） Util 各个簇C的成员没有变化，总目标代价Cost没有变化（16） End 输入论文P32 2018/12/28 Chunqiu Zeng,DB&KE Lab,CS Department, SCU

算法4.3:unassigned_kcluster:在未指定聚类中，相应的UA-UK-Means和UA-UK-Median算法输入：簇的个数K 不确定数据UD 输出：输出K个簇的集合Φ＝{C1，C2，……，Ck} 过程（1） Begin （2）从UD中随机选择K个不同的不确定对象u，并在每个u.S上选择一个不确定点t，把t.p作为每一个簇的中心代表（3） Repeat （4） Cost⟵0 //目标代价（5） For each u∈UD （6） For each t∈u.S （7） <pc,d> ⟵ unassigned_φ(u,t) （8）把t指派到pc所对应的簇中（9）如果是UA-UK-Means时， Cost ⟵ d2×t.p + Cost //累计期望代价如果是UA-UK-Median时，Cost ⟵ d×t.p + Cost //累计期望代价（10） EndFor （11）（12） For each C∈Φ （13）根据式4.4重新计算C 的中心代表pc （14）（15） Util 各个簇C的成员没有变化，总目标代价Cost没有变化（16） End 输出论文P32 2018/12/28 Chunqiu Zeng,DB&KE Lab,CS Department, SCU

算法4.3:unassigned_kcluster:在未指定聚类中，相应的UA-UK-Means和UA-UK-Median算法输入：簇的个数K 不确定数据UD 输出：输出K个簇的集合Φ＝{C1，C2，……，Ck} 过程（1） Begin （2）从UD中随机选择K个不同的不确定对象u，并在每个u.S上选择一个不确定点t，把t.p作为每一个簇的中心代表（3） Repeat （4） Cost⟵0 //目标代价（5） For each u∈UD （6） For each t∈u.S （7） <pc,d> ⟵ unassigned_φ(u,t) （8）把t指派到pc所对应的簇中（9）如果是UA-UK-Means时， Cost ⟵ d2×t.p + Cost //累计期望代价如果是UA-UK-Median时，Cost ⟵ d×t.p + Cost //累计期望代价（10） EndFor （11）（12） For each C∈Φ （13）根据式4.4重新计算C 的中心代表pc （14）（15） Util 各个簇C的成员没有变化，总目标代价Cost没有变化（16） End 论文P32 初始化k个簇 2018/12/28 Chunqiu Zeng,DB&KE Lab,CS Department, SCU

算法4.3:unassigned_kcluster:在未指定聚类中，相应的UA-UK-Means和UA-UK-Median算法
输入：簇的个数K 不确定数据UD 输出：输出K个簇的集合Φ＝{C1，C2，……，Ck} 过程（1） Begin （2）从UD中随机选择K个不同的不确定对象u，并在每个u.S上选择一个不确定点t，把t.p作为每一个簇的中心代表（3） Repeat （4） Cost⟵0 //目标代价（5） For each u∈UD （6） For each t∈u.S （7） <pc,d> ⟵ unassigned_φ(u,t) （8）把t指派到pc所对应的簇中（9）如果是UA-UK-Means时， Cost ⟵ d2×t.p + Cost //累计期望代价如果是UA-UK-Median时，Cost ⟵ d×t.p + Cost //累计期望代价（10） EndFor （11）（12） For each C∈Φ （13）根据式4.4重新计算C 的中心代表pc （14）（15） Util 各个簇C的成员没有变化，总目标代价Cost没有变化（16） End 论文P32 给定u和t，把t划分给一个簇，并返回簇中心 2018/12/28 Chunqiu Zeng,DB&KE Lab,CS Department, SCU

算法4.3:unassigned_kcluster:在未指定聚类中，相应的UA-UK-Means和UA-UK-Median算法输入：簇的个数K 不确定数据UD 输出：输出K个簇的集合Φ＝{C1，C2，……，Ck} 过程（1） Begin （2）从UD中随机选择K个不同的不确定对象u，并在每个u.S上选择一个不确定点t，把t.p作为每一个簇的中心代表（3） Repeat （4） Cost⟵0 //目标代价（5） For each u∈UD （6） For each t∈u.S （7） <pc,d> ⟵ unassigned_φ(u,t) （8）把t指派到pc所对应的簇中（9）如果是UA-UK-Means时， Cost ⟵ d2×t.p + Cost //累计期望代价如果是UA-UK-Median时，Cost ⟵ d×t.p + Cost //累计期望代价（10） EndFor （11）（12） For each C∈Φ （13）根据式4.4重新计算C 的中心代表pc （14）（15） Util 各个簇C的成员没有变化，总目标代价Cost没有变化（16） End 论文P32 累积计算期望代价 2018/12/28 Chunqiu Zeng,DB&KE Lab,CS Department, SCU

算法4.3:unassigned_kcluster:在未指定聚类中，相应的UA-UK-Means和UA-UK-Median算法输入：簇的个数K 不确定数据UD 输出：输出K个簇的集合Φ＝{C1，C2，……，Ck} 过程（1） Begin （2）从UD中随机选择K个不同的不确定对象u，并在每个u.S上选择一个不确定点t，把t.p作为每一个簇的中心代表（3） Repeat （4） Cost⟵0 //目标代价（5） For each u∈UD （6） For each t∈u.S （7） <pc,d> ⟵ unassigned_φ(u,t) （8）把t指派到pc所对应的簇中（9）如果是UA-UK-Means时， Cost ⟵ d2×t.p + Cost //累计期望代价如果是UA-UK-Median时，Cost ⟵ d×t.p + Cost //累计期望代价（10） EndFor （11）（12） For each C∈Φ （13）根据式4.4重新计算C 的中心代表pc （14）（15） Util 各个簇C的成员没有变化，总目标代价Cost没有变化（16） End 论文P32 指派一个不确定对象到一个簇 2018/12/28 Chunqiu Zeng,DB&KE Lab,CS Department, SCU

算法4.3:unassigned_kcluster:在未指定聚类中，相应的UA-UK-Means和UA-UK-Median算法输入：簇的个数K 不确定数据UD 输出：输出K个簇的集合Φ＝{C1，C2，……，Ck} 过程（1） Begin （2）从UD中随机选择K个不同的不确定对象u，并在每个u.S上选择一个不确定点t，把t.p作为每一个簇的中心代表（3） Repeat （4） Cost⟵0 //目标代价（5） For each u∈UD （6） For each t∈u.S （7） <pc,d> ⟵ unassigned_φ(u,t) （8）把t指派到pc所对应的簇中（9）如果是UA-UK-Means时， Cost ⟵ d2×t.p + Cost //累计期望代价如果是UA-UK-Median时，Cost ⟵ d×t.p + Cost //累计期望代价（10） EndFor （11）（12） For each C∈Φ （13）根据式4.4重新计算C 的中心代表pc （14）（15） Util 各个簇C的成员没有变化，总目标代价Cost没有变化（16） End 论文P32 重新计算簇中心 2018/12/28 Chunqiu Zeng,DB&KE Lab,CS Department, SCU

算法4.3:unassigned_kcluster:在未指定聚类中，相应的UA-UK-Means和UA-UK-Median算法输入：簇的个数K 不确定数据UD 输出：输出K个簇的集合Φ＝{C1，C2，……，Ck} 过程（1） Begin （2）从UD中随机选择K个不同的不确定对象u，并在每个u.S上选择一个不确定点t，把t.p作为每一个簇的中心代表（3） Repeat （4） Cost⟵0 //目标代价（5） For each u∈UD （6） For each t∈u.S （7） <pc,d> ⟵ unassigned_φ(u,t) （8）把t指派到pc所对应的簇中（9）如果是UA-UK-Means时， Cost ⟵ d2×t.p + Cost //累计期望代价如果是UA-UK-Median时，Cost ⟵ d×t.p + Cost //累计期望代价（10） EndFor （11）（12） For each C∈Φ （13）根据式4.4重新计算C 的中心代表pc （14）（15） Util 各个簇C的成员没有变化，总目标代价Cost没有变化（16） End 论文P32 迭代计算直到收敛 2018/12/28 Chunqiu Zeng,DB&KE Lab,CS Department, SCU

不确定数据聚类算法 UA-UK-Means和UA-UK-Median算法分析
论文P33 UA-UK-Means和UA-UK-Median算法分析引理4.3 算法UA-UK-Means和UA-UK-Median的时间复杂度为Ο(K×|u|×|UD|×r)，其中r为算法迭代的次数，K为簇的个数。实质上，可以把不确定数据对象u的未指定聚类算法看成是各个不确定对象u中不确定点t的常规聚类算法 2018/12/28 Chunqiu Zeng,DB&KE Lab,CS Department, SCU

不确定数据聚类未指定聚类算法 UA-UK-Means UA-UK-Median 指定聚类 A-UK-Means A-UK-Median 算法描述 2018/12/28 Chunqiu Zeng,DB&KE Lab,CS Department, SCU

不确定数据指定聚类算法算法4.4:assigned_kcluster:在指定聚类中，相应的A-UK-Means和A-UK-Median算法输入：簇的个数K 不确定数据UD 输出：输出K个簇的集合Φ＝{C1，C2，……，Ck} 过程（1） Begin （2）从UD中随机选择K个不同的不确定对象u，并在每个u.S上选择一个不确定点t，把t.p作为每一个簇的中心代表（3） Repeat （4） Cost⟵0 //目标代价（5） For each u∈UD （6） <pc,d> ⟵ assigned_φ(u) （7） Cost ⟵ d+ Cost //累计期望代价（8） For each t∈u.S （9）把t指派到pc所对应的簇中（10） EndFor （11）（12） For each C∈Φ （13）根据式4.4重新计算C 的中心代表pc （14）（15） Util 各个簇C的成员没有变化，总目标代价Cost没有变化（16） End 论文P34 给定不确定对象u，把u指派到一个 2018/12/28 Chunqiu Zeng,DB&KE Lab,CS Department, SCU

不确定数据指定聚类算法算法4.4:assigned_kcluster:在指定聚类中，相应的A-UK-Means和A-UK-Median算法
输入：簇的个数K 不确定数据UD 输出：输出K个簇的集合Φ＝{C1，C2，……，Ck} 过程（1） Begin （2）从UD中随机选择K个不同的不确定对象u，并在每个u.S上选择一个不确定点t，把t.p作为每一个簇的中心代表（3） Repeat （4） Cost⟵0 //目标代价（5） For each u∈UD （6） <pc,d> ⟵ assigned_φ(u) （7） Cost ⟵ d+ Cost //累计期望代价（8） For each t∈u.S （9）把t指派到pc所对应的簇中（10） EndFor （11）（12） For each C∈Φ （13）根据式4.4重新计算C 的中心代表pc （14）（15） Util 各个簇C的成员没有变化，总目标代价Cost没有变化（16） End 论文P34 遍历所有的不确定对象u，并指派到相应的簇与未指定区别在于，遍历的每一u，不会遍历u内的每一个t 2018/12/28 Chunqiu Zeng,DB&KE Lab,CS Department, SCU

不确定数据聚类算法论文P34 A-UK-Means和A-UK-Median算法分析引理4.4算法A-UK-Means和A-UK-Median的时间复杂度为Ο(K×|u|×|UD|×r)，其中r为算法迭代的次数。 assigned_φ(u) 分析 2018/12/28 Chunqiu Zeng,DB&KE Lab,CS Department, SCU

不确定数据聚类论文P31 算法4.2:assigned_φ(u):在指定聚类中，与不确定点相异度最小的簇选择算法输入：不确定对象u 簇集合Φ＝{C1，C2，……，Ck} 输出：与t相异度最小的簇C的中心点pc。以及相异度大小d:即返回<pc,d> 过程（1） Begin （2）初始化变量d ⟵∞，pc ⟵NULL （3） For each Ci∈Φ （4） temp ⟵0 （5） For each t∈u.S （6）如果是A-UK-Means，temp ⟵d2(t.p,pci)×t.c＋temp //相离度平方期望如果是A-UK-Median，temp ⟵d(t.p,pci)×t.c＋temp//计算期望相离度（7） EndFor （8） If(temp < d) （9） d ⟵temp （10） pc ⟵pci （11） EndIf （12）（13） Return <pc,d> （14） End O(|U|) 2018/12/28 Chunqiu Zeng,DB&KE Lab,CS Department, SCU

不确定数据聚类论文P31 算法4.2:assigned_φ(u):在指定聚类中，与不确定点相异度最小的簇选择算法输入：不确定对象u 簇集合Φ＝{C1，C2，……，Ck} 输出：与t相异度最小的簇C的中心点pc。以及相异度大小d:即返回<pc,d> 过程（1） Begin （2）初始化变量d ⟵∞，pc ⟵NULL （3） For each Ci∈Φ （4） temp ⟵0 （5） For each t∈u.S （6）如果是A-UK-Means，temp ⟵d2(t.p,pci)×t.c＋temp //相离度平方期望如果是A-UK-Median，temp ⟵d(t.p,pci)×t.c＋temp//计算期望相离度（7） EndFor （8） If(temp < d) （9） d ⟵temp （10） pc ⟵pci （11） EndIf （12）（13） Return <pc,d> （14） End O(|U|×| Φ |) O(|U|) 2018/12/28 Chunqiu Zeng,DB&KE Lab,CS Department, SCU

不确定数据聚类论文P31 算法4.2:assigned_φ(u):在指定聚类中，与不确定点相异度最小的簇选择算法输入：不确定对象u 簇集合Φ＝{C1，C2，……，Ck} 输出：与t相异度最小的簇C的中心点pc。以及相异度大小d:即返回<pc,d> 过程（1） Begin （2）初始化变量d ⟵∞，pc ⟵NULL （3） For each Ci∈Φ （4） temp ⟵0 （5） For each t∈u.S （6）如果是A-UK-Means，temp ⟵d2(t.p,pci)×t.c＋temp //相离度平方期望如果是A-UK-Median，temp ⟵d(t.p,pci)×t.c＋temp//计算期望相离度（7） EndFor （8） If(temp < d) （9） d ⟵temp （10） pc ⟵pci （11） EndIf （12）（13） Return <pc,d> （14） End O(|U|×|Φ|) O(|U|) 该u的指派过程代价为：O(|u|×|Φ|). 而该过程将会被调用|UD|×r次。如果已知u和某个C是最小的，就没有必要计算其余的簇Ci与u的相似度。如果能避免计算h个簇，则总的可以避免h×|UD|×r×|u|×|Φ|次计算。 2018/12/28 Chunqiu Zeng,DB&KE Lab,CS Department, SCU

不确定数据聚类关键技术研究引言不确定数据建模不确定数据聚类不确定数据聚类算法 PA-UK-Median剪枝算法 MA-UK-Means改进算法实验及性能分析结论及未来工作对A-UK-Median算法改进 2018/12/28 Chunqiu Zeng,DB&KE Lab,CS Department, SCU

PA-UK-Median剪枝算法可以通过Ed(u，pc)来估计Ed(u，pcx)的上界和下界
定理4.2 已知不确定对象u，和两个簇的中心点代表pc和pcx，如果记：则：（1）Ed(u，pcx) ≤Ed(u，pc)+d(pc，pcx)=upper(u，pcx) （2）Ed(u，pcx) ≥max{0，Ed(u，pc)－d(pc，pcx)}=lower(u，pcx) 三角不等式可以通过Ed(u，pc)来估计Ed(u，pcx)的上界和下界 2018/12/28 Chunqiu Zeng,DB&KE Lab,CS Department, SCU

PA-UK-Median剪枝算法论文P37-38 定理4.3 记min_upper(u) = minCi∈Φ{upper(u，pci)}，给定不确定对象u和一个簇Ci，如果lower(u，pci) >min_upper(u)，则u一定不会被指派到簇Ci。估计Ed(u,pcx)和Ed(u,pc)的上下界 min_upper(u)=3 lower(u,pc)=4>min_upper(u)故p被剪掉在迭代过程中，利用上次计算的点Ed(u，pcpre)来估计Ed(u，pc).有效利用前几次迭代的结果来剪枝 2018/12/28 Chunqiu Zeng,DB&KE Lab,CS Department, SCU

PA-UK-Median剪枝算法论文P40 额外的空间用于保存前几次迭代中计算的Ed（u，pc） h为剪枝掉的簇数引理4.6 带有剪枝技术的PA-UK-Median的运行时间复杂度为Ο((K-h)×|u|×|UD|×r)，其中r为迭代的次数；与算法A-UK-Median相比，空间复杂度将额外增加Ο(|UD|×K)。 PA-UK-Median剪枝算法分析中，K一般较小，K≪|UD|，额外空间需要与不确定对象个数成线性增长。同时时间代价当h足够大，时间效率将会有显著的提高。 2018/12/28 Chunqiu Zeng,DB&KE Lab,CS Department, SCU

不确定数据聚类关键技术研究引言不确定数据建模不确定数据聚类不确定数据聚类算法 PA-UK-Median剪枝算法 MA-UK-Means改进算法实验及性能分析结论及未来工作对A-UK-Means算法改进 2018/12/28 Chunqiu Zeng,DB&KE Lab,CS Department, SCU

MA-UK-Means改进算法首先给出以下表示：定理4.7 给定不确定对象u和一个簇C的中心代表pc，则u和pc的期望相离度可计算为：
d2(p1，p2) ＝||p1－p2||2 定理4.7 给定不确定对象u和一个簇C的中心代表pc，则u和pc的期望相离度可计算为：两点间的欧氏距离不确定对象u和簇中心点间的期望距离平方和不确定对象u的期望中心点 2018/12/28 Chunqiu Zeng,DB&KE Lab,CS Department, SCU

MA-UK-Means改进算法根据定理4.7中等式： MA-UK-Means算法思想：
论文P43 根据定理4.7中等式： d2(u，pc)为两确定点间的距离。计算复杂度不高如果u确定，um遍确定。则Ed2(u，um)确定 MA-UK-Means算法思想：（1）计算出每一不确定对象u的中心um，然后计算出Ed2(u，m)。（2）然后把|UD|个不确定对象u转换为|UD|个确定的中心点um的k-means算法 2018/12/28 Chunqiu Zeng,DB&KE Lab,CS Department, SCU

MA-UK-Means改进算法论文P45 引理4.8 改进算法MA-UK-Means的时间复杂度为Ο((|u|＋K)×|UD|×r)，其中r为迭代的次数；与A-UK-Means相比，额外的空间复杂度为Ο(|UD|)。 A-UK-Means算法的时间复杂度为Ο(K×|u|×|UD|×r)的复杂度，A-UK-Means算法与之相比大大的提高了时间效率。同时额外空间的增长，与|UD|呈线性增长，空间复杂度并不高。 2018/12/28 Chunqiu Zeng,DB&KE Lab,CS Department, SCU

不确定数据聚类关键技术研究引言不确定数据建模不确定数据聚类实验及性能分析实验平台和数据来源精确度比较实验 PA-UK-Median剪枝算法效率 MA-UK-Means改良算法效率结论及未来工作 2018/12/28 Chunqiu Zeng,DB&KE Lab,CS Department, SCU

实验及性能分析论文P47 实验环境实验数据实验运行在Intel(R) Core(TM)2 Duo T GHZ的处理器，2.0G内存的Window XP Professional 操作系统上。主要的用到的开发工具为Visual Studio 2008，编程语言为C Plus Plus。为了有效的评估不确定数据上的聚类算法的准确性，高效性以及可伸缩性，本文通过数据合成器来模拟真实世界的数据不确定性。以真实数据为中心，按正态分布产生不确定点构成不确定对象 2018/12/28 Chunqiu Zeng,DB&KE Lab,CS Department, SCU

不确定数据聚类准确性实验论文P50 伴随着不确定区域中的不确定点个数numUP变化，精确度的影响最好情况高11％最好情况高8％图 5.1为数据合成器选取参数为numOB=100，dim=2，exist=0.2，Range=5，miuRange=20，deltaRange=10，K=5时，UA-UK-Median算法准确率伴随numUP变化的情况图 5.2为数据合成器选取参数为numOB=100，dim=2，exist=0.2，Range=5，miuRange=20，deltaRange=10，K=5时，UA-UK-Means算法准确率伴随numUP变化的情况 2018/12/28 Chunqiu Zeng,DB&KE Lab,CS Department, SCU

不确定数据聚类准确性实验论文P51 伴随着不确定区域中的不确定点个数numUP变化，精确度的影响最好情况高12％最好情况高14％图 5.3为数据合成器选取参数为numOB=100，dim=2，exist=0.2，Range=5，miuRange=20，deltaRange=10，K=5时，A-UK-Median算法准确率伴随numUP变化的情况图 5.4为数据合成器选取参数为numOB=100，dim=2，exist=0.2，Range=5，miuRange=20，deltaRange=10，K=5时，A-UK-Means算法准确率伴随numUP变化的情况 2018/12/28 Chunqiu Zeng,DB&KE Lab,CS Department, SCU

不确定数据聚类准确性实验论文P53 伴随着簇个数K变化，精确度的影响最好情况高8％最好情况高12％图 5.5为数据合成器选取参数为numOB=200，dim=2，exist=0.2，numUP=50，Range=5，miuRange=20，deltaRange=10，UA-UK-Median算法准确率伴随K变化的情况图 5.6为数据合成器选取参数为numOB=200，dim=2，exist=0.2，numUP=50，Range=5，miuRange=20，deltaRange=10，UA-UK-Means算法准确率伴随K变化的情况 2018/12/28 Chunqiu Zeng,DB&KE Lab,CS Department, SCU

不确定数据聚类准确性实验论文P54 伴随着簇个数K变化，精确度的影响最好情况高8％最好情况高9％图 5.7为数据合成器选取参数为numOB=200，dim=2，exist=0.2，numUP=50，Range=5，miuRange=20，deltaRange=10，A-UK-Median算法准确率伴随K变化的情况图 5.8为数据合成器选取参数为numOB=200，dim=2，exist=0.2，numUP=50，Range=5，miuRange=20，deltaRange=10，A-UK-Means算法准确率伴随K变化的情况 2018/12/28 Chunqiu Zeng,DB&KE Lab,CS Department, SCU

剪枝算法PA-UK-Median实验分析
伴随着不确定区域不确定点个数numUP变化，时间效率的影响最好情况高50％图 5.9为数据合成器选取参数为numOB=100，dim=2，exist=0.2，Range=5，miuRange=20，deltaRange=10，k=5时，PA-UK-Median算法效率伴随numUP的情况 2018/12/28 Chunqiu Zeng,DB&KE Lab,CS Department, SCU

伴随着不确定对象个数numOB变化，时间效率的影响最好情况高25％图 5.10为数据合成器选取参数为numUP=100，dim=2，exist=0.2， Range=5，miuRange=20，deltaRange=10，K=5,PA-UK-Median算法效率伴随numOB变化的情况 2018/12/28 Chunqiu Zeng,DB&KE Lab,CS Department, SCU

伴随着数据集维度dim变化，时间效率的影响优势更加明显图 5.11为数据合成器选取参数为numOB=100，numUP=100，exist=0.2，Range=5，miuRange=20，deltaRange=10，K=5,PA-UK-Median算法效率伴随dim变化的情况 2018/12/28 Chunqiu Zeng,DB&KE Lab,CS Department, SCU

改进算法MA-UK- Means的实验分析
伴随着不确定区域不确定点个数numUP变化，时间效率的影响论文P58 最优提高10% 图 5.12为数据合成器选取参数为numOB=100，dim=2，exist=0.2，Range=5，miuRange=20，deltaRange=10，K=5,MA-UK-Means算法效率伴随numUP变化的情况 2018/12/28 Chunqiu Zeng,DB&KE Lab,CS Department, SCU

伴随着不确定对象个数numOB变化，时间效率的影响论文P58 最优提高10% 图 5.13为数据合成器选取参数为numUP=100，dim=2，exist=0.2，Range=5，miuRange=20，deltaRange=10，K=5,A-UK-Means算法准确率伴随numOB变化的情况 2018/12/28 Chunqiu Zeng,DB&KE Lab,CS Department, SCU

伴随着数据集维度dim变化，时间效率的影响论文P59 随着dim 的增加逐渐增加。增加的趋势变得更加陡峭图 5.14为数据合成器选取参数为numOB=100，exist=0.2，numUP=100，Range=5，miuRange=20，deltaRange=10，K=5,A-UK-Means算法准确率伴随dim变化的情况 2018/12/28 Chunqiu Zeng,DB&KE Lab,CS Department, SCU

不确定数据聚类关键技术研究引言不确定数据建模不确定数据聚类实验及性能分析结论及未来工作 2018/12/28 Chunqiu Zeng,DB&KE Lab,CS Department, SCU

结论及未来工作论文P60 提出了不确定数据上的聚类算法UA-UK-Median、UA-UK-Means、A-UK-Median和A-UK-Means算法。基于合成数据，通过实验分析了以上不确定聚类算法在对不确定数据聚类分析时的准确度。为了克服时间效率瓶颈，针对A-UK-Median提出了基于剪枝技术的改进算法PA-UK-Median。对算法A-UK-Means分析提出了改进算法MA-UK-Means。实验对比了PA-UK-Median和A-UK-Median算法，MA-UK-Means和A-UK-Means算法的执行效率。实验表明了改进算法效率的明显得到提升。未来工作：本文只针对部分不确定数据聚类算法进行了探讨。在未来的工作中可以在不确定数据的背景下，对其他常用算法如分类，关联等挖掘算法进行研究。另外实验只是在合成数据上进行，把这些算法应用于大规模的真实环境数据中将会显得更加有意义。 2018/12/28 Chunqiu Zeng,DB&KE Lab,CS Department, SCU

硕士文章发表论文P64 第一作者. MPSQAR: Mining Quantitative Association Rules Preserving Semantics. In proceedings of the 4th International Conference on Advanced Data Mining and Applications(ADMA’08) pp , EI 第三作者. Discovering Multi-dimensional Major Medicines from Traditional Chinese Medicine Prescriptions In:BMEI’2008 international conference 2008 EI 第五作者. MovStream: An Efficient Algorithm for Monitoring Clusters Evolving in Data Stream In:GrC’2008 IEEE International conference 2008 EI 第一作者. MPSQAR:无损语义的量化关联规则挖掘算法. 计算机科学与探索第五作者. "出生缺陷监测数据中的朴素干预规则挖掘".计算机科学与探索.(2009年第2期，2009.4，Vol.1，编号T ), "Mining Naive Intervention Rules in Birth Defect Data".Journal of Frontiers of Computer Science and Tehnology. 2009年第2期，2009.4 第六作者. TRAODGrid：基于Grid 空间划分的高效离群轨迹检测方法. 第二十五届中国数据库学术会议, 计算机研究与发展, 第45卷, 增刊, 2008年10月, pp 第六作者. 基于GPU的基因表达式编程性能提升技术. 第二十五届中国数据库学术会议, 2008, 计算机研究与发展, 第45卷,增刊, 2008年10月，pp 第五作者. E&AMode:一种新的基于引擎粒子系统的图像渲染模式 . 四川大学学报（自然科学版）2007年6期 2018/12/28 Chunqiu Zeng,DB&KE Lab,CS Department, SCU

END 谢谢！ 2018/12/28 Chunqiu Zeng,DB&KE Lab,CS Department, SCU

Chunqiu Zeng,DB&KE Lab,CS Department, SCU

Similar presentations

Presentation on theme: "Chunqiu Zeng,DB&KE Lab,CS Department, SCU"— Presentation transcript:

Similar presentations

About project

反馈

请登录

Auth with social network:

Chunqiu Zeng,DB&KE Lab,CS Department, SCU

Similar presentations

Presentation on theme: "Chunqiu Zeng,DB&KE Lab,CS Department, SCU"— Presentation transcript:

Similar presentations

About project

反馈