社交网络节点属性的可操作知识挖掘

可在ScienceDirect上获得目录列表专家系统与应用：X期刊主页：www.elsevier.com/locate/eswax专家系统与应用：X 3（2019）100013从具有节点属性的社交网络中提取可操作知识Nasrin Kalanat，Eynollah Khanjari伊朗科技大学计算机工程学院，伊朗德黑兰Ar ticlei n f o ab st ract文章历史记录：收到2019年2019年7月22日修订2019年7月24日接受在线预订2019年保留字：社交网络节点属性可操作的知识发现动作提取随机游走可操作的知识发现最近引起了人们的极大兴趣。这几乎是一个新的范式转变，以在每个特定领域挖掘更多可用和更适用的知识。行动是这个研究领域的一个新工具，它向用户建议一些改变，以在他/她的领域中获得利润。目前，大多数行为挖掘方法依赖于简单的数据，这些数据独立地描述了每个对象。由于个体之间的关系，社交数据具有更复杂的结构，因此主要问题是在动作挖掘过程中没有考虑这种结构信息。这导致错过一些有用的知识和有益的行动。因此，采矿行动需要更有效的方法。这项工作的主要重点是提取成本效益的行动从社交网络中的节点属性。这些动作建议节点属性中的最佳改变我们开发了一种基于随机游走的动作挖掘方法，该方法自然地将来自网络结构的信息与节点属性相结合。我们将动作挖掘公式化为一个优化问题，其目标是学习一个函数，该函数可以改变节点属性的值，从而影响网络中边的权重，以便目标个体的标签可能会采用所需的标签，同时最大限度地实验证实，所提出的方法优于当前最先进的动作挖掘。© 2019作者由Elsevier Ltd.发布。这是CC BY许可下的开放获取文章（http://creativecommons.org/licenses/by/4.0/）的网站上进行了介绍。1. 介绍数据挖掘系统试图从数据中提取有趣的模式和模型。然而，这些系统有两个主要缺点，即解释和质量，前者指出，诱导结果的可操作性对专家来说不透明，而后者表明它们不能无缝集成到业务领域中（Paul，Groza，Hunter，2014）。可操作的知识发现（AKD）是从数据驱动的数据挖掘到领域驱动的数据挖掘的范式转变，发现不仅具有技术意义，而且满足业务期望，并可立即应用于相应领域的运营的知识（Longbing，2012）。AKD的概念可以通过CRM中的一个例子来说明，涉及银行贷款系统。数据挖掘可能会给出以下问题的答案，但AKD可能会找到答案∗通讯作者。电 子 邮 件 地 址 ： kalanat@comp.iust.ac.ir （ N.Kalanat ） ， khanjari@iust.ac.ir（E.Khanjari）。“我们怎样才能提高客户偿还他的贷款，这样我们就需要支付更少的成本？"该动作是AKD领域的一个新工具，它明确描述了可以被中断的数据中的变化如何将实例从不期望的状态转移到期望的状态。 在社交网络中，需要有意义的行动来帮助公司进行决策。 作为一个例子，考虑一个由数百万个人组成的社会网络，这些人明确或隐含地是不同群体的成员。从这样的网络中提取操作可能表明数据中的一些潜在变化，这些变化在应用时可能影响个体的群体成员资格。为了说明这个概念，考虑图1所示的示例网络。其中穿白衬衫的人是特定产品的购买者。假设一种预测方法预测杰克只有20%的机会购买产品，即他不是买方集团的成员。一个交流-假设节点u的gem属性值从2变为1，那么Jack购买产品的概率将增加到60%。为了更详细地解释，建议的更改将加强Jack和u之间的关系，并可能导致影响Jack的组成员身份（类标签）。这种效应是社交网络https://doi.org/10.1016/j.eswax.2019.1000132590-1885/© 2019作者。出版社：Elsevier Ltd这是CC BY许可下的开放获取文章（http://creativecommons.org/licenses/by/4.0/）的网站上进行了介绍。2N. Kalanat和E.Khanjari/专家系统与应用：X 3（2019）100013Fig. 1. 一个样本网络（a）社交图，其中穿白衬衫的人是买家，穿蓝衬衫的人是非买家，以及样本网络中个人的相应属性（b）杰克邻居中节点属性的一些变化会影响他的（Anagnostopoulos，Kumar，Mahdian，2008）.特别是，标签可以作为属性中的某些更改的结果而传播个人。很明显，在业务环境中，领域专家通常会对他们应该如何处理DM模式感到困惑，这样的知识是更需要的。现有的动作挖掘方法依赖于简单的数据，例如描述独立实例集合的表。然而，在社交网络中，关系使一个个体能够与另一个个体相互联系，因此在行为挖掘过程中忽略它们会导致错过一些有利可图的行为。在本文中，我们开发了有效的方法，从社会网络中挖掘行动问题如下：给定一个社交图，包括一组标记的节点和节点该动作识别节点的属性值中的最优变化集。为了解决这个问题，我们需要在图上应用给定的标记方法A，然后改变属性值使得当A预测x的目标标签时，改变引起最小成本。在这方面，我们发展一种基于随机游走的算法，该算法将来自网络结构的信息与节点属性相结合。提出的方法如下：在第一阶段，我们应用Zhou&在第二阶段，为了提取具有成本效益的动作，我们需要探索图中的变化空间。我们将问题表述为优化函数，其中目标是学习节点属性的变化我们开发了一种算法MANA，它利用随机梯度下降法（Ruder，2016）来优化目标函数迭代。我们还提供了两个扩展，以提高效率和所提出的算法的可扩展性。我们在Facebook，Google+，DBLP和Hep-th网络上的实验表明，我们的方法完全优于最先进的方法。论文的其余部分组织如下：第2节包含相关的工作。第3节介绍了后面几节所需的概念、定义和术语。在第四节中，我们介绍了我们的基本算法MANA，以及两个改进算法MANA的扩展.第5节给出了在几个真实数据集上获得的实验结果。最后，我们在第6结束了本文。2. 相关作品动作挖掘是数据挖掘的一个子领域，称为可操作知识发现（AKD），它关注的是发现不仅具有技术意义，而且满足领域期望的知识，并且可以应用于操作，只需领域专家的最小进一步努力（Cao，Zhao，Zhang，&al，2010）。动作挖掘方法为给定的实例找到最佳动作（归纳方法），或为不同的相似实例组找到规则（归纳方法），这些方法可用于预测动作。Ras和Wieczorkowska（2000）定义了动作规则的概念，并提出了一种使用分类规则对生成规则的方法。之后，这项工作被开发为通过类似Apriori的算法（He，Xu，Deng，Ma，2005）在没有预先存在的分类规则的情况下挖掘操作规则，并通过基于Map-Reduce框架的算法（Tzacheva，Bagavathi，Ganesan，2016）以及基于Hadoop Map-Reduce和Apache Spark框架的算法（Bagavathi，Mummoju，Tarnowska，Tzacheva，Ras，2017）来处理大数据。Su，Mao，Zeng和Zhao（2012）介绍了可操作的行为规则挖掘，旨在从基于对象的数据中提取影响实体行为的动作规则。数据包括实体的观测（对象）而不是实体的成员。N. Kalanat和E.Khanjari/专家系统与应用：X 3（2019）1000133（f−f）..此外，有一个目前的观察，其中每一个变化的建议的动作规则需要从当前观察改变实体的属性值。然后，他们扩展了规则支持度的定义&Su等人提出了MABR（Su等人，2012）在支持和利润的框架内从基于对象的数据中找到行动规则。Zeng等提出了一种基于线性函数的观测加权方法一组属性向量，每个节点有一个单独的属性向量来描述该节点。设a为所有属性的集合（例如，年龄、性别、家乡）。节点u的属性向量是（1=fu1，2=fu2，.，k = fuk），其中每个i是属性，fui是来自其域Dom（i）的值。对于边缘（u，v）∈E，我们基于u和v之间的相似性来计算权重w uv，所述相似性通过高斯函数（诸如径向基函数（RBF））来计算（Zhou等人，（2004年）：方法（Zeng等人，2015），其处理了用于支持动作规则的不同实例的非统一贡献的问题。在挖掘这种行为规则时，经常会发生不同的规则可能会建议具有不同预期利润的相同行为。wuv=exp。−|Ф|k=12英国vk2K（一）叫做冲突规则。为了解决冲突，Su，Zhu和Zeng（2014）利用规则排名程序来选择具有最高利润的规则。为了保证可操作规则的可靠性，所述方法需要找到频繁动作集。然而，这将导致高时间复杂度。为了解决这个问题，他们提出了一种基于决策树分类器的挖掘方法（Su，Jian，Zhenpeng，Yuan，2017）。虽然操作规则是为了实现预期结果而需要进行的一组更改，但 元 操 作 是 为 了 触 发 相 应 更 改 而 需 要 执 行 的 操 作 。Ranganathan，Allen，Arunkumar和Angelina（2018）提出了一种新的有效系统，通过基于抓取策略实现特定的动作规则发现并将其应用于Twitter数据进行语义分析来生成元动作。Ras，Tarnowska，Kuang，Daniel和Fowler（2017）提出了从文本数据中自动挖掘元动作的策略。Yang，Yin，Ling和Pan（2007）提出了一种方法，首先从数据中学习决策树，然后为每个对象找到对象落在其中的叶子节点，并且对于每隔一个叶子计算将对象移动到该叶子的净利润。最后，将选择具有最大净利润的叶子节点，并需要-对象从当前的如果（u，v）∈E，我们用wuv表示图G为邻接矩阵W，否则为0。我们得到一组标记的节点LV（其他未标记）。我们用向量y表示标签，如果节点u被标记为目标或其他标签，则yv=1或−1，如果u未被标记，则y v =0一个动作：{α1，α2，...，αk}是节点属性值的属性i∈f的值的变化，从fui到frui的节点u是形式（fui→frui）的结构，其中f，fr∈Dom（i），f是i的观测值. 它对应于将属性i的值从f改变为fr， 最终干预。为了在挖掘成本效益行动中整合网络的特征，每个属性都有一个用户定义的成本函数c（）。背景知识。ci（）通过将值差（df = f' − f）映射到非负值来计算将属性i从f更改为f例如，属性的成本函数可以是（f为了衡量从F到F'成本函数C（F，n|Ф|节点到该节点的操作将作为推荐操作返回之后，为了找到最优操作，该方法被扩展到对树的集合进行后处理（Alam Alam，2012;C（F，Fr）=ck（dfuku=1k=1（2）Subraman 等 人 ， 2016 年 ; Tolomei ， Silvestri ， Haines ，&Lalmas，2017年）和模糊决策树（Kalanat，Shamsinejad，&Saraee，2015年; Kalanat& Minaei，2016年）Cui，Chen，He和Chen（2015年）提出了一个框架来后处理任何加法树模型类-sifier以提取最佳动作并将问题用整数线性规划表示。Lu，Zhicheng，Yixin和Xiaoping（2017）提出了一种状态空间图公式，将问题建模为一个可以通过图搜索解决的经过充分研究的组合优化问题。为了在搜索时间和动作质量之间取得良好的平衡，他们提出了一种次优启发式搜索。所有提出的方法都假设实例是独立的。然而，在许多现实领域中，实例之间存在关系网络。在动作挖掘过程中忽略这种关系将导致错过一些有利可图的活动，其中df =（fuk-f 0uk）。 而一个动作只直接改变节点的属性，这些改变又可能导致节点标签的改变。请注意，这些间接更改没有额外的成本，只有操作本身有成本。动作挖掘是一个机器教学问题（Zhu，2015;Zhu，Singla，Zilles，Raffeine，2018），其中给定训练集D，数据挖掘或机器学习方法A和期望的输出它的目标是返回一个包含一组变化的将方法输出转换为所需的训练集一个.通常，最优性是根据一些成本测量来定义的。为了提取导致期望模型θe的动作，最小成本，我们需要计算反函数A−1（θ）。而不是直接计算微分反函数A−1（θ）（Zhu，2015），我们将其转换为以下优化问题：选项。在本文中，为了从社交网络中发现行为，我们在动作提取过程中合并关系minFr∈FC（F，Fr）R（三）∗3. 预赛在本节中，我们将介绍本文中使用的符号，然后解释一种众所周知的节点分类方法。3.1.问题陈述我们考虑一个表示为图G=（V，E，F）的社会网络，其中V是一组对应于个人的n个节点;E是一组的m个边对应于个体之间的社会交互，使得边（u，v）意味着u与v交互; F是服从AFr（W）=θ问题的目的是找到属性数据FC（F，基于上述问题的定义，我们将一个动作表示为：F→Fr，表示输入属性数据中的一组变化。在问题陈述中，任何有封闭式可以将F '（W'）插入目标函数Eq. (1).对于具有连续闭型函数的情况，可以通过基于梯度的方法来提取最优动作。有人认为，在实际应用中的分类是不够的，需要采取一些行动，将一些实例重新分类到所需的类，.σ4N. Kalanat和E.Khanjari/专家系统与应用：X 3（2019）100013.||..... .−1u=1u在相应的领域可能是有趣的（He，Xu，Deng，2003）。在社交网络研究领域，节点分类的广泛应用促使我们专注于基于节点分类的有用行为的提取。 基于这样的考虑，我们的问题可以简单地定义如下：给定图G，包括一组标记节点和节点3.2.分类方法我们使用周选择该方法有以下几个考虑因素：1. 它是最成功的节点分类算法之一（Bhagat Cormode，2011）。2. 它是基于随机游走的。3. 它基于标签传播。4. 它学习了一个全局标记函数，并具有可证明的收敛保证。该方法是基于这样的想法，即用标签l标记节点u的概率是从u开始的随机游走访问标记为l的节点的总概率。假设参数r指定了来自节点邻居的标签信息的相对量BORS及其初始标签信息。设Q为转移矩阵（f c4，1.4 → 1.8）}（图2. （d）将节点c的得分标签增加到0.506和成本2.对于这种解决方案的复杂性，我们考虑了问题的简化版本，其中所有实值属性在应用该方法之前都被离散化。任何形式的改变（例如，f→fr），其中f是节点是尝试更改目标属性的候选操作每个属性可能出现在动作中，也可能不出现，如果出现，|Dom（Dom）|f r的1个可能值。这给出了<$∈<$Dom（<$）个候选动作，时间复杂度为O（dm-1）。显然，这种解决方案可能是即使是小数据集也难以处理。因此，我们提出了一个不同的策略，探索了一个大的变化空间的顺序为O（m）。4.1. 问题公式化这一提法是基于以下想法：1. 我们希望最小化修改后的属性数据F'（应用动作后的属性数据）与输入值F的偏差成本。2. 在由F'产生的修改后的网络W换句话说，偏离应该导致最大化第十章在遍历中，从x开始的遍历更有可能到达正节点。如前所述，根据周的方法，可以计算x以下列形式表示：y=x=。n（pxxy0）whe e定义为D-1/2WD-1/2，其中D是对角矩阵，其（i，i）-元素等于W的第i行元素之和。该方法总结在算法1中。算法1周氏迭代-Zhou（y，r）1. y0=y2. 重复3. yt= rQyt−1+（1− r）y0P=（1-r）（I-rQ）。值得注意的是尝试最小化标记节点上的初始标签和输出标签之间的差异。由于优选地避免节点上的标签，除了X偏离它们在前一步骤中的预测的标签，所以我们使用预测的标签proba。在这个step（yx=xyyx）中，它们的初始标签是bytes。基于上述直觉，我们定义了学习最优网络的优化问题如下：4. 直到收敛到y∞五、y=y∞六、returnyn证明y=（1−r）（I−rQ）−1y. 值得注意的是minFrMaxFrn|Ф|c英国（DF）u=1k=1n（pux×yu）（4）u=1Q的选择自然产生于以下两个重新对标签的要求：首先，标签节点上的初始标签和输出标签之间的差异应该很小。第二，邻居（特别是那些具有大边权重的邻居）的标签的差异应该很小。其中df=（f 我们把两个目标问题利用ε约束方法（Ching-LaiAbu Syed Md，1979）将问题分解为以下单目标问题：n|Ф|用节点分类法构造的模型，我们将在下一节介绍的动作提取过程中使用。minFr英国u=1k=1（df）4. 使用节点属性的在以下情况下，n（pux×yu）ε（5）

下载后可阅读完整内容，剩余1页未读，立即下载