讀古今文學網 > 機器學習實戰 > 10.4 示例：對地圖上的點進行聚類 >

10.4 示例：對地圖上的點進行聚類

假如有這樣一種情況：你的朋友Drew希望你帶他去城裡慶祝他的生日。由於其他一些朋友也會過來，所以需要你提供一個大家都可行的計劃。Drew給了你一些他希望去的地址。這個地址列表很長，有70個位置。我把這個列表保存在文件portland-Clubs.txt中，該文件和源代碼一起打包。這些地址其實都在俄勒岡州的波特蘭地區。

也就是說，一晚上要去70個地方！你要決定一個將這些地方進行聚類的最佳策略，這樣就可以安排交通工具抵達這些簇的質心，然後步行到每個簇內地址。Drew的清單中雖然給出了地址，但是並沒有給出這些地址之間的距離遠近信息。因此，你要得到每個地址的緯度和經度，然後對這些地址進行聚類以安排你的行程。

示例：對於地理數據應用二分k均值算法

  1. 收集數據：使用Yahoo! PlaceFinder API收集數據。
  2. 準備數據：只保留經緯度信息。
  3. 分析數據：使用Matplotlib來構建一個二維數據圖，其中包含簇與地圖。
  4. 訓練算法：訓練不適用無監督學習。
  5. 測試算法：使用10.4節中的biKmeans函數。
  6. 使用算法：最後的輸出是包含簇及簇中心的地圖。

你需要一個服務來將地址轉換為緯度和經度。幸運的是，雅虎提供了這樣的服務。下面將介紹Yahoo! PlaceFinder API的使用方法。然後，對給出的地址坐標進行聚類，最後畫出所有點以及簇中心，並看看聚類結果到底如何。

10.4.1　Yahoo! PlaceFinder API

雅虎的牛人們已經為我們提供了一個免費的地址轉換API，該API對給定的地址返回該地址對應的緯度與經度。訪問下面的URL可以瞭解更多細節：http://developer.yahoo.com/geo/placefinder/guide/。

為了使用該服務，需要註冊以獲得一個API key。具體地，你需要在Yahoo!開發者網絡（http://developer.yahoo.com/）中進行註冊。創建一個桌面應用後會獲得一個appid。需要appid來使用geocoder。一個geocoder接受給定地址，然後返回該地址對應的經緯度。下面的代碼將上述所有過程進行了封裝處理。打開kMeans.py文件，然後加入下列代碼。

程序清單10-4　Yahoo! PlaceFinder API 

