1. NCCU Academic Hub
  2. 學術產出
  3. College of Informatics
  4. Theses
  5. Item

學術產出-Theses

Article View/Open

Publication Export

Google ScholarTM

政大圖書館

Citation Infomation

  • No doi shows Citation Infomation
題名 質心范諾圖在選區重劃之應用
Using CVD in Electoral Redistricting
作者 吳振寰
Wu, Chen-Huan
貢獻者 何瑁鎧
Hor, Maw-Kae
吳振寰
Wu, Chen-Huan
關鍵詞 選區重劃
質心范諾圖
redistricting
centroidal voronoi diagram
日期 2009
上傳時間 9-Apr-2010 13:21:58 (UTC+8)
摘要 傳統之選區劃分多採用人工方式進行，不但費時耗力，同時不容易維持公平公正之原則，導致客觀性受扭曲而產生爭議。歷史上透過選區劃分來操弄選舉最有名的例子首推美國麻州的傑利蠑螈劃分方式，因此後人在選區劃分時必須堅守公平客觀之原則，自動化之選區劃分應運而生。以電腦科技自動劃分選區不但省時省力，同時也能滿足公平公正等客觀的選區劃分要求。
過去我們提出了一系列的選區劃分方法，著重於產生大量的劃分解集合，並從中挑選形狀較佳之解，卻沒有考慮到維持鄉鎮市層級行政區之完整性。本論文中，我們提出了一套新的選區劃分方式，除了考慮鄉鎮市層級行政區之完整性外，同時考慮選取較佳之起始點，以獲得較佳之選區形狀，成功的劃分出良好的選區。
我們首先從挑選較佳之起始點，透過質心范諾圖的觀念劃分出形狀較完整之初始選區，然後修正各選區之人口至合理的誤差範圍內，再進行鄉鎮市層級行政區分割數之修正，以避免該層級行政區被過渡分割。由於行政區分割數修正可能影響並擴大人口誤差，為確保人口誤差維持在合理範圍內，我們進行第二次人口修正，以免人口誤差過大，隨後進行形狀調整以提高凸包面積比，最後再度進行鄉鎮市層級行政區分割數修正，儘量少分割鄉鎮市層級之行政區域。
實作中我們以台北市為例，採用四組不同的起始點進行選區劃分，結果都十分良好。我們將中選會公佈之劃分法與這四組結果進行比較，中選會的劃分方式在行政區分割數上比我們的結果好，但在人口誤差與形狀上都不及我們的劃分方式優異。另外我們也選取行政中心為起始點進行劃分並將結果與中選會的結果比較，也獲得相同的結論。至於選情預估方面，我們也證實了不同的選區劃分方式的確將造成選舉結果之改變。
Traditionally, electoral redistricting was done manually which was time consumming, inefficient, and hard to maintain fairness. One of the most famous biased electoral redistricting in human history was proposed by Elbridge Gerry in 1812, socalled the Gerrymandering districting. After that, fairness and objectivity are required in every electoral redistricting and, hence, come to the era of automatic redistricting.
We have proposed a series of automatic electoral redistricting mechanisms that were emphasized on producing huge amount of feasible solutions and selecting the right solutions from them. However, we did not consider avoiding over partitioning a county in the proposed mechanisms. In this thesis, we developed a new mechanism for electoral redistricting which not only avoiding the over partitioning problem but also start the redistricting by chosing a better set of seeds.
Using a set of better seeds, we can get a better set of initial electoral districts through the help of centroidal Voronoi diagram. Then, we adjust the population in every district followed by reducing the partitioning number of each county. Since adjusting the county partitioning number may violate the population requirement of the districts, we shall check the population requirement of all the districts again before checking compactness of all the districts. Finally, we applied the county partitioning number reduction process once more to reduce the partitioning number as many as we can.
In the experiments, we used Taipei city to verify our mechanism. Four set of seeds were used to generate different redistricting solutions. We compared our results with the result announced by the Central Election Commission (CEC) and found that CEC’s results has better average county partitioning number but worse population error as well as worse compactness. We also used the administrative districts’ center as the seeds to generate the fifth redistricting solutions and obtained the same conclusion, i. e., CEC’s results has better average county partitioning number but worse population error as well as worse compactness. We also demonstrated that different redistricting results may change the election outcomes.
參考文獻 [1].李俊瑩，“應用基因演算法重劃選區”，碩士論文，政治大學資訊科學系，西元2006年
[2].何瑁鎧、李俊瑩、劉克鑛、游清鑫，“選區重劃之分析與探討”，TAAI 2005
[3].謝長紘，“計算幾何學在選區劃分上之分析與應用”，碩士論文，政治大學資訊科學系，西元2008年
[4].何瑁鎧、謝長紘，“計算幾何學在選區劃分上之分析與應用”，TAAI2008
[5].許宏敏，“多重選區劃分之分析與研究”，碩士論文，政治大學資訊科學系，西元2009年
[6].何瑁鎧、許宏敏，”多重選區劃分之分析與研究”，NCS2009
[7]. S.Hess, J.Weaver, H.Siegfeldt, J.Whealn and P.Zitlau, “Nonpartisan Political Redistricting by Computer” Operations Research 13, 1965
[8]. F. Bacao, V.Lobo, and M. Painho. “Applying genetic algorithms to zone design” Springer-Verlag , 2004
[9]. Gerrymandering, http://en.wikipedia.org/wiki/Gerrymandering
[10]. Voronoi diagram, http://en.wikipedia.org/wiki/Voronoi_diagram
[11]. Centroidal Voronoi diagram, http://en.wikipedia.org/wiki/Centroidal_Voronoi_tessellation
[12]. Texas style gerrymandering, http://www.commoncause.org/site/pp.asp?c=dkLNK1MQIwG&b=4849387
描述 碩士
國立政治大學
資訊科學學系
95753029
98
資料來源 http://thesis.lib.nccu.edu.tw/record/#G0095753029
資料類型 thesis
dc.contributor.advisor 何瑁鎧zh_TW
dc.contributor.advisor Hor, Maw-Kaeen_US
dc.contributor.author (Authors) 吳振寰zh_TW
dc.contributor.author (Authors) Wu, Chen-Huanen_US
dc.creator (作者) 吳振寰zh_TW
dc.creator (作者) Wu, Chen-Huanen_US
dc.date (日期) 2009en_US
dc.date.accessioned 9-Apr-2010 13:21:58 (UTC+8)-
dc.date.available 9-Apr-2010 13:21:58 (UTC+8)-
dc.date.issued (上傳時間) 9-Apr-2010 13:21:58 (UTC+8)-
dc.identifier (Other Identifiers) G0095753029en_US
dc.identifier.uri (URI) http://nccur.lib.nccu.edu.tw/handle/140.119/38540-
dc.description (描述) 碩士zh_TW
dc.description (描述) 國立政治大學zh_TW
dc.description (描述) 資訊科學學系zh_TW
dc.description (描述) 95753029zh_TW
dc.description (描述) 98zh_TW
dc.description.abstract (摘要) 傳統之選區劃分多採用人工方式進行，不但費時耗力，同時不容易維持公平公正之原則，導致客觀性受扭曲而產生爭議。歷史上透過選區劃分來操弄選舉最有名的例子首推美國麻州的傑利蠑螈劃分方式，因此後人在選區劃分時必須堅守公平客觀之原則，自動化之選區劃分應運而生。以電腦科技自動劃分選區不但省時省力，同時也能滿足公平公正等客觀的選區劃分要求。
過去我們提出了一系列的選區劃分方法，著重於產生大量的劃分解集合，並從中挑選形狀較佳之解，卻沒有考慮到維持鄉鎮市層級行政區之完整性。本論文中，我們提出了一套新的選區劃分方式，除了考慮鄉鎮市層級行政區之完整性外，同時考慮選取較佳之起始點，以獲得較佳之選區形狀，成功的劃分出良好的選區。
我們首先從挑選較佳之起始點，透過質心范諾圖的觀念劃分出形狀較完整之初始選區，然後修正各選區之人口至合理的誤差範圍內，再進行鄉鎮市層級行政區分割數之修正，以避免該層級行政區被過渡分割。由於行政區分割數修正可能影響並擴大人口誤差，為確保人口誤差維持在合理範圍內，我們進行第二次人口修正，以免人口誤差過大，隨後進行形狀調整以提高凸包面積比，最後再度進行鄉鎮市層級行政區分割數修正，儘量少分割鄉鎮市層級之行政區域。
實作中我們以台北市為例，採用四組不同的起始點進行選區劃分，結果都十分良好。我們將中選會公佈之劃分法與這四組結果進行比較，中選會的劃分方式在行政區分割數上比我們的結果好，但在人口誤差與形狀上都不及我們的劃分方式優異。另外我們也選取行政中心為起始點進行劃分並將結果與中選會的結果比較，也獲得相同的結論。至於選情預估方面，我們也證實了不同的選區劃分方式的確將造成選舉結果之改變。		zh_TW
dc.description.abstract (摘要) Traditionally, electoral redistricting was done manually which was time consumming, inefficient, and hard to maintain fairness. One of the most famous biased electoral redistricting in human history was proposed by Elbridge Gerry in 1812, socalled the Gerrymandering districting. After that, fairness and objectivity are required in every electoral redistricting and, hence, come to the era of automatic redistricting.
We have proposed a series of automatic electoral redistricting mechanisms that were emphasized on producing huge amount of feasible solutions and selecting the right solutions from them. However, we did not consider avoiding over partitioning a county in the proposed mechanisms. In this thesis, we developed a new mechanism for electoral redistricting which not only avoiding the over partitioning problem but also start the redistricting by chosing a better set of seeds.
Using a set of better seeds, we can get a better set of initial electoral districts through the help of centroidal Voronoi diagram. Then, we adjust the population in every district followed by reducing the partitioning number of each county. Since adjusting the county partitioning number may violate the population requirement of the districts, we shall check the population requirement of all the districts again before checking compactness of all the districts. Finally, we applied the county partitioning number reduction process once more to reduce the partitioning number as many as we can.
In the experiments, we used Taipei city to verify our mechanism. Four set of seeds were used to generate different redistricting solutions. We compared our results with the result announced by the Central Election Commission (CEC) and found that CEC’s results has better average county partitioning number but worse population error as well as worse compactness. We also used the administrative districts’ center as the seeds to generate the fifth redistricting solutions and obtained the same conclusion, i. e., CEC’s results has better average county partitioning number but worse population error as well as worse compactness. We also demonstrated that different redistricting results may change the election outcomes.		en_US
dc.description.tableofcontents 第一章 緒論.......................1
1. 研究動機....................... 1
2. 背景說明....................... 2
3. 問題描述....................... 3
4. 本研究與過去研究不同之處....................... 4
5. 論文貢獻....................... 5
6. 論文章節架構....................... 6
第二章 相關研究....................... 7
1. 線性規劃法....................... 7
2. 人口二分法與多重選區劃分法.......................7
3. 基因演算法....................... 9
第三章 系統架構....................... 11
1. 資料前處理....................... 11
2. 系統流程圖....................... 11
3. 系統說明....................... 14
第四章 挑選起始點與劃分初始選區.......................16
1. 挑選起始點....................... 17
1.1. 挑選起始點演算法....................... 17
1.2. 門檻值限制....................... 19
1.3. 門檻值挑選原則....................... 20
2. 初始選區劃分....................... 20
2.1. 范諾圖介紹....................... 20
2.2. 質心范諾圖介紹....................... 21
2.3. 劃分初始選區演算法....................... 23
2.4. 使用質心范諾圖劃分之原因....................... 24
第五章 人口調整與二級行政區分割數修正....................... 26
1. 人口調整....................... 26
1.1. 第一階段人口調整....................... 27
1.2. 第二階段人口調整....................... 29
2. 二級行政區分割數修正....................... 31
2.1. 二級行政區分割數修正....................... 31
2.2. 第二次分割數修正....................... 34
3. 連接性檢查....................... 35
第六章 選區形狀調整及選區劃分評估....................... 37
1. 選區形狀調整....................... 37
1.1. 選區形狀評估方式....................... 37
1.2. 凸包面積比不完備之處....................... 38
1.3. 形狀調整演算法....................... 38
1.4. 形狀調整前與調整後的結果比較....................... 42
2. 選區劃分評估....................... 45
2.1. 選區形狀評估....................... 45
2.2. 代入歷史選舉資料評估....................... 45
第七章 實驗結果....................... 47
1. 劃分結果....................... 47
1.1. 方式一....................... 47
1.1.1 初始選區階段....................... 47
1.1.2 人口調整以及行政區分割數修正階段.......................50
1.1.3 形狀調整階段....................... 53
1.1.4 評估....................... 54
1.2. 方式二....................... 60
1.2.1. 初始選區階段....................... 60
1.2.2. 人口調整以及行政區分割數修正階段.......................62
1.2.3. 形狀調整階段....................... 66
1.2.4. 評估....................... 66
1.3. 方式三....................... 72
1.3.1 初始選區階段....................... 72
1.3.2 人口調整以及行政區分割數修正階段.......................74
1.3.3. 形狀調整階段....................... 78
1.3.4. 評估....................... 78
1.4. 方式四....................... 83
1.4.1. 初始選區階段....................... 83
1.4.2. 人口調整以及行政區分割數修正階段.......................85
1.4.3. 形狀調整階段....................... 88
1.4.4. 評估....................... 89
2. 中選會劃分結果....................... 94
3. 劃分結果比較....................... 99
3.1. 凸包面積比比較....................... 99
3.2. 人口誤差比較....................... 101
3.3. 行政區分割數比較....................... 102
4. 第二次分割數修正後結果....................... 104
5. 以行政中心作為起始點劃分結果....................... 111
第八章 結論....................... 122
1. 結論....................... 122
2. 未來研究....................... 123
參考文獻....................... 125		zh_TW
dc.format.extent 9545377 bytes-
dc.format.mimetype application/pdf-
dc.language.iso en_US-
dc.source.uri (資料來源) http://thesis.lib.nccu.edu.tw/record/#G0095753029en_US
dc.subject (關鍵詞) 選區重劃zh_TW
dc.subject (關鍵詞) 質心范諾圖zh_TW
dc.subject (關鍵詞) redistrictingen_US
dc.subject (關鍵詞) centroidal voronoi diagramen_US
dc.title (題名) 質心范諾圖在選區重劃之應用zh_TW
dc.title (題名) Using CVD in Electoral Redistrictingen_US
dc.type (資料類型) thesisen
dc.relation.reference (參考文獻) [1].李俊瑩，“應用基因演算法重劃選區”，碩士論文，政治大學資訊科學系，西元2006年zh_TW
dc.relation.reference (參考文獻) [2].何瑁鎧、李俊瑩、劉克鑛、游清鑫，“選區重劃之分析與探討”，TAAI 2005zh_TW
dc.relation.reference (參考文獻) [3].謝長紘，“計算幾何學在選區劃分上之分析與應用”，碩士論文，政治大學資訊科學系，西元2008年zh_TW
dc.relation.reference (參考文獻) [4].何瑁鎧、謝長紘，“計算幾何學在選區劃分上之分析與應用”，TAAI2008zh_TW
dc.relation.reference (參考文獻) [5].許宏敏，“多重選區劃分之分析與研究”，碩士論文，政治大學資訊科學系，西元2009年zh_TW
dc.relation.reference (參考文獻) [6].何瑁鎧、許宏敏，”多重選區劃分之分析與研究”，NCS2009zh_TW
dc.relation.reference (參考文獻) [7]. S.Hess, J.Weaver, H.Siegfeldt, J.Whealn and P.Zitlau, “Nonpartisan Political Redistricting by Computer” Operations Research 13, 1965zh_TW
dc.relation.reference (參考文獻) [8]. F. Bacao, V.Lobo, and M. Painho. “Applying genetic algorithms to zone design” Springer-Verlag , 2004zh_TW
dc.relation.reference (參考文獻) [9]. Gerrymandering, http://en.wikipedia.org/wiki/Gerrymanderingzh_TW
dc.relation.reference (參考文獻) [10]. Voronoi diagram, http://en.wikipedia.org/wiki/Voronoi_diagramzh_TW
dc.relation.reference (參考文獻) [11]. Centroidal Voronoi diagram, http://en.wikipedia.org/wiki/Centroidal_Voronoi_tessellationzh_TW
dc.relation.reference (參考文獻) [12]. Texas style gerrymandering, http://www.commoncause.org/site/pp.asp?c=dkLNK1MQIwG&b=4849387zh_TW