数据挖掘的数学工具：集论与组合方法

需积分: 9 118 浏览量更新于2024-07-17 收藏 8.66MB PDF 举报

"《数学工具数据挖掘》是一本由Dan A. Simovici和Chabane Djeraba合著的经典英文版电子书，专为数据挖掘领域提供深入的数学基础。该书属于'高级信息与知识处理'系列，由Lakhmi Jain教授和Xindong Wu教授共同编辑。第二版内容涵盖了数学工具在数据挖掘中的关键应用，如集合论、偏序理论以及组合数学。书中详细探讨了如何运用这些数学原理来解析和理解大量复杂的数据，帮助读者掌握如何通过构建模型、算法和网络来提取有价值的信息。它不仅是数据科学家和分析师的必备参考资料，也为研究人员和学生提供了深入理解数据挖掘核心概念的桥梁。 Set Theory（集合论）部分介绍了基本的集合操作和理论，这对于数据预处理和数据结构设计至关重要。Partial Orders（偏序关系）则讨论了如何用有序结构组织数据，这对于排序、聚类和关联规则学习有重要影响。Combinatorics（组合数学）则是数据挖掘中用于计数和选择的方法，如排列组合和图论，对于优化搜索算法和网络分析非常有用。本书共123页，适合那些希望将数学与数据分析技能相结合的专业人士阅读。它不仅提供了理论知识，还包含了实践案例和实际应用示例，便于读者将理论知识转化为实际操作。该书的ISBN和DOI号码可供购买或在线获取，Springer出版社出版，版权所有。《数学工具数据挖掘》是一本不可或缺的教材，对于提升数据挖掘领域的理论素养和技术能力具有重要意义。无论你是初学者还是经验丰富的专业人士，都能从中收获宝贵的知识和洞察力。"

4 1 Sets, Relations, and Functions

Theorem 1.6 For any collection of sets C and set T, we have







∩ T =



{

C ∩ T | C ∈ C

}

If C is nonempty, we also have



⎟



∪ T =

⎟

{

C ∪ T | C ∈ C

}

Proof We prove only the ﬁrst equality; the proof of the second one is left as an

exercise for the reader.

Let x ∈ (

⎜

C) ∩ T. This means that x ∈

⎜

C and x ∈ T. There is a set C ∈ C

such that x ∈ C; hence, x ∈ C ∩ T, which implies x ∈

⎜

{

C ∩ T | C ∈ C

}

Conversely, if x ∈

⎜

{C ∩ T | C ∈ C},

there exists a member C ∩ T of this

collection such that x ∈ C ∩ T,sox ∈ C and x ∈ T. It follows that x ∈

⎜

C, and

this, in turn, gives x ∈ (

⎜

C) ∩ T.

Corollary 1.7 For any sets T, U, V , we have

(U ∪ V ) ∩ T = (U ∩ T) ∪ (V ∩T) and (U ∩ V ) ∪ T = (U ∪ T) ∩ (V ∪T).

Proof The corollary follows immediately by choosing C ={U, V } in Theorem 1.6.

Note that if C and D are two collections such that C ⊆ D, then



C ⊆



D and

⎟

D ⊆

⎟

e initially excluded the empty collection from the deﬁnition of the intersection of

a collection. However, within the framework of collections of subsets of a given set

S, we will extend the previous deﬁnition by taking



∅=S for the empty collection

of subsets of S. This is consistent with the fact that ∅⊆C implies



C ⊆ S.

The symmetric difference of sets denoted by ⊕ is deﬁned by U ⊕V = (U −V ) ∪

(V −U) for all sets U, V .

Theorem 1.8 For all sets U, V, T, we have

(i) U ⊕ U =∅;

(ii) U ⊕ V = V ⊕T;

(iii) (U ⊕ V ) ⊕ T = U ⊕(V ⊕T).

Proof The ﬁrst two parts of the theorem are direct applications of the deﬁnition of

