使用图算法寻找独立用户

最近有同事问了我一个数据处理的问题，给定一组数据（n行2列），第一列是手机号码，第二列是第一列中手机号码的机主（独立用户，以身份证明为id）的另外一个号码（每个机主可能有多个手机号码）。考虑到数据敏感性，我用英文大写字母模拟手机号码，数据长这样：

原始数据（脱敏）

他们想要知道有多少独立用户（机主），并且这个机主有哪些号码。就上面的数据来说，A, C, B, E, F其实都是属于同一个机主的。

我的思路如下：
把号码及号码的对应关系看成一个无向图，每个号码就是一个节点，号码与号码之间的对应关系就是一条边。要寻找所有的机主，其实就是找这个无向图的所有连通分量。而每个机主有哪些号码，其实就是他的连通分量里面的所有节点。

考虑到逻辑比较复杂，我用Python来实现：

# 首先加载一些包
from pandas import Series, DataFrame
import pandas as pd
import numpy as np

# 数据导入（这个数据就是上面的示例数据啦）
col_names = ['no1','no2']
data = pd.read_table('test data.txt',sep=',',header=None,names=col_names)

# 数据转换，转换为以字典表示的无向图
## 定义辅助函数gen_graph()
def gen_graph(load_data):
    """
    把输入数据转化为以字典表示的无向图
    """ 
    graph = {}
    for i in xrange(len(load_data)):
        if data['no1'][i] not in graph.keys():
            graph[data['no1'][i]] = set([data['no2'][i]])
        else:
            graph[data['no1'][i]].add(data['no2'][i])
    
        if data['no2'][i] not in graph.keys():
            graph[data['no2'][i]] = set([data['no1'][i]])
        else:
            graph[data['no2'][i]].add(data['no1'][i])
    
    return graph

# 看下转化后的数据
telno_graph = gen_graph(data)
telno_graph

转化为无向图的数据

# 下面我们定义一些常用的图算法来帮助我们实现统计
from collections import deque

def bfs_visited(ugraph, start_node):
    """
    输入无向图ugraph和一个节点start_node
    返回从这个节点出发，通过广度优先搜索访问的所有节点的集合
    """
    # initialize Q to be an empty queue
    que = deque()
    # initialize visited
    visited = [start_node]
    # enqueue(que, start_node)
    que.append(start_node)
    while len(que) > 0:
        current_node = que.popleft()
        neighbours = ugraph[current_node]
        for nei in neighbours:
            if nei not in visited:
                visited.append(nei)
                que.append(nei) 
    return set(visited)

def cc_visited(ugraph):
    """
    输入无向图ugraph
    返回一个list，list的元素是每个连通分量的节点构成的集合
    """
    remaining_nodes = ugraph.keys()
    connected_components = []
    while len(remaining_nodes) > 0 :
        # choose the first element in remaining_nodes to be the start_node
        start_node = remaining_nodes[0]
        # use bfs_visited() to get the connected component containing start_node
        con_component = bfs_visited(ugraph, start_node)
        # update connected_components
        connected_components.append(con_component)
        # update remaining_nodes
        remaining_nodes = list(set(remaining_nodes) - con_component)
    return connected_components

# 看看算法的结果如何
user_nos =cc_visited(telno_graph)
user_nos

连通分量集合

现在我们知道了数据里面一共有多少独立用户，每个用户有哪些号码了。下一步，做数据整合，把数据整合成一个表，列名分别为独立用户id, 实名号码，实名号码个数，具体如下：

# user_nos的每个元素是集合形式，先转化成list
def to_list_elements(x):
    return list(x)

set_to_list = np.frompyfunc(to_list_elements,1,1)
user_nos = np.array(user_nos)
user_nos = set_to_list(user_nos)
user_nos

集合转化为list

# 对user_nos的每个元素，求长度
len_them = np.frompyfunc(len,1,1)
user_nos_count =len_them(user_nos)

# 整合
combined_data= np.array([np.arange(len(user_nos)),user_nos,user_nos_count]).T
output = DataFrame(combined_data,columns=['独立用户id','实名号码','实名个数'])
output

最终结果

#导出csv格式数据
output.to_csv('test_output.csv')

好了，收工了，吃饭去吧。