Sumnous's Blog

LEARN TO DEATH

2013-Data Fusion_Resolving Conflicts From Multiple Sources-PaperNote

paper link

问题现状背景

数据管理应用需要整合多个来源的数据，这些多个来源的数据有可能冲突，为了提供数据的质量，需要解决冲突以及发掘反应真实世界的values，这个过程也叫做数据融合。

传统的方法是投票

论文的贡献（解决的问题）

本文提出了一种在大量有冲突的数据源中发现true values的数据融合方法，并且数据源之间可以copy。

  1. 考虑数据源之间copy的情况（但不支持两个数据源互相copy）
  2. truth discovery准确率提高
  3. 可扩展到大数据源的情况

举例

本文用一个例子，详细的对应计算贯穿全文，便于理解。

主要方法/特征

Intuition：

  1. 共享正确的值不一定表明copy，但如果两个源独立则共享错误值是一个低概率事件。
  2. 考虑投票的准确性（数据源的准确性用概率表示，需要鉴别数据源的独立性以及哪个源是copier）

Source Accuracy in data fusion

Problem: 给定数据源，对于每一个object确定其true value

计算一个数据源的准确性概率：

将数据源S的accuracy记作A(S)，计算方式为源中所有值为真的平均概率，S提供一个特定错误值的概率为(1-A(S))/n。

计算一个value为真的概率：

采用贝叶斯概率计算一个值为真的概率P(v)=Pr(v true/O的所有观察值)，通过计算先验概率Pr(O的所有观察值/v true)，Pr(O的所有观察值)

为了简化计算，v的置信度(confidence)记作C(v)，数据源的准确分数记作A’(S)，则C(v)为所有数据源分数的求和，P(v)也可以用C(v)表示。

Copying relationships in data fusion

分两种数据源：独立和有copy关系。

两个数据源提供的值分三种情况：Ot表示S1和S2提供相同的true value；Of表示S1和S2提供相同的false value；Od表示S1和S2提供different value；这三种value集合共同构成Phi空间。

依然采用贝叶斯概率，分别计算Pr(Phi/S1与S2独立)，Pr(Phi/S1->S2)，Pr(Phi/S2->S1)，可由此计算Pr(S1与S2独立/Phi)

Independent Vote Count of a Value

即使copier也会提供不同于原始源的值，我们会计算每个值的independent vote。首先，采用一种贪心算法去决定所有源独立性的排序，越独立的排序越靠前。然后，再计算S独立的提供v相较于其他源S0提供v的概率，I(S)。则v的confidence为，C(v) = A’(S)*I(S)对所有源的求和。

Iterative Algorithm - ACCUCOPY

迭代计算：accuracy of sources, copying between sources, and confidence of values

初始状态给每个源初始化相同的准确度，每个value相同的正确概率。1）根据前次的C(v)计算copying关系；2）更新C(v)；3）更新源的准确度。

最多2l*n0轮收敛(l为object个数，n0为每个源的value个数)，每轮的时间复杂度为O(object的个数x源的个数的平方xlog(源的个数))

效果结论

http://lunadong.com/fusionDataSets.htm上AbeBooks.com各个书店的计算机类图书书单。

我的总结

原先的判断true value的投票算法并未考虑源之间互相抄袭的情况，本文的算法中考虑了这种情况后，准确率大大提高。

Original link: http://sumnous.github.io/blog/2014/09/06/data_fusion_resolving_conflicts_from_multiple_sources-papernote/
 Written by sumnous Posted at http://sumnous.github.io

Gephi on OS X Mavericks 10.9

“Gephi is an open source visualization and exploration platform available on Windows, Linux and Mac OS X. It supports all types of networks – directed, undirected and mixed, and is capable of handling very large network graphs of up to one million nodes. Various metrics are supported including betweenness, closeness, diameter, clustering coefficient, average shortest path, pagerank and HITS. Dynamic filtering allows edges and/or nodes to be selected based on network structure or data. Ideal for social network analysis, link analysis and biological network analysis. Perhaps the most advanced of the open source tools.” <5 Free Social Network Analysis Tools - Butler Analytics>

Running OS X Mavericks 10.9.4. I downloaded Gephi 0.8.2-beta and it would not load correctly. After starting, it would freeze if I clicked anything. After looking for the solutions on the internet, I found this is a show-stopper for every normal Mac user caused by not supporting JAVA 7(which is installed on updating Mac 10.9) on Gephi. So we need to swich back to JAVA 6, it’s really annoying…

