应用决策树C4.5算法在电视用户收视行为之研究

方德坚，游景升

(福建师范大学)

应用决策树C4.5算法在电视用户收视行为之研究

方德坚，游景升

(福建师范大学)

采用数据挖掘技术中的决策树方法，进行收视数据分析.收集大量的调查问卷作为待挖掘的样本，利用决策树经典算法C4.5，对样本集中的样本进行学习，构造出一棵决策树.对决策树进行分析，得出电视收视分析相关的知识和规律，作为节目编制等的决策依据.

决策树;C4.5算法;收视分析

1 背景和相关技术

1.1 背景和意义

随着电视行业的发展，媒介运营商、电视节目供应商以及广告公司所面临的经营和管理问题日益严峻.收视调查所提供的数据，属于系统、定量、客观和连续的收视信息，有利于广告商及传播者了解传播信息所抵达的观众范围、分布和构成，成为他们把握观众及传播效果的重要工具.数据挖掘是对数据进行利用的一个更高级阶段.随着挖掘技术的发展和运用，发现海量数据背后所隐藏的知识和规律，并利用这些数据指导决策行为.决策树技术作为一种分类技术被广泛地运用在数据挖掘领域中.

该文的意义在于通过数据挖掘技术中的决策树理论对相应群体的收视数据进行分析，挖掘出不同人群的收视特性，以制作出更合理的节目编排，调整不同节目的播出时间以及不同广告的投放时段等，从而提高广告针对性效果，增加不同时段整体的广告收入，进而改善电视的总体运营.

1.2 关键技术和技术难点

关键点在于设计一个方案，将C4.5算法运用到电视收视数据的分析上.

技术难点包括:

(1)调查问卷的设计;

(2)对MySQL数据库中异常样本的清理;

(3)利用XML技术，模拟C4.5决策树;

(4)决策树的图形化显示.

1.3 决策树技术和建立

决策树算法是一种归纳学习算法，它对一无序的已知类别的样本集进行学习，得出一个分类器，该分类器是用“树”的形式进行表现.决策树的学习是“监督”的学习.

决策树的建立过程主要由“建树”和“剪枝”这两个阶段构成.“建树”阶段通常采用的是贪心测试，通过不断选取测试属性，对样本集进行划分，深度优先搜索，直到所划分的子集同属于一个类别.“剪枝”或是“修剪”阶段的任务是消除统计噪声或数据波动对决策树的影响，以达到净化树的目的.决策树算法关键的地方在于“测试”属性(或称之为“分割”属性、“分裂”属性)的确定.C4.5则采用“信息增益率”作为属性选择的度量.

C4.5算法的主要思想为:假设S为训练样本集，当对S进行划分时，选择信息增益率最大的属性作为分裂属性，根据分裂属性在S上的不同取值，对S进行划分.若Si中的类别一致或Si中样本数过少，则该节点就成为决策树的叶子节点并返回.而对于不满足此条件的S的其他子集，按照上面的方式方法继续划分，直至所有子集所含样本都属于一个类别为止.

具体的伪代码算法描述C4.5(S，attriList)如下，其中，假设S代表当前的样本集，attriList是一个列表，存储了该样本集中测试属性的候选.

(1)创建新的树节点N;

(2)如果S中的所有样本同属一个类别C，则将节点N作为以类C标记的叶节点返回;

(3)如果attriList不含任何元素，则将节点N作为标记为samples中最普遍的类的叶节点返回;

(4)选择attriList中的信息增益率最大的属性A;标记节点N为A;

(5)对于属性A中的每一个可能的取值ai，由节点N生长出一个条件为A=ai的分枝;

(6)设Si是S中A=ai的样本集合;

(7)如果 Si为空集合，那么N作为标记为samples中最普遍的类的叶节点返回;

(8)否则加上一个由 C4.5(Si，attriList－A)返回的节点.

2 需求分析

2.1 在线收视分析系统的需求分析

电视台每隔一段时间就会对观众进行收视调查，例如通过电话询问，或是进行随机的问卷调查.这些都是具有一定价值的收视数据.如果能够找到某种关系，对于观众的收视数据中所隐含的信息进行深一步的研究分析，如某个节目收视率与哪些因素有关等，必定会对电视台收视的提高起到非常积极的作用.

2.2 系统总体目标

在线收视分析系统主要利用C4.5算法，对收视数据进行挖掘，得到一棵决策树.通过对该决策树的分析，获取对电视台频道策划，创意设计等决策行为提供科学合理的信息与依据.

2.3 系统的用例分析

