20081204 進度報告。

這週的進度真的有點少
找最佳化理論的論文，花了好多時間
太數學的論文，看不懂就很難解釋，前後看了快三篇才找到一篇比較合適的

以上是題外話。

程式的部分，感覺不會很難
只是希望想說要怎麼寫才能達到相同效果又會耗費太多時間或是增加複雜度
跟登凱學長討論幾次後，總算有些概念，希望現階段就一步步按照流程完成

進度分為兩部份：

以下是研究的流程圖示：


1.這次主要在做machine learning中feature的建立，參考上次報告的論文
目前已經建立了12種features，仍有些feature尚未加入，之後會補上。
2.Data Collection，即收集文獻所測試的網頁，有三個部份：contact、Hotel和Pizza。
另外學生之前測試的網頁主要為school或是商家地址資訊。

其他，像是Related work的部分，已經有將上禮拜報告的論文加進去匯整
也已經開始寫Introduction和研究流程中最前面的部分。

未來的工作進度：
1.)盡快完成訓練資料
2.)完成網頁收集
3.)Introduction的撰寫

20081120 進度報告。

由於前幾個禮拜，找到一篇和目前研究方向極為相似的文獻
藉此次progress report，簡單介紹此論文所提出的方法及系統架構

1.參考文獻：High Accuracy Postal Address Extraction From Web Pages, Zheyuan Yu,
Dalhousie University, March 2007.請點此

2.論文摘要：此篇論文利用兩大類的方法做地址擷取，第一是Rule-Based Extraction Method，另
一個為Machine Learning Approach，前者包含reqular expression approach和
Gazetteer Based approach兩種系統。作者結合rule-based method和machine learning
為一hybrid system，增進precision。

3.系統架構：主要介紹machine learning系統架構


輸入網頁URL之後，將網頁的標籤刪去並且做tokenization，建立五種feature，分別為(1)Word Level,(2)Part-of-Speech Tagger(3)Geographical,(4)Puncuation,(5)Layout，利用Word n-gram Model產生每個token的n-gram，並建出每個n-gram的feature set給decision tree classifier做training和testing，其中decision tree classifier採用C4.5，將每個n-gram的中間項做標示分類，其中標示有四種：START,MIDDLE,END和OTHER。



然後，設起始為START，結束為END，中間至少要有一個MIDDLE，最多不能超過20個MIDDLE，輸出最後的擷取結果，即為所求的地址。

作者將rule-based approach和maching learning結合成hybrid system，主要將rule-based approach所產生的feature也加入maching learning中去作training。

最後，將這幾個系統做比較：



可看出原本machine learning的效果就蠻不錯，再加上rule-base approach補強缺失，增進precision。

4.測試網頁：作者提供DEMO網頁，網頁上註明只能擷取美國,加拿大和英國的地址。
學生用三個平常在測試程式的網頁來DEMO
(1)REI.COM
{2}School dictinary
(3)YellowPages
前兩個網頁內的地址，皆有被擷取出來，且沒有多餘資訊或是不完整的地方。
但第(3)個網頁，雖然是加拿大的地址，卻連一個地址都無法被擷取出來，不確定是否無法讀取某
些網頁格式的關係，可能要再多做些測試才知道。

5.整理研究方法：
學生所利用的方法，前面部份是利用state name和street suffix來做pattern
matching，找到可能的地址片段，之後的machine learning的部分想參考這篇論文的方法
藉由改善建立的feature或者是可以利用其他分類器來達到相同效果。這部分希望在這次的進
度報告後會有較清楚的方向，不過目前會朝這方向進行。

20080917 進度報告。

延續上週訂的進度目標，這次的進度主要著重在程式的撰寫上
將地址分成兩個部份：

1. location(包含street number、name、type...等)
2. Region (包含city、state、state code、country...等)

利用pattern matching的方式找出可能的地址片段
location使用street type當作pattern；region利用state name當作pattern。
顯示出的結果有兩種：

1.完整的地址片段(ex. 7810 N. Blackstone Ave. Fresno, CA 93720 如圖一)
2.有多餘資訊的地址片段 (ex.7810 N. Blackstone Ave. Fresno, CA 93720 (559)，如圖二)

