[發(fā)明專利]基于隱含分類信息的模式匹配方法

無(wú)效

• 申請(qǐng)?zhí)枺?/td>: 201010613046.2
• 申請(qǐng)日: 2010-12-29
• 公開（公告）號(hào): CN102063489A
• 公開（公告）日: 2011-05-18
• 發(fā)明（設(shè)計(jì)）人: 王國(guó)仁;趙宇海;丁國(guó)輝
• 申請(qǐng)（專利權(quán)）人: 東北大學(xué)
• 主分類號(hào): G06F17/30
• 分類號(hào): G06F17/30
• 代理公司: 沈陽(yáng)東大專利代理有限公司 21109
• 代理人: 梁焱

1.一種基于隱含分類信息的模式匹配方法，其特征在于包括以下步驟：

步驟1發(fā)現(xiàn)源數(shù)據(jù)實(shí)例的可能分類

通過(guò)最小生成樹聚類算法，計(jì)算每個(gè)屬性的數(shù)據(jù)對(duì)象聚類，出現(xiàn)在同一個(gè)聚類中數(shù)據(jù)對(duì)象所對(duì)應(yīng)的元組則表示源數(shù)據(jù)的一個(gè)可能的分類；

步驟2?尋找分類屬性

利用步驟1的結(jié)果，使用信息熵測(cè)量每個(gè)元組在不同屬性的聚類結(jié)果中的分布情況，最理想的情況，一個(gè)元組在不同屬性的聚類結(jié)果中出現(xiàn)在同一個(gè)聚類中，此時(shí)該元組的熵為零，最壞的情況是，該元組在每個(gè)屬性的聚類結(jié)果中都出現(xiàn)在不同的聚類中；尋找干擾屬性，所謂干擾屬性就是，根據(jù)該屬性對(duì)元組的聚類結(jié)果與大部分屬性都不相同，干擾屬性的熵要大于分類屬性，所以不斷地將其去除，直到所處理的關(guān)系的熵為零，最后得到分類屬性；

步驟3?為屬性匹配關(guān)聯(lián)相應(yīng)的過(guò)濾條件

為每個(gè)屬性匹配關(guān)聯(lián)合適的過(guò)濾條件。

2.按照權(quán)利要求1所述的一種基于隱含分類信息的模式匹配方法，其特征在于所述的步驟1中的發(fā)現(xiàn)源數(shù)據(jù)實(shí)例的可能分類，過(guò)程如下：

步驟1-1?計(jì)算對(duì)象之間的相似性

計(jì)算對(duì)象間的相似性，給定源模式S，R為S的一個(gè)數(shù)據(jù)表，A為R的某個(gè)屬性，定義集合C用于存儲(chǔ)屬性A中的數(shù)據(jù)對(duì)象，計(jì)算集合C中任意兩個(gè)對(duì)象間的距離，如果A為數(shù)字類型，則計(jì)算他們之間的歐式距離，如果為字符串類型，則計(jì)算3-grams距離；

步驟1-2?發(fā)現(xiàn)可能分類

根據(jù)對(duì)象之間的相似性，將對(duì)象進(jìn)行聚類，遍歷集合C中全部對(duì)象間的距離，找到最小距離并記錄其對(duì)應(yīng)的數(shù)據(jù)對(duì)象a和b，如果最小距離小于用戶給定的閾值r，則將對(duì)象a和對(duì)象b放入同一個(gè)聚類結(jié)果中，對(duì)屬性A中的所有數(shù)據(jù)對(duì)象進(jìn)行聚類，每一個(gè)結(jié)果聚類表示一個(gè)可能的分類。

3.按照權(quán)利要求1所述的一種基于隱含分類信息的模式匹配方法，其特征在于所述的步驟2中的尋找分類屬性，按以下步驟進(jìn)行：

步驟2-1?計(jì)算關(guān)系信息熵

為找到分類屬性，需要計(jì)算關(guān)系R的信息熵，用以求出屬性的信息增益，給定屬性A及其聚類結(jié)果，首先計(jì)算屬性A的熵值，該熵值表示A所在關(guān)系的元組在不同屬性聚類結(jié)果中的分布狀態(tài)，熵值越大，說(shuō)明元組的分布越混亂，熵值越小，說(shuō)明元組分布越有序；

步驟2-2?計(jì)算屬性的信息增益

根據(jù)步驟2-1得到的關(guān)系R的熵值，計(jì)算R中每個(gè)屬性的信息增益，對(duì)于某個(gè)屬性A，如果其信息增益是所有屬性中最大的，則說(shuō)明該屬性對(duì)R中元組的分布影響最大，將其去除，同理去除其他屬性；

步驟2-3?判定結(jié)束

?在每次將具有最大信息增益的屬性去掉后，判斷關(guān)系R的熵值是否為零以及關(guān)系R中的所有屬性的信息增益是否相同，如果算法滿足其中一個(gè)條件，則終止；關(guān)系R的熵值為零時(shí)說(shuō)明R中的元組在余下的屬性聚類結(jié)果中具有相同分布，即余下的屬性為分類屬性，所以算法終止，關(guān)系R中的所有屬性的信息增益相同說(shuō)明所有屬性對(duì)元組分布的影響相同，所以算法終止，余下屬性也同樣被看作分類屬性。

4.按照權(quán)利要求1所述的一種基于隱含分類信息的模式匹配方法，其特征在于所述的步驟3中為屬性匹配關(guān)聯(lián)相應(yīng)的過(guò)濾條件，按以下步驟進(jìn)行：

步驟3-1?構(gòu)建聚類匹配

給定一個(gè)分類屬性，每一個(gè)該屬性的對(duì)象聚類為一個(gè)過(guò)濾條件，該屬性可能和目標(biāo)的多個(gè)屬性之間存在匹配關(guān)系，為確定每一個(gè)過(guò)濾條件所要約束的屬性匹配，需要構(gòu)建聚類匹配，所謂聚類匹配是指兩個(gè)具有匹配關(guān)系的屬性的對(duì)象聚類之間的對(duì)應(yīng)關(guān)系；針對(duì)每一個(gè)分類屬性，找到其所有的同其他目標(biāo)屬性的聚類匹配；

步驟3-2?查找最優(yōu)c-mapping

給定一個(gè)分類屬性以及與其存在匹配關(guān)系的目標(biāo)屬性集合，枚舉所有的c-mapping，每一個(gè)c-mapping表示一個(gè)聚類匹配的集合，對(duì)每一個(gè)c-mapping進(jìn)行評(píng)估，找到最優(yōu)的c-mapping；

步驟3-3?關(guān)聯(lián)過(guò)濾條件

利用上步找到的最優(yōu)c-mapping構(gòu)建復(fù)合過(guò)濾條件，給定一個(gè)分類屬性A，如果其最優(yōu)c-mapping中存在兩個(gè)或者多個(gè)聚類匹配，且這些聚類匹配的目標(biāo)聚類來(lái)自同一個(gè)目標(biāo)屬性B，則使用邏輯“或”對(duì)這些聚類匹配的源聚類進(jìn)行鏈接，形成一個(gè)復(fù)合過(guò)濾條件c，并將條件c同屬性匹配(A,?B)進(jìn)行關(guān)聯(lián)，形成帶有約束的屬性匹配(A,?B,?c)。