⊕. We leave to the reader the proof of the third part (the associativity of ⊕).

The next theorem allows us to introduce a type of set collection of fundamental

importance.

Theorem 1.9 Let {{x, y}, {x}} and {{u,v}, {u}} be

two collections such that {{x, y},

{x}} = {{u,v}, {u}}. Then, we have x = u and y = v.

1.2 Sets and Collections 5

Proof Suppose that {{x, y}, {x}} = {{u,v}, {u}}.

If x = y, the collection {{x, y}, {x}} consists of a single set, {x}, so the collection

{{u,v}, {u}} will also consist of a single set. This means that {u,v}={u}, which

implies u = v. Therefore, x = u, which gives the desired conclusion because we

also have y = v.

If x = y, then neither (x, y) nor (u,v)are singletons. However, they both contain

exactly one singleton, namely {x} and {u}, respectively, so x = u. They also contain

the equal sets {x, y}and {u,v},

which must be equal. Since v ∈{x, y} and v = u = x,

we conclude that v = y.

Deﬁnition 1.10 An ordered pair is a collection of sets {{x, y}, {x}}.

Theorem 1.9 implies that for an ordered pair {{x, y}, {x}}, x and y are uniquely

determined. This justiﬁes the following deﬁnition.

Deﬁnition 1.11 Let {{x, y}, {x}} be an ordered pair. Then x is the ﬁrst component

of p and y is the second component of p.

From now on, an ordered pair {{x, y}, {x}} will be denoted by (x, y). If both

x, y ∈ S, we refer to (x, y) as

an ordered pair on the set S.

Deﬁnition 1.12 Let C and D be two collections of sets such that

⎜

C =

⎜

D. D is

a reﬁnement of C if, for every D ∈ D, there exists C ∈ C such that D ⊆ C.

This is denoted by C ⊥ D.

Example 1.13 Consider the collection C ={(a, ∞) | a ∈ R} and D ={(a, b) |

a, b ∈ R, a < b}. It is clear that

⎜

C =

⎜

D = R.

Since we have (a, b) ⊆ (a, ∞) for every a, b ∈ R such that a < b, it follows that

D is

a reﬁnement of C.

Deﬁnition 1.14 A collection of sets C is hereditary if U ∈ C and W ⊆ U implies

W ∈ C.

Example 1.15 Let S be a set. The collection of subsets of S, denoted by P(S),isa

hereditary collection of sets since a subset of a subset T of S is itself a subset of S.

The set of subsets of S that contain k elements is denoted by P

(S). Clearly, for

every set S,wehaveP

(S) ={∅}because there is only one subset of S that contains

0 elements, namely the empty set. The set of all ﬁnite subsets of a set S is denoted

by P

ﬁn

(S). It is clear that P

ﬁn

(S) =

⎜

k∈N

(S).

Example 1.16 If S ={a, b, c}, then P(S) consists of the following eight sets:

∅, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c}.

For the empty set, we have P(∅) ={∅}.

Deﬁnition 1.17 Let C be a collection of sets and let U be a set. The trace of the

collection C on the set U is the collection C

={U ∩ C | C ∈ C}.

剩余833页未读，继续阅读

J-10

粉丝: 18
资源: 483

数据挖掘的数学工具：集论与组合方法

Mathematical Tools for Data Mining-2015.pdf

Mathematical Tools for Data Mining - Set Theory

Understanding Complex Datasets - Data Mining with Matrix Decompositions

Data Mining Practical Machine Learning Tools and Techniques

Data Mining: Practical Machine Learning Tools and Techniques 4ed 2017

Handbook of Educational Data Mining

Big Data and Computational Intelligence in Networking-CRC(2018).pdf

Python Data Analysis(PACKT,2014)

Scipy - Scipy Lecture Notes

Visual Knowledge Discovery and Machine Learning-Springer(2018).pdf

最新资源