生物信息学推荐系统的设计与实现
发布时间：2015-07-07 09:26
摘要：在生物信息学系统设计中引进推荐系统，提出具有个性化服务的生物信息学网站模型，完成生物信息学推荐系统的设计和实现，体现出推荐系统在生物信息学中使用的必要性和优越性。
关键词：推荐系统；生物信息学
推荐系统(recommender system) [1]是个性化信息服务的主要技术之一，它实现的是“信息找人，按需服务”；通过对用户信息需要、兴趣爱好和访问历史等的收集分析，建立用户模型，并将用户模型应用于网上信息的过滤和排序，从而为用户提供感兴趣的资源和信息。生物信息学(bioinformatics)[2,3]是由生物学、应用数学和计算机科学相互交叉所形成的一门新型学科；其实质是利用信息科学的方法和技术来解决生物学问题。20世纪末生物信息学迅速发展，在信息的数量和质量上都极大地丰富了生物科学的数据资源，而数据资源的急剧膨胀需要寻求一种科学而有力的工具来组织它们，基于生物信息学的二次数据库[4]能比较好地规范生物数据的分类与组织，但是用户无法从大量的生物数据中寻求自己感兴趣的部分（著名的生物信息学网站ncbi(美国国立生物技术信息中心)，仅仅是小孢子虫(microsporidia)的dna序列就达3 399种），因此在生物二次数据库上建立个性化推荐系统，能使用户快速找到自己感兴趣的生物信息。特别是在当前生物信息数据量急剧增长的情况下，生物信息学推荐系统将发挥强大的优势。
1推荐系统的工作流程
应用在不同领域的推荐系统，其体系结构也不完全相同。一般而言，推荐系统的工作流程[5]如图1所示。
(1)信息获取。推荐系统工作的基础是用户信息。用户信息包括用户输入的关键词、项目的有关属性、用户对项目的文本评价或等级评价及用户的行为特征等，所有这些信息均可以作为形成推荐的依据。信息获取有两种类型[6]，即显式获取(explicit)和隐式获取(implicit)，由于用户的很多行为都能暗示用户的喜好，因此隐式获取信息的准确性比显式高一些。
(2)信息处理。信息获取阶段所获得的用户信息，一般根据推荐技术的不同对信息进行相应的处理。用户信息的存储格式中用得最多的是基于数值的矩阵格式，最常用的是用m×n维的用户—项目矩阵r来表示，矩阵中的每个元素rij=第i个用户对第j个项目的评价，可以当做数值处理，矩阵r被称为用户—项目矩阵。
(3)个性化推荐。根据形成推荐的方法的不同可以分为三种，即基于规则的系统、基于内容过滤的系统和协同过滤系统。基于规则的推荐系统和基于内容过滤的推荐系统均只能为用户推荐过去喜欢的项目和相似的项目，并不能推荐用户潜在感兴趣的项目。而协同过滤系统能推荐出用户近邻所喜欢的项目，通过用户与近邻之间的“交流”，发现用户潜在的兴趣。因此本文所用的算法是基于协同过滤的推荐算法。
(4)推荐结果。显示的任务是把推荐算法生成的推荐显示给用户，完成对用户的推荐。目前最常用的推荐可视化方法是top－n列表[7]，按照从大到小顺序把推荐分值最高的n个事物或者最权威的n条评价以列表的形式显示给用户。
2生物信息学推荐系统的设计
综合各种推荐技术的性能与优缺点，本文构造的生物信息学推荐系统的总体结构如图2所示。
生物信息学推荐系统实现的主要功能是在用户登录生物信息学网站时，所留下的登录信息通过网站传递到推荐算法部分；推荐算法根据该用户的用户名从数据库提取出推荐列表，并返回到网站的用户界面；用户访问的记录返回到数据库，系统定时调用推荐算法，对数据库中用户访问信息的数据进行分析计算，形成推荐列表。
本系统采用基于近邻的协同过滤推荐算法，其结构可以进一步细化为如图3所示。算法分为邻居形成和推荐形成两大部分，两部分可以独立进行。这是该推荐系统有别于其他系统的优势之一。由于信息获取后的用户—项目矩阵维数较大，使得系统的可扩展性降低。本系统采用svd矩阵降维方法，减少用户—项目矩阵的维数，在计算用户相似度时大大降低了运算的次数，提高了推荐算法的效率。
(1)信息获取。用户对项目的评价是基于用户对某一个项目(为表示简单，以下提及的项目均指网站上的生物物种)的点击次数来衡量的。当一个用户注册并填写好个人情况以后，系统会自动为该用户创建一个“信息矩阵”，该矩阵保存了所有项目的id号以及相应的用户评价，保存的格式为：s+编号+用户评价，s用于标记项目，每个项目编号及其评价都以“s”相隔开；编号是唯一的，占5位；用户评价是用户点击该项目的次数，规定其范围是0~100，系统设定当增加到100时不再变化。这样做可防止形成矩阵时矩阵评价相差值过大而使推荐结果不准确。 (2)信息处理。信息处理是将所有用户的信息矩阵转换为用户—项目矩阵，使用户信息矩阵数值化，假设系统中有m个用户和n个项目，信息处理的目的就是创建一个m×n的矩阵r，r[i][j]代表用户i对项目j的评价。
(3)矩阵处理。协同过滤技术的用户—项目矩阵的数据表述方法所带来的稀疏性严重制约了推荐效果，而且在系统较大的情况下，它既不能精确地产生推荐集，又忽视了数据之间潜在的关系，发现不了用户潜在的兴趣，而且庞大的矩阵增加了计算的复杂度，因此有必要对该矩阵的表述方式做优化，进行矩阵处理。维数简化是一种较好的方法，本文提出的算法应用单值分解(singular value decomposition，svd)技术[8]，对用户—项目矩阵进行维数简化。
(4)相似度计算。得到降维以后的用户矩阵us，就可以寻找每个用户的近邻。近邻的确定是通过两个用户的相似度来度量的。本文采用pearson相关度因子[9]求相似度。 (5)计算用户邻居。该方法有两种[10]，即基于中心的邻居(center－based neighbor)和集合邻居(aggregate neighbor)。本系统采用了第一种方法，直接找出与用户相似度最高的前n个用户作为邻居，邻居个数n由系统设定，比如规定n＝5。
(6)推荐形成。推荐形成的前提是把当前用户的邻居id号及其与当前用户的相似度保存到数据库中，而在前面的工作中已找出各用户的邻居以及与用户的相似度，推荐形成部分只需要对当前登录用户进行计算。推荐策略是：对当前用户已经访问过的项目不再进行推荐，推荐的范围是用户没有访问的项目，其目的是推荐用户潜在感兴趣的项目；考虑到系统的项目比较多，用户交互项目的数量很大，所以只筛选出推荐度最大的n个项目，形成top－n推荐集，设定n＝5。
3生物信息学推荐系统的实现
生物信息学推荐系统的实现可以用图4来表示。数据库部分主要存储用户信息和项目信息，用sql server 2000实现。
数据访问层实现了与用户交互必需的存储过程以及触发器，也使用sql server 2000，主要完成以下功能：初始化新用户信息矩阵；插入新项目时更新所有用户的信息矩阵；用户点击项目时更新该用户对项目的评价；删除项目时更新所有用户的信息矩阵。用户访问层主要涉及网页与用户的交互和调用数据访问层的存储过程，在这里不做详细的介绍。
推荐算法完成整个个性化推荐的任务，用java实现。
(2)数据操作类datacontrol。该类负责推荐算法与数据库的数据交换，静态成员con调用datacon. getcon()获得数据库连接，然后对数据库进行各种操作。把所有方法编写成静态，便于推荐算法中不创建对象就可以直接调用。
(3)recmmendsource与currentuserneighbor。这两个类作为fcrecommand类的内部类，recmmendsource用于保存当前用户的推荐列表，包括推荐项目号和推荐度；currentuserneighbor用于保存邻居信息，包括邻居id号、相似度及其访问信息。
(4)协同过滤推荐算法fcrecommand。该类实现了整个推荐算法，主要分为邻居形成方法fcarithmetic和推荐形成方法generaterecommend。
下面给出方法fcarithmetic的关键代码：
matrix user_item=_item_arry(); //获取用户—项目矩阵
user_item=_calculate(user_item); //调用svd降维方法
vector c_uservector = new vector(); //当前用户向量
vector o_uservector = new vector(); //其他用户向量
vector c_user_correlate_vector = new vector();
//当前用户与其他用户之间相似度向量
for(int i=0;i for(int j=0;j ment((i,j));
//1.获得当前用户向量
for(int k=0;k ();
for(int l=0;l ment((k,l));
//2.获得其他用户的向量
//3.计算当前用户与其他用户的相似度
usercorrelativity=ativity(c_uservector,o_uservector);
ment(usercorrelativity);
}
//4.根据当前用户与其他用户的相似度，计算其邻居
erneighbor(i,c_user_correlate_vector);
}
根据邻居形成方法fcarithmetic，可以得到每个用户的邻居。作为测试用例，图6显示用户jack与系统中一部分用户的相似度，可以看出它与自己的相似度必定最高；并且它与用户sugx访问了相同的项目，它们之间的相似度也为1，具有极高的相似度。
4结束语
在传统推荐系统的基础上，结合当前生物信息学网站的特点，提出一个基于生物信息平台的推荐系统，解决了传统生物信息网站平台信息迷茫的缺点，为用户推荐其感兴趣物种的dna或蛋白质序列。
优点在于协同过滤的推荐算法能发现用户潜在的兴趣，能促进生物学家之间的交流；推荐算法的邻居形成与推荐形成两部分可以单独运行，减少了系统的开销。 进一步的工作是分析生物数据的特点及生物数据之间的关系，增加用户和项目数量，更好地发挥推荐系统的优势。
参考文献：
［1］paul r，hal r v. recommender systems[j].communications of the acm，1997,40(3): 56－58.
[2]陈新.生物信息学简介[eb/ol].(2001)..
[3]林毅申, 林丕源.基于web services的生物信息解决方案[j]. 计算机应用研究, 2005,22(6): 157－158,164.[4]邢仲璟, 林丕源, 林毅申.基于bioperl的生物二次数据库建立及应用[j]. 计算机系统应用, 2004(11): 58－60.
[5]airia s, takahisa a, hiroya i,et al. personalization system based on dynamic learning:international semantic web conference[c].sardinia:[s.n.],2002.
[6]breese j s, heckerman d,kadie cal analysis of predictive algorithms for collaborative filtering:proceedings of the fourteenth conference on university in artificial intelligence[c]. madison:wi,1998:43－52.
[7]schafer j b, konstan j,riedl ender systems in e－commerce:proceeding of the acm conference on electronic commerce[c].pittsburgh:pa,1999:158－166.
[8]pryor m h. the effects of singular value decomposition on collaborative filtering[eb/ol].(1998).reports/tr98－.
[9]sarwar b, karypis g, konstan j,et al.analysis of recommendation algorithms for e－commerce:proceedings of the 2nd acm conference on electronic commerce[c].minneapolis:[s.n.],2000:158－167.
[10]sun tong,andr’e implemented e－commerce shopping system which makes personal recommendations[eb/ol].(2001－10)..
关键词：推荐系统；生物信息学
推荐系统(recommender system) [1]是个性化信息服务的主要技术之一，它实现的是“信息找人，按需服务”；通过对用户信息需要、兴趣爱好和访问历史等的收集分析，建立用户模型，并将用户模型应用于网上信息的过滤和排序，从而为用户提供感兴趣的资源和信息。生物信息学(bioinformatics)[2,3]是由生物学、应用数学和计算机科学相互交叉所形成的一门新型学科；其实质是利用信息科学的方法和技术来解决生物学问题。20世纪末生物信息学迅速发展，在信息的数量和质量上都极大地丰富了生物科学的数据资源，而数据资源的急剧膨胀需要寻求一种科学而有力的工具来组织它们，基于生物信息学的二次数据库[4]能比较好地规范生物数据的分类与组织，但是用户无法从大量的生物数据中寻求自己感兴趣的部分（著名的生物信息学网站ncbi(美国国立生物技术信息中心)，仅仅是小孢子虫(microsporidia)的dna序列就达3 399种），因此在生物二次数据库上建立个性化推荐系统，能使用户快速找到自己感兴趣的生物信息。特别是在当前生物信息数据量急剧增长的情况下，生物信息学推荐系统将发挥强大的优势。
1推荐系统的工作流程
应用在不同领域的推荐系统，其体系结构也不完全相同。一般而言，推荐系统的工作流程[5]如图1所示。
(1)信息获取。推荐系统工作的基础是用户信息。用户信息包括用户输入的关键词、项目的有关属性、用户对项目的文本评价或等级评价及用户的行为特征等，所有这些信息均可以作为形成推荐的依据。信息获取有两种类型[6]，即显式获取(explicit)和隐式获取(implicit)，由于用户的很多行为都能暗示用户的喜好，因此隐式获取信息的准确性比显式高一些。
(2)信息处理。信息获取阶段所获得的用户信息，一般根据推荐技术的不同对信息进行相应的处理。用户信息的存储格式中用得最多的是基于数值的矩阵格式，最常用的是用m×n维的用户—项目矩阵r来表示，矩阵中的每个元素rij=第i个用户对第j个项目的评价，可以当做数值处理，矩阵r被称为用户—项目矩阵。
(3)个性化推荐。根据形成推荐的方法的不同可以分为三种，即基于规则的系统、基于内容过滤的系统和协同过滤系统。基于规则的推荐系统和基于内容过滤的推荐系统均只能为用户推荐过去喜欢的项目和相似的项目，并不能推荐用户潜在感兴趣的项目。而协同过滤系统能推荐出用户近邻所喜欢的项目，通过用户与近邻之间的“交流”，发现用户潜在的兴趣。因此本文所用的算法是基于协同过滤的推荐算法。
(4)推荐结果。显示的任务是把推荐算法生成的推荐显示给用户，完成对用户的推荐。目前最常用的推荐可视化方法是top－n列表[7]，按照从大到小顺序把推荐分值最高的n个事物或者最权威的n条评价以列表的形式显示给用户。
2生物信息学推荐系统的设计
综合各种推荐技术的性能与优缺点，本文构造的生物信息学推荐系统的总体结构如图2所示。
生物信息学推荐系统实现的主要功能是在用户登录生物信息学网站时，所留下的登录信息通过网站传递到推荐算法部分；推荐算法根据该用户的用户名从数据库提取出推荐列表，并返回到网站的用户界面；用户访问的记录返回到数据库，系统定时调用推荐算法，对数据库中用户访问信息的数据进行分析计算，形成推荐列表。
本系统采用基于近邻的协同过滤推荐算法，其结构可以进一步细化为如图3所示。算法分为邻居形成和推荐形成两大部分，两部分可以独立进行。这是该推荐系统有别于其他系统的优势之一。由于信息获取后的用户—项目矩阵维数较大，使得系统的可扩展性降低。本系统采用svd矩阵降维方法，减少用户—项目矩阵的维数，在计算用户相似度时大大降低了运算的次数，提高了推荐算法的效率。
(1)信息获取。用户对项目的评价是基于用户对某一个项目(为表示简单，以下提及的项目均指网站上的生物物种)的点击次数来衡量的。当一个用户注册并填写好个人情况以后，系统会自动为该用户创建一个“信息矩阵”，该矩阵保存了所有项目的id号以及相应的用户评价，保存的格式为：s+编号+用户评价，s用于标记项目，每个项目编号及其评价都以“s”相隔开；编号是唯一的，占5位；用户评价是用户点击该项目的次数，规定其范围是0~100，系统设定当增加到100时不再变化。这样做可防止形成矩阵时矩阵评价相差值过大而使推荐结果不准确。 (2)信息处理。信息处理是将所有用户的信息矩阵转换为用户—项目矩阵，使用户信息矩阵数值化，假设系统中有m个用户和n个项目，信息处理的目的就是创建一个m×n的矩阵r，r[i][j]代表用户i对项目j的评价。
(3)矩阵处理。协同过滤技术的用户—项目矩阵的数据表述方法所带来的稀疏性严重制约了推荐效果，而且在系统较大的情况下，它既不能精确地产生推荐集，又忽视了数据之间潜在的关系，发现不了用户潜在的兴趣，而且庞大的矩阵增加了计算的复杂度，因此有必要对该矩阵的表述方式做优化，进行矩阵处理。维数简化是一种较好的方法，本文提出的算法应用单值分解(singular value decomposition，svd)技术[8]，对用户—项目矩阵进行维数简化。
(4)相似度计算。得到降维以后的用户矩阵us，就可以寻找每个用户的近邻。近邻的确定是通过两个用户的相似度来度量的。本文采用pearson相关度因子[9]求相似度。 (5)计算用户邻居。该方法有两种[10]，即基于中心的邻居(center－based neighbor)和集合邻居(aggregate neighbor)。本系统采用了第一种方法，直接找出与用户相似度最高的前n个用户作为邻居，邻居个数n由系统设定，比如规定n＝5。
(6)推荐形成。推荐形成的前提是把当前用户的邻居id号及其与当前用户的相似度保存到数据库中，而在前面的工作中已找出各用户的邻居以及与用户的相似度，推荐形成部分只需要对当前登录用户进行计算。推荐策略是：对当前用户已经访问过的项目不再进行推荐，推荐的范围是用户没有访问的项目，其目的是推荐用户潜在感兴趣的项目；考虑到系统的项目比较多，用户交互项目的数量很大，所以只筛选出推荐度最大的n个项目，形成top－n推荐集，设定n＝5。
3生物信息学推荐系统的实现
生物信息学推荐系统的实现可以用图4来表示。数据库部分主要存储用户信息和项目信息，用sql server 2000实现。
数据访问层实现了与用户交互必需的存储过程以及触发器，也使用sql server 2000，主要完成以下功能：初始化新用户信息矩阵；插入新项目时更新所有用户的信息矩阵；用户点击项目时更新该用户对项目的评价；删除项目时更新所有用户的信息矩阵。用户访问层主要涉及网页与用户的交互和调用数据访问层的存储过程，在这里不做详细的介绍。
推荐算法完成整个个性化推荐的任务，用java实现。
(1)数据连接类datacon。该类完成与sql server 2000数据库的连接，在连接之前必须要下载三个与sql server连接相关的包，即、和。
(2)数据操作类datacontrol。该类负责推荐算法与数据库的数据交换，静态成员con调用datacon. getcon()获得数据库连接，然后对数据库进行各种操作。把所有方法编写成静态，便于推荐算法中不创建对象就可以直接调用。
(3)recmmendsource与currentuserneighbor。这两个类作为fcrecommand类的内部类，recmmendsource用于保存当前用户的推荐列表，包括推荐项目号和推荐度；currentuserneighbor用于保存邻居信息，包括邻居id号、相似度及其访问信息。
(4)协同过滤推荐算法fcrecommand。该类实现了整个推荐算法，主要分为邻居形成方法fcarithmetic和推荐形成方法generaterecommend。
下面给出方法fcarithmetic的关键代码：
matrix user_item=_item_arry(); //获取用户—项目矩阵
user_item=_calculate(user_item); //调用svd降维方法
vector c_uservector = new vector(); //当前用户向量
vector o_uservector = new vector(); //其他用户向量
vector c_user_correlate_vector = new vector();
//当前用户与其他用户之间相似度向量
for(int i=0;i for(int j=0;j ment((i,j));
//1.获得当前用户向量
for(int k=0;k ();
for(int l=0;l ment((k,l));
//2.获得其他用户的向量
//3.计算当前用户与其他用户的相似度
usercorrelativity=ativity(c_uservector,o_uservector);
ment(usercorrelativity);
}
//4.根据当前用户与其他用户的相似度，计算其邻居
erneighbor(i,c_user_correlate_vector);
}
根据邻居形成方法fcarithmetic，可以得到每个用户的邻居。作为测试用例，图6显示用户jack与系统中一部分用户的相似度，可以看出它与自己的相似度必定最高；并且它与用户sugx访问了相同的项目，它们之间的相似度也为1，具有极高的相似度。
4结束语
在传统推荐系统的基础上，结合当前生物信息学网站的特点，提出一个基于生物信息平台的推荐系统，解决了传统生物信息网站平台信息迷茫的缺点，为用户推荐其感兴趣物种的dna或蛋白质序列。
优点在于协同过滤的推荐算法能发现用户潜在的兴趣，能促进生物学家之间的交流；推荐算法的邻居形成与推荐形成两部分可以单独运行，减少了系统的开销。 进一步的工作是分析生物数据的特点及生物数据之间的关系，增加用户和项目数量，更好地发挥推荐系统的优势。
参考文献：
［1］paul r，hal r v. recommender systems[j].communications of the acm，1997,40(3): 56－58.
[2]陈新.生物信息学简介[eb/ol].(2001)..
[3]林毅申, 林丕源.基于web services的生物信息解决方案[j]. 计算机应用研究, 2005,22(6): 157－158,164.[4]邢仲璟, 林丕源, 林毅申.基于bioperl的生物二次数据库建立及应用[j]. 计算机系统应用, 2004(11): 58－60.
[5]airia s, takahisa a, hiroya i,et al. personalization system based on dynamic learning:international semantic web conference[c].sardinia:[s.n.],2002.
[6]breese j s, heckerman d,kadie cal analysis of predictive algorithms for collaborative filtering:proceedings of the fourteenth conference on university in artificial intelligence[c]. madison:wi,1998:43－52.
[7]schafer j b, konstan j,riedl ender systems in e－commerce:proceeding of the acm conference on electronic commerce[c].pittsburgh:pa,1999:158－166.
[8]pryor m h. the effects of singular value decomposition on collaborative filtering[eb/ol].(1998).reports/tr98－.
[9]sarwar b, karypis g, konstan j,et al.analysis of recommendation algorithms for e－commerce:proceedings of the 2nd acm conference on electronic commerce[c].minneapolis:[s.n.],2000:158－167.
[10]sun tong,andr’e implemented e－commerce shopping system which makes personal recommendations[eb/ol].(2001－10)..
上一篇：基于访问趋势的热点副本创建策略