九十三学年度第二学期论文成果发表会.ppt

九十三學年度第二學期論文成果發表會,自然語言式GIS查詢介面 以大安區餐飲服務為例 指導教授：朱子豪 研究生：R89228012 黃如鈺,前言,GIS使用範圍已擴展至一般大眾，如電子地圖網站 目前大部分電子地圖網站所提供的查詢方式極為固定，不夠彈性化，亦無法直接用空間關係查詢 欲以自然語言方式切入，增進查詢介面使用上之彈性與便利性 透過對空間查詢語句整理及自然語言處理相關方法，設計建構出一自然語言式GIS查詢介面,研究目標,1. 透過文獻回顧，了解前人對空間查詢及空間描述之相關研究，整理出空間查詢語句之組成元素及主要類型 2. 檢視評估一般資料庫自然語言查詢介面之架構應用於空間資料查詢之可行性後，根據空間查詢語句及空間資料之特性，對架構作修改以符合所需 3. 提出一自然語言查詢介面處理架構，可處理空間關係，及應用於不同資料庫之查詢，並實作建構之,空間查詢及空間位置描述,一、空間查詢 Berry(1968) ，提出十種地理分析類型 Tsai et al.(1989) ，綜合Berry的地理分析類型與四種空間資料(空間資料、屬性資料、空間關係、時間資料) ，作出空間查詢問題類型分類 Chu(1993) ，對空間查詢過程作探討，將其分解為六個步驟 龍運濤(1995) ，將空間查詢問題加以歸納分類，將問題的對象分為空間資料與屬性資料兩大類，空間關係是運作於兩個資料間的查詢方式,空間查詢及空間位置描述,二、空間位置描述 1996年美國智慧型運輸系統標準需求工作小組，提出區位描述(Location Referencing)此概念，區位描述即是我們對物體所在位置的認知， 區位描述方法 (Location Referencing Methods)即是表示之方法 國內相關研究，如游怡芳(2001)對搶救災害通阻位置描述作了蒐集和歸納整理、蔡純純(2003)對新聞報導中空間資訊描述方式作整理等,中文自然語言處理主要步驟,一、斷詞（林文啟，1995） 辭典法：預先建立辭典， 詞優先原則，簡單易實行， 但會有未知詞問題 法則法：建立語法規則，搭配有語意語法詞類等辭典 來處理中文，如中研院詞庫小組所提出之 以訊息為本位的格位文法（陳克健等，1997 ） 統計法：用大量語料作統計，找出字與字、詞與詞間 相互關係，利用此關係建立關係參數之資料 庫，用參數找出最有可能之詞序組合,二、語句剖析(唐筠，1995） 以語法為主： 以語法句型結構及詞類作語句分析之依據，優點是易建立結構圖及較有明確規範，缺點是合乎語法之句子不一定語意正確 以語意為主： 使用模板比對(pattern matching)的方式，建立各個字詞出現的環境，並以統計方法決定各模板的強度和邊際效度，優點是可深入了解句子的意義，缺點是建立抽象結構前的工作較複雜,中文自然語言處理主要步驟,研究方法,一般資料庫查詢介面之自然語言處理架構。 空間查詢語句欲運用一般關聯式資料庫自然語言處理架構之實體限制，及修正方式。 空間查詢語句之相關語意語法分析方式。,一般資料庫查詢介面之自然語言處理架構,（林文啟，1995）,產生SQL等正規語言,產生剖析樹,以語意網等知識表現法之中間型式,應用此自然語言處理架構於空間查詢語句之限制,SQL對空間關係並無定義，故語句無法在Query Generator階段轉為SQL ，直接轉交Query Interpreter對資料庫進行查詢，空間關係仍需自行處理運算。 空間查詢語句在內部處理之流程 我找大安高工附近有二十四小時營業的餐廳 1.大安高工作buffer 2.對餐飲資料庫以屬性條件二十四小時營業找出相關資料 3.判斷2之結果是否落在1中，有則即為所求,一般資料庫自然語言查詢介面架構之修正,應具中文斷詞能力 除斷詞剖析、語意處理外，需進行空間資料庫查詢及空間運算,斷詞處理,語法分析,語意分析,空間查詢處理,空間查詢語句相關語意語法分析方式,空間查詢語句主要型式，分為以屬性條件查詢及空間條件查詢，亦有兩種之混合型式 以語句中直接影響查詢及空間運算之詞彚為對象，整理其種類，並由此整理出空間查詢語句之主要類型 根據出現元素之種類，建立系統斷詞辭典，並根據語句類型建構內部空間運算之邏輯,研究成果與討論,空間查詢語句主要構成元素 主要空間查詢語句類型 系統建構及運作流程 1.系統設計 2.系統架構 3.各模組運作方式 4.各類型語句所對應之空間運算定位方式,空間查詢語句主要構成元素一,空間查詢目標= （輔助定位物件|空間查詢目標 + 空間條件） + 查詢對象 + 屬性條件 STO = （ PRO | STO + SC ） + AC + TO 出現在句中順序可變動 例句 我找大安高工附近有24小時營業的餐廳,輔助定位物件,空間條件,屬性條件,查詢對象,空間查詢語句主要構成元素二,空間查詢目標（spatial target object，STO） 我找大安高工附近有24小時營業的餐廳 由語句查詢所得之餐飲資料。 輔助定位物件（positioning reference object，PRO） 我找大安高工附近有24小時營業的餐廳 作為空間定位點之用。,空間查詢語句主要構成元素三,當同一查詢語句作二次查詢時，空間查詢目標（STO）於第二次查詢作為輔助定位物件（PRO）之用。 我找大安高工附近有24小時營業的餐廳，還有離這些餐廳最近的咖啡店。,空間查詢語句主要構成元素四,空間條件（spatial criteria，SC） 我找大安高工附近有24小時營業的餐廳 由空間關係詞構成，將定位點與查詢對象之間關 係作定義。 屬性條件（attribute criteria，AC） 我找大安高工附近有24小時營業的餐廳 修飾查詢對象，將查詢對象之範圍細緻化。,空間查詢語句主要構成元素五,查詢對象（target object，TO） 我找大安高工附近有24小時營業的餐廳 本研究所整理的空間查詢語句主要查詢類型，均以空間條件查詢為主，屬性條件條件為輔，並依構成元素之個數將語句分類。,主要空間查詢語句類型分類方式,以構成元素個數種類分類，各元素之上限為兩個。 不處理亦不探討代名詞等句意指涉問題。 二次查詢的語句不在討論範圍。 以空間條件查詢為主，屬性條件查詢為輔，空間關係以附近及最近作為探討對象。,空間查詢語句句型1 一個空間定位點、查詢對象個數為一、空間關係詞只出現一次時：,1-0.空間定位點 空間關係詞 查詢對象 例句：我找大安高工附近的餐廳 1-1.空間定位點 空間關係詞屬性條件 查詢對象 例句：我找忠孝東路敦化南路口附近像是日本料理之類的餐廳,空間查詢語句句型2 一個空間定位點、查詢對象個數為一、空間關係詞出現兩次時：,2-0. 空間定位點 空間關係詞 Boolean 空間關係詞 查詢對象 例句：我找大安高工附近或 距離最近 的餐廳 2-1.空間定位點 空間關係詞 Boolean 空間關係詞 查詢對象 屬性條 件 例句：我找距離中廣最近或在附近像是韓 國烤肉之類的餐廳,空間查詢語句句型3 一個空間定位點、查詢對象個數為二、空間關係詞出現一次：,3-0.空間定位點 空間關係詞 查詢對象 Boolean 查詢對象 例句：我找大安高工附近的日本料理或 韓國菜 3-1.空間定位點 空間關係詞 屬性條件 查詢對象 Boolean 查詢對象 例句：我找大安高工附近的日本料理或 像是韓國菜之類的餐廳,空間查詢語句句型4 一個空間定位點、查詢對象個數為二、空間關係詞出現二次：,4-0.空間定位點空間關係詞 Boolean 空間關係詞查詢對象 Boolean 查詢對象 例句：我找大安高工附近或距離最近的日本料理 或 韓國菜 4-1.空間定位點 空間關係詞 Boolean 空間關係詞 查詢對象 屬性條件 Boolean 查詢對象 例句：我找大安高工附近或距離最近的餐廳像秀蘭 那樣或 韓國菜,空間查詢語句句型5 二個空間定位點、查詢對象個數為一、空間關係詞出現一次：,5-0.空間定位點 Boolean 空間定位點 空間關係詞 查詢對象 例句：我找大安高工 與中廣附近的日本料理 5-1. 空間定位點 Boolean 空間定位點 空間關係詞 查詢對象 屬性條件 例句：我找大安高工 或中廣附近像鼎泰豐之類的餐廳,空間查詢語句句型6 二個空間定位點、查詢對象個數為一、空間關係詞出現二次： 有兩種不同句型,6-0.空間定位點 Boolean 空間定位點 空間關係詞 Boolean 空間關係詞 查詢對象 例句：我找大安高工 與中廣附近或距離最近的日本料理 6-1.空間定位點 空間關係詞 Boolean 空間定位點 空間關係詞 查詢對象 例句：我找大安高工 附近或 離中廣 最近的餐廳,空間查詢語句句型7 二個空間定位點、查詢對象個數為二、空間關係詞出現一次：,7-0.空間定位點 Boolean 空間定位點 空間關係詞 查詢對象 Boolean 查詢對象 例句：我找大安高工 與中廣附近的 韓國菜和日本料理 7-1. 空間定位點 Boolean 空間定位點 空間關係詞 查詢對象 Boolean 屬性條件 查詢對象 例句：我找大安高工 與中廣附近的 韓國菜或 像上闔屋那樣的日本料理,空間查詢語句句型8 二個空間定位點、查詢對象個數為二、空間關係詞出現二次： 有兩種不同句型,8-0.空間定位點 Boolean 空間定位點 空間關係詞 Boolean 空間關係詞 查詢對象 Boolean 查詢對象 例句：我找大安高工 與中廣附近 或 距離最近的 韓國菜和日本料理 8-1.空間定位點空間關係詞查詢對象Boolean 空間定位點空間關係詞查詢對象 例句：我找大安高工 附近的 韓國菜或中廣附近的日本料理,系統建構及運作流程,1.系統設計 2.系統架構 3.系統實作 3.各模組運作方式 4.各類型語句所對應之空間運算定位方式,自然語言式GIS查詢介面資料庫架構圖,查詢對象屬性資料庫， 可依需要開放特定欄位作屬性條件查詢,系統架構圖,系統實作,實作對象：北市大安區之餐飲服務 使用軟體：VB + MO + Access資料庫 資料蒐集方式： 1.查詢對象資料庫： 餐飲資料服務，由網路美食討論站台及bbs美食討論精華區蒐集， 自行數化及建置其屬性資料，除名稱地址外，尚依所屬菜系等作分類 2.空間定位點資料庫： 以大安區重要地標、 一般道路、 道路交口，此三者作為空間定位之用，地標圖層由銳悌科技公司所產製的1/5000重要地標及設施圖層裁切出大安區範圍，一般道路圖採用工務局所製之1/5000街道圖自行裁切，道路交口點圖層則是以一般道路為底圖自行數化而得 3.空間關係資料庫： 附近、 最近兩種空間關係，於Access資料庫中，存成空間關係表，並建有同義詞,系統實作,處理斷詞之詞彙庫建置方式： 包括空間查詢語句主要構成元素、距離單位、布林敘述 1.查詢對象相關資料(餐飲服務) 此處視系統開放多少種屬性條件查詢而定，實作上開放以總稱、菜系、次菜系以及特定餐飲名稱查詢，故建置四個表：餐飲總稱(rest00) 、菜系大類別(rest01) 、菜系次類別(rest01d) ，及店家之名稱(restaurant) ，前三者有建同義字 2.空間定位點相關資料( 地標、路口、道路) 自已有之個別大安區空間圖層抽出屬性資料，各存於Access資料庫成地標資料表(mark) 、 道路交口資料表(inter) 、道路資料表(road)，均有建同義字,系統實作,處理斷詞之詞彙庫建置方式(續)： 包括空間查詢語句主要構成元素、距離單位、布林敘述 3.空間關係詞 附近、最近兩種空間關係類別，各存成modifier_a 、 modifier_b兩個表，並有建同義字 4.距離單位 公尺、公里，搭配空間關係作空間運算用，存成qualifier此表 5.布林敘述 處理且(and)、或(or)兩種，布林敘述出現之位置對語意判斷及空間運算均有影響，存成b_type此表，並建置同義字,詞彙庫之資料表種類,系統實作各模組運作方式,斷詞模組 將輸入之語句依序比對各資料表，找到相同之詞即存在以該資料表為名的陣列中，由於作空間查詢時最重要的是查詢的對象，也就是要找什麼，接下來才是相關之條件、以及其他語詞，故訂定比對順序 比對順序 查詢對象（餐飲服務）相關四個表（Restaurant Rest01d Rest01 Rest00）空間定位點三個相關表（Mark、Inter、Road）空間關係詞相關兩個表距離單位表布林敘述表。 每在一個資料表找到一筆符合資料，存在該資料表為名之陣列中繼續斷詞。,範例,斷詞模組說明,我找大安高工附近的義大利餐廳,例句：我找大安高工附近的義大利餐廳,Rest01d_arr(0) (3) = (義大利餐廳, 13, 10, 14),Rest00_arr(0)(3) = (餐廳, 1, 13, 14),Mark_arr(0)(3) =(大安高工, 26, 3, 6),Moda_arr(0)(3) = (附近, 1 , 7, 9),系統實作各模組運作方式,斷詞模組(續) 斷詞後可能會有詞重疊或是詞被遮蓋的問題，故作搶詞判斷，由兩個詞在句中起始結束位置間是否有重疊，判斷是否需要作搶詞處理 搶詞處理 此處僅對餐飲資料四個表相關陣列作處理，採長詞優先原則，判斷該詞歸屬後，再改變陣列，將判斷後不屬於該詞歸屬之詞之陣列元素刪除之,範例,斷詞模組搶詞處理說明,初步斷詞結果 Rest01d_arr(0) (3) = (義大利餐廳, 13, 10, 14) Rest00_arr(0)(3) = (餐廳, 1, 13, 14) Mark_arr(0)(3) =(大安高工, 26, 3, 6) Moda_arr(0)(3) = (附近, 1 , 7, 9),Rest01d_arr(2) = 10 Rest01d_arr (3) = 14,Rest00_arr(2) = 13 Rest00_arr (3) = 14,搶詞處理,範例,斷詞模組搶詞處理說明(續),Rest01d_arr(2) = 10 Rest01d_arr (3) = 14,Rest00_arr(2) = 13 Rest00_arr (3) = 14,採長詞優先原則 故義大利餐廳、餐廳兩者取義大利餐廳為其解,完整斷詞結果 Rest01d_arr(0) (3) = (義大利餐廳, 13, 10, 14) Mark_arr(0)(3) =(大安高工, 26, 3, 6) Moda_arr(0)(3) = (附近, 1 , 7, 9),系統實作各模組運作方式,語意判斷模組一 此部分處理1.屬性條件查詢，類似SQL中like的條件限制 我要找大安高工附近像是秀蘭那樣的餐廳 處理方式： 句中出現像是、比如等詞彙，即作屬性條件語意之推斷， 以出現位置較鄰近像是比如等詞彙之兩個餐飲服務表相關詞彙作判斷，判斷原則是當兩個不同類別的語詞出現時，以較小的類別為主，即將查詢對象限制到較小的類別，若是類別和餐飲服務名稱同時出現，則判斷是否該餐飲名稱上一層類別就是該出現之類別，若是，則以該類別為主，若否，則以落於兩者之間之另一個類別為查詢對象。最後再改變陣列之元素，即兩個餐飲服務取其中一個為查詢對象， 另一則將存於陣列中之資料移除,範例,語意判斷模組一說明 例句 像是中菜館之類的餐廳 像是北方菜之類的餐廳 像是北平半畝園之類的餐廳 像是北平半畝園之類的中菜館 像是北平半畝園之類的北方菜,判斷成找中菜館,判斷成找北方菜,判斷成找北方菜,判斷成找北方菜,判斷成找北方菜,系統實作各模組運作方式,語意判斷模組二 經過屬性條件處理後，將元素個數不為零之所有陣列存入一新陣列，將此新陣列依原所有個別陣列中字詞起始位置重新排序，另為一新陣列 轉成字串，即可知句中組成元素排列，作為空間查詢運作模組判斷句型之參考,範例,語意判斷模組二說明,Rest01d_arr(0) (3) = (義大利餐廳, 13, 10, 14) Mark_arr(0)(3) =(大安高工, 26, 3, 6) Moda_arr(0)(3) = (附近, 1 , 7, 9),系統實作各模組運作方式,空間查詢運作模組 根據已定義之語句處理類型及語句元素排列方式作對應之空間查詢運算,個數為二,例句：我要找大安高工附近的餐廳,查詢對象個數為一,各語句類型所對應之空間查詢及運算方式,句型一 空間定位點空間關係詞查詢對象 例句： 我要找中廣附近的餐廳,空間定位點,餐飲服務資料,各語句類型所對應之空間查詢及運算方式,句型二 空間定位點空間關係詞Boolean空間關係詞查詢對象 例句： 我要找中廣附近或距離最近的餐廳 當boolean = and， 空間關係為附近 最近 之交集 當boolean = or， 實際上是兩次空間查詢處理結果之聯集 1.我要找中廣附近的餐廳 2.我要找距離中廣最近餐廳,各語句類型所對應之空間查詢及運算方式,句型三 空間定位點空間關係詞 查詢對象 Boolean查詢對象 例句：我要找中廣附近日本料理或韓國菜 分解處理為：1.我要找中廣附近日本料理 2.我要找中廣附近韓國菜 當boolean = and，兩次查詢結果之聯集 當boolean = or，兩次查詢結果之聯集,夾在兩查詢對象間的boolean敘述and或or對查詢次數無影響,各語句類型所對應之空間查詢及運算方式,句型四 空間定位點空間關係詞 Boolean1 空間關係詞 查詢對象 Boolean2查詢對象 例句：我要找中廣附近或距離最近日本料理或韓國菜 分解處理： 當Boolean1 = and ，作兩次查詢 當Boolean1 = or ，作四次查詢,各語句類型所對應之空間查詢及運算方式,句型五 空間定位點A Boolean空間定位點B 空間關係詞查詢對象 例句：我要找中廣或大安高工附近的餐廳 分解處理： 當Boolean = and ， 定位點取原定位點A與原定位點B兩點連線之中點，作一次查詢 當Boolean = or ， 視之為求1.我要找中廣附近的餐廳 2.我要找大安高工附近的餐廳 作兩次查詢,各語句類型所對應之空間查詢及運算方式,句型六 空間定位點ABoolean1空間定位點B 空間關係詞A Boolean2空間關係詞B查詢對象 例句1：我要找在中廣與大安高工附近且距離最近的餐廳 例句2：我要找在中廣或大安高工附近或距離最近的餐廳 例句3：我要找在中廣與大安高工附近或距離最近的餐廳 例句4：我要找在中廣或大安高工附近且距離最近的餐廳 分解處理：例句1 查詢一次 例句2 查詢四次 例句3 查詢兩次 例句4 查詢兩次,各語句類型所對應之空間查詢及運算方式,句型七 空間定位點空間關係詞Boolean空間定位點空間關係詞查詢對象 例句：我要找中廣附近或離大安高工最近的餐廳 分解處理： 當Boolean = and ，視之為查詢對象要同時滿足兩空間條件，查詢 一次 1.中廣附近 2.離大安高工最近 兩者之交集 當Boolean = or ， 視之為求1.我要找中廣附近的餐廳 2.我要找離大安高工最近的餐廳 兩者查詢結果之聯集,各語句類型所對應之空間查詢及運算方式,句型八 空間定位點ABoolean1空間定位點B空間關係詞查詢對象A Boolean2查詢對象B 例句：我要找中廣或大安高工附近的日本料理和韓國菜 分解處理： 當Boolean1 = and ， 定位點取原定位點A與原定位點B兩點連線之中點，分別對查詢對象A,B作查詢 當Boolean1 = or ，所求為四次個別查詢結果之聯集,各語句類型所對應之空間查詢及運算方式,句型九 空間定位點ABoolean1空間定位點B空間關係詞ABoolean2 空間關係詞B查詢對象ABoolean