Took me almost a day to solve this problem… :(

This is the steps what I did to fix the problem for running Gephi on Mac OS X 10.9 @joernhees:

  1. Download and install JAVA 1.6: http://support.apple.com/kb/DL1572

  2. Delete your gephi settings dir: rm -r ~/Library/Application\ Support/gephi

  3. Find your java home with /usr/libexec/java_home -v 1.6, it should print something like /System/Library/Java/JavaVirtualMachines/1.6.0.jdk/Contents/Home

  4. Edit /Applications/Gephi.app/Contents/Resources/gephi/etc/gephi.conf to set your jdkhome e.g. like this: echo "jdkhome=\"$(/usr/libexec/java_home -v 1.6)\"" >> /Applications/Gephi.app/Contents/Resources/gephi/etc/gephi.conf

  5. Start Gephi and open the Les Miserables sample, if you see the graph good.

  6. Check Gephi’s about for the line saying Java: 1.6.0_65; Java HotSpot(TM) 64-Bit Server VM 20.65-b04-466.1

Moreover, according to @Kikohs, in your .bash_profile or .zshrc, add:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

# JAVA,
# Your java 6 version here
export JAVA_HOME=/Library/Java/JavaVirtualMachines/1.6.0_51-b11-457.jdk/Contents/Home

function setjdk() {
    if [ $# -ne 0 ]; then
        removeFromPath '/System/Library/Frameworks/JavaVM.framework/Home/bin'
        if [ -n "${JAVA_HOME+x}" ]; then
            removeFromPath $JAVA_HOME
        fi
        export JAVA_HOME=`/usr/libexec/java_home -v $@`
        export PATH=$JAVA_HOME/bin:$PATH
    fi
    echo JAVA_HOME set to $JAVA_HOME
    java -version
}
function removeFromPath() {
    export PATH=$(echo $PATH | sed -E -e "s;:$1;;" -e "s;$1:?;;")
}

Those functions allow you to quickly switch for java 6 to java 7 and vice-versa:

1
2

$> setjdk 1.6  # java 6
$> setjdk 1.7  # java 7

Attached a picture of American College football Network I drawed using Gephi :P

Reference: 1. About the ISSUE on Gephi 2. Discussions on Gephi forums

Original link: http://sumnous.github.io/blog/2014/07/24/gephi-on-mac/
 Written by sumnous Posted at http://sumnous.github.io

Install Octave on Mac OS X 10.9

Recently I am working on Stanford Machine Learning Course By Andrew NG on Coursera, Andrew recommended Octave to build prototype quickly. It’s been tricky to install octave on Mac, so I shared my process of intalling it.

1.Install XQuartz

2.Install Xcode and Command Line Tools3

1

$ xcode-select --install

3.Install homebrew

1
2

$ brew doctor
$ brew update && brew upgrade

It’s important to solve all the warning in homebrew, so it can work smoothly when installing octave.

4.Import the scientific computing packages

1

$ brew tap homebrew/science

5.Install Octave

1

$ brew install octave

6.Install gnuplot

1

$ brew install gnuplot

(Update: As phseven pointed out, gnuplot will be automatically installed with octave, but in some cases it won’t support X11.) For such cases, do the following:

1
2

$ brew uninstall gnuplot
$ brew install gnuplot --with-x

If you plot something in Octave, and it occures problems like this:

1
2
3

gnuplot> set terminal aqua enhanced title "Figure 1"  font "*,6" dashlength 1
	           			^	        	
	    line 0: unknown or ambiguous terminal type; type just 'set terminal' for a list

Just run:

1

setenv("GNUTERM","X11")

befor you plot anything, e.g.,

1

plot(x,y)

It will be convenient if you setup Octave startup file: vim ~/.octaverc and add the line setenv GNUTERM x11.

7.Open Octave just run octave, if you want to change the look of your Octave, just input PS1('>> ')

1
2
3
4

octave:1>
octave:1> PS1('>> ')
>>
>>

A One and a Two 《一一》

173分钟，却好似经历了人生的缩影，幼儿的洋洋，青少年的婷婷、莉莉、胖子，中年人的NJ，敏敏，阿弟，阿弟媳妇，阿瑞，蒋妈，云云，大田，还有NJ的老板，老年人的婆婆。

很多镜头平静却无法忘却，婆婆去世时婷婷手中的折纸，大田吹着口哨玩着鸟，洋洋跳进游泳池，胖子从旅馆中跑掉婷婷落寞又坚强的走在马路上，阿弟孩子满月闹剧NJ呆呆的又很镇静的站在门口，日本宾馆中阿瑞放声大哭映在玻璃上的影子。。。

就像人生的回放，平淡而忧伤。

就像NJ说的，人生虽然有很多遗憾，以为重活一次一定会不一样，可结果其实差不多，可再活一次真的没有那个必要了。如果带着记忆让我再活一次，我想我一定不会了，人生太累，过去就过去了，那些遗憾，那些错过，才是我们始终念念不忘的，记性好的人太痛苦，所以还是不要再回去了。

可能大田算活得明白的一个，站的高的人，思想境界高的人，可能看这个世界真的是不一样的，他们都在做自己感兴趣可能别人却不理解的事情。

还有洋洋，你们看不到的，我拍给你们看，还有他在片尾终于肯对已经过世的婆婆说的那段话，“我好想你。尤其是当我看到那个，还没有名字的小表弟，就会想起你常跟我说：你老了。我很想跟他说我觉得……我也老了。”

也许在一年前我不会喜欢这种又长又慢又无聊的电影，可如今看起来却好像我活在了这个电影里，想哭，想笑，却又无奈。

就像豆瓣上某篇影评的的题目那样，年华一帧一帧的逝去。

岁月静好。

最近的面试经历-百度，搜狗，腾讯滴滴打车，豆瓣

我的简历背景是主要做社区发现算法，之前做同构网络的社区发现算法，现在做异构网络的（学术网络为例），每位面试官都会让我介绍我做的内容。我写了图像处理的经历，百度和滴滴的面试官对这一经历很感兴趣。

百度

职位是机器学习。

第一面：

介绍我的社区发现论文，并给出论文中我认为创新的地方。我说了三点。

另外：

  1. 如何帮助超市定特价商品。

  2. 一个黑盒里是一个图，结构未知，只知道点的个数是n，边的个数是m，写公式给出两个点相连的概率。

第二面：（女面试官！）

写代码：给一个文档，以及stopwords，统计除掉停用词之后的词频统计。

之后问到给一个查询query，如何匹配相应地文档。

由于当时并不知道TF-IDF，向量空间模型（VSM），以及sphinx全文检索技术这一块，这一面减分很多。其实之后看了下资料，比较简单。

第三面：

隔了一周部门的leader面的。问得跟项目相关。给我提得建议是系统学习下机器学习，这样再做数据挖掘的时候会有更好的全局观。虽悲剧但受教。

一道概率题，54张牌，平均分成三堆，大小王在同一堆的概率？（17/53）

搜狗

随机数生成函数面试题

前阵子去某公司笔试，有道题是

已知随机数生成函数f()，返回0的概率是60%，返回1的概率是40%。根据f()求随机数函数g()，使返回0和1的概率是50%，不能用已有的随机生成库函数。

分析：

调用f()两次即可，会出现4种结果(0,0), (0,1), (1,0), (1,1)，其中出现(0,1), (1,0)的概率是一样的，可以构造出等概率事件，比如出现(0,1)可返回0，出现(1,0)可返回1，如果出现其他两种情况则舍掉重新调用。

代码如下：

1
2
3
4
5
6
7
8

def g():
    while(true):
        a = f()
        b = f()
        if [a,b] == [0,1]:
            return 0
        if [a,b] == [1,0]:
            return 1

这道笔试题到此为止。

接下来扩展一下，如何实现这个随机数生成函数f()，可用random()，也就是以指定概率获取元素。《Python Cookbook》中有此示例。分析一下，也就是在(0, 0.6]区间内取0，在(0.6, 1]区间内取1。扩展到多个数也一样。

Octopress Build Blog on Github 个人建站实录

为什么选择Octopress：静态+Markdown+Git提交+不需要服务器+有基础的话折腾1-2个小时就能看到效果（这些都是我喜欢的）

这篇《记录：Octopress建站之旅》很易上手，有篇易懂易follow的教程是好的开始~(多亏池大 @池建强 分享了 @Jacky130 的博客，我才看到了这篇文章，才想自己动手来做这件事情)

1. 首先安装Git和Ruby，检查是否安装好

1
2

git --version
ruby --version

2. 安装Octopress到本地，之后的所有操作都在octopress文件下

1
2
3
4
5

git clone git://github.com/imathis/octopress.git octopress
cd octopress
gem install bundler
rbenv rehash
bundle install

可能会有权限问题，请加sudo。在执行rbenv rehash的时候系统提示我没有此命令，于是参考这里

1

git clone https://github.com/sstephenson/rbenv.git ~/.rbenv

将$PATH写入~/.bash_profile，也可以参考rbenv的git页面

1
2
3
4
5

export RBENV_ROOT="${HOME}/.rbenv"
if [ -d "${RBENV_ROOT}" ]; then
  export PATH="${RBENV_ROOT}/bin:${PATH}"
  eval "$(rbenv init -)"
fi

检查rbenv是否可用rbenv -v。rbenv rehash这条命令，每当切换 ruby 版本和执行 bundle install 之后必须执行这个命令。

3. 安装主题

[Leetcode] Valid Parentheses @Python

Problem

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution:
    # @return a boolean
    def isValid(self, s):
        if s == '':
            return True
        left = '([{'
        right = ')]}'
        stack = []
        for i in s:
            if i == '(' or i == '[' or i == '{':
                stack.append(i)
                continue
            for j in xrange(3):
                if i == right[j]:
                    if not stack or stack[-1] != left[j]:
                        return False
                    else:
                        stack.pop()
                        continue
        return not stack
# test
s = Solution()
print s.isValid('()')

Original link: http://sumnous.github.io/blog/2014/05/10/leetcode-valid-parentheses-at-python/
 Written by sumnous Posted at http://sumnous.github.io

[Leetcode] Longest Valid Parentheses @Python

Problem

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

class Solution:
    # @param s, a string
    # @return an integer
    def longestValidParentheses(self, s):
        if s == '' or s == '(' or s == ')':
            return 0
        stack = [(-1, ')')]
        maxLen = 0
        for i in xrange(len(s)):
            if s[i] == ')' and stack[-1][1] == '(':
                stack.pop()
                maxLen = max(maxLen, i - stack[-1][0])
            else:
                stack.append((i, s[i]))
        return maxLen
#test
s = Solution()
print s.longestValidParentheses("()(()")
print s.longestValidParentheses('(()()')
print s.longestValidParentheses(')()())')

Original link: http://sumnous.github.io/blog/2014/05/10/leetcode-longest-valid-parentheses-at-python/
 Written by sumnous Posted at http://sumnous.github.io

[Leetcode] Edit Distance @Python

Problem

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

class Solution:
    # @return an integer
    def minDistance(self, word1, word2):
        len1 = len(word1)
        len2 = len(word2)
        dp = [[0 for j in xrange(len2+1)] for i in xrange(len1 +1)]
        for i in xrange(len1+1):
            dp[i][0] = i
        for j in xrange(len2+1):
            dp[0][j] = j
        for i in xrange(1, len1+1):
            for j in xrange(1, len2+1):
                if word1[i-1] == word2[j-1]:
                    dp[i][j] = dp[i-1][j-1]
                else:
                    dp[i][j] = min(dp[i-1][j-1], dp[i][j-1],dp[i-1][j]) + 1
        return dp[len1][len2]

Original link: http://sumnous.github.io/blog/2014/05/10/leetcode-edit-distance-at-python/
 Written by sumnous Posted at http://sumnous.github.io

DBLP数据集SQL导入

1. 创建数据库DBLP：

show databases;

create database dblp;

use dblp;

导入数据库：

mysql -u root -p dblp < /Users/ting/workspace/datasets/dblp.sql

CODE: DBLP-parser

三个表：

authors: pid, author

papers: pid, title, year, conference, abstract

cites: pid,cid

show tables;

[论文学习笔记] ICDM12-Topic-aware-Social-Influence-Propagation-Models(话题感知社会影响力传播模型)

Barbieri, N., Bonchi, F., & Manco, G. (2012, December). Topic-aware social influence propagation models. In Data Mining (ICDM), 2012 IEEE 12th International Conference on (pp. 81-90). IEEE.

社交网络传播模型的共同特征：

  1. 用户成为活跃用户的可能性随着他的邻居中活跃用户的数量单调增加。
  2. 影响过程遵循Progressive规则，即用户只可能从非活跃受影响变成活跃，而不可能由活跃变成非活跃。

Linear Threshold Model 线性阈值模型：是以接受者为中心的模型 Independent Cascade Model 独立级联模型：是以发射者为中心的模型

考虑时间延迟的模型(Continuous Time Delay Model)：在传统的IC，LT基础上引入连续时间延迟，也就是CTIC，CTLT。用于话题传播行为分析。

目标问题：确定有影响力的用户（例如病毒式营销中）

问题：离散对待的时间和大量参数（效率，可扩展行和过度拟合（过适，是指在调适一个统计模型时，使用过多参数。））

观察：1）用户有不同的兴趣；2）物品有不同的特征；3）用户有可能喜欢相似的物品 研究对象：物品特征，用户兴趣，社会影响

解决Mac下Chrome浏览器用Goagent打开HTTPS网站SSL证书错误不受信任问题

mac下用goagent FQiang总是会遇到https信任问题，每次访问网站都得点，很烦人，搜了一下，这个解决方法比较好。

打开［应用程序］>［实用工具］>［钥匙串访问］，并在左侧导航选择［系统］。

选择顶部的［文件］>［导入项目］，并定位到goagent安装目录的localCA.crt。选择导入。提示输入系统密码。

双击新导入的GoAgent CA证书，展开［信任］选项，确保所有的选择都是［总是信任］。重启浏览器即可。

windows下解决方案

mac、iOS下解决方案

推荐mac下工具GoAgentX，参考教程

Original link: http://sumnous.github.io/blog/2013/08/28/Goagent-SSL-Error/
 Written by sumnous Posted at http://sumnous.github.io