在具体的应用中，对象是收看过本台频道栏目的观众.希望根据观众的收视行为和习惯来分析出哪些因素对节目的收视是有影响的，例如观众收看电视的时间段，对广告长短和内容的看法，对节目主持人的喜好等，并希望用得到的分析结果来指导今后的工作，提高工作质量.

分析哪些方面能够影响节目的收视情况，首先需要获取观众的收视信息，这个信息的获取，是通过图1所示的调查问卷.

图1 电视收视调查问卷(部分)

图2 系统用例图

一个需要注意的地方在于，受到决策树算法的限制，调查问卷的题目都被设计为单选题，而不允许有多选题或是填空题.因为决策树算法中对于样本的属性取值是有限制的，只能取单个离散值，而不能取多个离散值或是连续值.故所设置的问题都被设定为单选题.其中“你最喜欢看哪个频道”作为类别属性.

图2为分析系统的用例图.从图中可以看出，系统共存在两个参与者，一个是参与问卷调查的观众，另一个是收视数据分析人员.

参与问卷调查的观众通过“问卷调查”用例，提交调查问卷.而收视数据分析人员可以提出查看决策树的请求，系统通过“数据库管理”“数据预处理”“决策树生成”“规则生成”以及“模型准确性评估”这几个用例，处理用户的请求，将最后的结果返还给用户.

其中“问卷调查”用于收集收视分析样本数据集，“数据库管理”用于操作后台MySQL数据库中所存储的样本数据及其他信息，“数据预处理”保证待学习样本集的一致性及正确性.“决策树生成”是本系统的核心用例，该用例将采用C4.5算法，“规则生成”用例方便决策者根据决策树进行分析，指定决策.“模型准确性评估”用例用于衡量决策树的准确性.

下面将对系统所需的各功能模块进行分析.

2.4 对各功能模块的分析

图3是系统的数据流图，从图中可以看出，系统共涉及5个主要的功能模块，分别是问卷填写，数据库管理，数据预处理，决策树生成以及决策树显示.

图3 系统数据流图

用户通过“问卷填写”模块在线填写收视调查问卷，问卷数据通过“数据库”管理模块，以记录的形式被保存到后台survey表中.当数据分析人员通过Web浏览器，提交查看决策树的请求后，数据预处理模块将清洗后台数据库的样本数据，删除异常的信息，然后将“干净”的样本集提交给“决策树生成”模块.“决策树生成”模块利用C4.5算法，生成决策树，将“决策树显示”模块进行显示，供数据分析人员查看分析.下面对每个模块的输入、处理、输出等内容进行介绍.

3 设计与实现

3.1 问卷填写

做数据挖掘分析，需要学习样本，这些样本通过“问卷调查”模块来收集.“问卷调查”模块提供了一个Web页面，该页面通过“表单”构造调查题目，让参与调查的观众在线进行填写.该模块需要提供一种纠错的功能，保证观众填写了所有的问题之后才允许提交.并且该模块需确保同一位观众不能重复提交问卷，以免影响最后的评估模型.一份填写正确的问卷就是一个样本.这些样本作为一条记录，保存在后台数据库中，供其他模块所使用.

调查表的设计，要充分结合以往收视调查的经验，并综合了决策树算法的特点.例如，询问观众看电视的动机，看电视的时间段，对综艺性节目的看法，以及对广告的态度等等.这些问题即样本的一般属性，充分反映了观众的收视心理和习惯，具有较大参考价值.

调查表在设计时不能涉及到观众的个人隐私(例如询问被调查者的月收入等)，也不能出现模棱两可的问题(例如询问被调查者收看电视的频度是较高还是较低)，也不能出现与收视无关的问题(例如询问被调查者喜爱的食物).

决策树算法只能处理离散的属性值，不能处理连续值，例如无法处理类似温度、高度这些连续的值，也不能处理“多值问题”.问卷调查中的问题都是“离散的”，并且都被设计成了“单选题”，即对于每个问题，被调查者都能根据自己的实际情况对其中的一个选项进行选择.

课题将调查问卷设计成在线填写提交的方式，方便及加快了数据的采集和处理.为了让更多的人接受调查，并避免一个人填写多份调查问卷，问卷调查页面可以放在电视台官网，并在电视节目中做一定的宣传，设置“有奖调查”的活动，并对用户IP进行限制，一个IP只能填写一份问卷.

另一个事实是，后台问卷数据(即学习样本)越庞大，获得的决策树价值越高.所以，只有当问卷数量达到数千甚至数万量级时，才让分析员做决策分析.这样可以确保较高的科学性.

3.2 数据预处理

