《区间关联函数及其应用研究(完整版)实用资料.doc》由会员分享，可在线阅读，更多相关《区间关联函数及其应用研究(完整版)实用资料.doc（45页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、区间关联函数及其应用研究（完整版）实用资料(可以直接使用，可编辑 完整版实用资料，欢迎下载）区间关联函数及其应用研究摘 要本文研究的是区间关联关联函数及其应用性问题.首先直接利用点的关联函数的概念给出了区间关联函数的定义.在此的基础上,又给出了区间关联函数的规范化方法,并得到了它的一个重要性质.然后再给出可能度的定义和性质,从而得到区间数的排序方法.为便于在综合评价和决策等方面的应用,根据空气污染指数范围及相应的空气质量类别建立了空气质量的关联函数.根据实际观测数据,通过此评价分析方法得到2007年中国具有代表性的6大城市空气质量关联函数的区间数,并依据区间数的排序方法得到了该6大城市空气质量
2、优劣的排序.关键词 区间关联函数; 可能度; 排序; 空气质量1、前 言从蔡文教授1983年提出可拓集合以来,从物元分析发展到可拓学,已初步形成了它的理论框架,并开始向应用领域发展.可拓集是可拓论的主要支柱之一,并用关联函数来刻画,所以在实际应用中要考虑区间关于区间的关联函数. 因此, 区间关联函数是一个值得研究的课题.现有文献提出了一些关联函数的计算公式,但都是假定物元的所有特征量值能被精确测量.然而,由于系统复杂性和信息不确定性的影响,使人们获得精确信息的愿望难以实现,为此人们提出了各种不确定性理论和方法,如灰色系统、粗糙集理论等.由于国内外对区间数的研究取得了不少成果,因此可用区间数表示
3、特征的不精确量值,以探讨不精确基元的定量问题.设为论域,文献125均把关联函数定义为论域到实域的一个映射,现已有许多应用.可拓学研究现实世界中的矛盾问题,探讨处理矛盾问题的规律和方法,而事物的发展、矛盾的转化有一个由量变到质变的过程;人们对发展中的事物以及模糊事物的认识也不会只停留在一个点上,而对事物认识的变化就要用到区间数.模糊数学中为描述不确定性和模糊性引入了区间数的概念,但其区间只能含于内,反映的是变化的模糊程度可有时并不能很好地刻划客观对象的变化情况.例如,人们对某事物的某一特征(如服装的颜色),不仅有“爱好”程度的区别,某些人可能会表现出截然相反的“厌恶”心理,在选购商品时首先排除具
4、有“厌恶”特征的事物.对水质、空气等的评价也有从“达标”向“优秀”和“污染”2个方向的变动.为反映这样具有“爱好”与“厌恶”、“利”与“弊”等不同程度的情况,引入包含正负数的区间数也就顺理成章了.文献6引入了区间与区间之距的概念,并在此基础上给出了区间关联函数的概念. 则直接利用文献1中点的关联函数概念,定义区间关联函数,并得到了区间关联函数的一个重要性质.为便于在评价和决策等方面的应用, 文献1在区间关联函数定义的基础上,给出了区间关联函数的规范化方法,然后再进行排序，并根据空气污染指数范围及相应的空气质量类别建立了空气质量的关联函数.根据实际观测数据通过计算得到了2007年中国具有代表性的
5、6大城市空气质量关联函数的区间数,并依据区间数的排序方法得到了该6大城市空气质量优劣的排序.2.区间关联函数的定义设为论域,点的关联函数的定义参考文献2,即定义1 设为论域,是到实域的一个映射,为给定的对中元素的变换,称为论域上关于元素变换的一个可拓集合,为的关联函数,为关于的关联度. 在此基础上,我们引入了区间关联函数的概念.本文中,为参考文献1所表示的区间,当时,记此时,令,当时,记.定义2 设为论域,若对中任何一区间,都有一个区间数与之对应,为给定中元素的变换,则称为论域上关于元素变换的一个区间可拓集合,为的关联函数,为区间关于的关联度,其中,. 虽然此定义并未提供具体构造区间关联函数的
6、方法,但只要建立了点的关联函数之后就不难求得区间关联函数的取值范围.3.区间关联函数的规范化2.1区间关联函数的规范化方法假设:,表示个对象或个决策方案.,表示个衡量条件(或属性),并假设这些条件是加性独立的.,以区间形式表示的个衡量条件的权重向量的取值范围,其中,. 把对象关于衡量条件的关联函数(区间数形式),记为,则条件各对象评判关联函数分别为矩阵称为判别矩阵,其中. 有时,由于各属性数量级的不同,对关联函数的值难以比较和综合,因此，必须将关联函数规范化.将规范化为,则规范化结果记为.规范化的方法如下: 规范化时之所以除以不同的数,正是因为事物变化经过零界点发生了质变,从而在不同变动区域内
7、呈现出不同变化特征的缘故.设个衡量条件的权重向量为,对文献3中方法作适当的调整,则对象的综合评价值,可由如下线性规划模型求得:由,容易证明. 通过上述两个模型可以得到所有对象的综合评价值.2.2区间关联函数的一个有用性质 性质1 设且无公共点,令点的关联函数为,则对于区间关联函数有 且; 且与有公共端点且;或; 或 证明 由参考文献1的性质以及本文定义2,即得到性质1.有时为了便于对优劣程度的比较或对不同指标的综合需要把关联函数规范化,设符合量值要求的范围为,为论域,通常在符合要求的范围内,在不符合要求的范围内.针对的不同符号,如果大于零则除以,如果小于零则除以,从而把化为之间的区间数. 如何
8、评判对象的优劣即对区间数进行排序非常重要,下面给出区间数的一种排序方法.4.区间数的排序方法3.1可能度的定义以及性质设为区间数,并认为所考察的变量(或指标)落在此区间内,且服从均匀分布.当时时,此时记,则称区间数退化.先考虑两个区间数排序的情形.定义3 设两个区间数,当时,称与相等,记为;如果的可能度大于0,则称区间数大于区间数,记;如果的可能度小于0,则称区间数小于区间数,记.定义4 若均为非退化区间数,此时有3种情形(图 1图 1 两个区间数非退化时的几种情形),区间数的可能度(记为) 及的可能度(记为)分别定义为,有其中一个退化,不妨设退化为一点,可能度定义为至于,均退化为一点的情形,
9、则是普通实数的比较,其可能度定义为图 1 两个区间数非退化时的几种情形 由上述定义,容易看出时,并且容易证明以下性质. 性质2 性质3 当时,有.性质4 在情况下,当时, ;当时, ;当时,有.由定义容易证明,且易知其逆也成立,即是:性质5 在时情况下,当,有;当时,有;当时,有利用可能度概念能否对多个区间数进行排序呢?利用上述性质容易证得以下性质6,即可能度的传递性,它对排序具有关键作用.性质6 设区间数,如果,则.3.2排序方法 利用性质6,即可能度的传递性,可以对区间数进行排序,对多个区间数排序仍然是不方便的,下面指出一种易于操作的简便排序算法. 设为一组区间数,建立区间数两两比较的可能
10、度矩阵,即由性质1便有区间数两两比较的可能度矩阵满足:,且,故矩阵为反对称矩阵.其中,表示的可能度,但由于上述排序方法所得数据仅仅是两两比较的结果.由性质6可知区间数较大则可能度较大,因此,对区间数排序可以采用如下步骤: 首先对可能度矩阵按行求和:求得排序向量,由上述我们得到: 性质7 设可能度矩阵,若对两区间数有(),则(). 因此,只要比较排序向量中各个分量的大小即可得到相应区间数的排序.5.城市空气质量评估与排序4.1选取城市空气污染指标数据空气污染指数()是用来衡量各地空气质量的一个标准.空气污染指数的计算方法是根据每天测得的主要污染物,和的浓度,计算出各污染物的污染分指出数,取最大值
11、作为该城市或区域当日的空气污染指数的值.空气质量与污染指数的关系如下表所示(表 1).表 1 空气污染指数范围及相应的空气类别空气污染指数()0-5051-100101-150151-200201-300300空气质量状况优良轻微污染轻度污染中度污染重污染为了减少计算的复杂性,以下我们选取了中国不同地理位置的6个城市2007年空气污染指数的分布情况,分别是北京、成都、乌鲁木齐、哈尔滨、上海和广州,数据来源于中国环境监测总站10.为了减少个别数据的误差或消除偶然性,提高结果的精确性,我们对数据进行了以下适当处理:即同一城市在一年中最大的10个数据取平均值作为最大值,在一年中最小的10个数据取平均
12、值作为最小值.得到如下全国6个城市的2007年空气污染指数区间数(表 1见表 2).表 2 选取的全国6个城市的2007年空气污染指数区间数城市北京成都乌鲁木齐哈尔滨上海广州区间数26.1,351.632.3,187.127.4,429.928.3,228.524.8,172.626.7,142.24.2污染指数的关联函数及规范化 根据表1空气质量与污染指数的关系,我们建立如下的空气质量关联函数,其中污染指数100是可正常活动的“好”与对身体有一定影响的“坏”的空气质量分界点. 根据区间关联函数的定义2,计算上述6个城市空气污染质量指数的区间关联函数的值所得如下(见表 3).表 3 选取的全国
13、6个城市的2007年空气污染指数区间关联函数值城市北京成都乌鲁木齐哈尔滨上海广州区间数-2.5160,0.2831-0.8710,0.2096-3.2990,0.2650-1.2850,0.2534-0.7260,0.3032-0.4220,0.2745 然后利用上述区间关联函数规范化的方法,进行规范后得到这6个城市空气污染质量指数新的区间数如下(见表 4).表 4 选取的全国6个城市的2007年空气污染指数区间关联函数值规范化后的区间数城市北京成都乌鲁木齐哈尔滨上海广州区间数-0.7627,0.3216-0.264,0.2381-1,0.301-0.3895,0.2878-0.2201,0.
14、3444-0.1279,0.31184.3城市空气质量排序 利用前面的规范化方法得到新的区间数以后,再利用可能度的定义,我们得到了空气污染指数关联函数的区间数两两比较的可能度矩阵(反对称矩阵)为: 其中,表示的城市依次是北京、成都、乌鲁木齐、哈尔滨、上海和广州.然后对以上的可能度矩阵按行求和，得到排序向量:其中,表示的城市依次是北京、成都、乌鲁木齐、哈尔滨、上海和广州.因此,我们比较此排序向量中各个分量的大小后即得到相应区间数的排序,进而得到上述6大城市空气质量由好到坏的次序依次为: 广州、上海、成都、哈尔滨、北京、乌鲁木齐. 值得特别指出的是根据由关联函数转化后的区间数进行排序与按照空气污染
15、指数的分布区间数直接排序,可能会出现不同结果.以成都与长沙这2个城市为例,在中国环境监测总站10查询2007年长沙2007年空气污染指数区间数为长沙,则区间关联函数的为长沙,规范化后得到长沙.那么计算得到规范化后成都与长沙2个城市空气污染指数关联函数的区间数两两比较的可能度矩阵(反对称矩阵)为:其中,表示的城市依次是成都与长沙.然后对以上的可能度矩阵按行求和，得到排序向量:其中,表示的城市依次是成都与长沙.因此,较此排序向量中各个分量的大小后即得到相应区间数的排序,进而得到成都空气质量好于长沙.但是成都与长沙如果按照空气污染指数的分布区间数进行排序,则空气质量长沙好于成都.原因是什么呢?实际上
16、,空气污染指数的分布区间数,上下2个端点数值的意义是不同的.上端点数大于100时离100越远,表示空气质量越坏,影响空气质量的主要污染物是可吸入颗粒物(),其波动幅度较大,数量级也较大.而下端点数小于100时离100越近,表示空气质量越好, 而且其波动幅度较小.因此,有必要引入以100为零界的关联函数,并将其所得区间数规范化.这样效果如何呢?从每天公布的成都与长沙2个城市空气污染指数的平均值,可以证明此结论,即成都空气质量好于长沙.5、结论本文针对具有不确定性区间数的多属性决策问题,完整地给出了一套分析方法.该方法主要针对以区间数形式引入了区间关联函数的一种新定义,并获得了一个有用的性质,给出
17、的综合评价值进行相应的方案排序.在决策者不能给出承担风险态度的情况下,本文提出了两个区间数相互比较的可能度的概念,这也就是给出了决策方案排序的可能度,并且将此分析方法成功地应用于城市的空气质量的综合评价.参考文献1 蔡文.物元模型及其应用M.北京:科学技术文献出版社,1994.2 杨春燕, 蔡文.可拓集合的新定义J.广东工业大学学报,2001,18(8):5960.3 Bryson N,Mobolurin A.An action learning evaluation procedure for multiple criteria decision making problemsJ.Europ
18、ean Journal of Operational Research,1996,96:379386.4 李志林,邓谋杰.区间关联函数及其在地区空气质量评估中应用J.海南大学学报,2007,25(1):3539.5 蔡文, 杨春燕,林伟初.可拓工程方法M.北京:科学出版社,1997.6 胡宝清,何娟娟.区间论域上的区间可拓集及其关联函数J.广州工业大学学报,2001,18(1):48547 李志林.区间关联函数的的新定义及其应用研究J.数学的实践与认识, 2006,36(2):2072108 李志林.区间关联函数为区间数的综合评价方法J.汉江大学学报,2003,31(1):17209 李志林.
19、区间数的一种排序方法J. 海南大学学报,2003,21(1):4710 中国环境监测总站 .CORRELATION FUNCTION WITH INTERVAL NUMBER AND ITS APPLICATIONABSTRACT This paper describes the problem of correlation function with interval number and its application. The method of normalization of correlation function with interval number was presente
20、d on the basis of its definition and obtains a useful property of it. Then giving the method of ranking for interval number was presented on the basis of possibilitys definition and Nature.In order to facilitate the comprehensive evaluation and decision-making in the areas of application. According
21、to the range of Air Pollution Index(API) and its corresponding classification of air. The correlation function of the quality fair was created. Based on the observation data and calculation, the interval numbers of correlation function of the quality of air of the representative ten cities of china
22、in 2007 were obtained and the ranking of the interval numbers was also created.KEY WORDS: correlation function with interval number; possibility; ranking; quality of air一类函数在闭区间上的最值问题魏立国某些函数在闭区间上的最值，经过等价转化，均可化为闭区间上二次函数的最值。求解的关键是按对称轴与区间的位置进行分类。本文对常见的“对称轴变化但区间确定”及“对称轴确定但区间变化”两种类型例说如下：1. “轴变区间定”型例1. 若的
23、最大值为求表达式。分析：视为整体，可将转化为关于的二次函数，然后利用余弦函数值域确定。解：是关于的二次函数，它的对称轴为：注意到所以当；当所以例2. 已知当时，对任意实数恒小于零，求实数m的取值范围。分析：设，则原题等价于当时，最大值恒小于零。解：设，对称轴。（1）当时，所以，于是（2）当所以于是（3）当于是综上所述，当时，在上恒小于零。例3. 已知时，不等式恒成立，求的取值范围。分析：将原不等式整理成关于x的一元二次不等式，得：设当时，不等式恒成立的必要条件是，且，即，且，由此可将取值范围缩小到第一象限，并且可以确定图象是开口向上的抛物线，在此基础上，再寻求恒成立，即最小值恒大于0的的取值范
24、围。解：原不等式化为：设要使时，恒成立，必须使且即且，则是第一象限角，此时抛物线的开口向上，其对称轴方程为：因为所以所以上最小值为顶点纵坐标，即当时，恒成立充要条件是最小值取正值。综上所述，得所以说明：先计算二次函数两个特殊值，这一招非常高明，不仅缩小的取值范围，而且确定了抛物线对称轴的位置（即顶点横向位置），从而避免了求最值的分类讨论，使解题过程大大简化。2. “轴定区间变”型例4. 已知函数，若时，求函数的最值。分析：由于对称轴是确定的，所以只要根据对称轴与区间的三种位置关系进行讨论，就容易求出最值。解：函数图象的对称轴为（1）当，即时（2）当，即（3）当即（4）当，即时，设函数最大值记为
25、，最小值记为，则有例5. 对时，恒为正，求实数a的取值范围。分析：设，要在时恒为正，则最小值必须为正。解：设（1）当时则且（2）当，即时，则又于是（3）当，即时于是所以当时，在时恒为正。週期性數值區間關聯規則探勘演算法摘要近年來，資料探勘已成唯一門新興的顯學。而由傳統關聯規則探勘延伸出的週期性關聯規則探勘，與數量關係關聯規則探勘，為其中兩個較新的領域。而在此前，此二領域只有單獨各自發展其研究方向，然若能將此二方向做結合，將可探勘出更有價值之關聯法則。本研究以最新開發出來的GRA演算法為基礎作修改，加入週期性關聯規則探勘之概念，並搭配PQAR演算法，以利用GRA高效率之優點，找出週期性頻繁項目集
26、後，再以PQAR找出具有數值區間關係之關聯規則。關鍵字：資料探勘；關聯法則；週期性資料探勘；數量關係關聯規則探勘1.緒論近幾年來，Data mining的重要性與日俱增，相關的研究與應用在各方面皆有豐碩的成果。其中又以關聯規則(Association Rule)探勘在交易資料上的應用最為廣泛。舉例來說，如果我們想要分析顧客的購買行為，那麼，針對交易資料庫(transaction database)可以探究出產品間的關聯性，藉以做交叉銷售等市場行銷的決策。一般說來，資料庫儲存的交易量都十分龐大(數目從數十萬筆到數百萬筆不等)，發展出一個有效率的演算法和改良現有的演算法因而十分重要。在以往的關聯規
27、則裡，雖然能找到商品之間的關聯性，但是，對於整個資料庫存在而言，這一類的方法所找出的association rules所考慮的時間範圍是包含了整個資料庫所存在的時間範圍；對於在現實生活中的人們，會依季節的不同，星期的循環，或是特定的節日來安排我們的活動，因此，若我們將時間的特性也考慮進去時，則將可挖掘出更多令人有興趣且特殊的有用關聯規則。而在實際的應用上，由於交易資料隨著時間而遞增，因此如何維護新增或減少的資料將是一個必須解決的問題。以往新增交易資料後，為了求得最新的資訊，此時，需將整個資料庫再一次完整地重新分析、探勘、評估，來取得符合的規則或型樣(Patterns)。這樣不僅重複探勘已存在資
28、料庫中的交易紀錄，而且大量花費時間，造成時效與處理成本上的浪費。透過漸增式的探勘模式，當資料庫中有新增資料時，以原來上次探勘後儲存的結果為基礎，只針對新的資料作資料探勘，得到新資料部分的結果，與舊有結果合併，如此便能增進效率並節省冗長的分析時間。此外，目前大部份的研究都是針對交易資料庫中的關聯規則探勘提出演算法，然而，卻只能找出項目間同時出現的關聯規則，而不考慮項目的數量關聯。換句話說，在以往的資料探勘方法中，會將購買三瓶牛奶和一包麵包與一瓶牛奶和三份麵包的交易視為相同交易內容(即同時包含牛奶和麵包)。諸如此類的作法，將導致我們遺漏掉一些重要的隱藏訊息，例如：一位消費者買超過十瓶牛奶，則他同時
29、三份麵包以上的可能性與只買一份麵包的可能性，就很可能有著極大的不同。因此，我們除了採用以往一般的關聯規則所具有的特性之外，將會再考慮消費者所購買的各項商品的數量及其可能性。本研究將以最新開發出來的GRA演算法為基礎作修改，加入週期性關聯規則探勘之概念，並搭配PQAR演算法，以期利用GRA高效率之優點，找出週期性頻繁項目集後，再以PQAR找出具有數值區間關係之關聯規則。2.相關文獻探討2.1 FUP演算法FUP演算法主要概念為將舊的頻繁項目集與它們的出現次數儲存起來，再根據變動的資料庫部分去更新這些舊的頻繁項目集的出現次數，最後再計算剩下的候選項目集的出現次數，整個演算法加速的關鍵在對於舊的頻繁
30、項目集我們只需考慮變動的資料庫的部分即可，但是演算法本身卻容易產生過多的候選項目集，以及需要掃描資料庫多次，以至於效率無法提昇。DB+新增的部份DB原有的資料庫DB，LKCK，LK，本篇研究在漸增式探勘方面將採用FUP之概念，但以更有效率的GRA演算法基礎，以改善FUP在執行效率不佳之缺點。2.2 Temporal Apriori演算法Temporal Apriori沿用 Apriori的基本架構，採用一層接一層掃瞄資料庫得到large itemsets，再以得到large itemsets產生或沒有candidates產生為止。在產生itemset的candidates時，應用到集合的觀念：
31、“一個large itemset的所有子集合都是large itemsets”得到在產生candidate itemsets時的一個重要原則：“當一個itemset不是large時，他的任何superset都不應該產生成為一個candidate itemset”上述的原則在各種類的association rules mining中被廣泛的用來減少candidates的產生。下圖為Temporal Apriori的演算法流程圖概述，其中，一個basic time interval為分割資料庫的最小時間單位。Temporal Apriori採用Apriori的架構，一層一層逐漸產生frequent
32、 calendar patterns所包含的large itemsets。首先，第一次掃瞄資料庫，針對每個basic time interval 找出所有的large 1-itemsets，然後對存在於涵蓋到此basic time interval的calendar patterns裡面的這些large 1-itemsets加以統計出現在calendar patterns的週期中是large的次數。例如：在一個calendar schema R=(year:1996,1997,2000, month:1,2,12, day:1,2,31)中，items A、B、C在(2000,10,20)裡面
33、是large，而涵蓋到(2000,10,20)的calendar patterns有(*,10,20)、(2000,*,20)、(2000,10,*)、(*,*,20)、(*,10,*)、(2000,*,*)六種calendar patterns，因此，這六種calendar patterns裡的A、B、C在掃瞄資料庫到(2000,10,20)時，其次數得以累加。最後，在第一次掃瞄資料庫之後，計算完每個calendar patterns裡面所有1-itemsets出現在該週期內的次數，再把滿足使用者所設定的match ratio threshold的1itemsets保留下來。則這些被保留下來
34、的large 1-itemsets即是具有所存在的frequent calendar patters這些週期的large 1-itemsets。在第二層之後，每一層在每個basic time interval中分為三個部份。1.產生candidate itemsets。2.計算candidate itemsets在此basic time interval中出現的support。3.以出現的large itemsets更新包含到此basic time interval的calendar patterns裡面的這些large itemsets出現次數。2.3 GRA演算法GRA演算法利用前一階段的
35、頻繁項目集中所含有的頻繁項目資訊，來刪除該階段資料庫中非頻繁的項目，同時，也將新更後的相同的交易記錄進行計數累計的處理，可避免不斷地重複拆解相同的交易記錄，經由上述的階段縮減機制後，將可使資料庫逐漸縮小，同時，也能使GRA演算法僅產生最有可能成為頻繁的項目集，可有效提昇執行效能及記憶體利用率。GRA演算法流程圖2.4 PQAR演算法PQAR演算法以空間分割的方式，先探勘出滿足相對密度限制的頻繁數值區間項集合，再由其產生數值區間關聯規則，其減少掃瞄資料庫次數，使得執行時間大幅縮減，亦使得探勘結果中的區間個數較少，並以找出精簡而重要的數值區間關聯規則之目的。則我們為了求得更精準的週期性項目數量關係
36、，所以，我們將考慮以PQAR演算法所提出的相對密度因素，以發展出一新的週期性數量關聯演算法，以便能更快速地且精準地找尋出使用者有興趣的週期性數值關聯規則。3.研究方法3.1 演算法流程架構本研究將GRA演算法結合週期性關聯規則探勘之概念，並搭配PQAR演算法，透過週期性關聯規則和GRA演算法的快速拆解特性，並且也融入了數值區間關聯規則的特性，來加以結合產生另一新的方法，以期能快速地找出週期性的常見數值區間項集合，進而能找尋出大部份關聯規則探勘方法所忽略的項目出現數值所隱含的資訊。演算法流程圖如下。第一階段先找出具有週期性之頻繁項目集，第二階段再利用第一階段找出之週期性頻繁項目集，探勘其數值區間
37、關聯規則。演算法流程圖交易資料庫DB資料分析異動的交易資料庫搜尋分析過後的資料庫資料，找出使用者設定的(1)calendar schema(2)探勘週期時間的資料利用GRA演算法之置換方式快速拆解basic time interval每筆交易資料還有資料是將拆解的項目存入因素項目表(ET)得到ET或異動的ET資料表整合原始ET資料表與異動ET資料表否使用者設定calendar schema使用者設定探勘的週期時間使用者設定minimal match ratio與min_sup分析出所有的frequent calendar patterns將具有週期性之frequent itemsets利用PQ
38、AR演算法分析數值區間關聯規則交易資料庫結束開始使用者設定最小相對密度3.2 階段縮減交易長度及合併處理為了更能適用於交易長度較長的資料庫，本篇研究沿用GRA階段縮減交易長度之特點，將於每階段加入縮減交易長度的方式。首先，依序將交易記錄讀入到記憶體裡，同時，也計算每個項目出現的次數，當讀取完所有交易記錄後，即可得知所有項目及對應的支持度，接著，再使用最小支持度得到頻繁1-項目集，並利用此資訊將資料庫中的非頻繁項目予以刪除，則此方式可縮減每筆交易長度；同樣的，在後續每階段裡，都將利用前階段的頻繁項目集中所含的頻繁項目來刪除資料庫中的非頻繁項目，對於後續的處理與空間皆有很大的幫助。由於交易經過縮減
39、後，會產生大量相同的交易記錄，為了避免重複拆解相同交易記錄，將於每筆交易記錄經過縮減處理後，進行相同交易記錄累計的處理，也就是當有多筆相同的交易記錄時，僅記錄交易內容及筆數即可；另外，當修剪前或修剪後的交易長度皆未達下階段長度時，可直接刪除，因為該筆交易無法產生下階段的項目集。舉例如下假設通過使用者設定之最低週期頻率(亦即具有週期性)的L1為A、C、E，原始資料庫經刪去非L1之項目與合併相同交易內容後，再刪去交易長度小於2之紀錄，產生新的D1資料表，如下所示TIDD1Item001A C D E F002B C D003A C D ETIDItem001A C D E F002B C D003
40、A C D EItemCountsACE1C1ACE1itemCountsACE2C1ItemCountsACE23.3 過濾頻繁項目集處理程序Lemma 1：假設Ln-1中的項目集中的元素出現少於n-1次，則該元素不可能為Ln中的元素，因此可以刪除，其中，Ln為全部長度為n的頻繁項目集。證明：可以利用歸謬證法證明。假設Ln-1中的項目集中的元素a出現少於n-1次，但該元素為Ln中頻繁項目A的元素。因為元素a為Ln中頻繁項目集A的元素，所以元素a在頻繁項目A的n個長度為n-1的子項目集中總共會出現n-1次。但這與我們之前的假設矛盾，因此Lemma成立。例：假設L3中的一頻繁項目集acd，其長度
41、為二的子項目集為ac、ad、cd，所以頻繁項目集acd的元素a、c、d至少在L2子項目集內各出現2次。反之，假設L2的項目集為ac、ad、cd、bc，其中元素b在L2只出現1次，因此元素b不會是L3中的元素。上述Lemma為GRA所提出一重要過濾機制之原理基礎，本研究將之修改後套用至週期性關聯規則探勘。首先，依序讀入交易記錄後，將同時計算每個項目的支持度，並藉由最小支持度來得到頻繁1-項目集，之後更新涵蓋到該時間區間(basic time interval)的all star calendar pattern，並以1-star calendar pattern之L1作為階段縮減交易長度及合併處
42、理的資訊，刪除每筆交易內非頻繁的項目，並存入另一時間區間作相同交易記錄次數的累計。接著，由各時間區間取得頻繁2-項目集資訊後，將進行過濾頻繁項目集處理的程序，同樣的，先更新涵蓋到該時間區間的all star calendar pattern取得所有1-star calendar pattern頻繁2-項目集後，累計每個頻繁2-項目集的項目數量，並以下階段的長度n-1作為門檻值，來取得出現次數大於或等於3-1=2的項目，並以這些項目資訊來執行階段縮減交易長度及合併處理的程序。同樣的，重複前一階段的處理過程，由各時間區間得到頻繁3-項目集，更新涵蓋到該時間區間的all star calendar
43、pattern取得所有1-star calendar pattern頻繁3-項目集後，累計每個頻繁3-項目集的項目數量並以下階段長度n-1作為門檻值來得到頻繁的項目，並再次執行階段縮減交易長度及合併處理的程序直到無任何項目存在。3.4 數值區間關聯規則探勘首先將演算法前半階段找出之週期性頻繁項目集至資料庫讀取其項目數量，將每個項目的數值值域量分(quantize)成一定數目的區間。接著進行下列三步驟：1.建立項目數值空間：對資料庫中每個最大頻繁項目集P，也就是不存在父集亦為頻繁項目集者，若其包含的項目個數為n，則建立一個n維(n-dimension)的數值空間，其中每個維度空間分別對應到P中一
44、種項目的數值值域範圍，而每筆交易記錄則對應到此空間中的一個資料點。經過如此轉換後，此空間中的任一個區塊便代表由P或P的子集所形成的一個區間項集合。因此，探勘密集頻繁區間項集合的問題就轉變成由此空間找出資料點數大於或等於最小支持度，且相對密度也大於或等於最小相對密度門檻值的區塊。2.探勘密集頻繁區間項集合：採用PQAR演算法中空間分割(partition)的方式找出空間內資料點分佈較密集的區塊。所找出的每個資料點密集區塊即對應到一個候選區間項集合S，該區塊中每個維度的項目名稱及其區間範圍值就對應到S中一個區間項，而區塊內的資料點數就是S的支持度計數值，只要計算出其支持度及相對密度，即可判斷S是否
45、為一個密集頻繁區間項集合。3.產生數值區間關聯規則：對每個密集頻繁區間項集合S，找出S的所有子集在項目數值空間中的對應區塊並計算區塊內的資料點數，就可以得到S每一子集S的支持度計數值，最後以這些資料來計算關聯規則SSS的確信度，找出所有大於或等於最小確信度門檻值的數值區間關聯規則。3.5 實例說明假設Calendar schema R =(year:2000,2001,2002,month:1,2.12,day:1,2.30)Minimal support s = 0.6, minimal match ratio m = 0.8,最小相對密度=1.2Step 1:針對每個basic time interval 找出所有的large 1-itemsetsStep 2:對存在於涵蓋到此basic time interval的calendar patterns裡面的這些large 1-itemsets加以統計出現在calendar patterns的週期中是large的次數。Step 3:將非1-star calendar pattern L1的項目從各basic time interval中刪除且合併相同的交易累加其次數，並將剩下的交易內容儲存至新的暫存basic time interval中。Step 4:由1-star calendar p