python k 近邻实现

knn.py

# coding: utf-8

#########################################
# kNN: k Nearest Neighbors

# Input:      newInput: vector to compare to existing dataset (1xN)
#             dataSet:  size m data set of known vectors (NxM)
#             labels:   data set labels (1xM vector)
#             k:        number of neighbors to use for comparison

# Output:     the most popular class label
#########################################

from numpy import *
import operator
import jieba.analyse


def cut_word(content):
    '''
    (u'\u65b9\u5e84', 2.4582479479)
    (u'\u82b3\u57ce\u56ed', 1.19547675029)
    (u'\u53ef\u6708\u4ed8', 1.19547675029)
    (u'\u4e00\u533a', 1.04666904475)
    (u'\u5355\u95f4', 1.02371160058)
    (u'\u51fa\u79df', 0.832472854883)
    (u'\u5730\u94c1', 0.8200234078590001)
    (u'\u4e2d\u4ecb', 0.7891864466530001)
    (u'\u9644\u8fd1', 0.516934129144)
    '''
    tags = jieba.analyse.extract_tags(content, withWeight=True, topK=20)
    return tags


def merge_tags(*tags):
    tag_dict_list = []
    v_list = []
    for tag in tags:
        tag_dict_list.append({i[0]: i[1] for i in tag})

    merged_tag = []
    for i in tag_dict_list:
        merged_tag.extend(i.keys())

    merged_tag = set(merged_tag)
    for tag_dict in tag_dict_list:
        v = []
        for i in merged_tag:
            if i in tag_dict:
                v.append(tag_dict[i])
            else:
                v.append(0)
        v_list.append(v)
    return v_list


def kNNClassify(newInput, dataSet, labels, k):
    numSamples = dataSet.shape[0]  # shape[0] 代表行的数目

    # 步骤1：计算欧几里得距离
    diff = tile(newInput, (numSamples, 1)) - dataSet
    squaredDiff = diff ** 2
    squaredDist = sum(squaredDiff, axis=1)
    distance = squaredDist ** 0.5

    # 步骤2：对距离排序
    sortedDistIndices = argsort(distance)

    classCount = {}
    for i in xrange(k):
        # 步骤3：选择最近的 k 个距离
        voteLabel = labels[sortedDistIndices[i]]
        # 步骤4：对 label 次数计数
        classCount[voteLabel] = classCount.get(voteLabel, 0) + 1

    # 步骤5：返回投票最大的结果
    sortedClassCount = sorted(classCount.iteritems(), key=operator.itemgetter(1), reverse=True)
    return sortedClassCount[0][0]