圖一，為完整的地址片段，包含號碼、街道名字、城市、州名以及區碼等資訊，能標示在地圖上，而所用的測試網頁連結。












圖二，含有多餘的資訊，像是電話號碼的區碼等多餘的資訊，但仍舊可以標示在地圖上，所用的測試網頁連結。






又將之前的論文找出來閱讀，將網頁進行Tag Elimination及split成token之後，通常先將判斷每個token是屬於那種型態(ex.NUMBER、STREET、COUNTRY等型態)，先建立Address Rule(ex. address = NUMBER+STREET+CITY+STATR+COUNTRY)，再利用sliding window去作parsing，找出可能的地址片段，這樣的方法就需要對整個token做兩次處理動作，感覺較浪費時間，若以pattern match找出的片段效果差不多的話，就只需要對整個token做一次處理。

若將地址分成更多部份，獲得正確地址片段的可能性也能提高。

而資料庫的部分還在建立當中，尚未完成

另外目前在閱讀的論文為Supporting Web-based Address Extraction with Unsupervised Tagging,Berenike Loos and Chris Biemann,2008，之前閱讀相關machine learning的論文，也正在做整理。

未來進度目標：
1. 整體架構規劃圖
2. 考慮如果換個國家是否有相同效果
3. 地址格式分成更多細項部分
4. paper reading

20080903 進度報告。

這周的進度主要處理以下四個部份：
1.Paper Reading的部分，將不了解的部分列出來。
2.可先建立地址架構，架構中各部分，利用不同patter來作match並找出片段。
3.從線上找到需要的城市洲名等資源。
4.Machine Learning可用在擷取pattern找不到的部分，所以這部份會在研讀論文後在進行。

首先，閱讀論文的部分，經過多次詳讀後，比起先前較有些概念(論文原文部分在此，HTML版)
論文中主要的部分在提出一個top-down relational algorithm ─ SRV .
不清楚的部分有幾個：
1.(page3)在SRV的sub title中的Search SRV，文中提到proceeds as... as few negative example as possible.學生想問正反面的例子為何負面要少，如果負面的例子也多會有怎樣的情況？
2.(page4)Procedure中提出random和LOUO兩種partition，主要的用意為何？
3.(page5)Results中提到OPD和MPD two cases不是很明白，Table3和Table4中的80%和20%的coverage是的意義為何？(Table3中的OPD有80%和20%的coverage，但Table4中MPD只有20%的coverage.)

接著在網路上相關的國家、省份、城市的資訊其實都可在維基百科找到
資料的來源其實很好找尋，目前也就這些資料開始建立資料庫。

另外，決定先建立地址架構，利用架構中的每個子部分去作pattern matching的動作
需決定每個子部份需要用哪些pattern去進行match
程式的部分進度較少，還在撰寫中，會盡快完成。

接下來，主要進度目標為：
1.將論文再詳細閱讀一遍
2.進行程式的撰寫(初步建立地址架構)
3.建立資料庫

20080820 進度報告。

這次的進度，是根據上禮拜和老師討論的結果來進行
將所閱讀的參考論文做整理：

Reference：
1. Address Extraction: Extraction of Location-Based Information from the Web.
2. Effective Extraction of Addresses from Web page: A heuristic Pattern-Based
Approach.
3. Discovering Geographic Locations in Web pages Using Urban Addresses.
4. Postal address detection from the web documents.

[1]、[3]在處理地址擷取上，先建立地址架構，像[1]中的地址主要包含Suite Information(Building no.、Room no….etc) 、Municipal Location ( Street Number、Street type…etc)和regional Position ( City、Country…etc)三個部份，反之，[2]和[4]沒有初步建立地址架構。

[1]在前置處理網頁後，找出網頁內容中，彼此之間的相互關係，建立資料庫來進行concept identification的動作，最後再依照地址架構，利用node mapping完成擷取地址，不限於某些地區，所建立的資料庫量也較[2]小，但是主要的比對利用graph matching，會增加其複雜度。