一般情况下，所收集的数据是不完整的、不一致的、含噪声的，所以需要对数据进行预处理，从而有助于提高后面的挖掘过程的精度和性能.对于本系统，可能出现一个数据“不干净”的问题在于，出现两个及以上的样本，它们的一般属性值一模一样，但是类别属性值不同.根据决策树算法，存在这种问题的样本集是无法进行决策树分析的，必须对其进行处理.处理的一种方法是采用“少数服从多数”，对上述存在问题的若干样本，进行统计，取出少数类别的样本，保留多数类别的样本.只有经过“数据预处理”这一步骤，数据库中的样本集才能被分析，才能得出正确的决策树.

3.3 决策树生成

“决策树生成”模块是系统的核心模块.C4.5决策树算法将在这个模块中得以体现.该模块利用“数据预处理”模块清理出的干净的数据集进行学习，得出一棵正确的C4.5决策树.该模块需要注意的是计算性能问题.随着样本集中，样本数的增加，“决策树生成”模块可以快速进行处理，得出正确的结果.该模块需要注意的另一个地方在于“树”如何进行表示，才能保证数据的通用性.

另一个要解决的问题就是后台调查数据如何与决策树算法进行关联的问题.在收视分析系统中，决策树待学习的样本就是一张张填写完整的调查问卷.调查问卷的问题与样本的属性相对应，而被调查者所选择的答案，就是样本属性所对应的属性值.例如一个样本可以表示为如下的多元组:(杂志，增长见识，4小时以上，……，经济频道).其中每个属性值，对应的属性是(“最喜欢的传播信息方式”，“看电视动机”，“平均每天收看电视的时间”，……，“喜欢的频道”).在这里，“最喜欢的传播信息方式”，“看电视动机”，“平均每天收看电视的时间”等是样本的一般属性，而“喜欢的频道”是类别属性.通过这样的对应关系，调查问卷即能自然的表示为决策树算法中的样本.

“决策树”生成模块利用C4.5算法对“干净的”样本集进行学习，生成一棵C4.5的决策树.其中生成过程按照图4所示的流程进行.该过程是一个不断递归的过程，从样本集(即调查问卷)中选取分裂属性，选择的标准是最大信息增益率.利用分裂属性对样本集进行划分，然后依次对各个子样本集重新选取分裂属性进行划分，决策树利用XML技术进行实现，直到生成最后的决策树.

图4 决策树生成流程图

4 结论

深入研究了决策树理论在电视频道节目收视分析中的应用.在研究中，设计了观众收视调查问卷，在线收集了大量的收视数据，组织成测试样本，设计、编程实现了一个完整的基于B/S架构的电视台收视分析系统，得到了最终的C4.5决策树，归纳出诸如“广告时间长短”，“播出时间段”等是决定收视的决定性因素等规律.由于测试样本数目过少、问卷的设计还不够合理，所得到的收视规则还不够完备，部分规则与事实有些许偏差，还需进一步完善.

［1］李善庆.基于数据挖掘的收视分析与决策系统的设计与实现［D］.2007.

［2］云玉屏.基于 C4.5算法的数据挖掘应用研究［D］.2008.

［3］何铭锋.关于品牌识别、传播与体验的工作方法研究［D］.2008.

［4］黄爱辉.决策树C4.5算法的改进及应用［J］.科学技术与工程，2009，9(1):56－59.

［5］刘鹏，姚正，尹俊杰，等.一种有效的C 4.5改进模型［J］.清华大学学报:自然科学版，2006，46(21):34－39.

［6］汪莉，刘超.数字电视用户收视行为调查系统最大并发量研究及推广前景［A］.2010年中国国际广播电视信息网络展览会CCBN2010论文集［C］，2010.

［7］Gjorgji Madzarov，Dejan Gjorgjevikj，Ivan Chorbev，et al.A Multi－class SVM Classifier Utilizing Binary Decision Tree［J］.Informatica，2009，33(2):25－29.

The Research on Decision Tree C4.5 Algorithm Based on Behavior of TV Users

Fang Dejian，You Jingsheng
(Fujian Normal University)

This thesis uses decision tree to analyze data for TV Station.Firstly a questionnaire is designed to allow the audiences to fill out and the surveys are the samples which are to be excavated.This thesis makes use of classical decision tree algorithm－C4.5，and constructs a decision tree from the sample set.By analyzing of the decision tree，the factors which can influence the TV ratings are got，and make programs reasonably.

Decision tree;C4.5 algorithm;Viewing analysis

2011－02－12

(责任编辑:黄永辉)