if __name__ == '__main__':

    # 租房相关
    content1 = u"""
                可月付 无中介 方庄地铁附近 芳城园一区单间出租
                我的房子在方庄地铁附近的芳城园一区，正规小区楼房，
                三家合住，现出租一间主卧和一间带小阳台次卧，室内家电齐全，
                冰箱，洗衣机等都有，可洗澡上网，做饭都可以，小区交通便利，四通八达，
                希望入住的是附近正常上班的朋友
                """
    content2 = u"""
                可月付 无中介 方庄地铁附近 芳城园一区主卧次卧出租
                我的房子在方庄地铁附近的芳城园一区，正规小区楼房，
                三家合住，现出租一间主卧和一间带小阳台次卧，室内家电齐全，
                冰箱，洗衣机等都有，可洗澡上网，做饭都可以，小区交通便利，四通八达，
                希望入住的是附近正常上班的朋友
                """

    content3 = u"""方庄地铁附近 芳城园一区次卧出租
                    我的房子在方庄地铁附近的芳城园一区，正规小区楼房，
                    三家合住，现出租一间主卧和一间带小阳台次卧，室内家电齐全，
                    冰箱，洗衣机等都有，可洗澡上网，做饭都可以，小区交通便利，四通八达，
                    希望入住的是附近正常上班的朋友
                    """

    test_content4 = u"""二环玉蜓桥旁下月27号后可入住二居
                方庄方古园一区5号楼下月27日到期出租，
                我是房主无中介费 ，新一年租6000元每月押一付三，主次卧可分开住。
                距地铁5号线蒲黄榆站5分钟路程。房屋60平正向，另有看守固定车位。
                """
    # 旅游相关
    content5 = u"""世界尽头和冷酷仙境 去南极大部分都是从乌斯怀亚出发，
                        这是南美大陆的最南端，所以也被称为世界尽头。在这里，有很多东西都已经到了终点：
                        世界最尽头的邮局；世界最尽头的徒步线路；还有传说中“泛美公路”的终点，
                        这条路从阿拉斯加一路向南开过来，17848公里，开到这里居然也到头了，没路了…然而，
                        世界尽头也可以是起点，这里距离南极大陆只有不到1000公里的距离，世界尽头之后就是冷酷仙境。
                """
    content6 = u"""走 走停停，看看世界上其中一条最美丽最浪漫的海岸线：那不勒斯湾到amalfi 海岸。
                    欧洲 最美是小镇，意大利南部小镇与北部山区小镇完全不一样的风格但又一样是浪漫和美丽的世 外桃源。
                    这个海岸线之所以美，原因跟托斯卡纳的山区一样， 建筑与自然的完美融合。海、 山与小屋群形成了一副美丽的风景画。
                    沿着铁路和公路，陆路从那不勒斯走到Amalfi。
                """
    content7 = u"""仙本娜是一个几乎由潜水业支撑的小镇，走几步路就是潜店，
                    来自世界各地的游客每个人都在说着潜水。不大，但是比起马布就丰富多了，
                    有旅馆，酒吧，咖啡店，饭店，小卖部，还有一个大超市。到了仙本娜，
                    去一间叫龙门客栈（DRAGON ING）的旅馆CHECK IN。这是一件建在水上的树皮旅馆，
                    不论室内室外的墙面全部是树皮，很有原始的风味，房间内有冷风机，价格也不贵，66马币，
                    一个大床，有电视机，带卫生间。从马布搬过来，觉得这个环境真是天堂。旅馆由水上的很多长廊组成，
                    连成一条网，我几乎迷路。

                """
    test_content8 = """ 环游世界当然不能真地把旅行都抛掉啦，伟大的古文明和异国文化是环游世界的其中一个重要目的。
                    美洲的玛雅文明，非洲的埃及文明，亚洲的印度文明，一个个从人类起源就可以追溯的古文明。
                    一个个让人目定口呆的世界文化遗产。感受人类的力量同时感受时间的伟大和残酷。 还有令人陶醉的异国文化，去捷克感受的波西米亚文化，
                    到伦敦西区和纽约百老汇看歌舞剧等等，品味澳大利亚的葡萄酒苏格兰的威士忌墨西哥的龙舌兰。有时候，小资也是一种情调啊！
                """

    tag1 = cut_word(content1)
    tag2 = cut_word(content2)
    tag3 = cut_word(content3)
    tag4 = cut_word(test_content4)
    tag5 = cut_word(content5)
    tag6 = cut_word(content6)
    tag7 = cut_word(content7)
    tag8 = cut_word(test_content8)

    v = [tag1, tag2, tag3, tag4, tag5, tag6, tag7, tag8]
    data = merge_tags(*v)

    v4 = data.pop(3)
    v8 = data.pop()

    dataSet = array(data)
    labels = array(['租房', '租房', '租房', '旅游', '旅游', '旅游'])

    k = 3
    v4 = array(v4)

    outputLabel = kNNClassify(v4, dataSet, labels, k)
    print "Your input is: v4 and classified to class: ", outputLabel

    v8 = array(v8)
    outputLabel = kNNClassify(v8, dataSet, labels, k)
    print "Your input is: v8 and classified to class: ", outputLabel