[2]因為沒有先行建立地址架構，在前置處理網頁後，利用建立的知識資料庫、擷取規則、關鍵字、Address Patterns和Location Names進行比對，所需的資料庫，要建立大量的資料，即便precision和recall都較[1]高，但適用的範圍只限於某些國家或城市。

[3]和[1]的做法很相似，除了建立地址架構和前置處理，主要是利用pattern來比對，找出可能的地址資訊，再使用Gazetteer擷取出相對應的地址，著重在解決當地址資訊不是這麼完整的情況。

[4]也沒先行建立地址架構，但是利用將網頁切割成許多文字區塊，將主體區塊的內容加以辨別，建立資料庫及辨別規則來判斷內容是否為地址，用以偵測地址準確度相當高，但是由於測試的資料量過少，不確定整體效能是否如此高。


因此可改善的地方有：
1.擷取的範圍不受限單一國家或城市
2.地址資訊不論完整與否，都能擷取
3.減少辨別地址時的複雜度

首先，在處理完網頁Tag及將內容split成一個個token後(這部分學生想改用論文[4]的作法，利用DOM tree找到tag之間的文字片段)，利用pattern和keyword找出可能的地址片段後，將這些片段的內容對應上所屬的lexicon，引用[4]的做法，使用辨別規則來擷取地址資訊。

在閱讀論文方面，目前初步閱讀Information Extraction from HTML：Application of a General Machine Learning Approach論文一次，對其提出的做法SRV並不是很了解，這部分學生會再將論文內容再詳讀一次。另外學生不曉得如何將Machine Learning的技術在我所提出的做法中使用，也就是說，以輸入URL→網頁前置處理→找出candidate address segmentation→parsing片段對應lexicon→Extraction這樣的流程來看，machine learning該置放在哪個步驟進行。

之後進度目標：
1.Paper Reading的部分，將不了解的部分列出來。
2.可先建立地址架構，架構中各部分，利用不同patter來作match並找出片段。
3.從線上找到需要的城市洲名等資源。
4.Machine Learning可用在擷取pattern找不到的部分，所以這部份會在研讀論文後在進行。

20080806 進度報告。

首先說明之前研究的進度，在寄給老師的信件中已提到。

整個主體概念為：使用者輸入網頁URL之後，經過地址擷取的分析，將地址標示在Google Map上。


第一、就程式整合方面，先前是利用ASP.NET來撰寫整個程式，不過Google Map所提供
的API是利用Javascript，所以必須將這兩個部份做整合，但學生後來將整個程式改成用javascript來撰寫，也較能省去整合程式語言上的時間。

第二、整體概念上，學生已完成的部分有，輸入網頁URL，將網頁原始碼進行消去Tag的動作，再利用split把文字內容切成一個個token存於陣列當中。觀察大部分的地址資訊，學生利用street type作為關鍵詞的判斷依據，抓取關鍵詞的前後二到三個token，與關鍵詞形成字串後存入陣列中，其中學生所使用的street type關鍵詞有：Street、Road、Way、Avenue、Place、Boulevard、Place、Pkwy，相關的縮寫也有列入考慮。

第三、地址擷取分析的部分，是學生目前最需處理的一塊。信中原本提到網頁架構不一的問題，可能會在每個文字片段中間出現多餘的空格，昨天regular meeting完後，萍華提到說可以用regular expression來解決，之前學生只有利用regular expression來做Tag的消去，所以這部份也經過修改之後，目前已解決這問題。另外就是地址資訊中若沒有出現關鍵字詞需要如何判斷的問題，以及用這樣的方式，可能會因為國家之間的用詞不同而侷限住範圍，因此如果想要不受限各個國家或語言，這個部份也是個問題。

在和老師討論之後，學生目前需要完成的項目有：

1.就先前看過的論文作比較，列出其優缺點，然後比較自己的想法和其他篇論文的差異在哪裡，哪方面可以改善或補強。
2.建議可從Machine Learning的角度切入，這個部份就需要多找相關Machine Learning資料閱讀。
3.老師所給的兩篇參考資料：information extraction from HTML: application of a general machine learning approach.及The WHIRL approach to integration: an Overview。
而另外一篇是學生昨天找的參考資料：address extraction using Hidden Markov Model。