import urllib
import json
def geoGrab(stAddress, city):
    apiStem = \'http://where.yahooapis.com/geocode?\'
    params = {}
    #❶ 將返回類型設為JSON 
    params[\'flags\'] = \'J\'
    params[\'appid\'] = \'ppp68N8t\'
    params[\'location\'] = \'%s %s\' % (stAddress, city)
    url_params = urllib.urlencode(params)
    yahooApi = apiStem + url_params
    #❷ 打印輸出的的URL
    print yahooApi
   c=urllib.urlopen(yahooApi)
    return json.loads(c.read)

from time import sleep
def massPlaceFind(fileName):
    fw = open(\'places.txt\', \'w\')
    for line in open(fileName).readlines:
        line = line.strip
        lineArr = line.split(\'t\')
        retDict = geoGrab(lineArr[1], lineArr[2])
        if retDict[\'ResultSet\'][\'Error\'] == 0:
            lat = float(retDict[\'ResultSet\'][\'Results\'][0][\'latitude\'])
            lng = float(retDict[\'ResultSet\'][\'Results\'][0][\'longitude\'])
            print \"%st%ft%f\" % (lineArr[0], lat, lng)
            fw.write(\'%st%ft%fn\' % (line, lat, lng))
        else: print \"error fetching\"
        sleep(1)
    fw.close

上述程序包含兩個函數：geoGrab與massPlaceFind。函數geoGrab從Yahoo返回一個字典，massPlaceFind將所有這些封裝起來並且將相關信息保存到文件中。

在函數geoGrab中，首先為Yahoo API設置apiStem，然後創建一個字典。你可以為字典設置不同值，包括flags = J，以便返回JSON格式的結果❶。（不用擔心你不熟悉JSON，它是一種用於序列化數組和字典的文件格式，本書不會看到任何JSON。JSON是JavaScript Object Notation的縮寫，有興趣的讀者可以在www.json.org找到更多信息。）接下來使用urllib的urlencode函數將創建的字典轉換為可以通過URL進行傳遞的字符串格式。最後，打開URL讀取返回值。由於返回值是JSON格式的，所以可以使用JSON的Python模塊來將其解碼為一個字典。一旦返回了解碼後的字典，也就意味著你成功地對一個地址進行了地理編碼。

程序清單10-4中的第二個函數是massPlaceFind。該函數打開一個tab分隔的文本文件，獲取第2列和第3列結果。這些值被輸入到函數geoGrab中，然後需要檢查geoGrab的輸出字典判斷有沒有錯誤。如果沒有錯誤，就可以從字典中讀取經緯度。這些值被添加到原來對應的行上，同時寫到一個新的文件中。如果有錯誤，就不需要去抽取緯度和經度。最後，調用 sleep函數將massPlaceFind函數延遲1秒。這樣做是為了確保不要在短時間內過於頻繁地調用API。如果頻繁調用，那麼你的請求可能會被封掉，所以將massPlaceFind函數的調用延遲一下比較好。

保存kMeans.py文件後，在Python提示符下輸入： 

>>> reload(kMeans)
<module \'kMeans\' from \'kMeans.py\'>

要嘗試geoGrab，輸入街道地址和城市的字符串，比如： 

>>> geoResults=kMeans.geoGrab(\'1 VA Center\', \'Augusta, ME\')
http://where.yahooapis.com/
     geocode?flags=J&location=1+VA+Center+Augusta%2C+ME&appid=ppp68N6k

實際使用的URL會被打印出來，通過這些URL，用戶可以看到具體發生了什麼。如果並不想看到URL，那麼將程序清單10-4中的print語句註釋掉也沒關係。下面看一下返回結果，應該是一個很大的字典。 

>>> geoResults
{u\'ResultSet\': {u\'Locale\': u\'us_US\', u\'ErrorMessage\': u\'No error\',u\'Results\':[{u\'neighborhood\': u\'\', u\'house\': u\'1\', u\'county\': u\'Kennebec County\', u\'street\': u\'Center St\', u\'radius\': 500, u\'quality\': 85, u\'unit\':u\'\', u\'city\': u\'Augusta\', u\'countrycode\': u\'US\', u\'woeid\': 12759521,
u\'xstreet\': u\'\', u\'line4\': u\'United States\', u\'line3\': u\'\', u\'line2\':u\'Augusta, ME 04330-6410\', u\'line1\': u\'1 Center St\', u\'state\': u\'Maine\',u\'latitude\': u\'44.307661\', u\'hash\': u\'B8BE9F5EE764C449\', u\'unittype\': u\'\',u\'offsetlat\': u\'44.307656\', u\'statecode\': u\'ME\',u\'postal\': u\'04330-6410\',u\'name\': u\'\', u\'uzip\': u\'04330\', u\'country\': u\'United States\',u\'longitude\': u\'-69.776608\', u\'countycode\': u\'\', u\'offsetlon\': u\'-69.776528\',u\'woetype\': 11}], u\'version\': u\'1.0\', u\'Error\': 0, u\'Found\': 1,u\'Quality\': 87}}

上面給出的是一部只包含鍵ResultSet的字典，該字典又包含分別以Locale、ErrorMessage、Results、version、Error、Found和Quality為鍵的其他字典。

讀者可以看一下所有這些鍵的內容，不過我們主要感興趣的還是Error和Results。

Error鍵值給出的是錯誤編碼。0意味著沒有錯誤，其他任何值都代表沒有獲得要找的地址。可以輸入下面內容以獲得錯誤編碼： 

>>> geoResults[\'ResultSet\'][\'Error\']
 0

現在看一下緯度和經度，可以輸入如下命令來實現： 

>>> geoResults[\'ResultSet\'][\'Results\'][0][\'longitude\']
u\'-69.776608\'
>>> geoResults[\'ResultSet\'][\'Results\'][0][\'latitude\']
u\'44.307661\'

上面給出的都是字符串，可以使用float函數將它們轉換為浮點數。下面看看在多行上的運行效果，輸入命令執行程序清單10-4中的第二個函數： 

>>> kMeans.massPlaceFind(\'portlandClubs.txt\')
Dolphin II 45.486502 -122.788346
                            .
                            .
Magic Garden 45.524692 -122.674466
Mary\'s Club 45.535101 -122.667390
Montego\'s 45.504448 -122.500034

這會在你的工作目錄下生成一個稱為places.txt的文本文件。接下來將使用這些點進行聚類，並將俱樂部以及它們的簇中心畫在城市地圖上。

10.4.2　對地理坐標進行聚類

現在我們有一個包含格式化地理坐標的列表，接下來可以對這些俱樂部進行聚類。在此過程中使用Yahoo! PlaceFinder API來獲得每個點的緯度和經度。下面需要使用這些信息來計算數據點與簇質心的距離。

這個例子中要聚類的俱樂部給出的信息為經度和維度，但這些信息對於距離計算還不夠。在北極附近每走幾米的經度變化可能達到數10度；而在赤道附近走相同的距離，帶來的經度變化可能只是零點幾。可以使用球面餘弦定理來計算兩個經緯度之間的距離。為實現距離計算並將聚類後的俱樂部標識在地圖上，打開kMeans.py文件，添加下面程序清單中的代碼。

程序清單10-5　球面距離計算及簇繪圖函數 

def distSLC(vecA, vecB):
    a = sin(vecA[0,1]*pi/180) * sin(vecB[0,1]*pi/180)
    b = cos(vecA[0,1]*pi/180) * cos(vecB[0,1]*pi/180) * cos(pi * (vecB[0,0]-vecA[0,0]) /180)
    return arccos(a + b)*6371.0

import matplotlib
import matplotlib.pyplot as plt
def clusterClubs(numClust=5):
    datList = 
    for line in open(\'places.txt\').readlines:
        lineArr = line.split(\'t\')
        datList.append([float(lineArr[4]), float(lineArr[3])])
    datMat = mat(datList)
    myCentroids, clustAssing = biKmeans(datMat, numClust, distMeas=distSLC)
    fig = plt.figure
    rect=[0.1,0.1,0.8,0.8]
    scatterMarkers=[\'s\', \'o\', \'^\', \'8\', \'p\', \'d\', \'v\', \'h\', \'>\', \'<\']
    axprops = dict(xticks=, yticks=)
    ax0=fig.add_axes(rect, label=\'ax0\', **axprops)
    imgP = plt.imread(\'Portland.png\')
    #❶  基於圖像創建矩陣
    ax0.imshow(imgP)
    ax1=fig.add_axes(rect, label=\'ax1\', frameon=False)
    for i in range(numClust):
        ptsInCurrCluster = datMat[nonzero(clustAssing[:,0].A==i)[0],:]
        markerStyle = scatterMarkers[i % len(scatterMarkers)]
        ax1.scatter(ptsInCurrCluster[:,0].flatten.A[0],ptsInCurrCluster[:,1].flatten.A[0],marker=markerStyle, s=90)
    ax1.scatter(myCentroids[:,0].flatten.A[0],myCentroids[:,1].flatten.A[0], marker=\'+\', s=300)
    plt.show

上述程序清單包含兩個函數。第一個函數distSLC返回地球表面兩點之間的距離。第二個函數clusterClubs將文本文件中的俱樂部進行聚類並畫出結果。

函數distSLC返回地球表面兩點間的距離，單位是英里。給定兩個點的經緯度，可以使用球面餘弦定理來計算兩點的距離。這裡的緯度和經度用角度作為單位，但是sin以及cos以弧度為輸入。可以將角度除以180然後再乘以圓周率pi轉換為弧度。導入NumPy的時候就會導入pi。

第二個函數clusterClubs只有一個參數，即所希望得到的簇數目。該函數將文本文件的解析、聚類以及畫圖都封裝在一起，首先創建一個空列表，然後打開places.txt文件獲取第4列和第5列，這兩列分別對應緯度和經度。基於這些經緯度對的列表創建一個矩陣。接下來在這些數據點上運行biKmeans並使用distSLC函數作為聚類中使用的距離計算方法。最後將簇以及簇質心畫在圖上。

為了畫出這些簇，首先創建一幅圖和一個矩形，然後使用該矩形來決定繪製圖的哪一部分。接下來構建一個標記形狀的列表用於繪製散點圖。後邊會使用唯一的標記來標識每個簇。下一步使用imread函數基於一幅圖像來創建矩陣❶，然後使用imshow繪製該矩陣。接下來，在同一幅圖上繪製一張新的圖，這允許你使用兩套坐標系統並且不做任何縮放或偏移。緊接著，遍歷每一個簇並將它們一一畫出來。標記類型從前面創建的scatterMarkers列表中得到。使用索引i % len(scatterMarkers)來選擇標記形狀 ，這意味著當有更多簇時，可以循環使用這些標記。最後使用十字標記來表示簇中心並在圖中顯示。

下面看一下實際效果，保存kMeans.py並在Python提示符下輸入如下命令： 

>>> reload(kMeans)
<module \'kMeans\' from \'kMeans.py\'>
>>> kMeans.clusterClubs(5)
sseSplit, and notSplit: 3073.83037149 0.0
the bestCentToSplit is: 0
                       .
                       .
                       .
sseSplit, and notSplit: 307.687209245 1118.08909015
the bestCentToSplit is: 3
the len of bestClustAss is: 25

執行上面的命令後，會看到與圖10-4類似的一個圖。

圖10-4　對俄勒岡州波特蘭市夜生活娛樂地點的聚類結果

可以嘗試輸入不同簇數目得到程序運行的效果。什麼數目比較好呢？ 讀者可以思考一下這個問題。

    機器學習實戰