就接下來需要完成的部分，學生會盡量趕上進度。

20080707 進度報告。

延續上次的進度，研讀論文以及程式的寫作仍為主要兩個部份

首先，我所閱讀的論文裡頭，大多的理論參考這篇論文
因此這次詳讀之後，但仍有不懂的內容需要解惑

第一，如右圖所示，P代表< p >；B代表< b >；S1代表"IBM Corporation"

文中提到S1的位置可由它的sibling求算：S1.Top = B.Top+B.Height
其中S1.Top表示y-coordinate of the upper-left corner of S1
B.Height表示the geometry height of B
我不是很了解這個式子的意思。

另外，左邊是cue block和body block的位置相關圖
A表示cue block，B表示body block，α表示confidence
A.X >B.X||(B.X-A.X) < α 中A.X代表x-coordinate of upper-left corner of A
這部份也不是很懂

第二，程式部分目前需要做整合

由於程式中按下input URL按鈕後，會找到網頁中的相關地址資訊，秀在label上
這部分的程式撰寫於Sub Button1_Click中，使用ASP.NET
另外同時在地圖上標示出多個地址撰寫於function中，使用javascript
目前即要把所擷取到的資訊地址能放到javascript中的function
現在程式整合還尚未解決，除了在網路上找相關文件，也與同學討論是否能用smarty來做整合，所以會先考慮將程式整合後在進行擷取研究

接下來的工作

除了詳讀論文之外，整合程式的能力希望能多加強，也需撥空多加強基本背景知識，還有group meeting時老師我提到針對同儕互評後，根據互評內容將專題報告做修正

20080626 進度報告。

這週的進度，主要在閱讀paper以及實作兩個部份

1.paper reading：Postal Address Detection from Web Documents

學生大致上粗略看過一遍，內容分為兩部份：vision based text segmentation和recognition of postal address，先把網頁分段成各小的文字區塊，再利用syntactic approach的方法於區塊的內容進行辨識的動作。文字區塊分成兩種，一種是cue block，另一種是body block；前者包含indication、annotation和explanation，後者則包含像是地址、電話等資訊。




例如：圖中Mailing address區塊為cue block；IBM那區塊為body block，然後再是判別body block裡面是否為postal address。





2.Address Extraction：學生目前實作之前的想法，觀察大部分的地址格式中會出現的關鍵字詞，像是Road、Street、Blvd、Ave等街道的資訊，先將消去Tag後的網頁內容做split的動作，找出這幾個關鍵字詞後，並將其前後的幾個字詞也列入考慮，因為學生想說在街道的關鍵字前後，應該會出現相關的地址資訊，這樣所找出來的字串算是蠻完整的，可列作之後分析的candidate address，但是有些字串會少了些資訊，如果只有單純street number+street name所找出的地址和street number+street name+city(or state)所找到的地址會有所不同，即為ambiguity的問題。因此學生認為如要標示出地址位置，基本上街道、城市(或是國家)等關鍵字詞是不可或缺的，目前學生先利用街道的14種關鍵字(包含縮寫)來做擷取，對於地址格式完整的網頁成效還算可以，之後可能再從candidate address中利用regular expression做分析，去掉擷取到多餘的資訊，這部份學生還會再多實作來測試並觀看成效


另外學生目前比較想加強Information extraction相關的知識，因為學生認為自己的基本認知蠻薄弱的，學生也有在找資料閱讀，希望可以補強不足的部分。

20080602 進度報告。

前兩周的進度，因為期末報告有所延遲。

目前程式已完成Tag Elimination的部分

然後學生花蠻多時間了解如何操作ANNIE系統
輸入URL或是網頁原始碼都可以達到效果
經由ANNIE系統Run過後，在notation的攔位中
點選裡頭的Adddress和Location的結果不太相同

address所標示出來的大多是e-mail address和區碼
location所標示的比較為我們所需要的地址資訊

學生還在想說要如何將ANNIE系統應用在本身撰寫的程式上
另外也找了篇paper來閱讀，希望在這部份能有多點進度

接下來為期末考周，報告考試有點繁多
研究進度的部分，會盡量趕上。

20080502 進度報告。

學生此次的進度，因為選修課程期中考及報告作業
先前所找的paper，大致上粗略看過

1.Extracting Spatial Knowledge from the Web,2003

提出一個系統，從收集的web pages當中擷取spatial knowledge
利用geospatial information extraction、concepts extraction技術
其中包含geoparsing(將地址找出來)，geocoding(轉成座標)和keyword extraction等部份
2.Web-a-where: geotagging web content,2004

主要部份有三個：先是spotting(spotting place name candidates)，再者是disambiguation(disambiguation spots)，最後是foucs determination(其中包括許多演算法)，用以tag individual place name。

3.Extracting Geographical Knowledge from the Internet,2002

conduct 3 series of experiments：tuned system、TiMBL Memory Based Learner和C4.5 Decision Tree Induction Algorithm.
paper中提出6種classes，每個class有各自對應的keyword以及相對應的pattern
像是city是一種class，有四種keyword(city、town、mayor、street)，相對應pattern像是
city+of+x、x+city、town+of+x...等，再利用演算法找到比較match的pattern



這是目前看的情況，會找比較符合且可實作的部份先嘗試看看

20080416 進度報告。

Geocoding multiple addresses的部分
根據這個網頁的內容提到，如果使用.getLatLng()來作Geocoding的動作
建議利用Longer dealy，原本是用setTimeout(function,delay time)，但還是會有抓不到地
址的問題，因此參照網頁中的例子更改原本的程式，結果是可行的。
所以這部分算是解決了。

另外Address Extraction的部分
看過兩篇相關的paper：
1.Address Extraction：Extraction of location-Based Information From the Web
2.Effective Extraction of Address from Web pages： A Heuristic Pattern-Based Approach
目前只有先將抓下來的原始碼作Tag-Elimination，現在的想法是要如何找出address boundary
也在網路上找了幾篇參考的文件：
1.Extracting Spatial Knowledge from the Web,2003
2.Web-a-where: geotagging web content,2004
3.Extracting Geographical Knowledge from the Internet,2002
有關這部分，學生會再多找資料作為參考，思考出自己的方法。

20080320 進度報告。

本週進度主要是針對地址轉座標的問題, 找出相關API,
如果想要同時input多個地址，必須要先想辦法知道每個地址座標，然後再把這些座標一口氣加到map中，這樣每次就只需要1個request。但是Geocoder multiple addresses好像有些限制, 所以目前的想法是，先把input addresses轉成XML的格式或是KML file再利用Geocoding中的getLocations() 去讀取並標示在Map上.

然後就是KML的部分, KML是tag-based 的架構，蠻像XML，所有的tags都列在KML 2.2 Reference可以呈現geograhic data在Google Earth，Google Maps以及Google Maps for mobile上
Reference的部分還沒看完，哲民那邊的code好像還要再修改，所以還沒拿到

Address extraction的話，Input URL後所得的原始檔會先進行pre-process，像是Tag Elimination，先把會造成ambiguous的字彙消除. 基本上是以之前看的paper：address extraction:extraction of location-based information from the Web為基礎去implement
然後再作修改，目前只做了pre-process的部分.

20070320 進度報告。

本週進度主要是針對地址轉座標的問題, 找出相關API,
如果想要同時input多個地址，必須要先想辦法知道每個地址座標，然後再把這些座標一口氣加到map中，這樣每次就只需要1個request。但是Geocoder multiple addresses好像有些限制, 所以目前的想法是，先把input addresses轉成XML的格式或是KML file再利用Geocoding中的getLocations() 去讀取並標示在Map上.

然後就是KML的部分, KML是tag-based 的架構，蠻像XML，所有的tags都列在KML 2.2 Reference可以呈現geograhic data在Google Earth，Google Maps以及Google Maps for mobile上
Reference的部分還沒看完，哲民那邊的code好像還要再修改，所以還沒拿到

Address extraction的話，Input URL後所得的原始檔會先進行pre-process，像是Tag Elimination，先把會造成ambiguous的字彙消除. 基本上是以之前看的paper：address extraction:extraction of location-based information from the Web為基礎去implement
然後再作修改，目前只做了pre-process的部分.